Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur GraphSearch.
Concept
Problème RSA
Résumé
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), 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 : N
e : N, premier avec φ(n)
C : N
Problème:
Trouver une racine e-ième de C modulo n.
Autrement dit trouver un entier m tel que me ≡ 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 Z/nZ, donc si e est inversible d'inverse d modulo φ(n), alors m = Cd 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 53 ≡ 60 mod 65, mais si on « chiffre » 45, on obtient aussi 453 ≡ 60 mod 65. 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.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.