Implémentation de RSA sans allocation dynamic

Une implémentation RSA typique comprend une bibliothèque de nombres entiers multi-précision. Une bibliothèque d’entiers multi-précision typique utilise l’allocation dynamic pour représenter des entiers de grande taille sous la forme de tableaux de mots-machines de la bonne taille.

J’imagine qu’il doit exister une limite sur les nombres entiers mathématiques que l’on peut rencontrer lors de l’utilisation des nombres entiers multi-précision uniquement pour chiffrer ou déchiffrer des messages de longueur connue (généralement des clés de chiffrement symésortingques) avec, par exemple, RSA-2048. possible de mettre en œuvre l’algorithme en allouant l’espace nécessaire pour tous les résultats intermédiaires nécessaires, de manière statique ou sur la stack.

J’ai trouvé ce fil de discussion suggérant que c’est possible. Il n’indique pas les tailles entières maximales. C’est peut-être évident («vous avez besoin de 2048 bits pour tous les entiers, duh!»). Dans tous les cas, je serais plus intéressé par une implémentation existante, le cas échéant.

En tant que question secondaire qui ne mérite pas sa propre entrée, les implémentations typiques de la cryptographie à courbe elliptique nécessitent-elles une allocation dynamic?

Est-il possible d’implémenter une classe entière multi-précision sans allocation dynamic

Oui.

Je suis au courant d’une implémentation similaire dans C # BigInteger Class . (Et nonobstant ce que fait le runtime sous-jacent de clr).

Je ne connais pas de mémoire tampon statique en C / C ++. Mais je ne connais que Botan, Crypto ++ et OpenSSL.

D’après ce que j’ai vu des implémentations, l’exposant public e obtient parfois une optimisation pour en faire un int ou un long . Mais n et d sont multi-précision. (Et j’aimerais voir comment ça explose un jour).

Enfin, les routeurs et autres équipements à faible consommation prennent souvent cette optimisation pour les tampons d’envoi et de réception (j’ai travaillé avec un gars qui était ingénieur élecsortingcien et qui a conçu les routeurs). Ils réservent simplement un bloc de mémoire et le logiciel utilise un index pour accéder au tampon statique. Il n’est donc pas difficile de croire qu’ils ont adopté l’optimisation dont vous parlez.


RSA-2048, et qu’il serait possible d’implémenter l’algorithme en allouant de l’espace pour tous les résultats intermédiaires nécessaires, de manière statique ou sur la stack.

Oui, vous pouvez le faire avec un schéma de magnitude de signe utilisant des tampons de taille fixe si vous acceptez de limiter la taille maximale du module RSA ou la taille du champ principal EC.

Une clé publique RSA est (e, n). Malgré l’avertissement sur les petits e , vous aurez besoin de deux mémoires tampon de 2048/8 = 256 byes ou octets.

Une clé privée RSA sans les astuces de précalcul est simplement (e, d, n). Donc, vous auriez besoin de trois tampons de 256 octets ou octets.

Si vous travailliez sur un PDP-8 avec des octets 12 bits, vous auriez alors besoin de moins d’octets.


Il n’indique pas les tailles entières maximales.

Le diable dans les détails est probablement la multiplication. Donc, vous auriez besoin d’un tampon de travail pour effectuer la multiplication. Cela signifie que vous aurez besoin d’un tampon de taille ~ 2 * 2048 bits (multiplier les tampons de taille 2 m crée un résultat de taille 2m -1 ). Le résultat de la multiplication devrait alors être réduit. Leurs optimisations sont peut-être plus poussées, mais je ne me préoccupe généralement pas de ces détails.

En relation, la taille maximale du message et la taille maximale du texte chiffré sont liées à n . Dans Crpyto ++, ils peuvent être récupérés avec MaxPreImageSize (pour le texte brut) et MaxImageSize (pour le texte chiffré). MaxPreImageSize et MaxImageSize renvoient n - 1 .


En tant que question secondaire qui ne mérite pas sa propre entrée, les implémentations typiques de la cryptographie à courbe elliptique nécessitent-elles une allocation dynamic?

Cela dépend de l’implémentation sous-jacente. Une courbe sur un champ premier est définie par les parameters de domaine (voir SEC1, Paramètres de domaine de courbe elliptique de la Section 3, page 16 de Certicom):

 Elliptic curve domain parameters over F_p are a sextuple: T = (p, a, b, G, n, h) 
  • p est un grand nombre premier et il a besoin d’un entier multi-précision

  • a et b sont des coefficients qui définissent la courbe. Ils sont généralement ‘petits’ (par exemple, a = 3), mais ils pourraient nécessiter des entiers multi- précision pour les courbes non standard. Par exemple, la courbe ed25519 de DJB est y^2 = x^3 - 102314837768112 x + 398341948620716521344 .

  • G est le sharepoint base, donc c’est vraiment un élément (ou un point) de la courbe. Cela signifie est une coordonnée (X, Y) et nécessite probablement un entier multi-précision.

  • n est un nombre premier d’ordre G ce qui signifie que sa taille est aussi grande que n

  • h est le cofacteur et est généralement très petit: 4 ou 2, ou 1.

Lorsque vous créez une paire de clés pour la courbe, vous avez besoin d’un exposant privé aléatoire d (ou x ), qui crée un élément (point sur la courbe) après l’exponentiation. C’est-à-dire, clé publique (X, Y) = G^x . Donc, vous avez trois autres entiers multi-précision.

Une courbe sur un fichier binary a besoin d’un moyen d’exprimer le polynôme. Donc, vous auriez probablement encore besoin de l’entier multi-précision (utilisé pour p dans le champ principal).

Ainsi, la plupart des “choses” sur une courbe elliptique ont besoin d’un entier multi-précision.

Vous pouvez voir des exemples de parameters de domaine sur, par exemple, Génération de courbes standard de Brainpool par cryptographie à courbe elliptique (ECC) .

Cette implémentation RSA , à l’intérieur de BearSSL , de Thomas Pornin, a exactement les propriétés que je cherchais . Sur la page Web de BearSSL:

Aucune allocation dynamic que ce soit. Il n’y a pas un seul appel malloc () dans toute la bibliothèque.

Sur les grands systèmes d’exploitation de bureau et de serveur, cette fonctionnalité offre toujours une caractéristique intéressante: immunité aux memory leaks et aux attaques de type DoS basées sur la mémoire. Les étrangers ne peuvent pas obliger BearSSL à allouer des mégaoctets de RAM, car BearSSL ne sait pas comment allouer de la RAM.