modulo

carl159 · 28/07/2006, 03h26

Bonjour,
j'ai : d*517 = k*((p-1)(q-1)) + 1
comment fait-on pour trouver d ?
est-ce qu'il existe plusieurs valeurs de d ?
k est-il une valeur unique ou il y a plusieurs possibilités et quelle est la méthode pour la trouver ?
Merci.

ericcc · 28/07/2006, 10h23

C'est quoi p et q ?
Pour d=1 il y a une solution évidente, de même avec p=q=2 ....

carl159 · 28/07/2006, 14h12

p=29 et q=31

Gwyddon · 28/07/2006, 14h17

Mets sous la forme d*x + k*y = z

(x,y,z connus, k et d inconnus). C'est la forme classique des équations diophantiennes du 1er degré.

Ensuite, cherche le pgcd de x et y ; si z n'est pas divisible par ce dernier, c'est foutu il n'y a pas de solution. Sinon, tu divises, puis tu résouds en utilisant la méthode classique avec l'algo d'Euclide + théorème de Gauss

Pole · 07/08/2006, 17h31

d=1/517 mod (p-1)*(q-1)
On peut utiliser l'algorithme d'Euclide modifié.
lien
Ca sent le RSA....

Pole.

kron · 09/08/2006, 23h06

Exa...

A ce propos, je voulais savoir, y a t-il une méthode simple pour inverser l'exposant public dans Z/nZ*, sans passer par les équations diophantiennes ?

rvz · 10/08/2006, 11h07

Tu serais pas en train de poser la question "Est ce que c'est facile de casser le RSA ?" par hasard.

Si c'est le cas, la réponse est non, car casser le RSA revient à trouver la décomposition en facteur premier de n, et, même si les algorithmes pour faire ça sont très simples théoriquement, ils sont néanmoins très très lourds informatiquement.

__
rvz

kron · 10/08/2006, 11h11

Pas exactement.
Ma question est juste de savoir s'il existe un algorithme rapide permettant, connaissant p,q,n,e de trouver d...
...
...
Oui en fait c'est ça, comment casser RSA en connaissant la factorisation de n...

Théoriquement, le calcul ne demande qu'un temps polynômial, non ? C'est "pas si long"...

rvz · 10/08/2006, 11h20

Ah ok.
Si tu connais tous tes paramètres, pour inverser d dans Z/(p-1)(q-1)Z, comme a dit Pole, on sait le faire, via des algorithmes d'Euclide, reposant essentiellement sur la division euclidienne et la relation de Bezout.

Par contre, pour la factorisation d'un entier, c'est très compliqué. Si tu te donnes un N, la seule manière de aire, c'est de tester par tous les nombres plus petit que, mettons, sa racine. Or la racine de N est bien expontielle en la taille des données ie log(N).

Cela dit, il existe des algorithmes probabilistes qui te disent si un nombre est premier avec une bonne probabilité. Cf test de Miller Rabbin et trucs du même genre : Je me souviens du livre très clair de Michel Demazure à ce sujet, intitulé Cours d'Arithmétique.

__
rvz

kron · 10/08/2006, 16h46

et sans utiliser l'algorithme d'euclide et Bézout ?
Y a t-il une altenative, même utilisant des outils mathématiques plus avancés ?

Pole · 11/08/2006, 09h08

Pourquoi chercher compliqué?
L'algorithme d'Euclide (pour a et b) fait O(log en base phi(minimun de a et b)) étapes.
(phi est le nombre d'or,(1+sqrt(5))/2)~1.618033)
On peut l'améliorer en prenant des restes qui peuvent être négatifs.
La complexité est toujours <= à l'algo d'Euclide, et son maximun est O(log en base 2(minimun de a et b)).
Je pense qu'on peut l'appliquer à l'algo d'Euclide modifié.
Ces algorithmes sont très rapides (par rapport à Rabin-Miller) et peuvent être appliqués rapidement jusqu'à environ 1000 chiffres.

Pour la factorisation, Peter Shor a trouvé un algo polynomial .... mais qui marche que sur des ordis quantiques.
Pour ton ordi, j'ai utilisé dans l'autre fil sur le RSA mon code en java (lien ici), ce qui m'a permis de factoriser ce nombre de 60 chiffres en 1100 secondes à 1.7 GHz. L'algorithme utilisé est le MPQS (Multi Polinomial Quadratic Sieve), pour le crible quadratique c'est trop long.
Je rapelle le record de factorisation pour un nombre du RSA : 200 chiffres.

Pole.