Discussion :

[grandv]

Bonjour à tous...

Je suis bloqué sur un petit problème de cryptanalyse de ElGamal...

Pour casser ElGamal je dois calculer un log discret cad connaissant A, p et n
je cherche y tel que A = (p^y) mod n

Je sais que l'algo de shanks fait ca pas trop mal, mais je n'arrive pas à bien le comprendre (malgrés mes cours et une recherche sur internet)

Un petit coup de pouce ne serait pas de refus.

Merci d'avance.

[jobherzt]

tu parles bien de baby step/giant step ?? qu'est ce que tu ne comprends pas exactement ??? l'idee est assez simple. en reprenant tes notations, l'idee est de poser m=partie entiere (racine(n)) . on sait alors qu'il existe (meme si on ne les connait pas encore) i et j tels que y=i*m+j .

on remarque que, par definition, i et j sont inferieur a racine(n), e qui n'est a priori pas du tout le cas de y. donc l'idee (et c'est une idee qui revient souvent en crypto), c'est : plutot que de chercher directement y ce qui risque d'etre long, on va chercher i et j, ce qui fait 2 nombre a chercher, mais 2 nombre beaucoup plus petits. donc au final on y gagne.

en effet, on a :

p^y=A

et donc

p^(i*m+j)=A

et finalement p^j=A*p^(-im) (*)

et donc au final on va calculer tous les p^j possibles (ca va vite, yen a a peu pres m) et on les mets dans une liste en conservant la valeur de j correspondante. Ensuite on va calculer des A*p^(-im) jusqu'a qu'on retombe sur un element de la liste precedemment caclulée. et donc la, ben on connait i et j qui donnent la relation (*), donc on a gagné.

sache quand meme que c'est quand meme exponentiel comme complexité, et qu'il existe des algorithme sous-exponentiel qui ne sont pas beaucoup plus compliqués.