Problème RSA

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.