Office Hours

• 3-4:30 Monday
• 10-11:30 Tuesday
• Also by appointment.

There will be a final exam: Friday, May 2, 8:00-10:30 AM

• I will be handing out study sheets.
• New homework assignment, see bottom of page.

Class Notes

• Lecture 1
  Introduction; Shift Cipher; Simple Substitution Cipher; Cryptanalysis.
• Lecture 2
  One Time Pad (Vernum cipher); Vigenere Cipher
• Lecture 3
  Mathematics of Vigenere cryptanalysis; Digram method for breaking Simple Subs. Ciphers (read Jakobsen).
• Lecture 4
  Playfair and Transposition ciphers; Remarks on Book ciphers.
• Lecture 5
  The Enigma. Simple.
• Lecture 6 and 7
  Finite Math (Chapter 3). Given by Victor Milenkovic.
• Lecture 8
  Finite Fields. Example of GF(9)
• Lecture 9
  Rijndael, the Advanced Encryption Standard.
• Lecture 10
  Rijndael concluded. Square attack.
  DES, Feistal systems.
• Lecture 11
  Differential Cryptanalysis.
• Lecture 12
  Modes of Operation: CBC, CFB, OFB
  Cascade of Cryptosystems: meet-in-the-middle attack (Merkle Hellman 1981).
  3DES and DESX.
• Lecture 13
  Security of F-x (Kilian Rogaway 2001).
  Multiple modes of operation.
• Lecture 14
  Birthday attack, probability
  CBC|CBC|CBC attack (Biham 98, 99)
• Lecture 15
  Entropy. Motivation and introduction
  Definition, technical lemma
  First basic property
• Lecture 16
  Joint entropy H(X,Y) and joint probability p(x_i,y_j)
  Independence
  Conditional probability p(x_i|y_j) and Bayes theorem
  Conditional entropy H(X|Y)
• Lecture 17
  Properties of conditional entropy
  Prefix-free, instantaneous and unambiguous codes
  Huffman coding
• Lecture 18
  Perfect security in the Shannon model
  Entropy and redundancy of English
• Lecture 19
  Discrete memoryless communication channel with noise
• Lecture 20
  Encoding, error reduction over a noisy channel
  Ideal Observer and Maximum Likelihood decoding rules
• Lecture 21
  Hamming distance, and some implications
  Channel capacity
• Lecture 22
  Channel capacity of a binary symmetricy channel and a binary erasure channel
  Wyner's wiretap channel. See Noisy channels and cryptography and (Maurer 93)
• Lecture 23
  Wiretap channel with back-channel
  Oblivious transfer over a binary erasure channel
  Bit commitment and fair coin flipping (information theoretic version).
• Lecture 24
  Hamming code, an introduction.
• Lecture 25
  Sphere packing bound, Perfect codes.
  Linear codes, parity check and generator matrices
• Lecture 26
  General decoding for linear codes: syndromes and coset leaders
  Systematic codes
• Lecture 27
  Hamming revisited
  Complexity based cryptography, P and NP
• Lecture 28
  Public key cryptography [Diffie]
  RSA
• Lecture 29
  Miller-Rabin primality test
• Lecture 30
  Roots of unity mod n, via Chinese Remainder Theorem
  Pollard p-1 algorithm to factor smooth numbers
  Quadratic Sieve, introduction
• Lecture 31
  Quadratic Sieve
• Lecture 32
  Discrete Logarithms
  Diffie-Hellman secret key agreement
  El Gamal encryption
  Order of elements in Z_n^*, various remarks
• Lecture 33
  Bit committment using Discrete logs
  Pohlig-Hellman algorithm for discrete logs
• Lecture 34
  Digital Signatures: RSA
  Blind signatures using RSA
  El Gamal signature scheme
  Cryptographic hash functions: pre-image, 2nd pre-image, collision resistance.
• Lecture 35
  Hashing: Chaum, van Heijst, Pfitzmann
  DSA signature algorithm
• Lecture 36
  MAC's using CBC
  Linear congruential pseudo-random number generator.
  Linear feedback shift register pseudo-random number generator.
• Lecture 37
  Cryptographically strong pseudo-random number generation: Blum-Blum-Shub.
  Equivalence of One Way Functions and Pseudo-random Number Generators under complexity assumptions.
  Interactive Proof: graph non-isomorphism. tutorial [Goldreich 91]
• Lecture 38
  From IP to Zero-knowledge.
  Formal definitions [Goldwasser 89] [Luby 96]
  Zero-knowledge Interactive Proof for Graph Isomorphism.
• Lecture 39
  Application of ZKIP: Fiat Shamir identification scheme.
• Lecture 40
  Bit commitment and ZKIP for all NP: Hamiltonian Cycles.
• Lecture 41
  Review for final
• Uncovered material
  Secret sharing
  HMAC

Homework

• See NOVA program Decoding Nazi Secrets. Solve the Cipher (note: Shockwave plugin required.)
  Send me the signer's name as proof of success.
• Assignment: Write a C or Java program which implements a simple substitution cipher. ssc [-e|-d] keyword encoding stdin to stdout.
• Extra Credit: Implement ssc -k normative_digram_table which cracks an ssc.
• Above programs due January 31
• Read in detail about the Enigma
• Read additional information about the Enigma
• Assignment:: Breaking Bad Ciphers. Due: 13 February 2003
• Assignment:
  1. Undergraduates: Problems 1-7, chapter 14 (section 14.6) of Trappe. Due: 6 March
  2. Graduates: undergraduate assignment, also all problems in chapter 1 and problems 1-6 in chapter 2 of Welsh. Due: 13 March
• Assignment:
  • Undergraduates: From Trappe and Washington,
    1. Problems 1, 3, 5, 7, 9 in Section 6.8;
    2. Problems 1, 3 in Section 7.5;
    3. Problems 2, 4, 6 in Section 8.6.
  • Graduates: From Welsh,
    1. All problems assigned to undergraduates;
    2. Read section 11.4 and do exercises 1 and 2 at the end of that section (page 193);
    3. Problems 8 and 9 at the end of chapter 11 (page 197).
  • Due: Friday, April 25

References
On campus access via e-link

• Aiello, W., and M. Bellare, G. Di Crescenzo, R. Venkatesan, Security amplification by composition: the case of doubly-iterated, ideal ciphers, CRYPTO '98, LNCS 1462 Springer Verlag 1998, 390 ff.
• Bellare, Mihir, and Joe Kilian, Phillip Rogaway, The security of the cipher block chaining message authentication code, J. Comp and System Sci 61:3 (Dec 2000) 335-581.
• Biham, Eli, Cryptanalysis of multiple modes of operation , J. Cryptology 11:1 (1998) 45-58.
• Biham, Eli, Cryptanalysis of triple modes of operation, J. Cryptology 12:3 (1999) 161-184.
• Csiszar, I., and J. Korner, Broadcast channels with confidential messages, IEEE Trans. on Info. Theory, Vol. 24, No. 3 1978. pp 339-348.
• Damgard, Ivan, and Lars Knundsen, Two-key triple encryption, J. Cryptology 11:3 (1998) 209-218.
• Diffie, Whitfield, and Martin E. Hellman, New directions in cryptography, IEEE Trans of Info Theory, Vol. 22, No. 6, Nov. 1976. pp 644-654.
• Goldreich, Oded, Silvio Micali and Avi Wigderson, Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems, J. ACM, 38(3), 1991. [cached]
• Goldreich, Oded, Silvio Micali and Avi Wigderson, How to prove all NP statements in zero-knowledge and a methodology of cryptographic protocol design, LNCS 0263, p. 171 ff.
• Goldwasser, Shafi, Silvio Micali and Charles Rackoff, The knowledge complexity of interactive proof systems, STOC 85, pp. 291-304. (reference to check)
• Goldwasser, Shafi, Silvio Micali and Charles Rackoff, The knowledge complexity of interactive proof systems, SIAM J. Comp, 18(1), Feb 89. pp. 186-208.
• Jakobsen, Thomas, A fast method for the cryptanalysis of substitution ciphers. Cryptologia 19:3 (July 1995).
• Kilian, Joe, and Phillip Rogaway, How to protect DES against exhaustive key search (an analysis of DESX) J. Cryptology 14:1 (2001) 17-35.
• Luby, Michael, Pseudorandomness and Cryptographic Applications, Lecture 18, pp 174-184. PUP 1996.
• Maurer, U., Secret key agreement by public discussion from common information, IEEE Trans. on Info. Theory, Vol. 39, 1993. pp. 733-742.
• Merkle, R. C., and M. Hellman, On the security of multiple encryption, Comm. of the ACM, 24:7 (1981) 465-467.
• Shannon, C. E., Communication theory of secrecy systems, Bell System Technical Journal, Vol. 28, Oct. 1949. pp 656-715.
• van Oorshot, P. C., and M. J. Wiener, A known-plaintext attack on two-key triple encryption, EUROCRYPT '90, LNCS 0473 Springer-Verlag (1991) 318-325.
• Wyner, A. D., The wire-tap channel, Bell System Technical Journal, Vol. 54, No. 8, 1975. pp. 1355-1387.

Critique