Discuter:Rivest Shamir Adleman

Un article de Wikipédia, l'encyclopédie libre.

WikiProjet Informatique
 Rivest Shamir Adleman fait partie du projet Informatique, qui a pour but d'enrichir le contenu de Wikipédia sur les sujets liés à l'informatique. Si vous voulez participer, vous pouvez modifier cet article ou visiter la page du projet où vous pourrez vous joindre au projet et consulter la liste des tâches et des objectifs. Le portail informatique pourrait aussi vous intéresser.
B Cet article a été classé comme d'Avancement B selon le Tableau d'évaluation du projet. (Voir les statistiques)
Moyenne Cet article a été classé comme d'Importance moyenne selon le Tableau d'évaluation du projet. (Contester?)

[modifier] 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 10100, ç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)

[modifier] 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 Φ(n) la fonction indicatrice d'Euler (qui correspond au nombre d'éléments de \mathbb{Z}/n\mathbb{Z})

  • Or, Φ(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)