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: -ssave 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.