Cryptography. Part 2.
Problem 1. Try Modular Arithmetic.
What time does a clock read 5495 hours after 5 o'clock?
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.
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.
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:
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, 1143, 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 * 1012" rather than 4,236,975,012,534.
Note: I hope that this convinces you that 1143 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 x2+y2
(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 x2+y2=3 (mod 4). Please use a similar argument to find what numbers, if any, x2+y2 (mod 8) cannot equal?
Problem 7. Fermat's Little Theorem.
Use the lab webpage on Fermat's little theorem
to try out values of ap-1 (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 ap-1 (mod p) ? Is p prime? Motivate your answer!
Can you show similarly that 452861 and 8462427 are not prime?
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 = (p-1)*(q-1). 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
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.
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?)
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 two-digit numbers.
TWAS BRILLIG AND THE SLITHY TOVES
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 x103 (mod 1441499):
0179148 0064110 0622149 1305250 0247442 1060445
You can check that with the magical value of s that you obtained earlier, the values of ys (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 ys (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 ys (mod 1441499) equals 2, write it as 002, as in the example above).
The corresponding 2-digit values:
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, no-one 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.
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.
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.
Problem C2. Odd squares modulo 8.
Show that if a is an odd integer, then a2 = 1 (mod 8).
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: