2
$\begingroup$

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

$\endgroup$
  • 2
    $\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 '17 at 5:31
6
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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