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:

• 38 * 16 * 173* 7015 * 51 * 1431 * 40 * 701 (mod 9)
  
• 19 * 27 * 26036 *  114 * 543 * 91 * 37 * 5009 (mod 10)
  

Answer:
  38 * 16 * 173 * 7015 * 51 * 1431 * 40 * 701 (mod 9)

  19 * 27 * 26036 *  114 * 543 * 91 * 37 * 5009 (mod 10)

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⁴³, 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¹²" rather than 4,236,975,012,534.

• Estimates of the age of the universe vary, but they are typically of the order of 10 billion years, or 10¹⁰ years. How many seconds does that make?

• Imagine filling a shoe box with sand. About how many sand grains would there be? We are looking for the "order of magnitude" here, meaning that your answer is still OK if it is about right - it could be off by a factor of 10, say, but not a factor of 1,000. Please explain how you get your answer. You may assume that a sand grain can be thought of as a little cube with each side measuring approximately 1/2 mm.

• One gram of iron contains about 10²² atoms. Assume that about half the weight of a car is due to its iron content (probably roughly right - many cars are still mostly made of steel and steel is mostly iron with carbon and other trace elements). How many iron atoms are there in a typical car?

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²+y² (mod 4) for at least five choices of x and y. Give the results here:

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²+y²=3 (mod 4). Please use a similar argument to find what numbers, if any, x²+y² (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^p-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:

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^p-1 (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 = (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 by 17
1+2*2952 = 5905 is not divisible by 17
1+3*2952 = 8857 is divisible by 17, so s = 8857 / 17 = 521.

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:
The first decoded message is:

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 two-digit numbers.

So 

becomes

Now break it up in pieces of length 3 :

Every one of these numbers x we now treat as before. We find for the x¹⁰³ (mod 1441499):

0060918 0179148 0064110 0622149 1305250 0247442 1060445
1064198 1094487 0661028 0144829 1371360 0317672 1071216
1392772 1353679 0583959 0018888 0542645 0514017 0923957
1056701

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):

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 2-digit values:


Please give the decoded sentence (in letters):

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, 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.

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² = 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:

• Grouping by 3 or by 4?
• Grouping by 3 or by 6?
• Grouping by 4 or by 6?

Answer: