mod

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

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)

Oooooooops!!!

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

Je cherche d, le reste est connu

Merci

@++

Raf

sans trop réfléchir je dirai :

Code:

---

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 ??

Exact, p et q sont premiers...

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

@++

Raf

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

Code:

---

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 ...

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)

Citation:

---

multiplier 2 nbre premier = nbr premier ?

---

ben non puisque c'est le facteur de deux nombres :roll:

:arrow: 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 :wink:

Vive la crypto !