Cryptography. Part 2.Problem 1. Try Modular Arithmetic. What time does a clock read 5495 hours after 5 o'clock? Answer:
Problem 2. Try Modular Multiplication. On the page "Modular Multiplication" in Part 2 of the Cryptography Lab, you can use a window on the web sheet to compute XY (mod 7) or XY (mod b)  where b is a base you choose yourself  and to check that the result is the same as when you first compute X (mod 7 or b) and Y (mod 7 or b) and then compute the product of these two remainders and mod out again all multiples of 7 or b, if necessary. Please try three small examples that you can calculate yourself, without using the computer. Show your work. Answer: Please explain why it follows from X = x (mod b) and Y = y (mod b) that XY = xy (mod b) . Hint: You may want to use that, X = x (mod b) means that X = (a multiple of b) + x, which means that X = b*i + x for some integer i. Answer: Problem 3. Modular multiplication of many numbers On the page "Modular Multiplication of Many Numbers" in Part 2 of Cryptography Lab, it is shown how to find, in an easy way, the modular product of more than two numbers. Using the same technique as explained there, compute the following modular products:
Answer:
Problem 4. Estimate large numbers The page "Modular Powers", in Part 2 of the Cryptography Lab, explains how to deal with powers in modular arithmetic. The number in the example, 11^{43}, is really a VERY large number. The following examples here give you some other more "concrete" numbers to compare it with. Let's estimate some large numbers. In each case, we want only an idea of the order of magnitude  that means an answer of the type "about 4 * 10^{12}" rather than 4,236,975,012,534.
Note: I hope that this convinces you that 11^{43} is a pretty large number! Yet we can find very precisely its remainder (mod 13) by the trick explained in the Lab. Problem 5. Sum of squares modulo 4. Before moving on to RSA encryption, we will explore a few ways in which Fermat himself played with modular arithmetic. Try out the value of x^{2}+y^{2}
(mod 4) for at least five choices of x and y. Give the results here:
Problem 6. Sum of squares modulo 9. Please review the whole argument in the section "Modular Arithmetic and Fermat  the Proof", explaining why you can't ever have two integers x and y such that x^{2}+y^{2}=3 (mod 4). Please use a similar argument to find what numbers, if any, x^{2}+y^{2} (mod 8) cannot equal? Answer:
Problem 7. Fermat's Little Theorem. Use the lab webpage on Fermat's little theorem
to try out values of a^{p1} (mod p) when p is not a prime number
you'll see that you don't always get 1 ! (Of course, for "lucky" values
of a you still get 1, but not for all of them.) Give a few examples here
when p is not prime:
Problem 8. Primality Testing You can in fact use Fermat's little theorem to show that a number is NOT prime. For instance, try the choices a=13674 and p=21581 . What is a^{p1} (mod p) ? Is p prime? Motivate your answer! Can you show similarly that 452861 and 8462427 are not prime? Answer: Problem 9. RSA Encoding To break the RSA examples, given n and r, you have to propose a suitable s. Use a calculator! Let's try for n = 3071 and r= 17. First, we need to find the two prime factors of n. That is, find the primes p and q such that n = p * q. So, we divide 3071 by 2, 3, 5, 7, 11, 13, etc... until we find a factor, or use the Lab and we find that 3071 = 37 * 83. Now that we have p and q, we compute = (p1)*(q1). In this case, m = 36*82 = 2952. We are given r = 17 and now must find s so that r*s equals 1 + a multiple of m. So let's try... 1+1*2952 = 2953 is not divisible
by 17 Now that we have s, we can use it to decode the encoded message in the Lab. Now find s when n = 1441499 and r = 103 (please show your work). Use s to decode the second encoded message on the same page. Answer: For the second message s equals: The second decoded message is: Problem 10. RSA encryption letter by letter In practice, RSA encryption of a text would not be done in the way we did it here: just encrypting the different positional numbers of the different letters would be easy to break if you had a text of even a few sentences. Can you explain why? (Hint: how many different numbers y would you encounter?) Answer: Problem 11. Three digits RSA encryption A better way is the following. Take the text, and replace every letter by its positional number in the alphabet, using always two digits (A is 01, B is 02, .. , Z is 26), and write 27 for for the space between words. But now we won't leave space between the different twodigit numbers. So TWAS BRILLIG AND THE SLITHY TOVES becomes 202301192702180912120907270114042 Now break it up in pieces of length 3 : 202 301 192 702 180 912 120 Every one of these numbers x we now treat as before. We find for the x^{103} (mod 1441499): 0060918
0179148 0064110 0622149 1305250 0247442 1060445 You can check that with the magical value of s that you obtained earlier, the values of y^{s} (mod 1441499) are again the blocks of 3 digits we had before. Even though several letters occurred more than once in our sentence, there is no trace of that in the encrypted version now  in fact, the one block that does occur twice (002 when we split into blocks of 3 digits), corresponds to different letters in the original! Try decrypting the following, encoded in the same way (same n, r and s): 1329846 1294355 0422280 0820721 NOTE: for each of these y values, you must compute y^{s} (mod 1441499) with the help of the Modular Calculator. Next you should regroup, so that you can change it back to letters again. Don't forget to fill in with zeros when necessary (for instance, when you get that y^{s} (mod 1441499) equals 2, write it as 002, as in the example above). Answer: Decrypted values: The corresponding 2digit values: Comment: Note that even though, as pointed out above, the pattern is less easy to recognize here because of our regrouping, there still is enough of a pattern that any serious cryptographer would have no problem decoding a text of any length that would be encoded this way. But the larger the blocks into which we regroup, the less obvious the pattern becomes. For "serious" RSA applications, one can regroup in blocks of 200 or 300 digits, and breaking the code by just analyzing patterns becomes impossible. In practical RSA applications, n would be of the order of 200 or 300 digits, corresponding with p and q having each over 100 digits. At present, noone knows how to break such codes. The record so far is the factoring of a number with less than 200 digits. Problem 12. Prime factorization timing. To get a feel for how difficult it is to factor numbers that are the products of large primes, use the "Prime Factorization Machine" in the lab to factor the following numbers, and write down how long it takes your computer to factor them. If takes longer than a couple minutes to factor one  do not attempt to factor the next number in the series. Based on these timings, estimate how long it would take to factor a 155 digit number. Describe how you obtained you answer. Answer: 1407673 took _______________ milliseconds. 13309117 took _______________ milliseconds. 137937281 took _______________ milliseconds. 1438671211 took _______________ milliseconds. 14698154927 took _______________ milliseconds. 135677280727 took _______________ milliseconds. 1389864140741 took _______________ milliseconds. 13472900573921 took _______________ milliseconds. 130062255272767 took _______________ milliseconds.
Challenge Questions Problem C1. Two dice. If you take two ordinary dice, which have the numbers 1 to 6 on their faces, then the total number you obtain in one throw of the two dice together could vary from 2 (if each die shows 1) to 12 (if each die shows 6), and all the intermediate numbers are possible results as well. Suppose you have two dice without numbers, that is, just cubes. You can "fill them in" yourself, that is, you can write a number on every face for each of the two cubes; the dice need not be identical. Choose numbers in such a way that when you throw them the result could be any number between 1 and 36. Can you do that? Explain. Answer: Problem C2. Odd squares modulo 8. Show that if a is an odd integer, then a^{2} = 1 (mod 8). Answer: Problem C3. Several digits RSA encryption In problem 11 above, we group the digital version of the text by three digits, before applying RSA. Obviously, if our n is big enough we can group by 4, 5, or even by 1000 digits. Compare the following groupings from the point of security. Which is more secure:
Answer:
