Skip to content

Instantly share code, notes, and snippets.

Last active January 8, 2022 16:02
What would you like to do?
Recovery of a full RSA PrivateKey from only the CRT exponent1 (dP) and exponent2 (dQ)
# Written by: Michael McKinnon @bigmac
# Get in contact with me if you found this useful
import os
import sys
import gmpy2
from Crypto.PublicKey import RSA
from Crypto.Cipher import PKCS1_v1_5
# This Python script is an implementation of the research here:
# 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:
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.
def rsa_keyfromprimes(p, q, e):
# we have e from the param - this is the publicExponent
# calculate n (modulus) is the product of p and q
n = long(gmpy2.mul(p, q))
# we need phi(n)
phi = (p - 1)*(q - 1)
# calculate d (the privateExponent)
d = long(gmpy2.invert(e,(p-1)*(q-1)))
#make the key
key = RSA.construct((n, long(e), d, p, q))
# Oh, while we're here have a new private key if you want
#print key.exportKey()
return key
# get the key
key = rsa_keyfromprimes(p, q, e)
# get a PKCS cipher object for padding
cipher =
# decrypt the ciphertext
decrypted = cipher.decrypt(ciphertext, None)
return str(decrypted)
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 = (0L, 0L, 0L, 0L, 0, 0, 0)
# start generalised loop for an unknown e
for j in range(start, 65538, 2):
dp1 = long(gmpy2.mul(dp, j) - 1)
for k in range(3, j):
d = long(k)
a, r = gmpy2.t_divmod(dp1, d)
assert(dp1 == (k * a) + r)
if r == 0:
count += 1
p = long(a + 1)
if gmpy2.is_odd(p) and gmpy2.is_strong_prp(p, 10):
count2 += 1
dq1 = long(gmpy2.mul(dq, j) - 1)
for l in range(3, j):
d = long(l)
a, r = gmpy2.t_divmod(dq1, d)
assert(dq1 == (l * a) + r)
if r == 0:
q = long(a + 1)
if gmpy2.is_odd(q) and gmpy2.is_strong_prp(q, 10):
count3 += 1
# just some basic progress on the console
if count3 % 10 == 0:
# only attempt the decrypt if p,q are expected bitlength
if p.bit_length() + q.bit_length() == keysize:
result = rsa_decrypt(p, q, ciphertext, j)
if len(result) == 0 or result == "None":
# indicates a failed decryption attempt
# SUCCESS! This is your decrypted message, sir...
print "\n:: DECRYPTED::\n message = %s" % result
# 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():
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)
# 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 -pubin -out helloworld.enc
sample_ciphertext = '9bccead296e0f33405ca8ee167ff366a95ac8cb667cfe2c7c5fcd10c2'\
sample_filename = 'helloworld.enc'
# write the sample encrypted file to disk
if not os.path.isfile(sample_filename):
with open('helloworld.enc', 'w') as f:
# read the file in, for whatever reason I had much better luck always reading the file in!
ciphertext = open('helloworld.enc').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__':
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment