Exams:

• Midterm:
• Final: Tue, May 6, 8-10:30 (take home exam)

Announcements

• See older courses an idea about this course.
• Required textbook for Csc 507: Introduction to Cryptography with Coding Theory, Trappe and Washington.
• Suggested for 609 students: Codes and Cryptography by Dominic Welsh. (book is out of print, 24 copies available from sellers via Amazon on 16 Jan)
• Homework: turn in hard copy (printouts) in class. The grader is Wenghui Lin linwh0520 _at_ hotmail _dot_ com.

Class Notes

• Introduction
  • Crypto talk
  • Nova: Decoding Nazi Secrets
  • Kryptos
• Hand ciphers
  • Substitution
  • Vignere
    • cracking vignere
  • Playfair
  • Transposition
• Enigma
  • Enigma description
  • Breaking Enigma
  • Cycle structure of P_iP_i+1 for a simple 6 letter enigma.
• Number theory
  • GCD and modular matrices: Hill Cipher
  • One Time Pad and Pseudorandomness (Linear Shift Registers)
  • Chinese Remainder Theorem, Little Fermat
  • Euler Phi function, Little Fermat for general n
• The Data Encryption Standard
  • DES, Differential Cryptanalysis
  • Modes of operation: ECB, CBC, CFB, OFB.
  • Multiple encipherment: 3DES and DESX and multiple modes
  • Meet in the Middle attacks, and Rainbow Cracking.
• Public Key Cryptography and Complexity based cryptography
  • RSA encryption
  • Information theoretic security and the One Time Pad
  • ZPP and Randomized computations
• Primarlity testing and factoring
  • Fermat test and Carmichael numbers
  • Miller-Rabin test
  • Quadratic Sieve
  • p-1 method (homework)
  • Pollard's Rho (wikipedia)
  • RSA is as hard as factoring by an RP reduction
• Discrete Logs
  • Generators and primitive roots (section 3.7)
  • Quadratic residues and the Legendre symbol
  • programs
  • Pohlig-Hellman
  • Bit security of discrete logs
  • Shanks algorithm (big step, little step)
  • Index calculus
• Public key encryption
  • Diffie-Hellman Key Exchange
  • ElGamal encryption
  • Bit commitment
  • Treaty verification
  • Optimal Asymmetric Encryption Padding (OAEP)
• Hash functions
  • cyptographic strength: pre-image, strongly and weakly collision-free
  • Chaum-van Heijst-Pftzmann hashing (solving ax=b(n) when gcd(a,n)!=1)
  • Merkle-Damgard construction
  • SHA-1
  • Random oracle model
  • cyphertext indistiguishability (semantic security)
• Signatures
  • Preimage and collision resistance.
  • RSA and El Gamal.
  • DSA and subgroups.

Homework

• One
  • See NOVA program Decoding Nazi Secrets.
  • Solve Nova program challenge, a simple subsitution cipher.
  • Try to solve the Nova program challenge, a series of playfair and transposition ciphers.
  • Read chapters 1 and 2 of Introduction.
  • Above problems due by Monday Jan 21.
• Two
  • Chapter 2, problems 1-8, 13, 14, 15, 19 and 20. Due Monday Feb 11.
  • Start learning Python, or Javascript/DHTML, your choice. We will be using this for computer experiments.
  • Is there anyone reading the Codes and Cryptography book?
• Three
  • Section 3.13 exercises 1, 2, 3, 4, 12, 13, 15.
  • Section 3.14 problems 1, 2, 4, 5. (Write in Python)
  • Write GCD, extended GCD, and fast exponentiation in Python.
  • Due: Monday 25 February.
• Four
  • Section 4.9 exercises, 1, 2, 4 and 5.
  • Section 6.9 problems 2, 4, 6 and 7.
  • Due: Monday 3 March.
• Five
  • Section 3.13 exercises 25, 26, 29.
  • Section 3.13, exercise 20. (challenge problem!)
  • Setion 3.14 problems 8, 11 and 12. (Write in Python)
  • Due: Monday 17 March.
• Six
  • Section 7.6, exercises 1, 2, 3 and 4.
  • Section 7.7, problems 1,2 and 3.
  • Section 8.8, exercises 1,2 and 3.
  • Due: Monday, 31 March
• Seven
  • Section 9.6, exercises 2, 3, 4 and 5.
  • Section 11.2, exercises 1, 2 and 4.
  • Section 12.3, exercise 3, 7 and 8.
  • Section 12.4, problem 2.
  • Due: Monday, 21 April
• Final
  • Section 9.7, problems 1 and 2.
  • Setion 13.3, exercises 1 and 2.
  • Section 14.3, exercises 2 and 4.
  • Section 16.8, problems 1, 2, 3, 4 and 5.

Books

• Cryptanalysis by Helen Gaines. Cryptanalysis of classic ciphers.
• Elementary Military Cryptography William F. Friedman.
• Handbook of Applied Cryptography by Oorshot and Vanstone.
• Lecture Notes on Cryptography by Goldwasser and Bellare.
• American Black Chamber, see also Yardley's book
• Enigma, Wladyslaw Kozaczuk. Articles on reconstruction and breaking of Enigma by Polish mathematicians prior to WWII.
• La cryptographie militaire by Auguste Kerckhoffs.

Other resources

• Simon Singh challenge
• Breaking Tunny by Tutte. Article on reconstructing the masking sequence for encryption of German High Command network.
• John Savard's page on machine ciphers.
• Beginner's Guide to Python
• GCD in Python by Andrew Kuchling.
• Rotonym, what the heck is a rotonym, Will McGugan. A nice Rot-13 implementation in Python.
• Elliptic Curves, John Milne.
• Cryptographic Secure Psudo-Random Bit Generation: The Blum-Blum-Shub Generator, Pascal Junod.

References

• 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.
• Cramer, Gennaro, Schoenmakers, A secure and optimally efficient mutli-authority election scheme, Eurocrypt 97.
• Jens Groth, Extracting witnesses from proofs of knowledge in the random oracle model
• Cramer, Damgard, Schoenmakers, Proofs of partial knowledge and simplified design of witness hiding protocosl, Crypto 94
• Michael Ben-Or, Shafi Goldwasser, Avi Wigderson, Completeness theorems for non-cryptographic fault-tolerant distributed computation, Proc. 20-th ACM Symposium on Theory of Computing, 1988. pp 1-10.
• Philippe Oechslin, Making a faster cryptanalytic time-memory trade-off, Crypto 03. (cached)
• M. Bellare, P. Rogaway. Optimal Asymmetric Encryption -- How to encrypt with RSA. Extended abstract in Advances in Cryptology - Eurocrypt '94 Proceedings, Lecture Notes in Computer Science Vol. 950, A. De Santis ed, Springer-Verlag, 1995. (full version (pdf))
• RSA Labs FAQ: OAEP

Cryptographic Games

• MIT 6.876, Course in Cryptographic Game Theory.
• The Knowledge Complexity of Interactive Proof-Systems (PDF)
• Proofs that Yield Nothing But Their Validity, or All Languages in NP Have Zero-Knowledge Proof Systems (PDF)
• How To Play Any Mental Game (PDF)
• Equivalence between two flavours of oblivious transfers (PDF)
• Completeness Theoerms for Fault Tolerant Distributed Computing (PDF)
• Parallel Reducibility for Information-Theoretically Secure Computation (PDF)

SliceOfLife

• Helger Lipmaa Notes
• mersenne.org, and Prime network
• Van Eck radiation (security, not crypto, but an enjoyable group of pages anyway.)