Problème RSA

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

Le problème RSA est le problème de l'inversion de la fonction de chiffrement du système de cryptographie asymétrique RSA. Sur le plan mathématique il s'agit du problème d'arithmétique modulaire suivant.

Étant donnés un entier n produit de deux nombres premiers distincts p et q, un entier naturel e premier avec (p - 1)(q -1), et un entier naturel c, trouver un entier naturel m tel que mec mod n.

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 Z/nZ, donc si e est inversible d'inverse d modulo φ(n), m = cd mod n par le théorème d'Euler (le résultat est en fait vérifié également si e n'est pas inversible modulo φ(n) car n est produit de nombres premiers distincts, voir Chiffrement_RSA#Déchiffrement_du_message).

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, chose que l'on a constatée jusqu'à aujourd'hui, mais pas démontrée.

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), mais la réciproque n'est pas connue.

Bibliographie[modifier | modifier le code]