This review consists mainly of a list of possible topics for questions on the Mid-term Exam. In many cases there are actual sample questions. The material is given in the order it appears in the book The Laws of Cryptography.

1: Cryptographer's Favorites

• 1.1: Exclusive-Or: Definition and properties. Show how to use xor and a stream of random bits for a cryptosystem.

• 1.2: Logarithms: The log base 2 of an integer shows how many bits are needed to represent the integer. How do you find the log base b, for any b > 1?

• 1.3: The integers mod n as a group, Z_n: Uses addition followed by remainder on division by n. The identity is 0 and the inverse of x is (x == 0 ? 0 : n-x).

• 1.4: The integers mod p as a field, Z_p: Uses addition and multiplication followed by remainder on division by p. The number p must be a prime. See 2.1 below for algorithm to determine the multiplicative inverse of an integer a not equal to zero.

• 1.5: Fermat's Theorem: Its statement and the example of p = 13. In exponentiation, reducing the exponent mod p-1.

• 1.5: Euler's Theorem: Its statement. For the case of mod n = p*q, arithmetic in the exponent is taken mod phi(n) = (p-1)*(q-1).

2: Favorite Algorithms

• 2.1: The Extended Euclidean Algorithm: Statement of what the algorithm provides. Stepwise example of finding the greatest common divisor. The algorithm's use to find the multiplicative inverse of a non-zero element in the field Z_p.

• 2.2: A Fast Exponentiation Algorithm: Understand it, without memorizing. For a random n-bit exponent, how many multiplications are needed on the average? Understand how the second version can be proved correct using a loop invariant.

• 2.3: The Simple Pseudo-prime Test: Its statement. How it can prove that a number is not prime, but can show that a number is probably prime.

3: Coding and Information Theory

• 3.1: Entropy: Definition and simple examples. It's intuitive meaning. What kind of message has the greatest entropy?

• 3.2: Three Kinds of Codes: Source coding (data compression), channel coding (error detection and correction), and secrecy coding (cryptography).

• 3.3: Channel Capacity: Understand roughly what it means. In the case of the binary symmetric channel, what is the formula for it? Intuitively, what does p = 0.9 in the binary symmetric channel mean? Intuitively, what does a channel capacity of 0.4 mean?

• 3.4: The Multiplicative Code: How you use repetitions of each bit to provide arbitrarily good error correction, while making the ciphertext arbitrarily large.

• 3.5: A Code Better Than the Repetition Code: A simple example.

• 3.6: Random Codes: Intuitively how these work. Statement of Shannon's Noisy Coding Theorem.

• 5.1: Shannon's Noiseless Coding Theorem: Its statement.

• 5.3: Examples from Huffman codes: Examples showing optimal codes with average code length equal to the entropy and not equal to the entropy.

• 7.2: ISBN Decimal Error Detection: What is it used for? Be able to work out an example, given the check equation.

• 8.2: The Dihedral Group: What is it like? A non-commutative group with 10 elements. It is not the same as Z₁₀. .

• 8.3: Verhoeff's Decimal Error Detection: Given the table, understand how to form the result of the group operation on two elements. (The result may be different, depending on the order of combining elements.) Why

• Cryptograms: What they are; how they work. How good a cryptosystem is a cryptogram?

• Cryptography terminology: Terms: Plaintext, ciphertext, encryption, decryption, cryptanalysis, brute-force attack, plaintext only attack, known plaintext attack, chosen plaintext attack.

• 10.1-10.3: Caesar cipher, Beale cipher, One-time Pad: How these work. In each case, how good a cryptosystem are they?

• 11.1-11.2: Discussion and attacks What they are; how they work. Ciphertext only, Known Plaintext, and Chosen Plaintext attacks.

• 11.3: Meet in the middle attack: Specific discussion of the Meet in the middle attack for double encryption.

• 11.4: Modes of Operation: ECB and (especially) CBC Mode of operation. (Including what the letters stand for.) Properties and advantages of the CBC mode.

• 12.1: Merkle's Puzzles: How these work to get a common key in the hands of two people who cannot communicate in secret.

• 12.2-12.3: The Diffie-Hellman Distribution System: How this works to get a common key in the hands of two people who cannot communicate in secret. Uses exponentiation and the discrete logarithm problem.

• 13.2-13.3: Structure and Modes: How this works to allow a secret message, a signed message, or a message both secret and signed.

• 13.2-13.5: Details about RSA:
  • Basic parameters for RSA:
    1. Choose large random primes p and q. (How large?)
    2. Calculate the product n = p*q.
    3. Use 3 for the encryption exponent e. (What must then be true about p and q?
    4. Calculate the decryption exponent, satisfying what?
    5. What is the encryption function?
    6. What is the decryption function?
    7. What is the public key (published)?
    8. What is the private key (kept secret)?
  • What is the role of the fast exponentiation algorithm in RSA?
  • What is the role of the extended Euclidean algorithm in RSA?
  • How does the speed of RSA compare with that of a conventional block cipher such as the AES?
  • How does the Chinese Remainder Theorem help speed up RSA?

• 16.1-16.2: Discussion and linear congruence generators.

• 16.3: Other distributions.

• 16.5: Java implementations.

• Know the statement of the extended Euclidean algorithm, and how it can be used to find the multiplicative inverse of a non-zero number in Z_p, where p is a prime.

• Know the statement of Fermat's theorem and how it can be used to show that a number is definitely not prime or is probably prime.

• Show how to use a random number generator and exclusive-or to create a conventional cryptosystem. (Remember: the seed plays the role of the key.)

• Be able to prove that the loop invariant remains true in the second version of the exponentiation algorithm. (You don't need to memorize the algorithm of the loop invariant.)

• Understand how a random code works for error correction. (Such a code is used to prove Shannon's noisy coding therorem.)

• Be able to use the multiplication table for the dihedral group to combine digits according to this rule.

• Understand the differences between the Caesar cipher, the Beale cipher, and the one-time pad.

• Understand the CBC mode of use of a block cipher and its advantages over ECB mode.

• Understand how the meet-in-the-middle attack works for double encryption.

• Be responsible for the Merkle puzzle key distribution system. How does it work?

• Be responsible for the Diffie-Hellman key distribution system. What is the underlying problem the system relies on for its difficulty of breaking?

• How can the use of a weak random number generator to generate cryptographic keys make the whole cryptosystem weak?

• Note: No questions on RSA or on Euler's theorem.