Discussion :

[raf_gug]

Hello!!!

Je sais ce qu'est le mod...

Mais je me retrouve face a ca: e * d mod (p - 1) * (q - 1), je connait e, p et qd et je cherche d.
Comment faire??? (c pr du RSA)

Merci

@++

Raf

[Be!!e F3e G0re]

il n'y aurait pas une faute dans ton algo là ?

et tu connais 'q' ou 'qd' ?

(et utilise la balise Code pour l'algo, merci)

[raf_gug]

Oooooooops!!!

Dsl: e * d mod (p - 1) * (q - 1) = 1

Je cherche d, le reste est connu

Merci

@++

Raf

[Be!!e F3e G0re]

sans trop réfléchir je dirai :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
 
si : e * d mod (p - 1) * (q - 1) = 1 
alors :
e*d = 1 + K * (p - 1) * (q - 1) avec K entier naturel (N*)
 
donc pour trouver d, il suffit que :
(1 + K * (p - 1) * (q - 1)) / e
ait un reste nul !

par contre, ne faut-il pas que d soit premier ??

edit : ah non ça doit être p et q qui doivent être premier ou un truc du genre non ??

[raf_gug]

Exact, p et q sont premiers...

Je vais voir avec, merci pour ta réponse rapide...

@++

Raf

[Be!!e F3e G0re]

pour te mettre sur la voie je ferai bêtement :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
 
unsigned long K, p, q, d, e;
unsigned long optim;
 
p = 3;
q= 5;
d = 0
e = 168;
 
K = 1;
do
{
    optim = (1 + K * (p - 1) * (q - 1));
    d = optim / e;
 
    K++;
}
while((d*e) != optim);

bon faut changer les unsigned long en _u64 (ou chai plus quoi) si les variables sont trop longues ...

[Fry]

pour trouver d dans l algo RSA il y a le theoreme de Bezout:

phi(n)=(p-1)(q-1)
e tel qu aucun facteur commun avec n ( dailleurs n est premier j ai verifier (multiplier 2 nbre premier = nbr premier?) donc il ne peut pas y avoir de facteur commun sauf si e=n ou 1?)

d = e^(-1) mod phi(n)

[scarabee]

multiplier 2 nbre premier = nbr premier ?

ben non puisque c'est le facteur de deux nombres

[kaisse]

d n'est pas premier, il s'agit juste de l'inverse de e modulo (p-1)(q-1), e qui lui est premier avec (p-1)(q-1) , et je crois que par conséquent d aussi. Etre premier avec un autre entier ne veut pas dire etre premier tout court

Vive la crypto !