Bonjour tout le monde !
Bon, voilà le problème :
j'ai un message à decrypter, je possède la clé publique, et aussi le modulus et sa factorisation en deux premiers.
Il me manque la clé de décryptage que j'essaye de calculer par l'algorithme d'euclide :
et il en résulte que ma clé de décryptage est négative... Et le message décodé avec cette clé est incompréhensible.
C'est un devoir. Donc j'ai essayé avec les clés des autres étudiants. Des fois je trouve une clé positive et aucun problème, je décode. Et des fois, une clé négative et là, tout merdouille.
Voici l'algo d'euclide avec m=p*q et je cherche d tel que e*d=1mod((p-1)*(q-1))
Code :
- int q;
- int r;
- int r1=17921; //clé publique
- int r2=114552856; //(p-1)*(q-1)
- int s;
- int s1=0;
- int s2=1;
- int t;
- int t1=1;
- int t2=0;
- while(r!=0){
- q=r2/r1;
- r=r2-q*r1;
- s=s2-q*s1;
- t=t2-q*t1;
- r2=r1;
- r1=r;
- s2=s1;
- s1=s;
- t2=t1;
- t1=t;
- printf("t2=%d et r=%d\n",t2,r);
- }
|
Apres, je teste si l'algo marche bien :
Code :
- int res=s2*114552856+t2*17921;
- printf("%d\n",res);
|
J'obtiens res=1 donc l'algorithme marche. Et de plus, il marche pour certaines clé...
Bref, perdu je suis.
Alors, une clé de décryptage négative, est-ce complétement aberrant ?
J'ai essayé avec Mathematica, et je trouve le même resultat. Donc je ne pense pas avoir d'overflow. J'ai essayé avec des long au lieu des int, même chose...
Merci de vos réponses
