CSC507/609-C: Cryptography
Prof. B. Rosenberg
Spring Semester, 2012 (122)
MWF 10:10-11:00
Memorial 315
Exams:
- Midterm: Friday, March 30th.
- MIDTERM IS HERE
- MIDTERM ANSWERS ARE HERE
- FINAL IS HERE
- Final: takehome. Out the evening of Friday, May 4; due by the end of Monday, May 7.
You can email me or scan and email your answers;
If necessary scan written pages, or you can leave it under my door.
Announcements
-
See older courses an idea about this course.
-
Required textbook for both Csc 507 and 609 students:
Stinson's Cryptography, 3-ird edition
- 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: Mr. Huan Song Fu is your grader.
- 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
- One Time Pad and Pseudorandomness
- 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 (taught embedded in topics where needed)
- GCD
- Chinese Remainder Theorem, Little Fermat
- Euler Phi function, Little Fermat for general n
- Galois fields, irreducible polynomials
- Quadratic residues and the Legendre symbol
- Hash functions
- cyptographic strength: pre-image, strongly and weakly collision-free
- Merkle-Damgard construction
- SHA-1
- Random oracle model
- Message Authentication Codes (MAC)
- Chaum-van Heijst-Pftzmann hashing (solving ax=b(n) when gcd(a,n)!=1)
- Universal Hashing and privacy amplification
- RSA, Primarlity testing and factoring
- Discrete Logs
- El Gamal encryption
- Generators and primitive roots (section 3.7)
- programs
- Pohlig-Hellman
- Bit security of discrete logs
- Signatures
- RSA and El Gamal.
- DSA and subgroups.
- Undeniable signature
- Fail-stop signature
- Pseudorandomness
- Definitions: next bit security, distinguishers
- The security of BBS
- Semantically secure BBS based encryption
- Eliptic curve cryptography
Assignments
- Problem set 1, due Wed, Feb 1
- Read chapter 1 in Stinson's book
- Exercises 1.1, 1.2, 1.5, 1.6, 1.7, 1.8, 1.9, 1.10, 1.11, 1.16, 1.17.
- Problem set 2, due Mon, Feb 6
- Read chapter 2 in Stinson's book
- If needed, resubmit exercises: 1.7, 1.8, 1.9, 1.10, 1.11 (Affine Ciphers)
- Exercises: 1.21, 1.30, 2.1, 2.2 and 2.3.
- Problem set 3, due Wed, Feb 15
- If need be, resubmit exercise 2.3.
- Exercise 2.4, 2.5, 2.8, 2.9.
- Problem set 4, due Fri, Feb 24
- Exercises 3.2, 3.3, 3.4 and 3.8.
- Problem set 5, due Mon, Mar 26
- Exercises 4.9, 4.10 and 4.11.
- Exercises 5.3, 5.4 and 5.6.
- Problem set 6, due Mon, April 9
- Exercises 5.15, 5.16, 5.17, 5.23 and 5.29.
- Problem set 7, due Mon, April 16
- Exercises 6.4, 6.6, 6.10, 6.11 and 6.21.
- Problem set 8, due Mon, April 23
- Exercises 7.3, 7.6, 7.7 and 7.11.
Practicum
- Optional practicum. Sign up for Csc402-01.
- Due dates, February 22, March
19 21, April 4 and April 25.
- Project 0:
- Email me for your class account login and password. You will be working
on the lab machines. You can login remotely using lee.cs.miami.edu.
Your webpages are placed in the public_html subdirectory of your directory
and will appear at http://web.cs.miami.edu/home/loginname,
example: http://web.cs.miami.edu/home/burt
- Read this blog post
about browser programming.
- Read this annotated
DHTML sample. You need to look at the source
to see what's going on.
- Project 1:
- Using Javascript, CSS, and DHTML, design a web page that will
give a graph of character counts and diagram counts for a given text.
- Due: Wednesday February 22.
- Project 2:
- Using what you have done in project 1, make a web page that
encodes and decodes a Vignere cipher.
-
Now include in the page code for breaking Vignere ciphers.
- Due: Wednesday, March 21
- Practicum class discontinued.
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)
SliceOfLife