Part I: Preliminaries

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

• 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?

• 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).

• The integers mod p as a field, Z_p: Uses addition and multiplication followed by remainder on division by p.

• The Extended Euclidean Algorithm: Statement of the algorithm, and its use to find the multiplicative inverse of a non-zero element in the field Z_p.

• Fermat's Theorem: Its statement. Arithmetic in the exponent is taken mod p-1.

• 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).

• The Fast Exponentiation Algorithm: Understand it, without memorizing. For a random n-bit exponent, how many multiplications are needed on the average?

• The Simple Pseudo-prime Test: Its statement.

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

• Channel Capacity: Understand 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?

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

• 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.)

• 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.

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

• Block ciphers: General properties. Meet in the middle attack for double encryption. ECB and (especially) CBC Mode of operation. (Including what the letters stand for.)

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

• The Diffie-Hellman Distribution System: How this works to get a common key in the hands of two people who cannot communicate in secret.

• Public Key Cryptography: How this works to allow a secret message, a signed message, or a message both secret and signed.

• The RSA Cryptosystem: Various 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?