Chiffrement RSA

Alice donne sa clé publique (n, e) à Bob et garde sa clé privée secrète. Bob veut envoyer le message M à Alice.

Il transforme d'abord M en un nombre m (style d'affichage m) plus petit que n (style d'affichage n) en utilisant un protocole réversible convenu, appelé "padding scheme". Il calcule ensuite le cryptogramme c correspondant :

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

Cela peut être fait rapidement en utilisant la méthode d'exponentiation par la quadrature. Bob envoie alors c à Alice.

Alice peut récupérer la clé m de la clé c en utilisant sa clé privée d dans la procédure suivante :

m = c d mod n {\displaystyle m=c^{d}{\bmod {n}}}

Étant donné le style d'affichage m , elle peut récupérer les nombres premiers distincts d'origine, en appliquant le théorème du reste chinois à ces deux congruences, ce qui donne

m e d ≡ m mod p q {\displaystyle m^{ed}\equiv m{\bmod {pq}}} .

Ainsi,

c d ≡ m mod n {\displaystyle c^{d}\equiv m{\bmod {n}}} .

Un exemple de travail

Voici un exemple de cryptage et de décryptage RSA. Les paramètres utilisés ici sont artificiellement petits, mais vous pouvez également utiliser OpenSSL pour générer et examiner une véritable paire de clés.

1. Choisissez deux nombres premiers aléatoires.
2.  p = 61 et q = 53 ; p = 61 et q = 53 Calculer n = p q {\displaystyle n=pq\,}
3.  : n = 61 ∗ 53 = 3233 {\displaystyle n=61*53=3233}
4. Calculer le patient ϕ ( n ) = ( p - 1 ) ( q - 1 ) {\displaystyle \phi (n)=(p-1)(q-1)\,}
5.  : ϕ ( n ) = ( 61 - 1 ) ( 53 - 1 ) = 3120 {\displaystyle \phi (n)=(61-1)(53-1)=3120}
6. Choisissez e > 1 {\displaystyle e>1} coprime à 3120
7.  : e = 17 {\displaystyle e=17}
8. Choisissez d {\displaystyle d\,} pour satisfaire d e mod ϕ ( n ) ≡ 1 {\displaystyle de{\bmod {\phi (n)}}\equiv 1\,}
9.  d = 2753 {\displaystyle d=2753}
10.  : 17 ∗ 2753 = 46801 = 1 + 15 ∗ 3120 {\displaystyle 17*2753=46801=1+15*3120} .

La clé publique est ( n = 3233 {\displaystyle n=3233} , e = 17 {\displaystyle e=17} ). Pour un message rembourré m, la fonction de cryptage c = m e mod n, c=m^{e}{\bmod {n}} devient :

c = m 17 mod 3 233 {\displaystyle c=m^{17}{\bmod {3}}233\,}

La clé privée est ( n = 3233 {\displaystyle n=3233} , d = 2753 {\displaystyle d=2753} ). La fonction de décryptage m = c d mod n {\displaystyle m=c^{d}{\bmod {n}}} devient :

m = c 2753 mod 3 233 {\displaystyle m=c^{2753}{\bmod {3}}233\,}

Par exemple, pour crypter m = 123 {\displaystyle m=123} nous calculons

c = 123 17 mod 3 233 = 855 {\displaystyle c=123^{17}{\bmod {3}}233=855}

Pour décrypter c = 855 {\displaystyle c=855} nous calculons

m = 855 2753 mod 3 233 = 123 {\displaystyle m=855^{2753}{\bmod {3}}233=123}

Ces deux calculs peuvent être effectués efficacement à l'aide de l'algorithme de l'exponentiation modulaire par carré et multiplication [en].

Le RSA peut facilement être dérivé en utilisant le théorème d'Euler et la fonction totient d'Euler.

En commençant par le théorème d'Euler,

m ϕ ( n ) ≡ 1 ( mod n ) {\displaystyle m^{\phi (n)}\equiv 1{\pmod {n}}}

nous devons montrer que le décryptage d'un message crypté, avec la bonne clé, donnera le message original. Étant donné un message chiffré m, le texte chiffré c, est calculé par

c ≡ m e ( mod n ) {\displaystyle c\equiv m^{e}{\pmod {n}}}

En remplaçant dans l'algorithme de décryptage, nous avons

c d ≡ ( m e ) d ≡ m e d ( mod n ) {\displaystyle c^{d}\equiv (m^{e})^{d}\equiv m^{ed}{\pmod {n}}}

Nous voulons montrer que cette valeur est également en accord avec m. Les valeurs de e et d ont été choisies pour satisfaire,

e d ≡ 1 ( mod ϕ ( n ) ) Displaystyle ed\equiv 1{\pmod {\phi (n)}}

C'est-à-dire qu'il existe un nombre entier k, tel que

e d = k × ϕ ( n ) + 1 {\displaystyle ed=k\times \phi (n)+1}

Maintenant, nous nous substituons au message crypté puis décrypté,

m e d ≡ m k ϕ ( n ) + 1 ≡ m × m k ϕ ( n ) ≡ m × ( m ϕ ( n ) ) k ( mod n ) {\displaystyle {\begin{aligned}m^{ed}&\equiv m^{k\phi (n)+1}\\&\equiv m\times m^{k\phi (n)}\\\\&\equiv m\times \left(m^{\phi (n)}\right)^{k}{\pmod {n}}\end{aligned}}}

Nous appliquons le théorème d'Euler, et nous obtenons le résultat.

m × ( 1 ) k ≡ m ( mod n ) {\displaystyle m\times (1)^{k}\equiv m{\pmod {n}}}

En pratique, l'ASR doit être combinée avec une forme de système de remplissage, de sorte qu'aucune valeur de M ne se traduise par des cryptogrammes non sécurisés. Le RSA utilisé sans rembourrage peut poser certains problèmes :

• Les valeurs m = 0 ou m = 1 produisent toujours des cryptogrammes égaux à 0 ou 1 respectivement, en raison des propriétés de l'exponentiation.
• Lors du chiffrement avec de petits exposants de chiffrement (par exemple, e = 3) et de petites valeurs de m, le résultat (non modulaire) de m e {\displaystyle m^{e}} peut être strictement inférieur au module n. Dans ce cas, les cryptogrammes peuvent être facilement déchiffrés en prenant la racine eth du cryptogramme sans tenir compte du module.
• Le cryptage RSA est un algorithme de cryptage déterministe. Il n'a pas de composante aléatoire. Par conséquent, un attaquant peut lancer avec succès une attaque en texte clair choisie contre le cryptosystème. Il peut créer un dictionnaire en cryptant des textes en clair probables sous la clé publique et en stockant les cryptogrammes qui en résultent. L'attaquant peut alors observer le canal de communication. Dès qu'il voit des cryptogrammes qui correspondent à ceux de son dictionnaire, l'attaquant peut alors utiliser ce dictionnaire afin d'apprendre le contenu du message.

En pratique, les deux premiers problèmes peuvent survenir lors de l'envoi de courts messages ASCII. Dans ces messages, m peut être la concaténation d'un ou de plusieurs caractères codés en ASCII. Un message constitué d'un seul caractère ASCII NUL (dont la valeur numérique est 0) serait codé comme m = 0, ce qui produit un texte chiffré de 0, quelles que soient les valeurs de e et N utilisées. De même, un message constitué d'un seul caractère ASCII SOH (dont la valeur numérique est 1) produirait toujours un texte chiffré de 1. Pour les systèmes qui utilisent conventionnellement de petites valeurs de e, telles que 3, tous les messages ASCII à un seul caractère codés selon ce schéma ne seraient pas sûrs, puisque le plus grand m aurait une valeur de 255, et 2553 est inférieur à tout module raisonnable. De tels clairxts pourraient être récupérés en prenant simplement la racine cubique du texte chiffré.

Pour éviter ces problèmes, les implémentations pratiques de la RSA intègrent généralement une forme de remplissage structuré et aléatoire dans la valeur m avant de la chiffrer. Ce remplissage garantit que m n'entre pas dans la gamme des clair-exts non sécurisés, et qu'un message donné, une fois rempli, sera chiffré dans l'un des nombreux cryptogrammes possibles. Cette dernière propriété peut augmenter le coût d'une attaque par dictionnaire au-delà des capacités d'un attaquant raisonnable.

Des normes telles que le PKCS ont été soigneusement conçues pour protéger les messages avant le cryptage RSA. Comme ces systèmes ajoutent un certain nombre de bits supplémentaires au texte en clair m, la taille du message M non rembourré doit être un peu plus petite. Les systèmes de remplissage RSA doivent être conçus avec soin afin de prévenir les attaques sophistiquées. Cela peut être facilité par une structure de message prévisible. Les premières versions de la norme PKCS utilisaient des constructions ad hoc, qui se sont révélées par la suite vulnérables à une attaque pratique de texte chiffré choisi de manière adaptative. Les constructions modernes utilisent des techniques sûres telles que le remplissage asymétrique optimal du chiffrement (OAEP) pour protéger les messages tout en empêchant ces attaques. La norme PKCS comporte également des schémas de traitement conçus pour apporter une sécurité supplémentaire aux signatures RSA, par exemple le schéma de signature probabiliste pour RSA (RSA-PSS).

Supposons qu'Alice utilise la clé publique de Bob pour lui envoyer un message crypté. Dans le message, elle peut prétendre être Alice mais Bob n'a aucun moyen de vérifier que le message provient bien d'Alice puisque n'importe qui peut utiliser la clé publique de Bob pour lui envoyer des messages cryptés. Ainsi, afin de vérifier l'origine d'un message, la RSA peut également être utilisée pour signer un message.

Supposons qu'Alice souhaite envoyer un message signé à Bob. Elle produit une valeur de hachage du message, l'élève à la puissance d mod n (comme lors du décryptage d'un message), et l'attache comme "signature" au message. Lorsque Bob reçoit le message signé, il élève la signature à la puissance e mod n (tout comme lors du cryptage d'un message), et compare la valeur de hachage résultante avec la valeur de hachage réelle du message. Si les deux s'accordent, il sait que l'auteur du message était en possession de la clé secrète d'Alice, et que le message n'a pas été altéré depuis.

Il convient de noter que les systèmes de remplissage sécurisés tels que RSA-PSS sont aussi essentiels pour la sécurité de la signature des messages que pour le cryptage des messages, et que la même clé ne doit jamais être utilisée à la fois pour le cryptage et la signature.