modulo

[invite06fa2eb2]

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]

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

[invite06fa2eb2]

p=29 et q=31

[Gwyddon]

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

[A voir en vidéo sur Futura]

[invite3d7be5ae]

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

Pole.

[invite4b9cdbca]

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 ?

[invite6b1e2c2e]

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

[invite4b9cdbca]

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

[invite6b1e2c2e]

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

[invite4b9cdbca]

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 ?

[invite3d7be5ae]

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.