As we have studied, the keys for the RSA algorithm are derived from two large prime numbers p and q. The modulus n, which is publicly known, is a product of these two prime numbers: n=p*q. If n can be broken into its factors, then all keys and parameters for the RSA scheme can be determined, including the decryption key d. The strength of RSA therefore relies on the inability to break n down into p and q.
Normally, for the RSA scheme to be effective, the modulus n should be at least 1024 bits long. Some say it should be at least 2048 bits long. You have been given a program with a small n and you are to try and hack this n by finding the prime numbers p and q that n is calculated from. You will perform this hack in an environment with 20 competing processes and by varying the priority of your process with its nice value. You will have to run your process as super-user.
Code for this lab has been given as follows:
hack.cpp - the hacking process (incomplete),
nestedLoop2.cpp - the competing process,
Makefile - the Makefile for hack and nLoop2,
start.bat - the start shell for running 20 nLoop2 processes and one hack process, and
stop.bat - the stop shell for stopping all nLoop2 processes and the hack process (if needed).
You will open a file. You will call DeterminePrimes() of hack.cpp 20 times while varying the nice value of the priority from -20 to +19. For each call to DeterminePrimes(), measure the time taken to crack the modulus n of the RSA scheme. Use the high resolution timing function clock_gettime() which produces a time-stamp to the nanosecond. Store the time before the call to DeterminePrimes() and after the call to DeterminePrimes(). The difference is the time it took to hack the modulus n of the RSA scheme. Store the hack time of each call in a file and make a plot of hack-time vs nice value. You can use the plotting feature in Microsoft Excel. Be sure to close your file when done. A sample file might look as follows: hackTime.dat, where the first value is the nice value and the second the hack time in seconds. If your hacking time is too large, you might want to stop at a nice value of +10.
While your processes are running (20 nLoop2 processes and 1 hack process), run top from the command line to see how much cpu time your hack is taking as nice is decreased.
For more information on setting priorities, see the video Linux Nice and Priority values.
QuestionsPlease mail your hack.cpp, your plot of hack-time vs nice value and answers to the questions to: miguel.watler@senecapolytechnic.ca
NB: My last name is Watler, not Walter.
You will be docked 10% if your lab is submitted 1-2 days late.
You will be docked 20% if your lab is submitted 3-4 days late.
You will be docked 30% if your lab is submitted 5-6 days late.
You will be docked 40% if your lab is submitted 7-8 days late.
You will be docked 100% if your lab is submitted over 8 days late.