2.8 Exercises – Introduction to Cryptography with Coding Theory, 3rd Edition

2.8 Exercises

  1. Caesar wants to arrange a secret meeting with Marc Antony, either at the Tiber (the river) or at the Coliseum (the arena). He sends the ciphertext EVIRE. However, Antony does not know the key, so he tries all possibilities. Where will he meet Caesar? (Hint: This is a trick question.)

  2. Show that each of the ciphertexts ZOMCIH and ZKNGZR, which were obtained by shift ciphers from one-word plaintexts, has two different decryptions.

  3. The ciphertext UCR was encrypted using the affine function 9x+2 mod 26. Find the plaintext.

  4. The ciphertext JLH was obtained by affine encryption with the function 9x+1 mod 26. Find the plaintext.

  5. Encrypt howareyou using the affine function 5x+7 (mod26). What is the decryption function? Check that it works.

  6. You encrypt messages using the affine function 9x+2 mod 26. Decrypt the ciphertext GM.

  7. A child has learned about affine ciphers. The parent says NONONO. The child responds with hahaha, and quickly claims that this is a decryption of the parent’s message. The parent asks for the encryption function. What answer should the child give?

  8. You try to encrypt messages using the affine cipher 4x+1 mod 26. Find two letters that encrypt to the same ciphertext letter.

  9. The following ciphertext was encrypted by an affine cipher mod 26:

    CRWWZ.

    The plaintext starts ha. Decrypt the message.

  10. Alice encrypts a message using the affine function xax (mod26) for some a. The ciphertext is FAP. The third letter of the plaintext is T. Find the plaintext.

  11. Suppose you encrypt using an affine cipher, then encrypt the encryption using another affine cipher (both are working mod 26). Is there any advantage to doing this, rather than using a single affine cipher? Why or why not?

  12. Find all affine ciphers mod 26 for which the decryption function equals the encryption function. (There are 28 of them.)

  13. Suppose we work mod 27 instead of mod 26 for affine ciphers. How many keys are possible? What if we work mod 29?

  14. The ciphertext XVASDW was encrypted using an affine function ax+1 mod 26. Determine a and decrypt the message.

  15. Suppose that you want to encrypt a message using an affine cipher. You let a=0, b=1, , z=25, but you also include ?=26, ;=27, "=28, !=29. Therefore, you use xαx+β(mod30) for your encryption function, for some integers α and β.

    1. Show that there are exactly eight possible choices for the integer α (that is, there are only eight choices of α (with 0<α<30) that allow you to decrypt).

    2. Suppose you try to use α=10, β=0. Find two plaintext letters that encrypt to the same ciphertext letter.

  16. You are trying to encrypt using the affine function 13x+22 mod 26.

    1. Encrypt HATE and LOVE. Why is decryption impossible?

    2. Find two different three-letter words that encrypt to WWW.

    3. Challenge: Find a word (that is legal in various word games) that encrypts to JJJ. (There are four such words.)

  17. You want to carry out an affine encryption using the function αx+β, but you have gcd(α, 26)=d>1. Show that if x1=x2+(26/d), then αx1+βαx2+β (mod26). This shows that you will not be able to decrypt uniquely in this case.

  18. You encrypt the message zzzzzzzzzz (there are 10 z’s) using the following cryptosystems:

    1. affine cipher

    2. Vigenère cipher with key length 7

      Eve intercepts the ciphertexts. She knows the encryption methods (including key size) and knows what your plaintext is (she can hear you snoring). For each of the two cryptosystems, determine whether or not Eve can use this information to determine the key. Explain your answer.

  19. Suppose there is a language that has only the letters a and b. The frequency of the letter a is .1 and the frequency of b is .9. A message is encrypted using a Vigenère cipher (working mod 2 instead of mod 26). The ciphertext is BABABAAABA. The key length is 1, 2, or 3.

    1. Show that the key length is probably 2.

    2. Using the information on the frequencies of the letters, determine the key and decrypt the message.

  20. Suppose you have a language with only the three letters a, b, c, and they occur with frequencies .9, .09, and .01, respectively. The ciphertext BCCCBCBCBC was encrypted by the Vigenère method (shifts are mod 3, not mod 26). Find the plaintext (Note: The plaintext is not a meaningful English message.)

  21. Suppose you have a language with only the three letters a, b, c, and they occur with frequencies .7, .2, .1, respectively. The following ciphertext was encrypted by the Vigenère method (shifts are mod 3 instead of mod 26, of course):

    ABCBABBBAC.

    Suppose you are told that the key length is 1, 2, or 3. Show that the key length is probably 2, and determine the most probable key.

  22. Victor designs a cryptosystem (called “Vector”) as follows: He writes the letters in the plaintext as numbers mod 26 (with a=0, b=1, etc.) and groups them five at a time into five-dimensional vectors. His key is a five-dimensional vector. The encryption is adding the key vector mod 26 to each plaintext vector (so this is a shift cipher with vectors in place of individual letters).

    1. Describe a chosen plaintext attack on this system. Give the explicit plaintext used and how you get the key from the information you obtain.

    2. Victor’s system is not new. It is the same as what well-known system?

  23. If v and w are two vectors in n-dimensional space, vw=|v||w|cosθ, , where θ is the angle between the two vectors (measured in the two-dimensional plane spanned by the two vectors), and |v| denotes the length of v. Use this fact to show that, in the notation of Section 2.3, the dot product A0Ai is largest when i=0.

  24. Alice uses an improvement of the Vigenère cipher. She chooses five affine functions

    a1x+b1, a2x+b2, , a5x+b5 (mod26)

    and she uses these to encrypt in the style of Vigenère. Namely, she encrypts the first plaintext letter using a1x+b1, the second letter using a2x+b2, etc.

    1. What condition do a1, a2, , a5 need to satisfy for Bob (who knows the key) to able to decrypt the message?

    2. Describe how to do a chosen plaintext attack to find the key. Give the plaintext explicitly and explain how it yields the key. (Note: the solution has nothing to do with frequencies of letters.)

  25. Alice is sending a message to Bob using one of the following cryptosystems. In fact, Alice is bored and her plaintext consists of the letter a repeated a few hundred times. Eve knows what system is being used, but not the key, and intercepts the ciphertext. For systems (a), (b), and (c), state how Eve will recognize that the plaintext is one repeated letter and decide whether or not Eve can deduce the letter and the key.

    1. Shift cipher

    2. Affine cipher

    3. Vigenère cipher

  26. The operator of a Vigenère encryption machine is bored and encrypts a plaintext consisting of the same letter of the alphabet repeated several hundred times. The key is a seven-letter English word. Eve knows that the key is a word but does not yet know its length.

    1. What property of the ciphertext will make Eve suspect that the plaintext is one repeated letter and will allow her to guess that the key length is seven?

    2. Once Eve guesses that the plaintext is one repeated letter, how can she determine the key? (Hint: You need the fact that no English word of length seven is a shift of another English word.)

    3. Suppose Eve doesn’t notice the property needed in part (a), and therefore uses the method of displacing then counting matches for finding the length of the key. What will the number of matches be for the various displacements? In other words, why will the length of the key become very obvious by this method?

  27. Use the Playfair cipher with the keyword Cryptography to encrypt

    DidheplayfairatStAndrewsgolfcourse.
  28. The ciphertext

    BPEGFCAIMAMGPOKBHU

    was encrypted using the Playfair cipher with keyword Archimedes. Find the plaintext.

  29. Encrypt the plaintext secret using the ADFGX cipher with the 5×5 matrix in Section 2.6 and the keyword spy.

  30. The ciphertext AAAAFXGGFAFFGGFGXAFGADGGAXXXFX was encrypted using the ADFGX cipher with the 5×5 matrix in Section 2.6 and the keyword broken. Find the plaintext.

  31. Suppose Alice and Bob are using a cryptosystem with a 128-bit key, so there are 2128 possible keys. Eve is trying a brute-force attack on the system.

    1. Suppose it takes 1 day for Eve to try 264 possible keys. At this rate, how long will it take for Eve to try all 2128 keys? (Hint: The answer is not 2 days.)

    2. Suppose Alice waits 10 years and then buys a computer that is 100 times faster than the one she now owns (so it takes only 1/100 of a day, which is 864 seconds, to try 264 keys). Will she finish trying all 2128 keys before or after what she does in part (a)? (Note: This is a case where Aesop’s Fable about the Tortoise and the Hare has a different ending.)

  32. In the mid-1980s, a recruiting advertisement for NSA had 1 followed by one hundred 0s at the top. The text began “You’re looking at a ‘googol.’ Ten raised to the 100th power. One followed by 100 zeroes. Counting 24 hours a day, you would need 120 years to reach a googol. Two lifetimes. It’s a number that’s impossible to grasp. A number beyond our imagination.”

    How many numbers would you have to count each second in order to reach a googol in 120 years? (This problem is not related to the cryptosystems in this chapter. It is included to show how big 100-digit numbers are from a computational viewpoint. Regarding the ad, one guess is that the advertising firm assumed that the time it took to factor a 100-digit number back then was the same as the time it took to count to a googol.)