We are provided with nothing but a ciphertext, a modulus, and an exponent. This narrows down the possible attacks to ones that do not involve any attacker advantage. Since we only have one message and one public key, GCD cannot be applied to factor the public modulus. Hastad's broadcast attack also could not be performed, and the exponent is also rather large. The size of the exponent in comparison to the modulus also makes it impossible that the message wouldn't wrap the modulus a large number of times if unpadded. The exponent is not overly large, however, suggesting that the d parameter is not small. This makes Wiener's attack unlikely. The size of the modulus makes using general factorization algorithms like GNFS impractical. An attempt to factor the modulus using Fermat's algorithm turns out to succeed: The RSA key provided is generated in a weak fashion, specifically because the primes are too close, leaving it susceptible. FeatherDuster (https://github.com/nccgroup/featherduster) can solve this, but requires RSA keys to be in a standard format, which is not what we are provided:

<span>c = 293430917376708381243824815247228063605104303548720758108780880727974339086036691092136736806182713047603694090694712685069524383098129303183298249981051498714383399595430658107400768559066065231114145553134453396428041946588586604081230659780431638898871362957635105901091871385165354213544323931410599944377781013715195511539451275610913318909140275602013631077670399937733517949344579963174235423101450272762052806595645694091546721802246723616268373048438591
n = 1209143407476550975641959824312993703149920344437422193042293131572745298662696284279928622412441255652391493241414170537319784298367821654726781089600780498369402167443363862621886943970468819656731959468058528787895569936536904387979815183897568006750131879851263753496120098205966442010445601534305483783759226510120860633770814540166419495817666312474484061885435295870436055727722073738662516644186716532891328742452198364825809508602208516407566578212780807
e = 65537

We can use PyCrypto to construct a PEM formatted RSA public key with the n and e values provided like so:

from Crypto.PublicKey import RSA
</span>n = 1209143407476550975641959824312993703149920344437422193042293131572745298662696284279928622412441255652391493241414170537319784298367821654726781089600780498369402167443363862621886943970468819656731959468058528787895569936536904387979815183897568006750131879851263753496120098205966442010445601534305483783759226510120860633770814540166419495817666312474484061885435295870436055727722073738662516644186716532891328742452198364825809508602208516407566578212780807L
e = 65537L
key = RSA.construct((n,e,))
outkey = open('sexyrsa.pub','w')
outkey.write(key.exportKey())
outkey.close()

Then we can run FeatherDuster against it in autopwn mode to solve it quickly:

<span>$ <span>python ~/featherduster/featherduster.py ./sexyrsa.pub 

</span></span>8< ----  8<  --snip-- 8< ---- 8<


FeatherDuster> autopwn
[+] Analyzing samples...
[+] At least one RSA key was discovered among the samples.
Running module: rsa_fermat
Starting factorization...


Modulus factored!
Found private key:
-----BEGIN RSA PRIVATE KEY-----
MIIDfAIBAAKBwQCAbGlBQvlKimWI6NBLDpB/QIpdbveg1aWtSLv7v+N1eiNUvlb6

8< ----  8<  --snip-- 8< ---- 8<

Given the private key, we can decrypt the ciphertext and get the flag.