Zenk - Security

Enoncé :

Afin d'établir une communication sécurisée, Alice et Bob procèdent à un échange de clef Diffie-Hellman. Pour cela ils utilisent le nombre premier p:

p=79293686916250308867562846577205340336400039290615139607865873515636529820700152685808430350565795397930362488139681935988728405965018046160143856932183271822052154707966219579166490625165957544852172686883789422725879425460374250873493847078682057057098206096021890926255094441718327491846721928463078710174998090939469826268390010887

Et l'entier g:

g=73114111352295288774462814798129374078459933691513097211327217058892903294045760490674069858786617415857709128629468431860886481058309114786300536376329001946020422132220459480052973446624920516819751293995944131953830388015948998083956038870701901293308432733590605162069671909743966331031815478333541613484527212362582446507824584241

Alice choisit en secret un nombre x, calcule X=gx mod p et envoie X sur un canal non sécurisé à Bob. De même, Bob choisit en secret un nombre y, calcule Y=gy mod p, et envoie Y à Alice, toujours sur le même canal. Tout deux peuvent ensuite calculer la valeur Z=Xy=Yx=gxy mod p.

En espionnant le canal, Charlie récupère la valeur de X et de Y:

X=53710695204323513509337733909021562547350740845028323195225592059762435955297110591848019878050853425581981564064692996024279718640577281681757923541806197728862534268310235863990001242041406600195234734872865710114622767319497082014412908147635982838670976889326329911714511434374891326542317244606912177994106645736126820796903212224

Y=17548462742338155551984429588008385864428920973169847389730563268852776421819130212521059041463390276608317951678117988955994615505741640680466539914477079796678963391138192241654905635203691784507184457129586853997459084075350611422541722123509121359133932497700621300814065254996649070135358792927275914472632707420292830992294921992

La clef de cette épreuve est le md5sum de la valeur de Z.

Solution :

Il s'agit d'un simple logarithme discret à résoudre, i.e. trouver x tel que X=g^x mod p.

Il est possible d'utiliser l'outil magma pour le résoudre (http://magma.maths.usyd.edu.au/calc/)

p:=79293686916250308867562846577205340336400039290615139607865873515636529820700152685808430350565795397930362488139681935988728405965018046160143856932183271822052154707966219579166490625165957544852172686883789422725879425460374250873493847078682057057098206096021890926255094441718327491846721928463078710174998090939469826268390010887;
g:=73114111352295288774462814798129374078459933691513097211327217058892903294045760490674069858786617415857709128629468431860886481058309114786300536376329001946020422132220459480052973446624920516819751293995944131953830388015948998083956038870701901293308432733590605162069671909743966331031815478333541613484527212362582446507824584241;
X:=53710695204323513509337733909021562547350740845028323195225592059762435955297110591848019878050853425581981564064692996024279718640577281681757923541806197728862534268310235863990001242041406600195234734872865710114622767319497082014412908147635982838670976889326329911714511434374891326542317244606912177994106645736126820796903212224;

Log(GF(p)!g, GF(p)!X);

Le résultat tombe alors :

5987017916693979800961865907625956492746942018842897309081319033525436025200275\
9467705768337098285569957371223987423277240609978767607029041030497475585357789\
74508050668215058880480572837679469513461940184995866029170866715848982

Il suffit alors de calculer Y^x mod p, en quelques ligne de python :

>>> p=79293686916250308867562846577205340336400039290615139607865873515636529820700152685808430350565795397930362488139681935988728405965018046160143856932183271822052154707966219579166490625165957544852172686883789422725879425460374250873493847078682057057098206096021890926255094441718327491846721928463078710174998090939469826268390010887
>>> Y=17548462742338155551984429588008385864428920973169847389730563268852776421819130212521059041463390276608317951678117988955994615505741640680466539914477079796678963391138192241654905635203691784507184457129586853997459084075350611422541722123509121359133932497700621300814065254996649070135358792927275914472632707420292830992294921992
>>> x=5987017916693979800961865907625956492746942018842897309081319033525436025200275946770576833709828556995737122398742327724060997876760702904103049747558535778974508050668215058880480572837679469513461940184995866029170866715848982
>>> pow(Y,x,p)
13209953273847904538937959330024620309948373964029285268129438495125916049103104947558307756205640430956011327318451971143649388976770482679169393296835669455452165748588628944673299856366435979160842244913860009798074516378816385040186737956522363508690793823200979322371545890826154011044304502071323934414763375923268294720810314905L

Puis le md5 :

$ echo 13209953273847904538937959330024620309948373964029285268129438495125916049103104947558307756205640430956011327318451971143649388976770482679169393296835669455452165748588628944673299856366435979160842244913860009798074516378816385040186737956522363508690793823200979322371545890826154011044304502071323934414763375923268294720810314905 | md5sum
e4b7e1d7768b7ca4002671754e061919