CS111 ASSIGNMENT 2
Problem 1:
Prove the following statement: if p and p+ 2 are twin primes and p > 5, then p3 + 3p2 p 3 ≡ 0 (mod 10).
Hint: The product of any k consecutive integers is divisible by k.
Alternatively, think what are possible values of p rem 5.
Problem 2:
Alice’s RSA public key is P = (e, n) = (5, 1501). Bob sends Alice the message by encoding it as follows.
First he assigns numbers to characters: A is 4, B is 5, …, Z is 29, a blank is 30, quotation marks: 31, a
period: 32, a coma: 33, an apostrophe: 34. Then he uses RSA to encode each number separately.
Bob’s encoded message is:
578 961 1247 311 1370 1167 119 1247 311 1167 1412 311 1024 311
699 1310 271 1167 1247 55 1403 311 1247 848 1369 1320 1167 699
1167 55 1247 1370 1403 311 296 1247 950 1247 1412 296 1247 1412
55 311 1310 1412 311 699 271 1167 1247 1412 271 1247 311 1024
1412 296 311 55 1247 271 444 1412 1310 1370 1310 934 1403 1321
311 1167 1412 311 961 444 1167 271 444 311 444 1024 1381 296
1370 1403 311 1024 1412 1403 1310 1412 1247 311 466 1412 1310 961
699 311 1024 1412 1403 55 444 1167 1412 934 311 1024 123 1310
1320 55 311 699 271 1167 1247 1412 271 1247 311 1024 1412 296
311 55 1247 271 444 1412 1310 1370 1310 934 1403 1078 578
Decode Bob’s message. Notice that you don’t have Bob’s secret key, so you need to ”break” RSA to decrypt
his message. For the solution, you need to provide the following:
(a) Describe step by step how you arrived at the solution: find p and q, φ(n) and d.
(b) Show your work (the computation) for one number in the message.
(c) To decode the remaining numbers, you need to write a program in C++, test it on Codeforces and
upload to canvas.
(d) Give the decoded message (in integers).
(e) Give Bob’s message in plaintext (also, what does it mean and who said it).
Your program should :
(i) Take three integers, e, n (the public key for RSA), and m (the number of characters in the message) as
input to your program. Next, input the ciphertext.
(ii) Test whether the public key is valid. If not, output a single line “Public key is not valid!” and quit the
program.
(iv) If the public key is valid, decode the message.
(v) Output p and q, φ(n) and d.
(vi) On a new line, output the decoded message in integers.
1
(vii) On a new line, output the decoded message in English. The characters should be all uppercase. You
can assume that the numbers will be assigned to characters according to the mapping above: A is 4,
B is 5, … .
Upload your code to Codeforces to test. There are two open test cases and five hidden ones. If you implement
everything correctly, codeforces will say you have 10 points. The link on how to register/submit code for the
RSA project is here. If you have any questions, post them on Slack.
Problem 3:
(a) Compute 71529 (mod 51). Show your work.
(b) Compute 9 1 (mod 19) by listing the multiples. Show your work.
(c) Compute 9 1 (mod 19) using Fermat’s Little Theorem. Show your work.
(d) Find an integer x, 0 ≤ x ≤ 18, that satisfies the following congruence: 9x + 13 ≡ 10 (mod 19). Show
your work. You should not use brute force approach.
Academic integrity declaration. The homework papers must include at the end an academic integrity
declaration. This should be a brief paragraph where you state in your own words (1) whether you did the
homework individually or in collaboration with a partner student (if so, provide the name), and (2) whether
you used any external help or resources.
Submission. To submit the homework, you need to upload the pdf file to Gradescope and the cpp file on
canvas (in Assignments). Before uploading your code to canvas, test it through Codeforces. The score that
you received on Codeforces will be your score for the RSA code. If you submit with a partner, you need to
put two names on the assignment and submit it as a group assignment.
Reminders. Remember that only LATEX papers are accepted.
2
