CSC507/609-D: Cryptography
Prof. B. Rosenberg
Spring Semester, 2014 (142)
MWF 11:15 PM – 12:05 PM
Memorial 318
News!
- Final: Wednesday, April 30, at 11:00–1:30 in our usual classroom.
- Midterm: Wednesday, March 19th.
- 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
- 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 264 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:
Class Notes
- Introduction
- Symmetic Ciphers
- Codes, ciphers and steganography
- Substitution, transposition, playfair
- 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: Z2[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
- 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.
- Buy stuff. Go to adafruit.com and purchase:
- this Arduino Micro with headers;
- this full sized breadboard;
- this breadboarding wire bundle;
- and this USB cable, micro to A
- Down and install the Arduino IDE
- 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.
- 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.
- 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.
- Upload and watch the blinking (on board) light.
- Go to the official Arduino Micro page
and get the board schematic.
Try to find the LED that is blinking on the schematic.
- See this helpful guide as well.
- Hook up and LED and resistor (ask for them in class) to the same pin as the onboard LED.
- 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:
- Agree on three pins, DATA, MASTER-CLOCK, SLAVE-CLOCK.
- Data flows from master to slave. The master sets DATA and MASTER-CLOCK pins to
output and SLAVE-CLOCK to input.
- Conversely, the slave sets DATA and MASTER-CLOCK pins to input and SLAVE-CLOCK to
output.
- Begin with both clock pins a False (0) and DATA at don't care.
- Master sets DATA pin according to bit of data that sets MASTER-CLOCK pin high.
- Slave waits for MASTER-CLOCK pin to go high; then reads the DATA pin; then
sets SLAVE-CLOCK pin high.
- Master waits for SLAVE-CLOCK bin to go high; then sets MASTER-CLOCK pin low;
- 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).
- 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
Other resources
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