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é:
http://icosaweb.ac-reunion.fr/OutilsCalculEnLigne/FormulairesWIMS/Docs/factoriser.htm
N = 783340156742833416191
=>
p = 27789079547
q = 28188776653
p = 27789079547
q = 28188776653
=>
phi = (p-1)*(q-1) = 783340156686855559992
calculer d
utilisons le script python inversemodulo.py
d = e exp -1 mod phi
=>
d = 334688979656405361773
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.phptrouver la clé privée méthode 2
calculer phip = 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
e = 653
phi = 783340156686855559992#!/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
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'
Aucun commentaire:
Enregistrer un commentaire