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!