Posted 3 September 2021 by Michael McKinnon How-Tos

RSA Encryption Key Recovery

A few years back while competing in a hacking competition, I became totally obsessed with one particular RSA key recovery challenge – so much so, that I burned the midnight hours for a couple of days solving it.

As a consequence it turned out I was the only person to complete it!

The experience and the knowledge I gained during this challenge, which forced me to dig into how RSA encryption actually works, left me with more questions than answers, which I’ll explain shortly.

The Challenge

First, let’s start with the crypto challenge itself in which the competitor is provided with only two items:

an encrypted file that contains the flag for the challenge; and
a badly corrupted RSA key that (if recovered) will decrypt the file

Here’s what the key looked like:

Corrupted RSA Key — A corrupted RSA key, can we recover it?

The task is to successfully decrypt the encrypted file but only after somehow repairing or recovering the RSA key.

As you can see from the corrupted key shown, there isn’t much of it left! And the first obvious thing to note is that the first line of question marks is supposed to be:

-----BEGIN RSA PRIVATE KEY-----

Next I needed to work out how long the key was – is it 1024 bit, or 2048 bit, and what else can I tell about the key – what remnants are left?

What follows are the main steps in my approach that helped me solve this challenge, that culminated in some tin-foil-hat speculation along with a Python script that did the job in just a couple of seconds.

Determining the length of the key

Generating keys of various standard lengths helped this process, so I just ran a couple of quick ones, such as:

openssl genrsa 512
openssl genrsa 1024
openssl genrsa 2048

Each one of these commands outputs an RSA private key, and by comparing the lines it was obvious the 1024-bit at 13 lines looked like a match.

What’s in an RSA key exactly?

Next I had to consider, what is inside one of these blobs of random looking text?

Funny how I’ve been dealing with cryptography in business for years, and yet I never really had time to stop and look at what’s in one of these.

First thing to understand is that the format we’re looking at is known technically as PEM which stands for “Privacy Enhanced Mail” – and it’s really nothing more than some data (more on that in a moment) which has been Base64 encoded and has the START and END lines attached.

The RSA key itself in its more native binary format known as DER (Distinguished Encoding Rules) can be extracted like this.

root@localhost:~# openssl rsa -in my1024.key -outform der | xxd
writing RSA key
00000000: 3082 0277 0201 0030 0d06 092a 8648 86f7  0..w...0...*.H..
00000010: 0d01 0101 0500 0482 0261 3082 025d 0201  .........a0..]..
00000020: 0002 8181 00ac 74f9 ba76 ce4e 38e9 ce49  ......t..v.N8..I
00000030: 1102 15fc 5dda c63d 9c28 fb72 2bee 9b6a  ....]..=.(.r+..j
00000040: 7b04 e2eb 4d89 c2e9 580b 36e5 15f9 47e5  {...M...X.6...G.
00000050: 238f ae47 86b5 8eff d188 70c0 4491 b1c7  #..G......p.D...
...

Funnily enough if you just took the Base64 block of text from the PEM format and decoded it directly, you’ll get exactly the same thing as above.

Notice the first two bytes are 0x3082 and this indicates the data is an ASN.1 sequence – there’s some good info from Let’s Encrypt on ASN.1 and DER if you’re interested in the fine detail.

So, other than the binary format of the data, what does it parse out to if we read the key using something that can interpret and decode DER and ASN.1 sequences? We do that like this:

openssl rsa -in some1024.key -noout -text

This will output all the pieces of data inside the key (show with hex removed):

Private-Key: (1024 bit, 2 primes)
modulus:
    <hex data in here>
publicExponent: 65537 (0x10001)
privateExponent:
    <hex data in here>
prime1:
    <hex data in here>
prime2:
    <hex data in here>
exponent1:
    <hex data in here>
exponent2:
    <hex data in here>
coefficient:
    <hex data in here>

Analysing the corrupted key

Armed with a bit more knowledge about how the RSA keys are stored in these formats, I was able to simply take the non-corrupted part of the challenge key and Base64 decode it – which returned a partial DER encoded ASN.1 sequence.

Using a hex editor I was able to determine the only two usable parts to be equivalent to this (a sample here not from the actual challenge)

exponent1:
    71:74:b7:4d:41:30:44:45:80:1d:f3:89:8a:4d:0d:
    cb:54:32:62:28:8d:eb:5e:e1:26:8f:cc:6c:5f:48:
    b5:f4:7d:05:77:48:4f:1e:d5:fc:8a:e8:3e:f3:67:
    a0:61:ba:5d:cd:7d:60:ba:fb:ec:ce:e7:a6:a1:de:
    bf:8f:b9:8d
exponent2:
    00:b5:5c:c1:48:a7:68:25:e4:e5:cb:85:92:d6:de:
    9c:0f:df:db:e8:e4:08:8d:2f:7e:55:27:ad:fa:34:
    53:af:dd:17:ac:7f:28:a4:7b:e5:76:fe:27:45:16:
    00:c9:9a:25:09:25:85:06:ec:94:ac:18:6c:d3:92:
    6a:80:a5:d8:73

What is an “exponent” in an RSA key?

It turns out these values are stored in an RSA key to speed up some of the mathematics operations since RSA uses multiplication of very large numbers – this is based on Chinese Remainder Theorem.

At this point in the challenge I had enough information to start thinking about a solution.

RSA key recovery and my tin-foil-hat

When searching for “RSA key recovery” and associated terms in search engines, I started reading all the documents where RSA, including the original RSA paper and also RFC3447 define the specifications.

The only references you’ll find to “key recovery” in official documentation is in the context of “message recovery” (i.e. protecting the integrity of the encrypted data), and otherwise it will refer to recovering a key from escrow or backup of some kind – but certainly is not what this challenge calls for, which is to somehow reconstruct a key some other way.

Initially it felt like I was on a dead end, until I was a few pages deep into one Google search when I stumbled across this…

“Key Recovery Method for CRT Implementation of RSA“
Paper: https://eprint.iacr.org/2004/147.pdf

What!? CRT – Chinese Remainder Theorem. Yes, this was exactly what I was looking for. I read this entire document. Several times.

Have you ever researched something, only to realise the magnitude of effort that awaits in order to realise whatever goal you’re trying to achieve? That’s how I was feeling, especially when I looked at the source code in the appendix.

Finishing the solution – RSA Key Recovery in Python

It took me a couple of days effort, and what I arrived at was a working Python (albeit Python 2) solution that amazingly is able to reconstruct the RSA key primes (p and q) in just a matter of seconds – all from the CRT exponents.

Behold the solution published here on Github. Enjoy, and stay safe out there.

	#!/usr/bin/python

	# 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: 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 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 = PKCS1_v1_5.new(key)
	# 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:
	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 len(result) == 0 or result == "None":
	# indicates a failed decryption attempt
	sys.stdout.write('x')
	else:
	# 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():
	'''
	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', 'w') 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!
	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__':
	main()