Recovery of a full RSA PrivateKey from only the CRT exponent1 (dP) and exponent2 (dQ)

rsa_crt_recovery.py

#!/usr/bin/env python3

# Written by: Michael McKinnon @bigmac
# Get in contact with me if you found this useful

import os
import sys
import binascii
import secrets

# This Python script is an implementation of the research here: https://eprint.iacr.org/2004/147.pdf
# my eternal thanks to those authors, this helped me solve a CTF challenge whereby I had to recover an
# RSA private key from just two things:
#
# dP - CRT Exponent 1 (i.e. d mod (p-1))
# dQ - CRT Exponent 2 (i.e. d mod (q-1))
#
# Using just these two elements it IS possible to recover the primes p and q - and then to reconstruct
# the entire RSA private key.
#
# Great site here to experiment with RSA keys:
# http://www.mobilefish.com/services/rsa_key_generation/rsa_key_generation.php

def _is_probable_prime(n, rounds=10):
    if n < 2:
        return False
    # small primes
    small_primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
    for sp in small_primes:
        if n % sp == 0:
            return n == sp
    # write n-1 = 2^s * d
    d = n - 1
    s = 0
    while d % 2 == 0:
        d //= 2
        s += 1
    for _ in range(rounds):
        a = 2 + secrets.randbelow(n - 3)  # in [2, n-2]
        x = pow(a, d, n)
        if x == 1 or x == n - 1:
            continue
        for _ in range(s - 1):
            x = pow(x, 2, n)
            if x == n - 1:
                break
        else:
            return False
    return True


def _pkcs1_v1_5_unpad(em):
    # Expect 0x00 0x02 PS 0x00 M
    if len(em) < 11:
        return b""
    if em[0] != 0x00 or em[1] != 0x02:
        return b""
    # PS must be at least 8 non-zero bytes
    try:
        sep_index = em.index(b"\x00", 2)
    except ValueError:
        return b""
    if sep_index < 10:
        return b""
    return em[sep_index + 1 :]


def rsa_decrypt(p, q, ciphertext, e=65537):
    '''
    I will take your ciphertext and primes p,q (and optionally e) and decrypt
    using a newly constructed RSA private key. Decrypt with assumed PKCS1_v1_5 padding.

    Call it with something like:
    rsa_decrypt(p, q, open('file.enc').read())

    This probably won't work if your ciphertext is bigger than the total bitlength of (p*q)
    so you'd need to play around with aes-cbc etc.
    '''
    # RSA private key components
    n = p * q
    phi = (p - 1) * (q - 1)
    d = pow(e, -1, phi)
    klen = (n.bit_length() + 7) // 8
    # RSA raw decrypt m = c^d mod n
    c = int.from_bytes(ciphertext, 'big')
    if c >= n:
        return b""
    m = pow(c, d, n)
    em = m.to_bytes(klen, 'big')
    # Remove PKCS#1 v1.5 padding
    return _pkcs1_v1_5_unpad(em)

def rsa_recovery(dp, dq, ciphertext, keysize=1024, start=3):
    '''
    This extensive process loops through all unknown e, typically between 3..65537
    and given the dP and dQ will search for primes p and q, then attempt to
    decrypt the ciphertext that is known to have been encrypted with them.
    '''
    # init counters
    r, p, q, d, count, count2, count3 = (0, 0, 0, 0, 0, 0, 0)
    # start generalised loop for an unknown e
    for j in range(start, 65538, 2):
        dp1 = dp * j - 1
        for k in range(3, j):
            d = int(k)
            a, r = divmod(dp1, d)
            assert(dp1 == (k * a) + r)
            if r == 0:
                count += 1
                p = int(a + 1)
                if (p & 1) == 1 and _is_probable_prime(p, 10):
                    count2 += 1
                    dq1 = dq * j - 1
                    for l in range(3, j):
                        d = int(l)
                        a, r = divmod(dq1, d)
                        assert(dq1 == (l * a) + r)
                        if r == 0:
                            q = int(a + 1)
                            if (q & 1) == 1 and _is_probable_prime(q, 10):
                                count3 += 1
                                # just some basic progress on the console
                                if count3 % 10 == 0:
                                    sys.stdout.write('.')
                                    sys.stdout.flush()
                                # only attempt the decrypt if p,q are expected bitlength
                                if p.bit_length() + q.bit_length() == keysize:
                                    try:
                                        result = rsa_decrypt(p, q, ciphertext, j)
                                        if not result:
                                            # indicates a failed decryption attempt
                                            sys.stdout.write('x')
                                        else:
                                            # SUCCESS! This is your decrypted message, sir...
                                            try:
                                                message = result.decode('utf-8')
                                            except Exception:
                                                message = repr(result)
                                            print("\n:: DECRYPTED::\n message = %s" % message)
                                        # show all the p, q candidates just in case
                                        print("\np = %X\nq = %X\n" % (p, q))
                                    except Exception as e:
                                        print("ERROR:", e) # if cipher text length wrong, change decryption padding etc.
                                        pass # do nothing
    # finish with a counter summary
    print("count: %d  count2: %d  count3: %d\n\n" % (count, count2, count3))

def main():
    '''
    Scenario:

    Most of the information of an RSA private key has been lost, but we're able to extract only this:
    (i.e. output from the command: openssl rsa -in helloworld.key -text -noout)

    exponent1:
    69:8a:cf:cb:5a:5d:d4:ca:b7:09:6d:fe:da:94:75:
    c7:80:c1:aa:d4:66:dc:75:35:b6:c7:91:7b:d2:ae:
    6e:11:28:13:98:a0:29:47:8d:35:f8:e0:66:ca:8a:
    9f:59:a7:48:97:78:21:00:bb:4c:f6:06:76:68:81:
    5c:3f:00:81

    exponent2:
    00:94:79:94:5a:b5:4e:5c:d4:fa:c5:80:b6:75:01:
    03:0e:e3:3a:e1:6d:bb:05:9e:8a:1a:78:30:d4:88:
    d2:fa:1a:7e:3e:90:98:07:cb:d1:12:0a:b8:05:a1:
    b9:09:15:bd:d3:c8:76:ca:74:c1:32:ef:ae:05:6b:
    55:ad:3d:fb:61

    '''
    # these exponents above are below as dP and dQ
    sample_dp = 0x698acfcb5a5dd4cab7096dfeda9475c780c1aad466dc7535b6c7917bd2ae6e11281398a029478d35f8e066ca8a9f59a74897782100bb4cf6067668815c3f0081
    sample_dq = 0x009479945ab54e5cd4fac580b67501030ee33ae16dbb059e8a1a7830d488d2fa1a7e3e909807cbd1120ab805a1b90915bdd3c876ca74c132efae056b55ad3dfb61
    # this is an already encrypted file made, using
    # openssl rsautl -encrypt -in helloworld.txt -inkey helloworld.pub -pubin -out helloworld.enc
    sample_ciphertext = '9bccead296e0f33405ca8ee167ff366a95ac8cb667cfe2c7c5fcd10c2'\
                        '78962777f3583138fad52db987a4f7f6a10e8798330151a816bc32a20'\
                        'b4d9c82f512027cd4c817cbf3399bde736935ebf7404308eb7419fcc3'\
                        'b7ace7841e8f8a28cd8c5e7c5b90e6b0a32a03ff4e5392b044caf851a'\
                        '0fccc615da166c68495d8f1b7a7e'
    sample_filename = 'helloworld.enc'
    # write the sample encrypted file to disk
    if not os.path.isfile(sample_filename):
        with open('helloworld.enc', 'wb') as f:
            f.write(binascii.unhexlify(sample_ciphertext))
    # read the file in, for whatever reason I had much better luck always reading the file in!
    with open('helloworld.enc', 'rb') as fh:
        ciphertext = fh.read()
    # Here is where the magic happens...
    rsa_recovery(sample_dp, sample_dq, ciphertext, keysize=1024, start=65537)
    # IMPORTANT: If you have a publicExponent (e) that is not assumed to be 0x10001 (65537)
    # you will probably want to change start to start=3 above. 3, 17, 65537 are the most common 'e' used.

if __name__ == '__main__':
    main()