Description
Programming Problem: (35 points) What you have to turn in and where you have to turn it in is similar to how
you needed to turn in stuff for the HW1 programming problem. In this problem, in the HW2 submission, along with the
self-critique, the easy to read source code, a printout of the output, you also need to show how much time each of the
attacks took for each of the inputs. Please read the programming guidelines (in the course outline on Canvas) before
starting to work on the programming problem. You need to read this carefully to understand what has to be turned in and
how, including the self-critique.
You have to write a program (or if you find it easier, two different programs) to implement two different attacks on RSA
and see which works faster. For each attack, your program will take as input the public key e, n, and a ciphertext C and
produce as output the plaintext M and the total amount of time the attack took to obtain M
1. Attack 1: Here you will generate all possible values of M till you find one for which M e = C mod n. You can use the
naive and inefficient method for modular exponentiation. Here the output should consist of M .
2. Attack 2: Here you will factor n to recover the primes p, q such that n = pq. You will then calculate the private key
d, n, and then calculate M = Cd mod n. You can use the naive and inefficient methods for factoring n, for finding d
from e and Φ(n), and for modular exponentiation. Here the output should consist of p, q, d, M .
You have to run your program on three different inputs.
1. e = 7, n = 15, C = 10. It is possible that this problem gets solved so fast that you do not get very meaningful timing
results for this example.
2. e = 13, n = 527, C = 356. Again, it is possible that this problem gets solved so fast that you do not get very meaningful
timing results for this example.
3. An input generated by you – you should generate the largest values for which you can get results in a “reasonable”
amount of time. Here you have to start from scratch in terms of finding p,q,e,d etc i.e. you have to find these values.
Notes:
1. As discussed in class, you will need to do the mod operation frequently to keep the numbers small so as to avoid
overflow errors.
2. You will have to figure out some kind of clock function to do the timing calculation.
Extra Credit Problems: 9.5, 9.7, 9.15, 10.4, 11.1, 11.4. 14.6
Extra Credit Problem 3: Implement a brute force attack on Diffie-Hellman and show how it works on some examples.
2
