/ crypto

abctf - Sexy RSA

Enoncé:

I recovered some RSA parameters. Can you decrypt the message?

c = 293430917376708381243824815247228063605104303548720758108780880727974339086036691092136736806182713047603694090694712685069524383098129303183298249981051498714383399595430658107400768559066065231114145553134453396428041946588586604081230659780431638898871362957635105901091871385165354213544323931410599944377781013715195511539451275610913318909140275602013631077670399937733517949344579963174235423101450272762052806595645694091546721802246723616268373048438591
n = 1209143407476550975641959824312993703149920344437422193042293131572745298662696284279928622412441255652391493241414170537319784298367821654726781089600780498369402167443363862621886943970468819656731959468058528787895569936536904387979815183897568006750131879851263753496120098205966442010445601534305483783759226510120860633770814540166419495817666312474484061885435295870436055727722073738662516644186716532891328742452198364825809508602208516407566578212780807
e = 65537

Solution:
Ici n est beaucoup trop grand pour être factorisé ...

print len(n)
463

... sauf si p et q ont mal été choisis !
Le titre nous guide vers les nombres premiers sexys. Ces nombres premiers ont la particularité d'être différent de 6.

Nous pouvons donc retrouver p et q grâce à l'équation suivante :

n = p * q = (x - 3)*(x + 3) = x² - 9
donc
p = sqrt(n + 9) - 3 
q = sqrt(n + 9) + 3

On regénère la clé privée :

$ rsatool.py -n <n> -p <p> -q <q> -o key.pem

On écrit c dans un fichier :

import binascii
c = 293430917376708381243824815247228063605104303548720758108780880727974339086036691092136736806182713047603694090694712685069524383098129303183298249981051498714383399595430658107400768559066065231114145553134453396428041946588586604081230659780431638898871362957635105901091871385165354213544323931410599944377781013715195511539451275610913318909140275602013631077670399937733517949344579963174235423101450272762052806595645694091546721802246723616268373048438591
open('cipher','w').write(binascii.unhexlify("%x"%c))

Puis on déchiffre :

$ openssl rsautl -decrypt -in cipher -inkey key.pem -raw
ABCTF{i_h4ve_an_RSA_fetish_;)}