How to factor an RSA256 public key with YAFU?

Question

(Layman's terms please, I'm just a kid stuck on a puzzle)

I'm trying to factor the following RSA256 public key to find the corresponding private key:

MDwwDQYJKoZIhvcNAQEBBQADKwAwKAIhAIl47p5SrV3uMTsUAbwE0E+j+QynAY/CVq/Gf8IAOQy7AgMBAAE=

I got as far as downloading a YAFU factorization program found here, which I was told is capable of factoring such a key in 103 seconds on a core i7. This program works great for factoring base 10 numbers, but I have no idea how to use it on a RSA key. Any help would be hugely appreciated. Thanks!

Answer 1

There are various ways of doing this. Let's assume you're using Python.

1. Start by installing PyCrypto. This includes a lot of useful tools.

2. You need to convert the raw base64 string into a readable RSA key file. This is easily done:

   -----BEGIN PUBLIC KEY-----
   MDwwDQYJKoZIhvcNAQEBBQADKwAwKAIhAIl47p5SrV3uMTsUAbwE0E+j+QynAY/C
   Vq/Gf8IAOQy7AgMBAAE=
   -----END PUBLIC KEY-----
   

   Save this to a file called, for example, rsa256.pub.

3. Import this key into Python and extract the values of $n$ and $e$:

   from Crypto.PublicKey import RSA
   key = RSA.importKey(open('rsa256.pub').read())
   print key.n, key.e
   

4. Now factorize $n$. YAFU sounds perfect for the job. (I use msieve, which also works well.) On a decent computer, it should only take a few minutes to break a 256-bit modulus. This will give you two factors. Call the larger one $p$ and the smaller one $q$.

5. Back in Python, you need to run a bit of code to calculate the decryption exponent $d$. You should then have sufficient information to generate a private key:

   def egcd(a, b):
       """Extended Euclidean algorithm"""
       """https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm"""
       x,y,u,v = 0,1,1,0
       while a != 0:
           q, r = b // a, b % a
           m, n = x - u * q, y - v * q
           b,a,x,y,u,v = a,r,u,v,m,n
       return b, x, y
   
   def modinv(e, m):
       """Modular multiplicative inverse"""
       """https://en.wikipedia.org/wiki/Modular_multiplicative_inverse"""
       g, x, y = egcd(e, m) 
       if g != 1:
           return None
       else:
           return x % m
   
   def pqe2rsa(p, q, e):
       """Generate an RSA private key from p, q and e"""
       from Crypto.PublicKey import RSA
       n = p * q
       phi = (p - 1) * (q - 1)
       d = modinv(e, phi)
       key_params = (long(n), long(e), long(d), long(p), long(q))
       priv_key = RSA.construct(key_params)
       print priv_key.exportKey()
   

   Call pqe2rsa() with the values of $p$ and $q$ from step 4 and the value of $e$ from step 3, and you should get a private key.

Answer 2

Use RsaCtfTool: https://github.com/Ganapati/RsaCtfTool, to force the "Yafu" method, add the "--attack siqs" option. You have to perform step 2 from the previous answer.

Here is the command:

root@hi# ./RsaCtfTool.py --publickey publicKey.txt --private --verbose  --attack siqs
[*] Performing siqs attack.
[*] Yafu SIQS is working.
-----BEGIN RSA PRIVATE KEY-----
MIGpAgEAAiEAiXjunlKtXe4xOxQBvATQT6P5DKcBj8JWr8Z/wgA5DLsCAwEAAQIg
XKM8kT3/i9OOI1SJEq1fvbzsNjcenxVV2DomCFqurfkCEQCotpt39ZPKiigNzX11
fZWXAhEA0JiXjN4SueEBtRnULKVOfQIQOPeX3VSVt7EYvzhgoXhrNwIQeXiiqDGa
DgxthhyoZedNsQIQZyCqQN+b8IBG4W5ZMCjxTw==
-----END RSA PRIVATE KEY-----

Time elapsed (from the log file):

12/24/19 11:10:09 v1.34.5 @ hi, prp39 = 260436577402156008758227210148551506407
12/24/19 11:10:09 v1.34.5 @ hi, prp39 = 294877806852892942790124409850407821443
12/24/19 11:10:09 v1.34.5 @ hi, Lanczos elapsed time = 1.8100 seconds.
12/24/19 11:10:09 v1.34.5 @ hi, Sqrt elapsed time = 0.0200 seconds.
12/24/19 11:10:09 v1.34.5 @ hi, SIQS elapsed time = 2.0205 seconds.