News!

• Final: Wednesday, April 30, at 11:00–1:30 in our usual classroom.
  Final (PDF)
• Midterm: Wednesday, March 19th.
  • Test and solutions
  • Histogram (Vertical is points from 0 to 25;
    horizontal is one box per person with that grade.)
• Draft of two writing credit papers: Wednesday, March 19th.
• No class Friday, January 24.

Assignments

• Problem set 1, due Friday, Jan 31
  • 1.1, 1.2, 1.5, 1.6, 1.7 and 1.8.
• Problem set 2, due Friday, February 7
  • 1.9, 1.13 and 1.14.
  • 2.4.
• Problem set 3, due Monday, February 17
  • 2.6, 2.8, 2.9, 2.10, 2.12.
• Problem set 4, due Monday, February 24
  • Write pseudo-code for the space-time tradeoff that shows that 3 DES keys only gives the security of 2 DES keys, using 2⁶⁴ space.
  • Write pseudo-code for the hash chain attack against any encryption. You may use "symbolic" calls such as "isEndHashChain(k)" which yields true if the key k is predicted to be in the collection of hash-chain start/ends; as well as calls getStartOfHashChain(k) which returns the start of the hash chain that ends with k if isEndHashChain(k) is true, or a special undefined symbol if k is not of that form, or if there is no matching start key.
  • 3.1, 3.3, 3.4, 3.5, and 3.6.
• Problem set 5, due Monday, March 17.
  • Please study chapter 4
  • 4.2, 4.3, 4.4, 4.5, 4.6, 4.7, 4.10 and 4.11
  • Nothing from chapter 5.
• Midterm: Wednesday, March 19th.
• Problem set 6, due Monday, March 31.
  • Problems 7.5, 7.6, 7.8, 7.9, 7.10, 7.11, 7.12, 7.13.
• Problem set 7, due Monday, April 7.
  • Problems 8.1 through 8.8.
• Problem set 8, due Friday, April 25.
  • Problems 9.5, 9.7, 9.9, 10.5, 10.10, 10.14, 10.16.

Syllabus

• See older courses an idea about this course.
• Required textbook for both Csc 507 and 609 students: Understanding Cryptography: A textbook for students and practitioners, by Paar and Pelzl.
• Sign up for Csc402-01 for the 1 credit practicum. This entails some programing assignments related to class material.
• Homework: Weekly assignments count for 30% of the grade.
• Grader: there is no grader for this course.
• Midterm: The midterm counts for 30% of the grade.
• Final: An in-class final counts for 40% of the grade.
• Twitter (for updates on homework postings): csc609
• class blog
• Additional books of interest:
  • The Handbook of Applied Cryptography by Menezes, van Oorschot and Vanstone
  • Introduction to Cryptography with Coding Theory by Trappe and Washington.
  • Codes and Cryptography by Dominic Welsh.

Class Notes

• Introduction
  • Crypto talk
• Symmetic Ciphers
  • Codes, ciphers and steganography
  • Substitution, transposition, playfair
  • Vignere
    • cracking vignere
  • The Enigma
• Stream ciphers and perfect secrecy
  • Shannon's theorem for perfect secrecy, probability distribution as "knowledge".
  • One Time Pad and Pseudorandomness
  • Pseudorandomness and shift register PRNG's.
  • linear PRNG
  • Trivium, RC4
• Basic number theory
  • Extended GCD with Python.
  • Polynomials with coefficients mod 2, modulo a polynomial: Z₂[x]/g.
• Block 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
  • Counter mode, Message Authentication Code (MAC)
    • Checksums, malleability, and the MAC-attack on WEP.
• AES
  • Galois fields, irreducible polynomials
• Public Key and RSA
  • Introduction to public key: RSA, DLOG, Elliptic Curves
  • Euler Phi function, Little Fermat for general n
  • The RSA assumption, factoring, and the calculation of Phi(n)
    • Phi(n) and n computes p and q
    • Proof of Little Fermat and (almost) Euler's.
  • RSA
  • Cautionary tales: Chinese Remainder Theorem and pad prime number generation
  • Implementation: Fast Exponentiation
  • Optimal Asymmetric Encryption Padding (OAEP)
  • Fermat test and Carmichael numbers
  • Miller-Rabin test (Kleinberg at Cornell) (cached copy)
• Discrete Logs
  • Generators and primitive roots
  • Diffie-Hellman
  • El Gamal encryption
  • Bit commitment using Discrete Logs
  • Bit security of discrete logs
    • Quadratic Residue and Legendre Symbol
    • Square roots for primes 3 mod 4 (see blog)
    • Bit security for primes 3 mod 4
    • Square roots for otherwise (see blog)
    • Bit security for primes p-1=2^t s for t>1 (see blog)
    • Generalized: Pohlig-Hellman disclosures
  • programs
• Eliptic curve cryptography
• Hash functions and signatures
  • cyptographic strength: pre-image, strongly and weakly collision-free
  • Random oracle model
  • Merkle-Damgard construction
  • SHA-1
  • RSA and El Gamal.
  • DSA and subgroups.
  • ECDSA Certicom
• Additional topics
  • Secret Sharing, xor k or k, Shamir's k of n, Lagrange polynomials
  • Digital Cash, Chaum's construction (blog), BitCoin
  • Practicum presentations, in class.

Practicum

• Optional practicum. Sign up for Csc402-01.
• Project 1: Make the on-board LED on the Arudino Micro blink Hello World in morse code.
  1. Buy stuff. Go to adafruit.com and purchase:
     1. this Arduino Micro with headers;
     2. this full sized breadboard;
     3. this breadboarding wire bundle;
     4. and this USB cable, micro to A
  2. Down and install the Arduino IDE
  3. Download and install the FTDI drivers
     Hint: You need the drivers, even if you are a OSX user. They don't ship with the Arduino IDE install.
  4. Put the Arduino in the breadboard so that the board straddles the center groove; attach the USB cable;
     Hint: Exercise care when removing the Arduino from the breadboard. One end or the other tends to come up first, and that bends the pins of the end that stays inserted. Use an item to insert between the Arduino board and the breadboard and gently unseat the Arduino, working alternately and evenly on the two ends.
  5. Start up the Arduino IDE and select the blink sample program, select board type and serial board.
     Hint: The IDE provides for selection of the serial port and the board. For the serial port, select the one with an unrecognizable sequence of letters as it's name. There are two options among them, I think either works. The exact Arduino type should be listed in the pulldown.
  6. Upload and watch the blinking (on board) light.
  7. Go to the official Arduino Micro page and get the board schematic. Try to find the LED that is blinking on the schematic.
  8. See this helpful guide as well.
  9. Hook up and LED and resistor (ask for them in class) to the same pin as the onboard LED.
  10. Write the program that blinks "Hello World" in Morse Code.
• Project 2: Partner and create an encrypted authenticated channel between the two Ardunos
  • Implement Trivium as the cipher.
  • Use the following electronic protocol to send and receive data:
    1. Agree on three pins, DATA, MASTER-CLOCK, SLAVE-CLOCK.
    2. Data flows from master to slave. The master sets DATA and MASTER-CLOCK pins to output and SLAVE-CLOCK to input.
    3. Conversely, the slave sets DATA and MASTER-CLOCK pins to input and SLAVE-CLOCK to output.
    4. Begin with both clock pins a False (0) and DATA at don't care.
    5. Master sets DATA pin according to bit of data that sets MASTER-CLOCK pin high.
    6. Slave waits for MASTER-CLOCK pin to go high; then reads the DATA pin; then sets SLAVE-CLOCK pin high.
    7. Master waits for SLAVE-CLOCK bin to go high; then sets MASTER-CLOCK pin low;
    8. Slave waits for MASTER-CLOCK pin to go low; then sets SLAVE-CLOCK pin to low; then the slave is done with this bit transfer (goes back to step 4).
    9. Master waits for SLAVE-CLOCK pin to go low; then the master is done with this bit transfer (goest back to step 4).
  • Use the serial line to communicate from the computer to the master, and from the slave to the computer, using a terminal window.
  • Consider issues of data framing and format: LSB first? How does the slave know the start and end of a byte?
• Project 3:
  • Implement RC4 and MD5.
  • Use SPI rather than the hand-written serial protocol of Project 2.
  • Include integrity check using MD5 and a MAC.

Writing Credit

• For opt-in writing credit, three 1500 word papers, one at least due by the midterm.
• Suggested topics: 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.

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

• Nova: Decoding Nazi Secrets
• 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)
• The best known SPRP bases

SliceOfLife

• Helger Lipmaa Notes
• mersenne.org, and Prime network
• Random dot org: a supply of random numbers.
• The NIST Beacon
• Van Eck radiation (security, not crypto, but an enjoyable group of pages anyway.)