Demonstration RSA

[deugeur]

bonjour
je bloque sur un exo maison qui me demande de démontrer en koi le processus de décriptage d'un msg codé en language RSA nous donne bien le msg initial.

voila ou j'en suis.

P et Q 2 grd nombres premiers

n = P * Q

pgcd( e ; (P-1) * (Q-1) ) = 1

et d est telque e*d=1 [(P-1)*(Q-1)]

on note B le msg initial ( pas encore crypté )

et C le msg crypté (telque C=B^e [n] )

pour décrypté C il faut calculé C^d [n] ( n'est-ce pas???)

d'ou B doit etre égale a ( B^e [n] )^d [n]

merci de me donné qque piste de recherche

[Quidam]

, pour un certain K entier.
Ca t'aide ?

[amine801]

validite de rsa
soit P=(e,n) ta cles public et S=(d,n) ta cles prive
f=(q-1)(p-1)
soit M le message qui doit etre crypte


on doit prouve que P(S(M))=S(P(M))=M
ainsi on doit demontrer

-----------------------------------------------------------------
comme e et d sont inverse modulo f alors:
ed=1+k(p-1)(q-1)
pour un certain k si


d'autre part
si donc

de maniere analogue en trouve que

ainsi d'apres le theoreme du reste chinois on peux dire que

[deugeur]

oui j'ai oublié de marqué la relation e*d=1 [(P-1)*(Q-1)]

ce qui nous donne que B^(1+k(P-1)*(Q-1)) [n] doit etre egal a B [n]

en maniant dans tout les sens l'expression je ne vai pas plus lion que


B^(1+k(P-1)*(Q-1)) [n] <=> B*(B^((P-1)*(Q-1)))^k

donc pas trés loin :hum:

[amine801]

j'ai modifie le message

[deugeur]

le theoreme du retse chinoi ???

[amine801]

http://fr.wikipedia.org/wiki/Th%C3%A9or%C3%A8me_des_restes_chinois
si ta pas compris demande moi

[amine801]

moi j'utilise plutot un corolaire
soit
premier entre eu deux a deux si

x et a sont des entiers quelconque alors

si et seulement si

[amine801]

verifie qu'il est present dans ton cours

[deugeur]

je sui dzl mais je comprend pas vous allez devoir me macher tout le travaille lol


comprend pas comment tu sait que:

_" e et d sont inverse modulo f "

et comment t fai toute les etape suivante


d'autre part
si donc

de maniere analogue en trouve que

ainsi d'apres le theoreme du reste chinois on peux dire que

[amine801]

pour e et d inverse modf c'est toi qui l'a ecrit ta juste oublie de noter "mod"

e*d=1 [(P-1)*(Q-1)]

[amine801]

cette partie la

c'est juste l'utilisation du theorem de fermat
ou de euler sa depent de celui que vous avez vu en cours

[deugeur]

merci beaucoup de vaux aides

[switch_df]

Bonjour,
j ai une autre preuvre qui arrive aussi à

mais je n arrive pas à comprendre pourquoi ce résultat permet de conclure qu'on retrouve bien le message original.
Pourriez vous m éclairer?

[switch_df]

personnne ne sait me dire pourquoi ca nous garantit qu'on retrouve bien le même message?
Ca m arrangerai plus que beaucoup de comprendre pourquoi.

Merci

[leon1789]

Bonjour,
j ai une autre preuvre qui arrive aussi à

mais je n arrive pas à comprendre pourquoi ce résultat permet de conclure qu'on retrouve bien le message original.
Pourriez vous m éclairer?

Paul veut transmettre M
Paul envoie le chiffrement
Pierre reçoit et décode
Comme , Pierre voit bien M
:zen:

[switch_df]

Paul veut transmettre M
Paul envoie le chiffrement
Pierre reçoit et décode
Comme , Pierre voit bien M
:zen:

En fait, pour moi cette conclusion marche seulement si M est premier a n. Ce qui n a pas ete mentionné, donc peut etre que je me trompe...

[leon1789]

Ce n'est pas entre M et n que cela se joue.

Pour un premier , une version du théorème de Fermat dit pour tout !

En fait, c'est l'exposant de M qui doit être bien choisi en fonction de n.
Ici (produit de deux premiers distincts) et ...

Le résultat n'est pas évident, mais il est tout a fait abordable avec une bonne référence (que je n'ai pas sous la main). Mais sur le web, on trouve ça. :id:
C'est du théorème chinois.

[leon1789]

Ce n'est pas entre M et n que cela se joue.

Pour un premier , une version du théorème de Fermat dit pour tous et !

En fait, c'est l'exposant de M qui doit être bien choisi en fonction de n.
Ici (produit de deux premiers distincts) et .

Pour prouver l'algo, on peut (je ne sais pas faire autrement d'ailleurs) utiliser le théorème chinois .

[switch_df]

Ok, je vais regarder ca demain (c est une peu tard pour moi).
Mais je crois que le but de la preuve que j ai vue, c est justement de se passer du théorème chinois en distinguant deux cas, M premier avec n et M pas premier avec n (dans ce cas on utilise le lemme de Gauss).
Sur ce, bonne nuit.