Cracking 256-bit RSA Keys – Surprisingly Simple!

As it’s been making the rounds recently, I wanted to try my hand at cracking 256-bit RSA keys.

Cracking 256-bit RSA – Introduction

If you haven’t seen the video yet, Crown Sterling cracked a 256-bit RSA key in front of a live audience in 50 seconds.

I wasn’t sure how impressive this was originally, and I wanted to try it out myself.

For more information about RSA, and the math behind it, you can always check out the Wikipedia article.

Additionally, for another example of the math behind RSA, and cracking it, I recommend the following post.

All of that said, I’m no cryptographer, so this was more an attempt to see how easy it was for me to crack these keys. I’m in no way making any claims about anyone else’s research, or whether something is invalid or fake. This is also a fitting example of verifying claims yourself where possible though!

Private Key Generation

First, I generated a 256-bit RSA private key using OpenSSL

root@kali:~/rsa256# openssl genrsa -out private.pem 256
Generating RSA private key, 256 bit long modulus
...+++++++++++++++++++++++++++
............+++++++++++++++++++++++++++
e is 65537 (0x10001)

Next, I printed the actual private key, as well as the modulus (n)

root@kali:~/rsa256# openssl rsa -in private.pem -modulus
Modulus=B19D0C77A45D2A8FD9B9EEE42BEBE6CE0F0AF88B5FF529982D2D52257412A507
writing RSA key
-----BEGIN RSA PRIVATE KEY-----
MIGpAgEAAiEAsZ0Md6RdKo/Zue7kK+vmzg8K+Itf9SmYLS1SJXQSpQcCAwEAAQIg
OYL194O0W0TLJoaxQXuYd1SIY0QN+97UIyDMjgZAOXkCEQDbKDy09Z3qWI1cn+C+
ls5NAhEAz3jqOoDgWeu/Q/3DmGtyowIQZQolCu0elDelXOndDSGsFQIQO2ErAKWE
EJhlfIszoPsXqwIQZ7estf3MM1uuXDAvw6Hvsw==
-----END RSA PRIVATE KEY-----

I also generated the public key, as this is what I would be attacking.

root@kali:~/rsa256# openssl rsa -in private.pem -outform PEM -pubout -out public.pem
writing RSA key

As you can see, the exponent and modulus are the same for the public key and the private key.

root@kali:~/rsa256# openssl rsa -pubin -in public.pem -text -noout
Public-Key: (256 bit)
Modulus:
    00:b1:9d:0c:77:a4:5d:2a:8f:d9:b9:ee:e4:2b:eb:
    e6:ce:0f:0a:f8:8b:5f:f5:29:98:2d:2d:52:25:74:
    12:a5:07
Exponent: 65537 (0x10001)

root@kali:~/rsa256# openssl rsa -pubin -in public.pem -modulus -noout
Modulus=B19D0C77A45D2A8FD9B9EEE42BEBE6CE0F0AF88B5FF529982D2D52257412A507

Finally, I converted the modulus from hex to an integer using ‘bc’, as this is the input I will use for cracking it.

root@kali:~/rsa256# echo "ibase=16;B19D0C77A45D2A8FD9B9EEE42BEBE6CE0F0AF88B5FF529982D2D52257412A507" | bc
80336855234907714168477675917972994189398342031083238074132216291031\
761724679

Cracking the Key

First, to crack the key, I created a 16 CPU DigitalOcean droplet.

I verified the processors by checking cpuinfo after the machine booted.

root@ubuntu-c-16-nyc3-01:~/rsa256# cat /proc/cpuinfo | grep "model name"
model name	: Intel(R) Xeon(R) Platinum 8168 CPU @ 2.70GHz
model name	: Intel(R) Xeon(R) Platinum 8168 CPU @ 2.70GHz
model name	: Intel(R) Xeon(R) Platinum 8168 CPU @ 2.70GHz
model name	: Intel(R) Xeon(R) Platinum 8168 CPU @ 2.70GHz
model name	: Intel(R) Xeon(R) Platinum 8168 CPU @ 2.70GHz
model name	: Intel(R) Xeon(R) Platinum 8168 CPU @ 2.70GHz
model name	: Intel(R) Xeon(R) Platinum 8168 CPU @ 2.70GHz
model name	: Intel(R) Xeon(R) Platinum 8168 CPU @ 2.70GHz
model name	: Intel(R) Xeon(R) Platinum 8168 CPU @ 2.70GHz
model name	: Intel(R) Xeon(R) Platinum 8168 CPU @ 2.70GHz
model name	: Intel(R) Xeon(R) Platinum 8168 CPU @ 2.70GHz
model name	: Intel(R) Xeon(R) Platinum 8168 CPU @ 2.70GHz
model name	: Intel(R) Xeon(R) Platinum 8168 CPU @ 2.70GHz
model name	: Intel(R) Xeon(R) Platinum 8168 CPU @ 2.70GHz
model name	: Intel(R) Xeon(R) Platinum 8168 CPU @ 2.70GHz
model name	: Intel(R) Xeon(R) Platinum 8168 CPU @ 2.70GHz

With the machine up and running, I installed make, cmake, and g++ to compile any tools that I might use.

Next, I found a tool that implemented a Number Field Sieve called msieve.

First, I cloned the GitHub repository.

root@ubuntu-c-16-nyc3-01:~/rsa256# git clone https://github.com/radii/msieve
Cloning into 'msieve'...
remote: Enumerating objects: 1504, done.
remote: Total 1504 (delta 0), reused 0 (delta 0), pack-reused 1504
Receiving objects: 100% (1504/1504), 634.68 KiB | 15.87 MiB/s, done.
Resolving deltas: 100% (1132/1132), done.

Next, I had to edit the makefile, so that the architecture matched the CPUs that I was using (Skylake).

root@ubuntu-c-16-nyc3-01:~/rsa256/msieve# cat Makefile | grep "march"
# gcc with basic optimization (-march flag could
OPT_FLAGS = -O3 -fomit-frame-pointer -march=skylake -DNDEBUG
#OPT_FLAGS = -O3 -fomit-frame-pointer -march=k8 -DNDEBUG
	$(CC) $(CFLAGS) -march=pentium2 -DBLOCK_KB=64 -DCPU_PENTIUM2 \
	$(CC) $(CFLAGS) -march=pentium3 -DBLOCK_KB=64 -DCPU_PENTIUM3 \
	$(CC) $(CFLAGS) -march=pentium4 -DBLOCK_KB=64 -DCPU_PENTIUM4 \
	$(CC) $(CFLAGS) -march=pentium-m -DBLOCK_KB=32 -DCPU_PENTIUM_M \
	$(CC) $(CFLAGS) -march=prescott -DBLOCK_KB=32 -DCPU_CORE \
	$(CC) $(CFLAGS) -march=athlon -DBLOCK_KB=64 -DCPU_ATHLON \
	$(CC) $(CFLAGS) -march=athlon-xp -DBLOCK_KB=64 -DCPU_ATHLON_XP \
	$(CC) $(CFLAGS) -march=k8 -DBLOCK_KB=64 -DCPU_OPTERON \
	$(CC) $(CFLAGS) -march=nocona -DBLOCK_KB=64 -DCPU_PENTIUM4 \
	$(CC) $(CFLAGS) -march=nocona -DBLOCK_KB=32 -DCPU_CORE \
	$(CC) $(CFLAGS) -march=k8 -DBLOCK_KB=64 -DCPU_OPTERON \
root@ubuntu-c-16-nyc3-01:~/rsa256/msieve# make x86_64
gcc -D_FILE_OFFSET_BITS=64 -O3 -fomit-frame-pointer -march=skylake -DNDEBUG  -Wall -W -I. -Iinclude -Ignfs -Ignfs/poly -Ignfs/poly/stage1 -c -o common/filter/clique.o common/filter/clique.c

After that change, I was able to successfully compile the application and view the help.

root@ubuntu-c-16-nyc3-01:~/rsa256/msieve# ./msieve --help

Msieve v. 1.46

usage: ./msieve [options] [one_number]

numbers starting with '0' are treated as octal,
numbers starting with '0x' are treated as hexadecimal

options:
   -s  save intermediate results to 
             instead of the default msieve.dat
   -l  append log information to 
             instead of the default msieve.log
   -i  read one or more integers to factor from
              (default worktodo.ini) instead of
             from the command line
   -m        manual mode: enter numbers via standard input
   -mb  hint for number of megabytes of memory for
             postprocessing (set automatically if unspec-
             ified or zero)
   -q        quiet: do not generate any log information,
             only print any factors found
   -d   deadline: if still sieving after 
             minutes, shut down gracefully (default off)
   -r   stop sieving after finding  relations
   -p        run at idle priority
   -v        verbose: write log information to screen
             as well as to logfile
   -t   use at most  threads

 elliptic curve options:
   -e        perform 'deep' ECM, seek factors > 15 digits

 quadratic sieve options:
   -c        client: only perform sieving

 number field sieve options:
   -n        use the number field sieve (80+ digits only;
             performs all NFS tasks in order)
   -nf  read from / write to NFS factor base file
              instead of the default msieve.fb
   -np [X,Y] perform only NFS polynomial selection; if
             specified, only cover leading coefficients
             in the range from X to Y inclusive
   -np1 [X,Y] perform stage 1 of NFS polynomial selection; if
             specified, only cover leading coefficients
             in the range from X to Y inclusive
   -np2      perform stage 2 of NFS polynomial selection
   -ns [X,Y] perform only NFS sieving; if specified,
             handle sieve lines X to Y inclusive
   -nc       perform only NFS combining (all phases)
   -nc1 [X,Y] perform only NFS filtering. Filtering will
             track ideals >= X (determined automatically
             if 0 or unspecified) and will only use the 
             first Y relations (or all relations, if 0 
             or unspecified)
   -nc2      perform only NFS linear algebra
   -ncr      perform only NFS linear algebra, restarting
             from a previous checkpoint
   -nc3 [X,Y] perform only NFS square root (compute 
             dependency numbers X through Y, 1<=X<=Y<=64)

With msieve running, I timed it using the q and n flags, as that seemed basic and straightforward.

root@ubuntu-c-16-nyc3-01:~/rsa256/msieve# time ./msieve -q -n 80336855234907714168477675917972994189398342031083238074132216291031761724679

80336855234907714168477675917972994189398342031083238074132216291031761724679
prp39: 275778021469467750604832321873164071587
prp39: 291309854232898176366046870573797527117


real	2m44.099s
user	2m43.996s
sys	0m0.092s

While two minutes and forty-four seconds wasn't bad from a random program, I was hoping that I could do it faster!

Cracking 256-bit RSA Keys - Docker Images

I decided to try a few Docker images, to see if any of them could give me a lower time.

First, I installed Docker to my droplet.

Next, I found an image titled rsacrack, which sounded perfect

I pulled down the image to my droplet.

root@ubuntu-c-16-nyc3-01:~# docker pull b4den/rsacrack
Using default tag: latest
latest: Pulling from b4den/rsacrack
5667fdb72017: Pull complete 
d83811f270d5: Pull complete 
ee671aafb583: Pull complete 
7fc152dfb3a6: Pull complete 
b83d8b6245c4: Pull complete 
36cb8498468a: Pull complete 
22aaf58c64c7: Pull complete 
fb0d231b82e1: Pull complete 
fc922e878061: Pull complete 
84cf9426007f: Pull complete 
897258e3faf3: Pull complete 
6dc87ced1f13: Pull complete 
71db44ed3509: Pull complete 
b266cfc4f7eb: Pull complete 
e62159d0a47e: Pull complete 
8fc467efa1ec: Pull complete 
d4b519fd0423: Pull complete 
da3c0b30b580: Extracting [==================================================>]  3.126kB/3.126kB
365f1efd6c17: Download complete 
fa0aa39ead30: Download complete 
97567ded379a: Download complete 
ca8390f60942: Download complete 
54e964f3a0f6: Download complete 
878a41964830: Download complete 
85beee49cceb: Download complete 

Once I finally figured out how the image worked, I was able to run and time it. Also, it gave me a bit more information about the cracked prime, as well as generating a new private key for me.

(after a few attempts, I was able to time it and run it)

root@ubuntu-c-16-nyc3-01:~# time docker run b4den/rsacrack 80336855234907714168477675917972994189398342031083238074132216291031761724679
[*] pubkey.e: 65537
[*] pubkey.n: 80336855234907714168477675917972994189398342031083238074132216291031761724679
[*] Key looks like 256 bits
[*] Using cadonfs to compute primes
[*] results are: [u'275778021469467750604832321873164071587', u'291309854232898176366046870573797527117', 65537L]
[*] Key extraction done.
-----BEGIN RSA PRIVATE KEY-----
MIGqAgEAAiEAsZ0Md6RdKo/Zue7kK+vmzg8K+Itf9SmYLS1SJXQSpQcCAwEAAQIgOYL194O0W0TL
JoaxQXuYd1SIY0QN+97UIyDMjgZAOXkCEQDPeOo6gOBZ679D/cOYa3KjAhEA2yg8tPWd6liNXJ/g
vpbOTQIRAMPjbcGJUbxD1IK6JAci8ZcCECHcFgi4g6NUoxoNBUMvszICEG1I5uI3mwxY9rfO3XxE
Hcs=
-----END RSA PRIVATE KEY-----


real	1m13.985s
user	0m0.038s
sys	0m0.025s

As you can see, it only took one minute and fourteen seconds this time, which was a huge improvement!

Note that the RSA private key is a bit different from the one I generated earlier, even though the modulus is the same.

I also wanted to try cado-nfs, for no particular reason. That said, I was unable to get the boost libraries to properly work on my Ubuntu droplet.

I was able to find a cado-nfs Docker image, so that seemed like the next best choice.

First, I pulled down the image.

root@ubuntu-c-16-nyc3-01:~# docker pull cyrilbouvier/cado-nfs.py
Using default tag: latest
latest: Pulling from cyrilbouvier/cado-nfs.py

...

docker.io/cyrilbouvier/cado-nfs.py:latest

When running this image, a lot seemed to be going on, but it eventually printed the same primes as everything else.

root@ubuntu-c-16-nyc3-01:~# time docker run cyrilbouvier/cado-nfs.py 80336855234907714168477675917972994189398342031083238074132216291031761724679
Info:root: Using default parameter file /cado-nfs/share/cado-nfs-2.2.1/factor/params.c75
Info:root: No database exists yet
Info:root: Created temporary directory /tmp/cado.33dpijhe
Info:Database: Opened connection to database /tmp/cado.33dpijhe/c75.db
Info:root: Set tasks.threads=16 based on detected physical cpus
Info:root: tasks.polyselect.threads = 2
Info:root: tasks.sieve.las.threads = 2
Info:root: slaves.scriptpath is /cado-nfs/bin
Info:root: Command line parameters: /cado-nfs/bin/cado-nfs.py 80336855234907714168477675917972994189398342031083238074132216291031761724679
Info:root: If this computation gets interrupted, it can be resumed with /cado-nfs/bin/cado-nfs.py /tmp/cado.33dpijhe/c75.parameters_snapshot.0

...

Info:Linear Algebra: Total cpu/real time for bwc: 16.08/0.000250816
Info:Linear Algebra: Aggregate statistics:
Info:Linear Algebra: Krylov: WCT time 2.07
Info:Linear Algebra: Lingen CPU time 4.26, WCT time 0.51
Info:Linear Algebra: Mksol: WCT time 1.62
Info:Quadratic Characters: Total cpu/real time for characters: 0.81/0.234679
Info:Square Root: Total cpu/real time for sqrt: 28.48/2.57451
Info:HTTP server: Shutting down HTTP server
Info:Complete Factorization: Total cpu/elapsed time for entire factorization: 324.42/70.4059
Info:root: Cleaning up computation data in /tmp/cado.33dpijhe
275778021469467750604832321873164071587 291309854232898176366046870573797527117

real	1m11.840s
user	0m0.040s
sys	0m0.095s

As you can see, this brought the time down even further, and in the realm of under one minute!

In the end, I only needed this droplet for around 20 minutes, so it only cost me ~$0.16 to crack my key.

Verifying the Crack

While all these applications had the same output, I wanted to verify that I was actually successful.

First, I used Python to calculate the original modulus from my derived factors.

root@kali:~/rsa256# python -c 'print (275778021469467750604832321873164071587*291309854232898176366046870573797527117)'
80336855234907714168477675917972994189398342031083238074132216291031761724679

Next, I encrypted a secret message with my public key. Note that the message needs to be shorter than the original key, so I only had 32 bytes.

root@kali:~/rsa256# cat plaintext.txt 
Secret message!
root@kali:~/rsa256# openssl rsautl -encrypt -pubin -inkey public.pem -in plaintext.txt -out encrypted.txt
root@kali:~/rsa256# cat encrypted.txt 
??=79eUn?B????????Y?x??c???

I saved the output of the rsacrack Docker image as my cracked private key.

root@kali:~/rsa256# cat cracked.pem 
-----BEGIN RSA PRIVATE KEY-----
MIGqAgEAAiEAsZ0Md6RdKo/Zue7kK+vmzg8K+Itf9SmYLS1SJXQSpQcCAwEAAQIgOYL194O0W0TL
JoaxQXuYd1SIY0QN+97UIyDMjgZAOXkCEQDPeOo6gOBZ679D/cOYa3KjAhEA2yg8tPWd6liNXJ/g
vpbOTQIRAMPjbcGJUbxD1IK6JAci8ZcCECHcFgi4g6NUoxoNBUMvszICEG1I5uI3mwxY9rfO3XxE
Hcs=
-----END RSA PRIVATE KEY-----

Using this private key, I was still able to decrypt the message, even though it was different than my original private key!

root@kali:~/rsa256# openssl rsautl -decrypt -inkey cracked.pem -in encrypted.txt -out decrypted.txt
root@kali:~/rsa256# cat decrypted.txt 
Secret message!

Private Key Generation

While I was able to decrypt my secret message using the cracked private key, I was unsure how this key was generated.

In this case, I found a StackOverflow post on how to generate an RSA key using specific input numbers.

First, I created a small Python script (that I'll share below) to create a configuration file for asn1parse.

root@kali:~/rsa256# python genKey.py 
asn1=SEQUENCE:rsa_key

[rsa_key]
version=INTEGER:0
modulus=INTEGER:80336855234907714168477675917972994189398342031083238074132216291031761724679
pubExp=INTEGER:65537
privExp=INTEGER:26013220088499269151307883495663593232543266314163563907943768170179715938681
p=INTEGER:275778021469467750604832321873164071587
q=INTEGER:291309854232898176366046870573797527117
e1=INTEGER:78928976741425555000913069889908578219
e2=INTEGER:134304701857683726732992144809608195093
coeff=INTEGER:145264379791353023195410394043851742667
root@kali:~/rsa256# python genKey.py > gen.conf

Using this configuration file, I generated another private key using these values.

root@kali:~/rsa256# openssl asn1parse -genconf gen.conf -out newkey.der
    0:d=0  hl=3 l= 169 cons: SEQUENCE          
    3:d=1  hl=2 l=   1 prim: INTEGER           :00
    6:d=1  hl=2 l=  33 prim: INTEGER           :B19D0C77A45D2A8FD9B9EEE42BEBE6CE0F0AF88B5FF529982D2D52257412A507
   41:d=1  hl=2 l=   3 prim: INTEGER           :010001
   46:d=1  hl=2 l=  32 prim: INTEGER           :3982F5F783B45B44CB2686B1417B9877548863440DFBDED42320CC8E06403979
   80:d=1  hl=2 l=  17 prim: INTEGER           :CF78EA3A80E059EBBF43FDC3986B72A3
   99:d=1  hl=2 l=  17 prim: INTEGER           :DB283CB4F59DEA588D5C9FE0BE96CE4D
  118:d=1  hl=2 l=  16 prim: INTEGER           :3B612B00A5841098657C8B33A0FB17AB
  136:d=1  hl=2 l=  16 prim: INTEGER           :650A250AED1E9437A55CE9DD0D21AC15
  154:d=1  hl=2 l=  16 prim: INTEGER           :6D48E6E2379B0C58F6B7CEDD7C441DCB
root@kali:~/rsa256# openssl rsa -in newkey.der -inform der -text -check
Private-Key: (256 bit)
modulus:
    00:b1:9d:0c:77:a4:5d:2a:8f:d9:b9:ee:e4:2b:eb:
    e6:ce:0f:0a:f8:8b:5f:f5:29:98:2d:2d:52:25:74:
    12:a5:07
publicExponent: 65537 (0x10001)
privateExponent:
    39:82:f5:f7:83:b4:5b:44:cb:26:86:b1:41:7b:98:
    77:54:88:63:44:0d:fb:de:d4:23:20:cc:8e:06:40:
    39:79
prime1:
    00:cf:78:ea:3a:80:e0:59:eb:bf:43:fd:c3:98:6b:
    72:a3
prime2:
    00:db:28:3c:b4:f5:9d:ea:58:8d:5c:9f:e0:be:96:
    ce:4d
exponent1:
    3b:61:2b:00:a5:84:10:98:65:7c:8b:33:a0:fb:17:
    ab
exponent2:
    65:0a:25:0a:ed:1e:94:37:a5:5c:e9:dd:0d:21:ac:
    15
coefficient:
    6d:48:e6:e2:37:9b:0c:58:f6:b7:ce:dd:7c:44:1d:
    cb
RSA key ok
writing RSA key
-----BEGIN RSA PRIVATE KEY-----
MIGpAgEAAiEAsZ0Md6RdKo/Zue7kK+vmzg8K+Itf9SmYLS1SJXQSpQcCAwEAAQIg
OYL194O0W0TLJoaxQXuYd1SIY0QN+97UIyDMjgZAOXkCEQDPeOo6gOBZ679D/cOY
a3KjAhEA2yg8tPWd6liNXJ/gvpbOTQIQO2ErAKWEEJhlfIszoPsXqwIQZQolCu0e
lDelXOndDSGsFQIQbUjm4jebDFj2t87dfEQdyw==
-----END RSA PRIVATE KEY-----

While this private key is different from either of my two earlier ones, at least I know that I generated it myself.

Using this generated RSA key, I was still able to decrypt my secret message!

root@kali:~/rsa256# openssl rsautl -decrypt -inkey generated.pem -in encrypted.txt -out decrypted-gen.txt
root@kali:~/rsa256# cat decrypted-gen.txt 
Secret message!

Genkey Code

You can find the code for my genkey.py script below. For more information on RSA cracking, as well as where I got the egcd and modinv methods from, then you should check out this post

#!/usr/bin/python

def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = egcd(b % a, a)
        return (g, x - (b // a) * y, y)

def modinv(a, m):
    gcd, x, y = egcd(a, m)
    if gcd != 1:
        return None  # modular inverse does not exist
    else:
        return x % m

def main():
    p = 275778021469467750604832321873164071587  # edit with factor #1
    q = 291309854232898176366046870573797527117  # edit with factor #2
    n = 80336855234907714168477675917972994189398342031083238074132216291031761724679  # edit with modulus
    e = 65537  # edit if exponent is different

    phi = (p -1)*(q-1)
    d = modinv(e,phi)
    dp = modinv(e,(p-1))
    dq = modinv(e,(q-1))
    qi = modinv(q,p)

    print "asn1=SEQUENCE:rsa_key"
    print ""
    print "[rsa_key]"
    print "version=INTEGER:0"
    print "modulus=INTEGER:" + str(n)
    print "pubExp=INTEGER:" + str(e)
    print "privExp=INTEGER:" + str(d)
    print "p=INTEGER:" + str(p)
    print "q=INTEGER:" + str(q)
    print "e1=INTEGER:" + str(dp)
    print "e2=INTEGER:" + str(dq)
    print "coeff=INTEGER:" + str(qi)

if __name__ == "__main__":
    main()

As usual, you can find the code and updates in my GitHub repository as well.

Cracking 256-bit RSA - Conclusion

This was a fun exercise, and it was much faster than I expected to do the cracking.

I could see a CTF using this as a challenge in the future, so it helps to know how to perform this attack.

Finally, for some more examples of cracking and math, check out Rob's Twitter thread.