[w3challs] RSA

Cet article décrit une méthode pour résoudre une cryptanalyse RSA. Il est basé sur le challenge RSA de w3challs
Il fait suite à mon premier article sur le sujet http://www.infond.fr/2010/10/quelques-outils-pour-rsa.html

énoncé:

déchiffrer
025452037205229131300
128922268479958795704
507343151027440334004
313628318349495303097
740609869255617681333
743928343077804788556
405219023562734491540
211783513258751189510
649941440719152320279
106298250239853604423
N=783340156742833416191
e=653

factoriser N

http://icosaweb.ac-reunion.fr/OutilsCalculEnLigne/FormulairesWIMS/Docs/factoriser.htm
N = 783340156742833416191
=>
p = 27789079547
q = 28188776653

trouver la clé privée méthode 1

http://www.mobilefish.com/services/rsa_key_generation/rsa_key_generation.php

trouver la clé privée méthode 2

calculer phi
p = 27789079547
q = 28188776653
=>
phi = (p-1)*(q-1) = 783340156686855559992

calculer d
utilisons le script python inversemodulo.py

http://www.infond.fr/2010/10/quelques-outils-pour-rsa.html

#!/usr/bin/python
# -*- coding: utf-8 -*-
# usage:
# pour calculer l'inverse de 11 modulo 63:
# $ python inversemodulo.py 11 63
from sys import argv
def bezout(a, b):
''' Calcule (u, v, p) tels que a*u + b*v = p et p = pgcd(a, b) '''
if a == 0 and b == 0: return (0, 0, 0)
if b == 0: return (a/abs(a), 0, abs(a))
(u, v, p) = bezout(b, a%b)
return (v, (u - v*(a/b)), p)
def inv_modulo(x, m):
''' Calcule y dans [[0, m-1]] tel que x*y % abs(m) = 1 '''
(u, _, p) = bezout(x, m)
if p == 1: return u%abs(m)
else: raise Exception("%s et %s ne sont pas premiers entre eux" % (x, m))
if __name__ == "__main__":
try :
x, m = int(argv[1]), int(argv[2])
print "L'inverse de %s modulo %s est : %s" % (x,m,inv_modulo(x,m))
except Exception, m:
print m
print "Merci de choisir un autre couple de valeurs"

e = 653

phi = 783340156686855559992
d = e exp -1 mod phi
=>
d = 334688979656405361773

déchiffrer

Nous appliquons la fonction pow() en python qui permet de faire une exponentiation modulaire. Puis nous récupérons la sortie codée en décimal, la transformons en hexadécimal et enfin en chaîne unicode.

#!/usr/bin/python
# -*- coding: utf-8 -*-

# pow(c,d,n)  = c ** d mod n

from binascii import unhexlify

cipher = [25452037205229131300,\
128922268479958795704,\
507343151027440334004,\
313628318349495303097,\
740609869255617681333,\
743928343077804788556,\
405219023562734491540,\
211783513258751189510,\
649941440719152320279,\
106298250239853604423]
d = 334688979656405361773
n = 783340156742833416191
out = ''
for c in cipher:
out += hex(pow(c,d,n))[2:-1] #  '6565' -> '0x4141L'  -> '4141'
print unhexlify(out) # '4141' -> 'AA'