Prime Factorization
With your program now working hard to factor large numbers, let's put it to the test! I am providing code which can encrypt and decrypt using RSA encryption (as briefly discussed in class). For each challenge, you are provided the public key (encryption key e), modulus (n - the result of multiplying two large prime numbers p and q), and some encrypted text. I can decrypt the messages because I have my generated private key (d for decryption key)! However, if you can figure out the prime factors which were used to obtain n (i.e., p and q) then you know that d * e = (p-1)(q-1)+1 (in other words you can compute d and see what the original text was)!
You have the following tools at your disposal: an encrypt executable which was used to encrypt files (and source code), and the decrypt executable which you can use to decrypt files (and source code). These executables were compiled and tested on the campus linux machines (physical machines) in 213 (specifically rc08ucs213.managed.mst.edu). If you want compile from scratch (for whatever reason), you will need the cryptopp libraries compiled in a subdirectory from where you are attempting to compile (see this sample Makefile to get an idea how to do that).
You should be able to do a simple test with ciphertextSample. It has n, e, d, p, and q for a 4096 bit RSA key (bigger than you could crack). Execute your decrypt executable with the ciphertextSample and it will generate ciphertextSample.decrypted (and should tell you something in English like you couldn't crack this on your own). Once you get the setup working, start with some simple ciphertext where you do NOT have all the data given to you. Use the given n to factor p and q and then use the formula to generate d ( here is a handy Excel spreadsheet if you need help calculating).
The challenge will progressively unlock harder and harder encrypted text. Everyone can start with cracking ciphertext1. The output of this text is the key to the next level. When you get the output text character(s), use that to unlock the next piece of the puzzle & harder ciphertext by visiting web.mst.edu/~mrghx4/UNLOCK_CHARACTER(S)/ ...
---------------------------------------------------------------------------
Have a nice day!