PROJET AUTOBLOG


Tiger-222

Archivé

Site original : Tiger-222

⇐ retour index

Factorisation - P and Q

mardi 9 avril 2013 à 15:28
Le but est de déchiffrer le mot de passe de validation.
Voici la clef utilisée : ch6.zip, ainsi que le texte chiffré :
e8oQDihsmkvjT3sZe+EE8lwNvBEsFegYF6+OOFOiR6gMtMZxxba/bIgLUD8pV3yEf0gOOfHuB5bC3vQmo7bE4PcIKfpFGZBA


Récupérer N et e


$ openssl rsa -in pubkey.pem -pubin -text -modulus
Public-Key: (576 bit)
Modulus:
00:c2:cb:b2:4f:db:f9:23:b6:12:68:e3:f1:1a:38:
96:de:45:74:b3:ba:58:73:0c:bd:65:29:38:86:4e:
22:23:ee:eb:70:4a:17:cf:d0:8d:16:b4:68:91:a6:
14:74:75:99:39:c6:e4:9a:af:e7:f2:59:55:48:c7:
4c:1d:7f:b8:d2:4c:d1:5c:b2:3b:4c:d0:a3
Exponent: 65537 (0x10001)
Modulus=C2CBB24FDBF923B61268E3F11A3896DE4574B3BA58730CBD652938864E2223EEEB704A17CFD08D16B46891A61474759939C6E49AAFE7F2595548C74C1D7FB8D24CD15CB23B4CD0A3
writing RSA key
-----BEGIN PUBLIC KEY-----
MGQwDQYJKoZIhvcNAQEBBQADUwAwUAJJAMLLsk/b+SO2Emjj8Ro4lt5FdLO6WHMMvW
UpOIZOIiPu63BKF8/QjRa0aJGmFHR1mTnG5Jqv5/JZVUjHTB1/uNJM0VyyO0zQowIDAQAB
-----END PUBLIC KEY-----
Conversion héxa => décimale :
$ python -c "print int('valeur_Modulus', 16)"
Nous avons donc :
N =
188198812920607963838697239461650439807163563379417382700763356422988859715234665485319060606504743045317388011303396716199692321205734031879550656996221305168759307650257059
e = 65537


Déterminer les facteurs p et q


Le site factordb permet de les trouver facilement.
http://www.factordb.com/index.php?query=valeur_N
Nous trouvons donc :
p = 398075086424064937397125500550386491199064362342526708406385189575946388957261768583317
q = 472772146107435302536223071973048224632914695302097116459852171130520711256363590397527


Trouver d


Voici le code de rsatool.py.
Dans le code suivant, par soucis de clarté je ne renseigne pas les valeurs de p, q ni N.
$ python rsatool.py -p valeur_p -q valeur_q -n valeur_N -e valeur_e
Using (p, q) to initialise RSA instance
d = 32030e42c69d4e77de7e2397b13dba2e52f2c57a205f5973fed6f87632f53cf8886609ff63fa114e2b5df1db6249f8eaf0bf5fa26ad5b8e48b7fab050d32fc574b446e22d08ba7b1
Conversion héxa => décimale :
$ python -c "print int('valeur_d', 16)"
Enfin, d =
48318251158920145864930035723053089097690375168562443830554407970661009102774592695057202204701378327623682075089028698815133956650193819978456750305738325912711134934968241


Final


La solution finale peut-être trouvée à l'aide du module rsa (pip install rsa) :
import rsa
pk = rsa.PrivateKey(N, e, d, p, q)
import base64
rsa.decrypt(base64.b64decode(ciphertext), pk)
>>> Hop, le mot de passe de validation est "*****".

Sources diverses : infond, m0x39.blogspot et doc python.