OVH Cloud OVH Cloud

Précision à propos de RSA (Delphi) ?

5 réponses
Avatar
Paul Sean
Bonjour,

J'ai un petit problème à comprendre ce code, je voudrais implenter RSA dans
mon soft, ce que je comprend pas , c'est comment est calculer E dans ce
code, il est toujours pareil (même en changeant les valeurs p et q), j'ai
l'impression que c'est E = Exponent, car je ne peux pas lui attribuer un
chiffer au hasard, merci de votre aide.

Source du code ici : http://triade.studentenweb.org/

// Enter a random number to generate a prime, i.e.
// incremental search starting from that number
Base10StringToFGInt('123456789123', p);
PrimeSearch(p);
Base256StringToFGInt('123456789123', q);
PrimeSearch(q);

// Compute the modulus
FGIntMul(p, q, n);
// Compute p-1, q-1 by adjusting the last digit of the GInt
p.Number[1] := p.Number[1] - 1;
q.Number[1] := q.Number[1] - 1;
// Compute phi(n)
FGIntMul(p, q, phi);
// Choose a public exponent e such that GCD(e,phi)=1
// common values are 3, 65537 but if these aren 't coprime
// to phi, use the following code
Base10StringToFGInt('65537', e); // just an odd starting point

Base10StringToFGInt('1', one);
Base10StringToFGInt('2', two);
FGIntGCD(phi, e, gcd);
While FGIntCompareAbs(gcd, one) <> Eq Do
Begin
FGIntadd(e, two, temp);
FGIntCopy(temp, e);
FGIntGCD(phi, e, gcd);
End;
FGIntDestroy(two);
FGIntDestroy(one);
FGIntDestroy(gcd);
// Compute the modular (multiplicative) inverse of e, i.e. the secret
exponent (key)
FGIntModInv(e, phi, d);
FGIntModInv(e, p, dp);
FGIntModInv(e, q, dq);
p.Number[1] := p.Number[1] + 1;
q.Number[1] := q.Number[1] + 1;

FGIntDestroy(phi);
FGIntDestroy(nilgint);

// Now everything is set up to start Encrypting/Decrypting,
Signing/Verifying
test := 'ABCD12345678 ';

RSAEncrypt(test, e, n, test);

//Memo1.Lines.Add(Base64Encode(test));
RSADecrypt(test, d, n, Nilgint, Nilgint, Nilgint, Nilgint, test);
// this Is faster : RSADecrypt(test, nilGInt, n, dp, dq, p, q, test);

// RSASign(test, d, n, Nilgint, Nilgint, Nilgint, Nilgint, signature);
// this Is faster : RSASign(test, nilgint, n, dp, dq, p, q, signature);
// RSAVerify(test, signature, e, n, ok);

FGIntDestroy(p);
FGIntDestroy(q);
FGIntDestroy(dp);
FGIntDestroy(dq);
FGIntDestroy(e);
FGIntDestroy(d);
FGIntDestroy(n);

5 réponses

Avatar
Jean-Marc Desperrier
Paul Sean wrote:
[...] ce que je comprend pas , c'est comment est calculer E dans ce
code,


Lire le code ...

// Choose a public exponent e such that GCD(e,phi)=1
// common values are 3, 65537 but if these aren 't coprime
// to phi, use the following code
Base10StringToFGInt('65537', e); // just an odd starting point

Donc, le code commence par un exposant e qui vaut 65537.

FGIntGCD(phi, e, gcd);
While FGIntCompareAbs(gcd, one) <> Eq Do
Begin
FGIntadd(e, two, temp);
FGIntCopy(temp, e);
FGIntGCD(phi, e, gcd);
End;

Et ensuite tant que le plus grand denominateur commun entre phi et e est
supérieur à 1, il augmente e pour passer au nombre impair suivant
jusqu'à trouver un e qui marche.

En fait, il n'y qu'une chance sur 65537 essais qu'on ait besoin
d'utiliser autre chose que 65537 pour la valeur de e.
Donc, effectivement tu as obtenu à chaque fois 65537.

Avatar
Paul Sean
Merci pour le détails, je pensais que E pouvais avoir n'importe quelle
valeur, c pour ca

Merci Jean Marc ! :)

"Jean-Marc Desperrier" a écrit dans le message de
news:bn6j8h$hgh$
Paul Sean wrote:
[...] ce que je comprend pas , c'est comment est calculer E dans ce
code,


Lire le code ...

// Choose a public exponent e such that GCD(e,phi)=1
// common values are 3, 65537 but if these aren 't coprime
// to phi, use the following code
Base10StringToFGInt('65537', e); // just an odd starting point

Donc, le code commence par un exposant e qui vaut 65537.

FGIntGCD(phi, e, gcd);
While FGIntCompareAbs(gcd, one) <> Eq Do
Begin
FGIntadd(e, two, temp);
FGIntCopy(temp, e);
FGIntGCD(phi, e, gcd);
End;

Et ensuite tant que le plus grand denominateur commun entre phi et e est
supérieur à 1, il augmente e pour passer au nombre impair suivant
jusqu'à trouver un e qui marche.

En fait, il n'y qu'une chance sur 65537 essais qu'on ait besoin
d'utiliser autre chose que 65537 pour la valeur de e.
Donc, effectivement tu as obtenu à chaque fois 65537.




Avatar
Jean-Marc Desperrier
Paul Sean wrote:
Merci pour le détails, je pensais que E pouvais avoir n'importe quelle
valeur, c pour ca


Moi aussi en fait, je pensais que la seule condition était que e soit
premier. J'ai multiplié mes connaissance sur RSA. :-)

Mais si e est premier, PGCD(e,phi)=1 <=> phi n'est pas multiple de e.

Je pense que les gens qui utilisent un e fixe, doivent préférer changer
de q ou de p, plutôt que changer de e quand e n'est pas bon.
En fait, j'en viens à demander comment font les gens qui utilisent e=3,
car ils doivent être obligé alors de jeter un paquet de nombres premiers.

En fait, comme si p-1 *ou* q-1 est multiple de e, phi n'est pas bon,
pour e=3, 4 chances sur 9 d'être bon du premier coup, 4 chances sur 9 de
devoir changer soit p soit q, 1 chance sur 9 de devoir changer les deux.

Pour ee537, le vrai chiffre était à peu de chose près deux chances sur
65537 que le premier essai ne soit pas bon, et non pas une.

Avatar
Johann Dantant
"Jean-Marc Desperrier" a écrit dans le message de
news:bn8452$nng$

Je pense que les gens qui utilisent un e fixe, doivent préférer changer
de q ou de p, plutôt que changer de e quand e n'est pas bon.
En fait, j'en viens à demander comment font les gens qui utilisent e=3,
car ils doivent être obligé alors de jeter un paquet de nombres premiers.


Oui, absolument, les systèmes (embarqués le plus souvent ?) avec un e fixe
et faible (3 ou même 2) imposent des contraintes supplémentaires sur p et q,
d'où un tirage un peu plus long.

Avatar
Erwan David
Jean-Marc Desperrier écrivait :

Paul Sean wrote:
Merci pour le détails, je pensais que E pouvais avoir n'importe quelle
valeur, c pour ca


Moi aussi en fait, je pensais que la seule condition était que e soit
premier. J'ai multiplié mes connaissance sur RSA. :-)

Mais si e est premier, PGCD(e,phi)=1 <=> phi n'est pas multiple de e.

Je pense que les gens qui utilisent un e fixe, doivent préférer
changer de q ou de p, plutôt que changer de e quand e n'est pas bon.
En fait, j'en viens à demander comment font les gens qui utilisent
e=3, car ils doivent être obligé alors de jeter un paquet de nombres
premiers.

En fait, comme si p-1 *ou* q-1 est multiple de e, phi n'est pas bon,
pour e=3, 4 chances sur 9 d'être bon du premier coup, 4 chances sur 9
de devoir changer soit p soit q, 1 chance sur 9 de devoir changer les
deux.

Pour ee537, le vrai chiffre était à peu de chose près deux chances
sur 65537 que le premier essai ne soit pas bon, et non pas une.


Il faut voir aussi que le calcul est plus efficace si e a peu de bits
à 1.