Discussion:Chiffrement RSA

Sécurité

J'ai corrigé le texte suivant qui était imprécis et inexact et l'ai remplacé par la version en ligne du jour.

La sécurité de cet algorithme repose sur deux conjectures :

1. « casser » RSA nécessite la factorisation du nombre n,
2. la factorisation est un problème difficile, car il n'existe pas d'algorithme suffisamment rapide. De façon plus précise, les mathématiciens affirment qu'il n'existe pas d'algorithme ayant une complexité polynomiale en temps qui donne les facteurs premiers d'un nombre quelconque.

Il est possible que l'une des deux conjectures soit fausse, voire les deux. Si c'est le cas, alors RSA n'est pas sûr. Cela fait néanmoins maintenant plus de 25 ans que RSA est cryptanalysé et il n'a pas encore été « cassé ». On peut donc raisonnablement le considérer comme un algorithme sûr. Cependant si une personne venait à trouver un moyen « rapide » de factoriser ce nombre n, tous les algorithmes de chiffrement fondés sur ce principe seraient remis en cause ainsi que toutes les données chiffrées auparavant à l'aide de ces algorithmes.

Il faut distinguer les attaques par la force brute, qui sont très difficiles sur les ordinateurs standards vu la complexité exponentielle de la factorisation, et les autres attaques visant l'implémentation des algorithme RSA (choix des nombres premiers, de e ...), où nombre d'idées ingénieuses surgissent en pratique. Comme de la recherche secrète a lieu sur ce sujet, il faut aussi rester prudent quant à trop d'affirmations. Pour les avis des spécialistes à la suite de ce paragraphe, des références sont nécessaires. Merci à toute collaboration. --CryptoMania (d) 15 février 2010 à 16:53 (CET)

Une clef RSA de 1024bit à été cassée en 2010 par l'université du Michigan, voir: http://www.securi-toile.com/securite/cle-rsa-1024-casse

Déchiffrement du message

J'ai un problème avec la ligne.

Or $x^{\varphi (n)}\equiv 1{\pmod {n}}$, d'après le théorème d'Euler.

Le x sort de nulle part. D'après le contexte, on devrait le remplacer par un M. Mais pourquoi M serait-il premier avec n (pour qu'on puisse appliquer Euler)? PierreL 31 mai 2006 à 13:53 (CEST)

M n'a aucune raison d'être premier avec n a priori. Mais comme n est le produit de deux premiers, il y a peu de chances pour que M ne soit pas premier avec n. Plus précisément, il y a exactement p+q-1 nombres non premiers avec n. Si p et q sont de l'ordre de ${\sqrt {n}}$, la probabilité pour que M ne soit pas premier avec n est de l'ordre de ${\frac {p+q-1}{n}}\sim 2{\frac {\sqrt {n}}{n}}\sim {\frac {2}{\sqrt {n}}}$. Pour n de 1000 bits, soit de l'ordre de $10^{100}$, ça fait une chance plus que faible.

Au pire, l'expéditeur peut vérifier que M n'est pas premier avec n (en temps logarithmique, ça ne pose pas de problème), et redemander un n et un e différents si ce n'est pas le cas... Mais ça m'étonnerait :)

PS : tout ceci n'est qu'hypothétique, je n'y connais rien, mais c'est ce qui me semble raisonnable (je m'étais posé la même question :)). (Rnlabra, le 25 juillet 2006).

La démonstration présentée est effectivement fausse si M n'est pas premier avec n. Néanmoins on peut montrer que $C^{d}\equiv M{\pmod {n}}$ lorsque M n'est pas premier avec n. (Yves, le 21/09/2006)

$M^{1+k(p-1)(q-1)}\equiv M{\pmod {p}}$ et $M^{1+k(p-1)(q-1)}\equiv M{\pmod {q}}$ sont vrais pour tout M (même si M multiple de p ou q). On conclut par les restes chinois. Cette remarque a été ajoutée par Sgsixhuit (d · c · b) le 5 janvier 2008

La démonstration aujourd'hui dans l'article me semble non convaincante car trop compliquée. La démonstration proposée par Sgsixhuit est celle que l'on trouve généralement dans la littérature (livre de TS). Elle a le mérite de la simplicité et ne nécessite même pas l'allusion au théorème des restes chinois mais tout bêtement au théorème de Gauss : si A est multiple de p et q et si p et q sont premiers entre eux alors A est multiple de pq. Sauf avis contraire, je compte changer la dem dans les 8 jours. HB (d) 13 février 2008 à 21:41 (CET)

Proposition de démo

• $ed\equiv 1{\pmod {(p-1)(q-1)}}$ donc $ed=k(p-1)(q-1)+1$
• Une généralisation du petit théorème de Fermat nous donne

$M^{\Phi (n)}\equiv 1{\pmod {n}}$, avec $\Phi (n)$ la fonction indicatrice d'Euler (qui correspond au nombre d'éléments de $\mathbb {Z} /n\mathbb {Z}$)

• Or, $\Phi (n)=(p-1)(q-1)$, d'où

$M^{(p-1)(q-1)}\equiv 1{\pmod {n}}$

• D'où $C^{d}\equiv ({M^{e}})^{d}\equiv M^{ed}\equiv M^{k(p-1)(q-1)+1}\equiv M{\pmod {n}}$

Il y a toujours le même problème :la propriété évoquée demande que M soit premier avec n. le cas où M et n ne sont pas premiers entre eux doit être traitée. c'est pourquoi je préfère la version de Sgsixhuit.HB (d) 13 février 2008 à 21:41 (CET)

Algorithme de Shor

Je n'ai pas le droit de modifier la page donc j'écris ici. L'algorithme de Shor à été introduit en 1994, non en 1996 (voir réference precise sur Algorithme de Shor). Ça pourrait être utile d'écrire explicitement que cet algorithme ne permet pas encore de casser le RSA en pratique vu que il n'y a pas encore d'ordinateur quantique assez puissant.

Titre

Je suis assez étonné du titre de cet article, je ne crois pas que 3 noms propres séparés par des espaces puissent désigner le système de chiffrement : on précise, chiffrement ou algorithme, et probablement il faudrait des tirets. Mais étant donné que l'acronyme est universellement utilisé, il me semble qu'un titre correct serait plutôt chiffrement RSA (ou algorithme RSA). Proz (d) 16 décembre 2012 à 16:00 (CET)

section : "Contrat secret avec la NSA"

cette section nouvellement ajoutée est vraiment hors sujet, elle concerne la société RSA Security, où il y a déjà quelque chose, à voir si ce qu'il y a ici peut permettre d'améliorer. Par ailleurs, le problème étant a priori la méthode choisie pour engendrer les clefs (sujet à mieux traiter ici), il pourrait y avoir 3 mots et/ou une note renvoyant à l'article RSA Security, sur le fait que ça a bien été exploité. Proz (discuter) 21 décembre 2013 à 13:06 (CET)

Comme elle est présentée actuellement (unique sous section de la section sécurité - titre accrocheur genre minute - non contextualisé) je trouve qu'elle arrive comme un cheveu sur la soupe et je partage ton sentiment de rejet. Cependant, il me semble que cette information, reformulée et contextualisée, a sa place dans la section sécurité. Déjà on pourrait supprimer le titre de section, indiquer qu'un problème de sécurité concernant le codage RSA est la génération de clef qui nécessite des algorithmes non maitrisés par l'utilisateur (il faudrait dire cela de manière moins béotienne) et glisser à ce moment le problème de fiabilité soulevé par Reuters. Plus généralement, il me semble que la section sécurité serait à retravailler, (completer, sourcer, éviter les doublons avec la section attaque). HB (discuter) 21 décembre 2013 à 17:39 (CET)

Pour moi c'est une question banale de là ou placer une information, avec la source idoine. Est-on d'accord que c'est de l'histoire du "contrat secret" dont on parle (info. très récente et peut-être à confirmer, au minimum à préciser) dont je persiste à penser qu'elle n'a pas à faire l'objet d'un paragraphe ici (info. très récente et peut-être à confirmer, au minimum à préciser, pas évident du tout qu'il faille y faire même allusion) ? Pour la question de la façon d'engendrer les clefs, il est certain que l'article est très faible (j'avais ajouté quelque chose à ce sujet dans le chapeau de la section "fonctionnement détaillé" il y a quelques temps mais il faudrait développer dans une partie "mise en oeuvre"), et que le problème posé par l'algorithme mis en cause (en disant clairement qu'il n'est pas forcément utilisé, que ce n'est pas le chiffrement lui-même qui est en cause, de façon précise où il intervient, il faut forcément une "vraie" source aléatoire ...) est à aborder. Ce qui a un rapport c'est la possibilité d'une porte dérobée pour cet algo. (une chose connue avant qu'il soit question de "contrat secret"). Proz (discuter) 22 décembre 2013 à 11:55 (CET)

À mon avis cette section pourrait être supprimée : cet article parle de chiffrement RSA en général, pas d'une implémentation particulière qui pourrait être défectueuse. Et la section en question paraît remettre en cause le principe même de l'algorithme RSA, alors qu'il ne s'agit que de son implémentation par la société RSA security (et, comme dit auparavant, ceci est déjà mentionné sur la page de cette entreprise).

Par ailleurs, au début de notre article, il est déjà mentionné que « le couple (clé privée, clé publique) doit être engendré par un procédé vraiment aléatoire qui, même s'il est connu, ne permet pas de reconstituer la clé privée. » Love Sun and Dreams (discuter) 28 décembre 2013 à 19:28 (CET)

Le plus gênant est effectivement que ça peut être mal interprété. Par ailleurs il il y a peut-être quelque chose à dire sur la façon d'engendrer deux nombres premiers (le problème pourrait être qu'ils utilisent la même "graine" aléatoire), c'est peut-être ça qui est en jeu mais je n'en suis pas sûr, il faudrait des sources moins généralistes). Sauf nouvel avis contraire je supprimerai. Proz (discuter) 28 décembre 2013 à 23:30 (CET)

Section supprimée, suivant le consensus en attendant un développement sur la génération de clés. HB (discuter) 29 décembre 2013 à 18:11 (CET)

Fonctionnement détaillé

Parlez aussi du théorème de Carmichael ...--Mbachkat (discuter) 12 mai 2014 à 20:10 (CEST) et de la génération des clés avec le lcm, lambda, cf. pkcs --Mbachkat (discuter) 15 mai 2014 à 00:55 (CEST)

première transaction chiffrée sur Internet

D'après le New York Times, le logiciel PGP reposant sur le chiffrement RSA a été utilisé pour chiffrer la première transaction sur Internet le 11 aout 1994. Si une section historique devait voir le jour dans cet article, je pense que cette info pourrai y avoir sa place. Pamputt ✉ 14 août 2014 à 22:58 (CEST)

Fonctionnement détaillé

Le paragraphe parle de «brèche secrète (ou porte dérobée)». En fait il doit s'agir d'une mauvaise traduction de fonction à trappe. Si quelqu'un capable de modifier peut ajouter ce lien qui remplacerait la référence nécessaire. Merci. Vincent 54000 (discuter) 7 décembre 2022 à 17:30 (CET)

Bien vu. Correction effectuée. Theon (discuter) 8 décembre 2022 à 10:13 (CET)