Exams:

• Midterm: Wed March 24. In class, open book.
• Final: Monday, May 10, 8:00-10:30 AM (and paper)
  Download final here
  Note: there is an example python code for the extended euclidean algorithm posted on my blog.

Announcements

• See older courses an idea about this course.
• Required textbook for Csc 507: Introduction to Cryptography with Coding Theory, Trappe and Washington.
• Required textbook for 609 students: Complexity and Cryptography: An Introduction by Talbot and Welsh.
• Sign up for Csc401-01 for the 1 credit practicum. This entails some programing assignments related to class material.
• Homework: turn in hard copy (printouts) in class. Midterm: Wed March 24. In class, open book.
• Final: The final will be two part, in class and final paper.
• In class final: Monday, May 10, 8:00-10:30 AM.
• Final paper: read and report on Richard Dedekind's Essays on the Theory of Numbers. Make sure to comment on the concept of the "Dedekind cut".
• Twitter (for updates on homework postings): csc609

Class Notes

• Introduction
  • Crypto talk
  • Nova: Decoding Nazi Secrets
  • Kryptos
• Classical cryptograhpy
  • Codes, ciphers and steganography
  • Substitution, transposition, playfair
  • Vignere
    • cracking vignere
  • The Enigma
    • Enigma description
    • Breaking Enigma
    • Cycle structure of P_iP_i+1 for a simple 6 letter enigma.
• Symmetic Ciphers
  • DES, Differential Cryptanalysis
  • Modes of operation: ECB, CBC, CFB, OFB.
  • Multiple encipherment: 3DES and DESX and multiple modes
  • Meet in the Middle attacks, Rainbow Cracking, see also Hellman 1980.
  • AES
  • RC4, stream ciphers
• Number theory
  • GCD and modular matrices: Hill Cipher
  • One Time Pad and Pseudorandomness (Linear Shift Registers) and Linear shift registers
  • Chinese Remainder Theorem, Little Fermat
  • Euler Phi function, Little Fermat for general n
  • Galois fields, irreducible polynomials
• 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.
• Digital Cash, blind signatures
• Secret Sharing and threshold cryptography
• Elliptic Curve Cryptography
  • Elliptic curves
  • El-Gamal using elliptic curves for encryption and signatures
  • Discrete log problem for elliptic curves, Pohlig-Hellman
  • Factoring with elliptic curves
  • Identity based encryption
• Zero-Knowledge
  • The Knowledge Complexity of Interactive Proof-Systems, Goldwasser, Micali and Rackoff. 1985. Original version (PDF)
  • The Knowledge Complexity of Interactive Proof Systems, Goldwasser, Micali and Rackoff. SIAM J. Comput 1989. (PDF)
  • Proofs that Yield Nothing But Their Validity, or All Languages in NP Have Zero-Knowledge Proof Systems, Goldreich, Micali, Wigderson (PDF)

Homework

• Problem set 1, due Feb 1.
  • 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.
• Problem set 2, due Feb 15. Exercises from 4.9, page 146 of Trappe.
  Exercises 1, 2, 3, 4, 5, 6, 9, 10.
• Problem set 3, due Mar 3. Exercises from Trappe:
  Exercises from section 3.13: 1 through 8, 33 and 34.
• Problem set 4, due Mar 12. Exercises from Trappe:
  Section 5.5, problems 1 through 5.
• Problem set 5, due Monday, April 5. Exercises from Trappe:
  Section 7.6, 1 through 6;
  Section 7.7, 1 through 3 (a computer might help. Python does big numbers.)
• Problem set 6, due Monday, April 12. Exercises from Trappe:
  Section 8.8, 1, 2 and 3.
  Section 9.6, 1, 2, 3, 4 and 5.
  Section 9.7, 1, 2 and 3.
• Problem set 7, due Monday, April 19. Exercises from Trappe:
  Section 12.4, 1, 2, 3, 4, 7, and 8.
  Section 12.4, 1, 2 and 3. (Please use Python for you calculations)
• Problem set 8, due Friday, April 30 (last day of class)
  Section 16.7, 1, 2, 3, 6, 11, 12, 13. (Note: extra credit for 11(d)).
  Section 16.8, 1, 2, 3, 4.

Practicum and Writing Credit

• For opt-in writing credit, two reports of books relating to computer security, cryptography, cyperwarfare, cyber-utopianism or cyber-dystopianism;
  • For instance, several books tage Bletchly Park are good historical cryptography books for thie project: The Hut 6 Story, Code Breakers: In inside story of Bletchly Park, Between Silk and Cyanide
  • The American Black Chamber
  • Diamond Age or other cyberpunk, and probably some steampunk, it it is sufficiently focused on the impact of cyberspace and how cryptography is relevant.
• For optional Practicum, explore the attack against WEP.
  • Read and implement the RC4 cipher.
  • Attacks on RC4 and WEP, Fluhrer, Mantin, Shamir, Cryptobytes Vol 5., No. 2, 2002, pp 26-34.
  • Korek attacks
  • Weakness in the Key Scheduling Algorithm of RC4 Scott Fluhrer, Itsik Mantin, Adi Shamir.
  • Using the Fluhrer, Mantin, and Shamir Attack to Break WEP Adam Stubblefield, John Ioannidis, Aviel Rubin.
  • Write a program that identifies weak keys and extracts keys. (see weakkeys.c for a general idea).

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