Cryptographie à clé publique : RSA

La cryptographie a pour but d'assurer la sécurité des données, en les chiffrant afin de les rendre incompréhensibles sans l'usage d'une clé de déchiffrement. Pendant longtemps, la cryptographie a reposé sur l'usage d'une clé secrète, qui devait être partagée par l'émetteur et le récepteur. En 1976, Diffie et Hellman suggérèrent la possibilité d'assurer la confidentialité sans recourir à un secret partagé, au moyen d'une clé connue de tous. Cette idée a profondément transformé la cryptographie. Le système de chiffrement à clé publique RSA, proposé en 1977 par Rivest, Shamir et Adleman, est maintenant couramment utilisé par les systèmes de chiffrement, par exemple par PGP, généralement en complément d'un chiffrement à clé secrète à usage unique. Le développement du commerce électronique et l'irruption de l'Internet dans la vie privée ont entraîné une large diffusion des outils cryptographiques, longtemps réservés à des usages militaires. L'exponentielle modulaire intervient dans les algorithmes de la cryptographie à clé publique, car elle est considérablement plus facile à calculer que son inverse, le logarithme modulaire.

Pour construire ses clés, chaque utilisateur de RSA

• choisit deux grands nombres premiers p et q ;
• calcule n=pq ;
• choisit un entier e<n qui est premier avec (p-1)(q-1) ;
• calcule l'inverse d de e modulo (p-1)(q-1) ;
• publie sa clé publique, qui est formée des deux entiers e et n ;
• conserve sa clé privée d ;
• détruit les entiers p et q qui ne doivent pas être divulgués.

Les fonctions de chiffrage et de déchiffrage sont respectivement :

$$\begin{eqnarray*}C(m) &= &m^e \mathop{\normalfont\mathrm{mod}}\nolimits n \\ D(m) &= &m^d \mathop{\normalfont\mathrm{mod}}\nolimits n \end{eqnarray*}$$

 

Les fonctions et paramètres d'un utilisateur A sont notés C_A, D_A, n_A, e_A, d_A ; la fonction de chiffrage C_A est connue de tous, tandis que la fonction de déchiffrage D_A n'est connue que de A. Soient A et B deux utilisateurs de RSA. Quand A veut communiquer confidentiellement un entier m (0<m<n) à B, il calcule C_B(m) à l'aide de la clé publique de B, qu'il envoie à B ; à la réception d'un message chiffré c, B calcule D_B(c) à l'aide de sa clé privée. Il s'agit bien d'un déchiffrage car $D_B(C_B(m)) = C_B(m)^{d_B} \mathop{\normalfont\mathrm{mod}}\nolimits n_B = m^{e_Bd_B}\mathop{\normalfont\mathrm{mod}}\nolimits n = m$, grâce au théorème d'Euler qui assure que $m^{\phi(n)} = 1 \mathop{\normalfont\mathrm{mod}}\nolimits n$ si m est premier avec n, et au fait que $\phi(n)=(p-1)(q-1)$.

La sécurité de ce schéma provient de la difficulté à factoriser de grands entiers. En effet, déterminer d à partir de e demande la connaissance de (p-1)(q-1); or la publication de n=pq n'est en aucune façon une aide pour calculer (p-1)(q-1), qui ne peut être obtenu qu'à partir de p et q. D'autre part, on ne sait pas calculer efficacement des racines e-ièmes, ce qui permettrait d'avoir le texte clair m à partir du texte chiffré C(m). Contrairement à la plupart des autres problèmes, pour lesquels on cherche des algorithmes efficaces, le chiffrement n'est utile que si le problème de déchiffrement est difficile, c'est-à-dire que si tous les algorithmes que l'on peut proposer sont extrêmement inefficaces.

La méthode RSA est également employée pour l'authentification  des données. Si A veut communiquer un entier m (0<m<n) à B et garantir à B qu'il est l'auteur de ce message, il joint à m sa signature  s = D_A(h(m)) grâce à sa clé privée et à une fonction de hachage h publique (voir § 2.10, par exemple, la fonction MD5). Recevant m et s de la part de A, Bcalcule à la fois C_A(s) grâce à la clé publique de A et h(m) ; normalement, C_A(s) = C_A(D_A(h(m))) = h(m), par le même théorème d'Euler ; donc si B obtient le même nombre par dxes deux calculs, le message est authentifié ; sinon, c'est que A n'en est pas l'auteur, ou bien que m a été altéré au cours de la transmission. La sécurité de ce schéma d'authentification repose sur la difficulté, étant donné h, à trouver m tel que h(m) = h.