rsa

RSA Encryption Toolbox - Experimental Utilities For Deriving Private Keys From Public Keys

Baden Delamore

Sep 24, 2019 • 4 min read

TLDR: I've created a toolbox that will allow you to break RSA 128 & 256bit keys in less than five minutes with minimal hardware (2 vCPU's, 2048MB memory). Grab yourself a copy here.

Over the last couple of weeks there's been quite a bit of chatter around breaking RSA encryption. As a newcomer to the world of cryptography I wanted to explore how this actually works in practice. The fruits of this work rely on projects such as cado-nfs and various cryptography libraries. The toolbox is merely the amalgamation of the NFS algorithm, key construction methods and other utilities developed to derive private keys from public keys.

Rationale

I wanted to create a simple to use toolbox that:

Allows anyone to generate keypairs of negligible length from any operating system, and without the programming experience requirement
Takes a public key with small key sizes (although larger keys are supported too)
Extracts the modulus supporting three input types (modulus int, base64 public key values, and public key strings)
Extracts the exponent e
Factors primes p and q using either cado-nfs for larger key lengths or factordb for lengths <= 128 bits
Reconstructs the private key from p, q and e for ease-of-use
Prints the private key value to stdout for immediate use

Given cryptographers are notorious for their hard-to-compile code, I decided to package the toolbox up into a simple docker image. The source code is freely available on Github. This means that anyone, regardless of their operating system of choice, can make use of this toolbox.

Using the toolbox

Pull the docker image

docker pull b4den/rsacrack

Generating RSA private key

openssl genrsa -out private_key.pem 256

Extract public key from private key

openssl rsa -in private_key.pem -pubout > public_key.pub

Cracking a 128-bit key using rsacrack

docker run -it b4den/rsacrack "$(cat public_key_128.pub)"

Cracking a >=256-bit key using rsacrack

docker run -it b4den/rsacrack "$(cat public_key_256.pub)"

Now simply save the key output from the command above to a text file. To check your computed primes, exponents and modulus you can run: openssl rsa -inform PEM -text -noout < recovered.pem.

Experimental results so far

Key lengths of 128bits or small are computed in less than three seconds using a lookup table
Key lengths of 256bits are computed in under 5 minutes
Key lengths >= 512bits - not tested

Verification

You may verify that private keys extracted using the methods employed by the rsacrack image are in fact correct by doing the following:

Generate an encrypted message using your private key

echo -n "Soon to be encrypted" | openssl rsautl -encrypt -inkey private_key.pem > message.encrypted

So you've got your message encrypted with your private key. Now let's use the toolbox to derive the value of that private key, by simply passing it your public key string or modulus. Assuming the key length is 256bits, you could run docker run -it b4den/rsacrack "$(cat public_key_256.pub)"

Dealing with private key output

Copy the output from our docker image. This should look like the following:

[*] results are: ['<snip>', '<snip>', <snip>]
[*] Key extraction done.
-----BEGIN RSA PRIVATE KEY-----
<snip>
-----END RSA PRIVATE KEY-----

Copy everything from ----BEGIN RSA PRIVATE KEY---- up to and including ----END RSA PRIVATE KEY---- and save that to a text file. Let's call it recovered.pem.

Decryption with recovered key

cat message.encrypted | openssl rsautl -decrypt -inkey recovered.pem

Running the above should now print the decrypted message using the recovered.pem key our toolbox computed! Pretty cool, huh.

Additional notes

For keys sizes of <= 128bits we make use of factordb's lookup tables. For larger key sizes we rely solely on the cado-nfs library.

Input specification

The application takes one and only one argument. From there the modulus, exponent and eventually primes are deduced from that key.

Valid inputs

public key strings docker run -it b4den/rsacrack "$(cat public_key.pem)"
public key value docker run -it b4den/rsacrack "base64encoded-pubkey"
public key modulus docker run -it b4den/rsacrack modulusint

Openssl version

Some newer versions of openssl won't let you generate rsa keys of 128/256 bit sizes. As a workaround the image comes pre-compiled with openssl 1.0.0: docker run --entrypoint openssl -it b4den/rsacrack genrsa 256

For Macbook's they come with LibreSSL so you should be able to use your builtin openssl library for key generation using small key lengths.

Conclusion

The idea of passing in a public key string or modulus and having the toolbox output the private key in the appropriate format was an enjoyable learning experience. And while small keys are super easy to compute with today's hardware and factorization algorithms, quantum computing aside, we can rest assured that RSA is not "broken" as some might say, particularly when using industry standard key lengths of 2048 and greater. I would be happy to be proven otherwise - enjoy cracking!