Zenk - Security

Enoncé :

Alice a envoyé un message chiffré à Bob en utilisant le système de chiffrement RSA. Pour cela, elle a d'abord transformé son message clair, une chaîne de caractères, en un entier de la façon suivante. À chaque lettre minuscule de l'alphabet latin ont fait correspondre un nombre entier de 1 à 26 (a=1, b=2, …,z=26). Au caractère espace on fait correspondre 0.

Puis, à la chaîne de caractères m0 m1… ml-1 (avec 0 ≤ mi ≤ 26), on fait correspondre l'entier: m= ∑ i=0 l-1 m i 27 i

Une fois cet entier m obtenu, Alice utilise la clef publique (n,e) de Bob pour calculer c=me mod n. L'entier c envoyé par Alice est:

c=97313723999427158707313571074505809044734576227366074775197337179596924131890323110047188776214753462110672927375882648122238543395136397500411230385539389860460250957019288356953382932530827442895828951533573302647648238521279077394005914829458808700551912957892108347414768602246507965856863930813172801853

L'exposant e était e=216+1. Le modulus n était un produit de deux nombres premiers distincts de 512 bits. Ce nombre n est l'un des 100 nombres contenus dans le fichier moduli.txt.

Retrouvez le message en clair envoyé par Alice, puis prenez son md5sum et vous obtiendrez la clef de cette épreuve.

Solution :

L'ensemble des clés fournies est un indice permettant de trouver la clé ayant permis le chiffrement, ainsi que sa factorisation.

La solution consiste à prendre les clés deux à deux et à leur chercher un pgcd. Si le pgcd n'est pas 1, alors on a trouvé un facteur commun aux deux clés.

for i in xrange(len(keyz)):
 for j in xrange(i+1, len(keyz)):
  if pgcd(keyz[i], keyz[j]) != 1:
   print keyz[i], keyz[j]

On ne trouve alors que deux clés qui ont un facteur commun. L'une d'entre elles étant plus petite que le message chiffré, c'est donc l'autre clé qui est la bonne :

k= 98781552300009170955990131617391919700813256922533758490281507977083725235957148538022358994194052134326247721771842345487221802392547735585733563803410632307523319827594203688761160518601578877229961402217765066929662773736629684840067633380034685254354143619946552567835663589537732419849836562797839430341
(p,q)=(10688126999474359596196619069014191561535191916249832616087079047459405891115441022155537490938057789282711387720380745142168406323396226117898496201521417, 9242176136648379285957208109854487701302868820662560573339760743928086063237334334575652783354189982127965454897980966564441967960002811618933947596375773)

On peut alors déchiffrer le message c à l'aide de cette clé. On obtient alors :

10540770684526967966093382710075805468141070858169415651810630380174340770246021727067583765431180874899250445144638738337404794150723458480860561439297517737688964450316682015249018027473687369915652803183031287133702697724323753608006727813279402709158058295560840704634721560132500082401545099357309700

Il suffit alors de décomposer ce nombre en polynome de la forme mi*27^i.

rem=10540770684526967966093382710075805468141070858169415651810630380174340770246021727067583765431180874899250445144638738337404794150723458480860561439297517737688964450316682015249018027473687369915652803183031287133702697724323753608006727813279402709158058295560840704634721560132500082401545099357309700
out=""
for k in xrange(212,-1,-1):
 blah=27**k
 val=int(rem/blah)
 rem = rem - val*blah
 if val==0:
  out+=" "
 else:
  out+=chr(0x60+val)
print out[::-1]

On obtient le message :

que j aime a faire apprendre un nombre utile aux sages immortel archimede artiste ingenieur qui de ton jugement peut priser la valeur pour moi ton probleme eut de pareils avantages jadis mysterieux un probleme etc

Puis le flag :

$ echo 'que j aime a faire apprendre un nombre utile aux sages immortel archimede artiste ingenieur qui de ton jugement peut priser la valeur pour moi ton probleme eut de pareils avantages jadis mysterieux un probleme etc' | md5sum
=> d6dc1c23415c6765becebe17bbcc688a