Problème RSA

En cryptanalyse, le problème RSA est le problème de l'inversion de la fonction de chiffrement du système de cryptographie asymétrique RSA. Étant donné que RSA est un chiffrement surjectif, ce problème a toujours une solution.

La difficulté calculatoire supposée de ce problème implique la sécurité sémantique du chiffrement RSA avec un remplissage adéquat (comme OAEP par exemple^[1]), puisque le chiffrement RSA tel qu’il est usuellement décrit est déterministe et ne peut donc pas être sémantiquement sûr.

Plus formellement, le problème RSA est le problème d'arithmétique modulaire suivant.

Entrées:
  · n : ℕ
  · e : ℕ, premier avec φ(n)
  · C : ℕ
Problème:
  Trouver une racine e-ième de C modulo n.

Autrement dit trouver un entier m tel que m^e ≡ C mod n avec les notations précédentes.

Le problème a toujours une solution qui est unique modulo n. En effet φ(n) = (p-1)·(q-1) est l'ordre du groupe des éléments inversibles de l'anneau ℤ/nℤ, donc si e est inversible d'inverse d modulo φ(n), alors m = C^d mod n par le théorème d'Euler.

En revanche si e n'est plus premier avec φ(n), alors le problème perd l'unicité de la solution, et son existence pour tout C. On peut le voir à l’aide d’un exemple jouet du problème RSA avec n = 65 = 5·13 et e=3, de telle manière que e | φ(65) = 48, alors en « chiffrant » 5, on obtient 5³ ≡ 60 mod 65, mais si on « chiffre » 45, on obtient aussi 45³ ≡ 60 mod 65^[2]. En transmettant uniquement 60 comme chiffré, il est donc impossible de remonter au message initial. Le chiffrement n’est plus injectif.

Mathématiquement, cela vient du fait qu’un inverse de e modulo φ(n) est un élément d tel que e·d = 1 + k·φ(n) pour un certain entier relatif k. Ainsi e inversible modulo φ(n) est équivalent à écrire qu’il existe deux entiers relatifs d et k tels que e·d - k·φ(n) = 1. Cette relation n’est réalisable que si pgcd(e,φ(n)) = 1 par le théorème de Bézout.

La sécurité de l'algorithme RSA repose sur le fait que ce problème devient impossible à résoudre calculatoirement pour n un produit de deux nombres premiers suffisamment grands, n étant connu mais pas sa factorisation.

En revanche, si l’on dispose de la factorisation de n, il devient facile de calculer φ(n), qui est la clef privée du chiffrement RSA. Résoudre ce problème revient alors à lancer l'algorithme de déchiffrement du cryptosystème. C'est pour cela que l’on considère la fonction “m ⟼ m^e mod n” comme étant une fonction à sens unique avec trappe (one-way trapdoor function en anglais).

De plus, comme résoudre le problème de la factorisation nous donne une solution pour résoudre le problème RSA, RSA est au moins aussi facile que la factorisation. Savoir si les deux problèmes sont équivalents reste en 2016 une question ouverte. Une autre manière de dire la même chose est de dire que le problème devient calculatoirement facile à résoudre si les deux facteurs p et q sont connus, donc φ(n), ce sur quoi s'appuie le déchiffrement. On pourrait donc résoudre (sur le plan calculatoire) le problème RSA si on savait résoudre le problème de la factorisation d'un entier (la recherche de sa décomposition en facteurs premiers par une méthode calculatoirement efficace). On ne sait toutefois pas s'il existe des méthodes plus efficaces.

Dans certaines situations, cette hypothèse n’est pas suffisante pour démontrer des propriétés sur les schémas considérés. On a alors parfois besoin d’hypothèses renforcées, qui impliquent la difficulté du problème RSA.

Ce renforcement de l’hypothèse a été utilisée pour la première fois en 1997 pour construire un schéma de signature sûr dans le modèle standard^[3], et a ensuite été utilisé pour construire des schémas que l’on ne savait pas construire autrement, comme le premier schéma de signature de groupe cryptographiquement sûr^[4].

Dans ce renforcement, il n’est plus demandé de trouver une racine e-ième de C étant donné (n, e, C), mais de trouver une racine modulaire quelconque, c'est-à-dire qu’étant donné (n, C) comme définis plus haut, le but est de trouver un couple (m,e) tel que m^e = C mod n. Autrement dit l’attaquant a la possibilité de choisir l’exposant avec lequel il attaque le problème RSA.

On peut remarquer que si on sait résoudre le problème RSA pour un e donné, alors on sait aussi résoudre le problème RSA-fort, puisqu’il suffit de renvoyer le couple (e, m) pour le e connu en entrée et le résultat m renvoyé par l'attaquant contre le problème RSA. Ce qui confirme bien que le problème RSA-fort est polynomialement plus facile que le problème RSA, et que sa difficulté implique ainsi celle du problème RSA.

• [Barić et Pfitzmann 1997] (en) Niko Barić et Birgit Pfitzmann, « Collision-Free Accumulators and Fail-Stop Signature Schemes Without Trees », Eurocrypt,‎ 1997 (DOI 10.1007/3-540-69053-0_33)
• [Ateniese et al. 2000] (en) Giuseppe Ateniese, Jan Camenisch, Marc Joye et Gene Tsudik, « A Practical and Provably Secure Coalition-Resistant Group Signature Scheme », Crypto,‎ 2000 (DOI 10.1007/3-540-44598-6_16)
• [Fujisaki et al. 2001] (en) Eiichiro Fujisaki, Tatsuaki Okamoto, David Pointcheval et Jacques Stern, « RSA-OAEP Is Secure under the RSA Assumption », Crypto,‎ 2001 (DOI 10.1007/3-540-44647-8_16)
• [Menezes, van Oorschot et Vanstone 1996] (en) Alfred Menezes, Paul C. van Oorschot et Scott A. Vanstone, Handbook of Applied Cryptography, Boca Raton, CRC Press, octobre 1996, 780 p. (ISBN 0-8493-8523-7, présentation en ligne, lire en ligne), chap. 3 (« The RSA problem »).

• Hypothèse calculatoire
• Cryptographie asymétrique
• Décomposition en produit de facteurs premiers
• Chiffrement RSA
• Compétition de factorisation RSA
• OAEP
• Preuve de sécurité

[Rivest et Kaliski 2003] (en) Ronald Rivest et Burt Kaliski, « RSA Problem »

• Portail de la cryptologie
• Arithmétique et théorie des nombres