Lipsum.dev

Arithmétique modulaire, HTTPS et SSH

27 avril 2020 — Python

L’arithmétique modulaire correspond aux calculs effectués « à un multiple de n près ».

Par exemple, si on calcule modulo 1212, on a 7+9=47 + 9 = 4 et 3×8=03 \times 8 = 0.

Ce cas particulier correspond à des calculs sur des nombres d’heures, le résultat s’affichant sur un cadran d’horloge ne permettant de connaître l’heure qu’à un multiple de 1212 heures près.

Pour ramener des calculs d’un ensemble plus grand (ici les entiers relatifs Z\Z) à un ensemble plus petit (ici {0,1,2,3,4,5,6,7,8,9,10,11}\{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11\}), les mathématiciens utilisent la notion d’ensemble quotient.

Nous utiliserons ici cette approche, sur le cas particulier des ensembles Z/nZ\Z/n\Z (définis pour tout entier n>0n > 0), qui sont le cadre naturel de l’arithmétique modulaire.

Ces ensembles, qui contiennent nn éléments, seront très utiles en informatique. Leurs éléments peuvent tous être représentés avec un espace mémoire fini (contrairement à Z\Z) et les calculs y sont exacts (contrairement aux nombres de R\R, par exemple).

Nous verrons en particulier comment ils sont utilisés en cryptographie.

L’ensemble Z/nZ\Z/n\Z

Nous avons vu l’ensemble Z\Z des entiers relatifs (positifs, négatifs ou nuls).

Pour nN,n>0n \isin \N, n > 0, l’ensemble nZn\Z est défini comme l’ensemble des multiples de nn (la notation signifie littéralement « nn fois n’importe quel nombre de Z\Z »).

Ainsi, 2Z2\Z est l’ensemble des nombres pairs, 3Z3\Z des nombres divisibles par 33 (e.g. 333,0,21-333, 0, 21), etc.

L’ensemble Z/nZ\Z/n\Z est un ensemble d’ensembles, dont les éléments sont les classes d’équivalence modulo nn.

Une classe d’équivalence modulo nn, c’est un ensemble de nombres de Z\Z qui ont tous le même reste quand on considère leur division euclidienne par nn. En particulier, tous les nombres qui sont dans la même classe d’équivalence diffèrent d’un multiple de nn.

Par exemple :

  • Z/2Z\Z/2\Z correspond à deux sous-ensembles, les nombres pairs et les nombres impairs
  • Z/3Z\Z/3\Z correspond à trois sous-ensembles, qui sont les nombres de la forme 3×k{3 \times k}, ceux de la forme 3×k+1{3 \times k + 1} et ceux de la forme 3×k+2{3 \times k + 2}.
  • Z/12Z\Z/12\Z correspond à regrouper les nombres d’heures comptés à partir d’un temps 00, en fonction de ce qu’il donneraient, si on les affichait sur une horloge à cadran (et en ignorant les changements d’heure…)
  • etc.

Z/nZ\Z/n\Z contient nn éléments, qui correspondent aux ensembles de nombres dont les restes modulo nn sont respectivement 0,1,...,n10, 1, ..., n-1.

Par abus de langage, on notera 0,1,...,n10, 1, ..., n-1 les éléments de Z/nZ\Z/n\Z. Ils correspondent aux ensembles nZn\Z, {1+k,knZ}{\{1 + k, k \isin n\Z\}}, …, {n1+k,knZ}{\{n-1 + k, k \isin n\Z\}}.

Addition sur Z/nZ\Z/n\Z

L’addition est compatible avec le calcul modulo nn.

Par exemple, d’une addition modulo 33 ne change pas si on remplace l’un des nombres par un autre qui lui est égal modulo 33 :

5+20=2+2=15 + 20 = 2 + 2 = 1 modulo 33

Cette observation nous permet de définir une table d’addition sur Z/3Z\Z/3\Z :

+012
0012
1120
2201

On définit une addition sur Z/nZ\Z/n\Z, en considérant le résultat modulo n de l’addition sur Z\Z.

💡 Un ensemble muni d’une opération notée ++ avec certaines propriétés similaires à l’addition sur Z\Z s’appelle un groupe.

Multiplication sur Z/nZ\Z/n\Z

De la même façon, l’égalité suivante où a,b,i,ja, b, i, j sont des entiers quelconques, nous montre que la multiplication de Z\Z est compatible avec le calcul modulo nn :

(a+i×n)×(b+j×n)=a×b+(a×j+i×b+i×j×n)×n(a + i \times n) \times (b + j \times n) = a \times b + (a \times j + i \times b + i \times j \times n) \times n

Par exemple, dans Z/8Z\Z/8\Z on aura 6×7=2{6 \times 7 = 2} (conséquence de 6×7=42=2{6 \times 7 = 42 = 2} modulo 88).

On obtient une multiplication sur Z/nZ\Z/n\Z, en considérant le résultat modulo n de la multiplication sur Z\Z.

On obtient par exemple la table de multiplication suivante sur Z/5Z\Z/5\Z :

×01234
000000
101234
202413
303142
404321

💡 Un ensemble muni des opérations ++ et ×\times, avec des propriétés similaires à l’addition et la multiplication sur Z\Z s’appelle un anneau.

Question : déterminer la table d’addition et de multiplication sur Z/2Z\Z/2\Z, à quelles opérations booléennes correspondent-elles ?

Éléments inversibles de Z/nZ\Z/n\Z

Observons la table de multiplication de Z/6Z\Z/6\Z :

×012345
0000000
1012345
2024024
3030303
4042042
5054321

On remarque que l’on a les égalités suivantes :

  • 5×5=15 \times 5 = 1
  • 2×3=02 \times 3 = 0

La première égalité nous donne envie de dire que, pour la multiplication, 55 est inversible et son inverse est 51=55^{-1} = 5.

En d’autres termes, une équation d’inconnue xx de la forme 5×x=35 \times x = 3 se résout en x=5×3=3x = 5 \times 3 = 3.

La seconde égalité nous montre en revanche que 22 et 33 ne peuvent pas être inversibles, car ils sont « diviseurs de zéro ». Si 22 était inversible on pourrait réécrire l’égalité 2×3=02 \times 3 = 0 en 3=21×0=03 = 2^{-1} \times 0 = 0.

On vérifie sur la table de multiplication que les éléments inversibles de Z/6Z\Z/6\Z sont 11 et 55.

Retour sur l’identité de Bézout

L’algorithme d’Euclide permet d’obtenir l’identité suivante (je vous renvoie à l’article d’introduction à l’arithmétique, je remplace ici volontairement bb par nn, ce qui ne change pas le résultat) :

Il existe deux nombres u,vZ{u, v \isin \Z} tels que : u×a+v×n=gcd(a,n){u \times a + v \times n = \gcd(a, n)}

Que signifie pour un entier aa, l’existence d’un inverse a1a^{-1} dans Z/nZ\Z/n\Z ?

Cela traduit l’égalité a×a1=1{a \times a^{-1} = 1} modulo nn, ce qui signifie encore qu’il existe un entier kZ{k \isin \Z} tel que : a×a1k×n=1{a \times a^{-1} - k \times n = 1}.

En particulier, si gcd(a,n)=1\gcd(a, n) = 1, on peut construire des entiers a1=u{a^{-1} = u} et k=v{k = -v} qui satisfont exactement cette égalité.

L’identité de Bézout nous indique donc que aa est inversible modulo nn si et seulement si aa et nn sont premiers entre eux.

C’est d’ailleurs bien ce que l’on constatait sur le cas n=6n = 6 au-dessus.

Question : Montrer que si l’on considère un nombre pp premier, tous les éléments non nuls de Z/pZ\Z/p\Z sont inversibles (pour la multiplication).

Fonction indicatrice d’Euler

On définit la fonction ϕ(n)\phi(n) pour un entier n>0n \gt 0 appelée fonction indicatrice d’Euler, qui donne le nombre d’éléments inversibles pour la multiplication dans Z/nZ\Z/n\Z.

D’après ce qui précède, il s’agit du compte de nombres k,0<knk, 0 \lt k \leq n qui sont premiers avec nn.

💻 On peut calculer les premières valeurs de ϕ(n)\phi(n) avec le script Python ci-dessous :

from math import gcd
for n in range(1, 100):
print("phi({n}) = {phi}".format(
n=n,
phi=sum(1 for k in range(1, n + 1) if gcd(k, n) == 1)
))
phi(1) = 1
phi(2) = 1
phi(3) = 2
phi(4) = 2
phi(5) = 4
phi(6) = 2
phi(7) = 6
...
phi(95) = 72
phi(96) = 32
phi(97) = 96
phi(98) = 42
phi(99) = 60

Calcul de ϕ(n)\phi(n)

Dans certains cas, on peut calculer simplement la fonction indicatrice d’Euler.

Par exemple, si pp est un nombre premier, alors ϕ(p)=p1\phi(p) = p - 1 car tous les nombres inférieurs à pp sont premiers avec pp.

Dans le cas n=p×qn = p \times qpp et qq sont des nombres premiers distincts, les nombres qui sont premiers avec nn sont ceux qui ne sont multiples ni de pp ni de qq.

  • Les multiples de pp inférieurs à nn étant les nombres p,p×2,...,p×qp, p \times 2, ..., p \times q, il y en a qq.
  • De même, il y a pp multiples de qq.
  • Le seul multiple commun parmi ceux-ci est p ×qp \times q, qu’il ne faut donc compter qu’une fois.

On en déduit donc ϕ(p×q)=p×qpq+1=(p1)×(q1){\phi(p \times q) = p \times q - p - q + 1 = (p-1) \times (q-1)}.

Théorème d’Euler

Le théorème d’Euler, qui date de 1761, peut se formuler ainsi :

Si aa est un entier premier avec nn, alors aϕ(n)=1{a^{\phi(n)} = 1} modulo nn.

On vérifiera par exemple que 4ϕ(5)=44=16=1{4^{\phi(5)} = 4^4 = 16 = 1} modulo 55.

On en déduit également, comme 1919 est premier, que 19ϕ(97)=1996=1{19^{\phi(97)} = 19^{96} = 1} modulo 9797.

Ce dernier résultat montre à quel point le théorème d’Euler peut simplifier certains calculs (199619^{96} est un nombre plus grand que le nombre d’atomes d’hydrogène dans le soleil…).

Une autre façon équivalente de formuler ce théorème, dans le langage de Z/nZ\Z/n\Z, est la suivante :

Si aZ/nZa \isin \Z/n\Z est inversible alors aϕ(n)=1{a^{\phi(n)} = 1}.

Nous allons donner l’idée de la preuve dans le cas de Z/7Z\Z/7\Z, dont voici la table de multiplication :

×0123456
00000000
10123456
20246135
30362514
40415263
50531642
60654321

Les éléments inversibles, au nombre de 66, sont 1,2,3,4,5,61, 2, 3, 4, 5, 6 (tous premiers avec 77, puisque 77 est premier).

Considérons le produit de ces éléments P=1×2×3×4×5×6P = 1 \times 2 \times 3 \times 4 \times 5 \times 6.

En multipliant PP par 3ϕ(7)3^{\phi(7)} on obtient :

3ϕ(7)×P=36×P=36×1×2×3×4×5×6=(3×1)×(3×2)×(3×3)×(3×4)×(3×5)×(3×6)=3×6×2×5×1×4=P3^{\phi(7)} \times P = 3^6 \times P \\ = 3^6 \times 1 \times 2 \times 3 \times 4 \times 5 \times 6 \\ = (3 \times 1) \times (3 \times 2) \times (3 \times 3) \times (3 \times 4) \times (3 \times 5) \times (3 \times 6) \\ = 3 \times 6 \times 2 \times 5 \times 1 \times 4 \\ = P

On remarque en particulier que :

  • le produit PP étant par définition constitué de ϕ(7)=6\phi(7) = 6 éléments, on peut « répartir » les facteurs 33 devant chaque élément du produit
  • chaque nouveau facteur obtenu est un autre nombre, toujours inversible (car produit de deux nombres inversibles)
  • les nombres inversibles obtenus sont deux-à-deux distincts, on a donc uniquement changé l’ordre des facteurs de PP

En simplifiant par PP (lui-même inversible), on obtient bien que 3ϕ(7)3^{\phi(7)} = 11.

Question : En utilisant le théorème d’Euler et le calcul de ϕ(p)\phi(p)pp est un nombre premier, montrer le petit théorème de Fermat ci-dessous (historiquement, ce résultat fut découvert précédemment) :

Pour pp premier et aa un entier quelconque, on a ap=a{a^p = a} modulo pp.

Application à la cryptographie

Nous avons vu précédemment comment le théorème d’Euler pouvait permettre de simplifier considérablement certains calculs comme 199619^{96} modulo 9797.

Ce résultat est au coeur d’un algorithme appelé RSA, qui permet de générer des clefs cryptographiques (clef privée et clef publique, on parle de cryptographie asymétrique) et de les utiliser pour chiffrer et déchiffrer des messages.

Voici comment fonctionnent les différentes parties de cet algorithme.

Génération des clefs

  1. Choisir deux nombres premiers pp et qq et noter n=p×qn = p \times q.
    On a alors ϕ(n)=(p1)×(q1)\phi(n) = (p-1) \times (q-1) (voir le calcul de ϕ(p×q)\phi(p \times q) plus haut).

  2. Choisir un nombre ee premier avec ϕ(n)\phi(n).

  3. Calculer un inverse dd de ee modulo ϕ(n)\phi(n) : d×e=1+k×ϕ(n){d \times e = 1 + k \times \phi(n)}, où kZ{k \isin \Z}

Les clefs générées sont alors :

  • Une clef publique : (n,e)(n, e)
  • Une clef privée : (n,d)(n, d)

Nous discuterons plus loin de l’implémentation pratique des différentes étapes.

Chiffrement d’un message

Pour être chiffré, un message doit être encodé sous la forme d’un nombre m<n{m < n}.

Le message chiffré est obtenu par le calcul modulo nn suivant :

c=memodn{c = m^e \mod n}

Une autre façon (équivalente) de formuler les choses est d’identifier un message en clair à un élément mZ/nZ{m \isin \Z/n\Z} et calculer le message chiffré comme l’élément c=meZ/nZc = m^e \isin \Z/n\Z.

Déchiffrement d’un message chiffré

À partir du message chiffré cc, par construction un nombre entre 00 et n1{n - 1} (inclus), on obtient le message déchiffré par la formule suivante :

m=cdmodn{m = c^d \mod n}

Preuve du fonctionnement

Il s’agit de vérifier que la formule de déchiffrement de cc redonne bien le message mm d’origine.

On a par construction d×e=1+k×ϕ(n){d \times e = 1 + k \times \phi(n)}.

On développe alors la formule de déchiffrement :

cd=me×d=m1+k×ϕ(n)modnc^d = m^{e \times d} = m^{1 + k \times \phi(n)} \mod n \\

On obtient deux cas. Le premier permet de conclure rapidement. Le second nécessite des calculs un peu plus compliqués…

  1. Si gcd(m,n)=1\gcd(m, n) = 1, le théorème d’Euler indique que mϕ(n)=1modnm^{\phi(n)} = 1 \mod n et le calcul donne cd=mmodn=m{c^d = m \mod n = m} : on retrouve bien mm.
  2. Sinon, c’est que pp ou qq divise mm. Les deux ne peuvent être diviseurs simultanément puisque m<n=p×q{m < n = p \times q}), on peut supposer par exemple que pp divise mm.

On peut alors écrire m=pα×M{m = p^{\alpha} \times M}, où α>0\alpha > 0 et MM n’est divisible ni par pp ni par qq et est donc premier avec nn.

On obtient :

me×d=(pα×M)e×d=pα×e×d×Me×d=pα×e×d×Mmodnm^{e \times d} = (p^{\alpha} \times M)^{e \times d} = p^{\alpha \times e \times d} \times M^{e \times d} = p^{\alpha \times e \times d} \times M \mod n

(on a utilisé que MM est premier avec nn, ce qui ramène au cas 1)

On a par ailleurs :

pα×e×dpα=pα×(pα×(e×d1)1)=0modpp^{\alpha \times e \times d} - p^{\alpha} = p^{\alpha} \times (p^{\alpha \times (e \times d - 1)} - 1) = 0 \mod p

et aussi :

pe×d=p1+k×ϕ(n)=p×pk×(p1)×(q1)=p×(pk×(p1))q1=pmodqp^{e \times d} = p^{1 + k \times \phi(n)} = p \times p^{k \times (p-1) \times (q-1)} = p \times (p^{k \times (p-1)})^{q-1} = p \mod q

La dernière simplification vient du petit théorème de Fermat qui permet d’écrire aq1=1modq{a^{q-1} = 1 \mod q}, lorsque qq est premier et aa n’est pas divisible par qq.

Ces deux derniers calculs nous montrent que pα×e×dpαp^{\alpha \times e \times d} - p^{\alpha} est divisible par pp et par qq, donc également par n=p×qn = p \times q, ce qui nous permet de reprendre le calcul initial :

me×d=pα×e×d×Mmodn=pα×Mmodn=mmodn=mm^{e \times d} = p^{\alpha \times e \times d} \times M \mod n \\ = p^{\alpha} \times M \mod n \\ = m \mod n \\ = m

🙂

💻 Implémentation de RSA en Python

Nous avons décrit la recette de l’algorithme RSA, je vous en propose maintenant une implémentation basique en Python, afin de vérifier que tout cela fonctionne bien !

⚠️ Cette implémentation naïve ne doit évidemment pas être utilisée en production, elle n’est ni optimale ni robuste du point de vue de la sécurité. Son but est purement didactique.

Pour démarrer, cliquez sur Run ▶️, puis commencez par générer une paire de clefs.

Voici par exemple ce que j’ai obtenu :

Création des clefs
DEBUG: p=257205938468792623586345060713, q=564292122274801049105971923463,
n=145139284880236882068996179284591347066612215282786124209119,
e=5, d=29027856976047376413799235856753969801173724322018761444989
Clef privée :
eyJtb2R...3MzcyNDMyMjAxODc2MTQ0NDk4OX0=
Clef publique :
eyJtb2R..CAiZXhwb25lbnQiOiA1fQ==
Chiffrement
Entrez la clef publique :
eyJtb2R..CAiZXhwb25lbnQiOiA1fQ==
Message à chiffrer :
Lorem ipsum
Message chiffré :
12906681535323653913467296579360861757391479192915128204736
Déchiffrement
Entrez la clef privée :
eyJtb2R...3MzcyNDMyMjAxODc2MTQ0NDk4OX0=
Message à déchiffrer :
12906681535323653913467296579360861757391479192915128204736
Message déchiffré :
Lorem ipsum
Quelques remarques
  • Les clefs — couples (module, exposant) — sont sérialisées en utilisant base64.
    De façon générale, différentes implémentations de RSA peuvent utiliser différents formats pour représenter les clefs (nous y reviendrons).
  • L’étape 2 de l’algorithme de génération des clefs demande de générer ee premier avec ϕ(n)\phi(n). Nous avons ici utilisé une méthode essai-erreur pour trouver une valeur de ee satisfaisante :
    e = 2
    while gcd(e, phi) != 1:
    e += 1
  • Dans cette implémentation naïve, nous avons simplement codé en dur une liste de nombres premiers. Le problème de la génération de grands nombres premiers est compliqué.
    Beaucoup d’algorithmes reposent sur des méthodes probabilistes (le nombre généré pourrait ne pas être premier, mais la probabilité que ce soit le cas est négligeable, par exemple inférieure 101510^{-15}).
  • Le calcul de l’inverse modulaire est disponible nativement dans Python à partir de la version 3.8 :
    d = pow(e, -1, phi)
    Si vous utilisez une version antérieure, vous pouvez utiliser l’implémentation de SymPy ou implémenter votre propre version (par exemple avec l’algorithme d’Euclide étendu, détaillé ici).

RSA dans la vraie vie

Navigation en HTTPS

J’ai obtenu les informations ci-dessous avec Firefox en cliquant sur le petit symbole 🔒 à gauche de la barre d’adresse, depuis https://www.github.com.

Informations sur un certificat dans Firefox

On peut y lire notamment que :

  • le certificat utilise RSA avec une clef sur 2048 bits : il s’agit de la taille du module nn généré.
  • l’exposant ee est 6553765537. Pour certaines raisons, ce nombre est très souvent utilisé comme exposant public.
  • le contenu du module est également affiché (en hexadécimal)

Utilisation dans le cadre de TLS

En pratique, RSA est un algorithme assez lourd en terme de calculs et qui ne permet, comme nous l’avons vu, que de chiffrer des messages m<nm <n,

Il est donc généralement utilisé pour échanger d’autres clefs, propres à la session, qui vont permettre de chiffrer la suite de l’échange. Par exemple, RSA pourra être utilisé pour échanger des clefs de chiffrement symétrique AES.

Dans le cadre de HTTPS, RSA ne consitue ainsi qu’une brique du protocole de sécurisation TLS.

TLS peut aussi utiliser d’autres algorithmes de chiffrement asymétriques que RSA.

Des méthodes basées sur les courbes elliptiques, objets mathématiques plus « modernes » constituent un exemple d’alternatives. Ces méthodes permettent notamment d’obtenir des niveaux équivalents de sécurité avec des clefs plus petites.

💡 La construction des courbes elliptiques utilisées en cryptographie repose notamment sur les corps Fp=Z/pZ\mathbb{F}_p = \Z/p\Z, que nous avons vus plus haut (cas où pp est premier).

Décorticage de clefs avec OpenSSL

OpenSSL est une bibliothèque libre et ouverte de fonctionnalités cryptographiques, écrite en C. Elle est de fait très utilisée, par exemple par des serveurs web ou par OpenSSH.

Nous allons l’utiliser ici pour générer des vraies clefs, telles qu’elles sont utilisées en pratique.

La commande ci-dessous permet de générer une paire de clefs RSA 2048 bits, et de l’enregistrer dans un fichier dummy.pem.

(Cette clef n’est évidemment pas utilisée en production. Le contenu est tronqué pour alléger la présentation.)

$ openssl genrsa -out dummy.pem 2048
-----BEGIN RSA PRIVATE KEY-----
MIIEowIBAAKCAQEAxZTA6Tlfs+/le2obemsioULR3ipwupIXvnATYGpjpbdLsKEn
HJnoOl/IoeQHzDcS10/NKHWWklcK4WfxnRX62XyyWYmnnfJQPLepGPujbPYsxLAu
l4ON9INOulHXHKrorqyQNvzeCm46gQAeEd2+IH2HtFHEM2Avtw0qYxQc5y0rEeTQ
...
v+gagQKBgFHsYq9M8E7Po67DNfK9f0qfxev1PTV584vVWs4O0vr2p/+RorEed3Xa
W02mZnqg0wS/4wuKz43UUU9x8GEZuNIW0/5XX/YrvEV90OktQ9lbanNLWJaqSyoC
6PLdT49uniyhkiySmVt9EgJSIaYy32F3HCYaNWkF9pyZ+SNXlB23
-----END RSA PRIVATE KEY-----

La commande suivante permet d’examiner un tel fichier pour voir ce qu’il contient :

$ openssl rsa -text -noout < dummy.pem
Private-Key: (2048 bit)
modulus:
00:c5:94:c0:e9:39:5f:b3:ef:e5:7b:6a:1b:7a:6b:
22:a1:42:d1:de:2a:70:ba:92:17:be:70:13:60:6a:
...
08:32:9a:2c:57:cc:3c:1b:08:1f:1f:e4:38:de:a4:
40:43:98:39:56:70:d5:d5:03:71:1f:3a:06:dd:d0:
da:6f
publicExponent: 65537 (0x10001)
privateExponent:
4d:9d:b6:fe:a7:84:39:fa:66:8a:c9:cf:0b:93:24:
...
38:1c:d4:5c:1e:67:37:08:6a:81:cf:56:ad:8f:b5:
11
prime1:
00:fe:94:9b:60:59:99:11:4c:8d:48:f4:a4:39:af:
...
b9:f0:d6:3b:d9:f4:4d:d3:07
prime2:
00:c6:ae:c8:d8:32:17:25:bc:89:86:cc:b2:38:e7:
...
6f:ba:ac:12:be:7a:89:5b:59
exponent1:
00:ae:b5:ed:ab:c1:d1:7a:3d:be:f8:42:6c:31:ea:
...
7c:dc:fb:29:37:fa:a1:2e:21
exponent2:
0a:d1:19:3e:2b:fb:f6:a1:fd:1a:c9:aa:2a:4e:f6:
...
3f:61:7e:e3:bf:e8:1a:81
coefficient:
51:ec:62:af:4c:f0:4e:cf:a3:ae:c3:35:f2:bd:7f:
...
9c:99:f9:23:57:94:1d:b7

Nous pouvons faire les observations suivantes :

  • Ce format encode les deux clefs (privées et publique) dans le même fichier. La commande openssl rsa -in dummy.pem -pubout permet d’en extraire une clef publique.
  • Le fichier stocke le module nn et les exposants ee (public) et dd (privée), mais aussi d’autres données.
    Ces informations supplémentaires permettent d’optimiser la fonction de déchiffrement du message, le calcul pouvant alors être rendu plus rapide.
    Cette optimisation, appelée RSA-CRT, utilise le théorème des restes chinois.

Attaques contre RSA

RSA reste très largement utilisé et considéré comme robuste, mais des scénarios d’attaque sont connus si les clefs ne respectent pas certaines contraintes.

En particulier, le module nn doit être suffisamment grand pour rendre extrêmement complexe sa factorisation (aujourd’hui, on considère qu’il faut une taille de clef d’au moins 20482048 bits).

D’autres scénarios d’attaque existent, par exemple l’attaque de Wiener, qui permet de retrouver la clef privée à partir de la clef publique lorsque dd est trop petit.

Un exercice intéressant pourrait être de la mettre en oeuvre pour casser l’implémentation naïve fournie plus haut…



Maths et applications, avec les mains et avec du code 💻
Suivre sur Twitter

© 2020 Lipsum.dev — Contactez-moi (questions, remarques, etc.)