Part I: Preliminaries

1. (4) 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.

   The a = b xor c, because b xor c = b xor (a xor b) = a xor (b xor b) = a xor 0 = a

   ---

2. (4) 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 log₁₀(10¹²), and the fact that log₁₀2 = 0.3. Actually log₁₀2 = 0.3010299... but 0.3 is close enough.)

   # of bits to represent x is log₂x, and log₂(10¹²) = log₁₀(10¹²) / log₁₀(2) = 12 / 0.3 = 40 bits

   ---

3. (3) The integers mod n as a group, Z_n: Find the additive inverse of the element 10 in the group Z₁₄.

   inv(10) = 14 - 10 = 4, so that (4 + 10)%14 = 0

   ---

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

   No, only 0 has no multiplicative inverse

   ---

5. (3) 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 Z₁₉.

   Knowing that y = -5, x is clearly 12. Then 12*8 = 1 + 5*19, so (12*8) % 19 = 1

   ---

6. (4) Fermat's Theorem: If p is a prime, what is a^p mod p equal to? Find the value of 1437³⁷ mod 19.

   a^p mod p = a (if a < p). 1437³⁷ mod 19 = 1437^{37 mod 18} mod 19 = 1437¹ = 12

   ---

7. (4) Euler's Theorem: Find the value of 25⁸⁰² mod 15.

   phi(15) = (3-1)*(5-1) = 8, so that 25⁸⁰² mod 15 = 25^{802 mod 8} mod 15 = 25² mod 15 = 625 mod 15 = 10

   ---

8. (3) 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?

   n interations of the loop, with a square in each iteration, and a product for each 1 bit, so n/2 products on the average. Thus 3n/2 multiplications on the average.

   ---

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

   n cannot be prime

   ---

Part II: Coding and Information Theory

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

   H = (1/2)*log₂(1/(1/2)) + (1/4)*log₂(1/(1/4)) + (1/4)*log₂(1/(1/4)) = (1/2)*1 + (1/4)*2 + (1/4)*2 = 3/2

   ---

2. (3) 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?

   One can get at most 1/4 of the channel bandwidth through, so that a 56K channel could transmit at most 14K bits/sec of information. That is a theoretical limit, but general codes to meet the limit have never been devised.

   ---

3. (4) ISBN Decimal Error Detection: The ISBN number of a book uses the following check equation:
   (10*a₀ + 9*a₁ + 8*a₂ + 7*a₃ + 6*a₄ + 5*a₅ +
   4*a₆ + 3*a₇ + 2*a₈ + a₉) mod 11 = 0.

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

   (9 + 32 + 20 + 24 + 15 + 12 + a₉) % 11 = (112 + a₉) % 11 = (2 + a₉) % 11, and for this to be 0, one must have a₉ = 9

   ---

4. (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?

   Non-commutativity. No. 0#a = a#0 for any a, and any of 0, 1, 2, 3, and 4 commute

   ---

Part III: Introduction to Cryptography

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

   No. They give word breaks and one can use letter frequencies or occurrences of double letters

   ---

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

   Known: have corresponding plaintext/ciphertext pairs. Chosen: can choose plaintext and get the corresponding ciphertext

   ---

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

   Trivial, very hard, impossible (if key used only once)

   ---

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

   IV is xored in at the beginning

   ---

   See the writeup about CBC mode

   ---

1. (4) 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?

   Alice obtains the puzzle sequence number by breaking the puzzle, but since the puzzles were sent in random order, Boris must break puzzles until he finds that number.

   ---

2. (4) 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 = a^M 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?

   Commutativity of encryption: E_B(E_A(M)) = E_A(E_B(M)). Also, difficulty of solving discrete log problem.

   ---

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

   Alice fetches Bob's public key and encrypts for Bob. Bob uses his secret key to decrypt.

   ---

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. (3) What simple value is commonly used for the encryption exponent? 3

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

         They must not be divisible by 3

         ---

      3. (3) What equation does the decryption exponent satisfy?

         e*d mod((p-1)*(q-1)) = 1

         ---

      4. (3) How do you encrypt? (Give equation) c = m^e mod n

      5. (3) How do you decrypt? (Give equation) m = c^d mod n

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

      Used to calculate the secret exponent d from e, p, and q

      ---

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

      RSA is very slow, AES is very fast

      ---

   4. (2) By what factor does the variation of RSA using the Chinese Remainder Theorem speed up ordinary RSA? 4, or about 3.4 in my actual software implementation