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

  • 3
    $\begingroup$ 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. $\endgroup$
    – fgrieu
    Apr 19, 2017 at 5:31

2 Answers 2


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-----
    -----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"""
        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"""
        g, x, y = egcd(e, m) 
        if g != 1:
            return None
            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.

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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.