Introduction. In this assignment we will use the GNU multi-precision arithmetic library to implement the well- known public-key encryption algorithm known as Rivest-Shamir-Adelman (RSA). Our program will choose appropriate public/private key pairs, choose random messages, encrypt the random message with the public key, decrypt the random messagse with the private key, and verify that the decrypted message matches the original messages.
Choosing the RSA public/private key pair. To select the public key (n, d) and private key (n, e), do the following.
2.Selecttworandomprimenumberspandqofsizeszbits. (Notewewillvaryszasdescribedbelow). The gmprandclassobjecthasamethodcalledgetzbitswhichreturnsarandomvalueofthespecifiedsize.The GNUmulti-precisionlibraryhasafunctionmpzprobabprimeptodetermineifagivennumberis“likely” tobeprime.Forthisassignment,use100iterationsoftheprimalitytestingalgorithm(thesecondparameteron thempzprobabprimepfunction).
3. Compute n = p ∗ q.
4. Compute φ(n) = (p − 1) ∗ (q − 1)
5. Choose a random d of size sz * 2 and with d < φ(n). Note that d does not have to be prime.
6.Insure thatthegreatestcommondivisorofdandφ(n)isexactly1.Ifnot,chooseanotherd.TheGMPlibrary hasafunctionmpzgcdtocomputethegreatestcommondivisor.
7.Finally,computeeasthemultiplicativeinverseofdmoduloφ(n). UsetheGMPfunctionmpzinvertfor this.
At this point the pair (n, d) is the public key, and (n, e) is the private key (although this is arbitrary, we could use
(n, d) as the private key and (n, e) as the public).
PerformingtheEncryptionandDecryption. Givenakey(eitherpublicorprivate)(n,d),andaplaintextmessage m,theRSAencryptionalgorithmissimple. Justcomputetheciphertextmessagecasc=md mod n. The GMP function mpz powm does this for us.
Specific program details.
1. Start with sz as 32 bits, and double the size for each iteration up to and including 1024 bits. Recall that sz is the size of p and q, and n is p ∗ q, so n has twice as many bits.
2. For each value of sz, compute 100 different public/private key pairs as described above.
3. For each public/private key pair compute 100 random messages of size less than n bits. Again, you can use the
4. For each random message, compute the ciphertext (using the RSA algorithm), and then decrypt the ciphertext message (again using the RSA algorithm) and verify the decrypted message is identical to the original plaintext message.
6. IMPORTANT. Feel free to add as much debug code (with screen prints) as you need to get the program debugged. However, the grading script will fail if extra prints are left in the submitted program.
7. Grad Students Only. Attempt to “break” the RSA algorithm for the 64 bit n values using a factoring algorithm of your choice. For this a skeleton BreakRSA.cc will be provided.
Copying the Project Skeletons
1. Log into deepthought19.cc using ssh and your prism log-in name.
2. Copy the files from the ECE6122 user account using the following command:
/usr/bin/rsync -avu /nethome/ECE6122/RSA .
Be sure to notice the period at the end of the above command.
3. Change your working directory to RSA
4. Copy the provided RSA-skeleton.cc to RSA.cc as follows:
cp RSA-skeleton.cc RSA.cc
5. Then edit RSA.cc to create your code for the project
Turning inyourProject. Usethesameturninscriptaspriorassignments,specificallyturnin-ece6211orturnin- ece4122