Back Story: After infiltrate the space pirate base, some important documents about their leadership have been discovered. Here's the important part 1. The pirates are guided from a secret command post somewhere in the Andromeda galaxy. 2. The secret commander of the space pirates is known under a code name1. 3. There are 7 different code names stored all associated with very important Andromedarians: 1. Debussy = Vovef Nug 2. Beethoven = Dithid Dodiki 3. Kilmister = Lemmy Ofcourse 4. Ravel = Dailbealas Aguces 5. Mozart = Feirer Nastir 6. Bach = Gof Glernav 7. Stravinsky = Rotisto Gilborna To inform the inner circle of the secret leader the following procedure as been developed: 1. Every member creates a public/private key pair (see Appendix and sample code on Canvas) 2. Every member then sends information to a server with the public key. 3. The server sends a message back with 1. The public key (just to be sure!) 2. The encrypted year of birth of the historical person used as the code name. 4. Since the recipient (hopefully still) has the private key, she can decrypt the birth year and then google the other name to see which of the 7 was born in this year. This then reveals the true commander.

Now comes the fun part: You can intercept only one server responses: n = 598115629, e = 71 576148263 Your assignment: Write a program in C, C++ or Java that breaks this encryption. 1. Read n and e from the keyboard (I have some values prepared) [3] 2. Print out the private key that was obtained by breaking the public key. [12] 3. Read a value encrypted with the public key. [5] 4. Print the original value by using the private key you discovered. [6] 2. Also supply a text file with the code name of the pirate leader. [4]

Appendix: Key pair generation algorithm 1. Generate a pair of large, random primes p and q. 2. Compute the modulus n = pq 3. Select an odd public exponent e between 3 and n-1 that is relatively prime to p-1 and q-1 4. Compute the private exponent d from e, p and q: 1. Let l = lcm(p1, q1) least common multiple 2. Solve the equation de 1 mod l for d 5. Output (n,e) as the public key and (n,d) as the private key. Key pair generation algorithm (example) p = 5, q = 11 (not really large!) p -1 = 4, q -1 = 10 n = 55 e = 3 l = 20 Solve 3d 1 mod 20 for d: d = 7 (21 1 mod 20) (55,3) public key, (55,7) private key. Appendix: Key pair generation algorithm 1. Generate a pair of large, random primes p and q. 2. Compute the modulus n = pq 3. Select an odd public exponent e between 3 and n-1 that is relatively prime to p-1 and q-1 4. Compute the private exponent d from e, p and q: 1. Let l = lcm(p1, q1) least common multiple 2. Solve the equation de 1 mod l for d 5. Output (n,e) as the public key and (n,d) as the private key. Key pair generation algorithm (example) p = 5, q = 11 (not really large!) p -1 = 4, q -1 = 10 n = 55 e = 3 l = 20 Solve 3d 1 mod 20 for d: d = 7 (21 1 mod 20) (55,3) public key, (55,7) private key.

Breaking RSA? Reconstruct the private key from the public key! How can you work with (n,e)? If you can recover p and q, you could just re-run the key generation algorithm! Well, we know n = pq, both p and q being prime! So, it's pretty easy! 1. Find a (prime) factor of n, call it p 2. Divide n by p, giving q 3. Run the key generation algorithm with p and q .