CS 4953 -- Cryptography
Mid-term Exam
Wednesday, 20 March 2002

Please try to give your answers on the lines provided below. In each case you should show your work for full credit. (An incorrect answer with proper work might get full credit.)

Part I: Preliminaries

  1. Exclusive-Or: Start with a and b, and set c = a xor b, where the variables are single booleans or bit strings. Show a simple way to write a in terms of b and c using xor. Show why your formula works using properties of xor.

  2. Logarithms: Calculate about how many binary bits are required to represent a 12-digit number? For full credit you must explain briefly why your answer is correct. (Use your knowledge of log10(1012), and the fact that log102 = 0.3. Actually log102 = 0.3010299... but 0.3 is close enough.)

  3. The integers mod n as a group, Zn: Find the additive inverse of the element 10 in the group Z14.

  4. The integers mod p as a field, Zp: Assuming that p is a prime, does every element of Zp have a multiplicative inverse? (Yes or no). If "no", which element or elements do not have a multiplicative inverse?

  5. The Extended Euclidean Algorithm: Find integers x and y such that x*8 + y*19 = 1. (Big hint: y = -5.) Use this result to find the multiplicative inverse of 8 in Z19.

  6. Fermat's Theorem: If p is a prime, what is ap mod p equal to? Find the value of 143737 mod 19.

  7. Euler's Theorem: Find the value of 25802 mod 15.

  8. The Fast Exponentiation Algorithm: For a random n-bit exponent, approximately how many multiplications (including squarings) are needed on the average, using one of the fast exponentiation algorithms?

  9. The Simple Test: Suppose the following is true for a large random integer n:
    3n-1 mod n is not equal to 1. What does this say about n?

 

 

 

 

Part II: Coding and Information Theory

  1. Entropy: Suppose there are 3 messages with probabilities 0.5, 0.25, and 0.25. What is the entropy in this case?

  2. Channel Capacity: Using the binary symmetric (noisy) channel, assume that the channel capacity is 0.25. Intuitively, what does this imply about the performance of the channel? In particular, using a 56K bit per second channel, how much information could you get through this channel?

  3. ISBN Decimal Error Detection: The ISBN number of a book uses the following check equation:

    Suppose the data digits of an ISBN number are 014004656. Determine the value of the final digit, labeled a9 above, so that the check equation is true.

  4. Verhoeff's Decimal Error Detection: Using # as the group operation, the group used in Verhoeff's scheme has the property that 2 # 9 = 6, while 9 # 2 = 7. What is the name of this property? Is it true that a # b and b # a are different for any two distinct group elements a and b?

 

 

Part III: Introduction to Cryptography

  1. Cryptograms: Is it hard to break a cryptogram? Give at least two facts about cryptograms that make it easier to break them.

  2. Cryptography terminology: Briefly explain the difference between a known plaintext attack and a chosen plaintext attack.

  3. Caesar cipher, Beale cipher, One-time Pad: For each of these three example ciphers, say how hard it is to break?

  4. Block ciphers: Consider the CBC mode of operation. What is the initialization vector? Give two important properties of the CBC mode.

Part IV: Public Key Cryptography

  1. Merkle's Puzzles: Suppose Bob is using this to communicate with Alice, and that Boris is listening in. Bob sends Alice a large number of puzzles. Why is it that Alice only needs to break (or solve) one of the puzzles, but Boris has to break half of them on the average?

  2. The Diffie-Hellman Distribution System: This system essentially uses exponentiation as a cryptosystem, so that if M is a message, then the ciphertext is computed as C = aM mod p for some public integer a and public prime p. What essential property does this cipher have that allows it to be used in this distribution system?

  3. Public Key Cryptography: Explain how Alice uses a public key cryptosystem to send a secret message to Bob, and how Bob reads the message.

  4. The RSA Cryptosystem: Various details about RSA:
    1. Basic parameters for RSA:
        Each RSA user chooses large random primes p and q and calculates the product n = p*q.
      1. What simple value is commonly used for the encryption exponent? ____________

      2. With this exponent, what must then be true about p-1 and q-1?

      3. What equation does the decryption exponent satisfy?

      4. How do you encrypt? (Give equation) _________________________

      5. How do you decrypt? (Give equation) _________________________

    2. How is the extended Euclidean algorithm used in RSA?

    3. How does the speed of RSA compare with that of a conventional block cipher such as the AES?

    4. By what factor does the variation of RSA using the Chinese Remainder Theorem speed up ordinary RSA? _______________