# How to factor an RSA256 public key with YAFU?

(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:

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!

• What you have is Base64-encoded. Decode it to hex, you'll find a familiar ASN.1 formatting indicative of PKCS#1 format. Peel that away and you'll get your value of $n$, in hexadecimal. Now convert that to something your factoring tool can process, such as base 10.
– fgrieu
Apr 19, 2017 at 5:31

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-----
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
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.

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.