Chapter 13 1. Ask your bank what sort of encryption is used in your internet transactions. You may get an answer such as “128 bit encryption.” Without knowing the algorithm, this tells us almost nothing. Try to find out which algorithm is used.
2. In the back and forth mailing scheme that was described to allow communication using classical systems without prior key exchange, I claimed that some of the systems described in Book I would work. For each of the following explain why it would or would not be usable in this manner.
a) Caesar shift
3. Use the Euclidean algorithm to find the greatest common divisor (GCD) of 294,906 and 178,549. Also, find integer multiples of these numbers whose sum is the GCD.
4. Use the Euclidean algorithm to find the greatest common divisor (GCD) of 219,828 and 275,912. Also, find integer multiples of these numbers whose sum is the GCD.
5. Use the Euclidean algorithm to find the greatest common divisor (GCD) of 875,156 and 12,576. Also, find integer multiples of these numbers whose sum is the GCD.
6. Use the Euclidean algorithm to find the greatest common divisor (GCD) of 98,545 and 47,521. Also, find integer multiples of these numbers whose sum is the GCD.
7. Use repeated squaring to compute 5100 mod 26.
8. Use repeated squaring to compute 74845 mod 391.
9. Use repeated squaring to compute 66452 mod 817.
10. Use repeated squaring to compute 221007 mod 1479.
11. Use repeated squaring to compute 86243 mod 87. Can you find a quicker way to do this one?
12. Look back at the example used in this text for RSA encryption. Did Bob correctly encipher the first three blocks? Use repeated squaring to check his work.
13. Find 541-1 mod 8692.
14. Find 122-1 mod 761.
15. Find 362-1 mod 2547.
16. Find 47-1 mod 1258.
17. Try to find 230-1 mod 6752. What’s going wrong?
18. Calculate φ(4), φ(8), φ(16), φ(32), φ(64), and φ(128).
19. Calculate φ(9), φ(27), φ(81), φ(243).
20. Based on your answers to Exercises 18 and 19, form a conjecture for the value of φ(nm). Does your conjecture work for φ(42) and φ(43)? What about for φ(52) and φ(53)? For what values does your conjecture seem to work?
21. Suppose n = pq, where p and q are distinct primes. Prove that (n) = (p–1)(q–1). Hint: Don’t count how many integers less than n are relatively prime to n, but rather how many have a divisor in common with n, and then subtract this from the total. The numbers that have a common divisor with n will be the multiples of p and q.
22. Prove the conjecture you made in answer to Exercise 20 for the kind of values for which it appears to work.
23. Let p = 19, q = 29 and e = 215. Encipher the message M = 15 using the RSA scheme. Now decipher your ciphertext to make sure you get 15 back.
24. Encipher the following quote from Whitfield Diffie using e=535 and n = (1009)(1033) = 1042297. “Two people can work on a problem better than one.” Use groups of six numbers for the plaintext blocks.
25. The example supplied to Martin Gardner by the M.I.T. professors for his historic article in Scientific American used the text ITS ALL GREEK TO ME, an enciphering exponent of 9,007 and the modulus 1143816257578888676692357799761466120102182967212423625625618429357
06935245733897830597123563958705058989075147599290026879543541, which was found by multiplying a 64-digit prime and a 65-digit prime together. Generate the ciphertext yourself by converting the message to a single number (it will begin 09201...), raising it the given power, and moding out by the large modulus. Hint: use technology!
26. Go to www.google.com and do a search for 3^6 mod 5. What happens? Next try M^e mod n using various integer values for M, e, and n. For what size values does Google return answers?
27. Key sizes are often stated in bits, even for a system such as RSA, where part of the key is the modulus. I used base ten numbers throughout this chapter of the text. What is the approximate relationship between the number of decimal digits in a modulus and its length in bits?
28. Typically the primes multiplied together to form the modulus for RSA are of about the same size. Can you find a reason for this?
29. How might the large primes needed for RSA be found? Would it be a good idea to obtain them from some table of large primes?