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 . L'exponentielle modulaire intervient dans les algorithmes de la cryptographie à clé publique, car l'exponentielle modulaire est considérablement plus facile à calculer que son inverse, le logarithme modulaire. Le système de chiffrement à clé publique RSA a été proposé en 1977 par Ron Rivest, Adi Shamir et Leonard Adleman.

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:

Quand A veut communiquer 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(C(m)) = C(m)^d \mathop{ \normalfont \mathrm{mod}}\nolimits n = m^{ed}\mathop{ \normalfont \mathrm{mod}}\nolimits n = m$, grâce au théorème d'Euler $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é 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).