The Kryptos Sculpture, Langley, VA.

CSC507/609-C: Cryptography

by: burt rosenberg
at: university of miami
semester: spring 2018 (182)
time: MW 10:10 AM – 11:00 AM
location: Whitten LC 140

News:

• No news is good news.

Assignments:

• Project 1: Cracking Vigenere.
  Due: Monday, February 5.
• Project 2: Adversary Games.
  Due: Monday, February 26.
• Project 3: Attacking Authenticated Encryption.
  Due: Monday, March 19.
• Project 3-bis, due date extension for problem 2.
  Due: Monday, March 26.
• Project 4: Exercises in RSA.
  Due: Friday, April 13.
• Project 5: Exercises in Discrete Logs.
  Due: Friday, April 27.

Syllabus:

• Required textbook for both Csc 507 and 609 students:
  Introduction to Modern Cryptography,
  (Chapman & Hall/CRC Cryptography and Network Security Series) 2nd Edition,
  by Jonathan Katz and Yehuda Lindell.
  ((Amazon))
• 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.
• Homework: Weekly assignments count for 30% of the grade.
• Midterm: The midterm counts for 30% of the grade.
• Final: An in-class final counts for 40% of the grade.
• TA: Kyle Poore
• You will be using subversion to submit your python work. Please see my Subversion tutorial
• The projects will also use make. Windows users should install Cygwin, and select for install at least subversion, make, and python.
• Compare the princeton cos433

Class Notes:

• Encryption, History, and Politics
  • Crypto talk
  • Codes, ciphers and steganography
  • Substitution, transposition, playfair
    • Cracking substitutions
  • Vignere
    • cracking vignere
  • The Enigma
• Perfect Secrecy and Adversarial Indistinguishability.
  • Shannon's theorem for perfect secrecy, probability distribution as "knowledge".
  • One Time Pad and Pseudorandomness
  • Class notes
• Security models and Reductions
  • Eavesdropping Attack
  • Multiple Message Attack
  • Chosen Plaintest Attack
  • Chosen Ciphertext Attack
  • Semantic Security
  • Ciphers from PRG, and modes of operation
    • in practice: ECB, CBC, CFB, OFB.
    • counter modes
• Pseudorandom Generators and Probabilistic Polynomial Time (PPT) Adversaries
  • Review of Models of Computation and Complexity
  • Pseudorandomness
  • Stream Ciphers
  • PRG's: Linear Feedback Shift Register
• Hash functions and Message Authentication Codes (MAC)
  • cyptographic strength: pre-image, strongly and weakly collision-free
  • Random oracle model
  • Merkle-Damgard construction
  • Merkle trees
  • Commitment Schemes
• In practice: Integrity and Authenticated Encryption
• In practice: Bitcoin and the Blockchain
• Modern Ciphers
  • Trivium, RC4
  • Feistal networks.
  • the Digital Encryption Standard: DES
    • The standard: FIPS 46-3
    • S-Box statistics
  • Differential Cryptanalysis (3 round)
  • Multiple encipherment: 3DES and DESX
    • multiple modes
    • 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.
• Key Agreement
  • Needham Schroeder
  • Introduction to public key: DH key exchange
• Background on Diffie-Hellman and Discrete Logs
  • Euler Phi function, Little Fermat for general n
  • Generators and subgroups
  • Quadratic Residue
    • Galois Fields
    • Bit commitment using Discrete Logs
    • Bit security of discrete logs p-1=2^t s for t>1 (see blog)
    • Legendre Symbol
    • Square roots for primes 3 mod 4 (see blog)
    • Square roots for otherwise (see blog)
  • Pohlig-Hellman and disclosures about small subgroups
• Background on RSA and integer factorization
  • Extended GCD with Python or Ruby
  • The RSA assumption, factoring, and the calculation of Phi(n)
  • RSA and Probabilistic Factoring
  • Fermat test and Carmichael numbers
  • Miller-Rabin test (Kleinberg at Cornell) (cached copy)
• Background on Elliptic curves
  • The group law
  • The point at infinity
  • hard problems based on elliptic curves
• Public Key Systems in practice
  • El Gamal encryption
  • Reduction of El Gamal to DDH
  • KEM/DEM
  • CCA El Gamal KEM in the Random Oracle Model
  • RSA
    • Small message attacks
    • chinese remainder attack on a multiply encrypted message
    • related message attack (m and m + D)
    • root-N trick
  • PKCS #1 v1.5 and the Bleichenbacher attack
  • malleability: self-similarity, average case hardness
  • Chaumian Blind signatures
  • Optimal Asymmetric Encryption Padding (OAEP)
    • 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))
• Digital Signatures
  • Definition, and adversary
  • Plain RSA signatures and forgeries
  • RSA-FDH (Full Domain Hash) and reduction to the RSA problem
  • Identification schemes, perfect correctness and probabilistic soundness
  • Schnorr identification, and knowledge extraction
  • Fiat-Shamir transformation and Schnorr dig-sig's
  • Lamport one-time signature based on hash functions.
  • Sigcryption
• Putting it all together:
  • SSL/TLS
• Zero-knowledge Proof Systems
  • Interactive Proof systems
  • Completeness, and soundness
  • Relationship to NP and BPP
  • Graph Non-isomorphism is in IP
  • Zero knowledge, knowledge and information
  • ZK proof for Graph Isomorphism
  • Simulator, role of non-halting for language instances
  • Zero Knowledge proofs of knowledge: modular square root
  • All of NP in Zero Knowledge: 3-colorability
  • References
    • The Knowledge Complexity of Interactive Proof-Systems, Goldwasser, Micali and Rackoff.
      • 1985 version (PDF)
      • SIAM J. Comput 1989 version (PDF)
    • Proofs that Yield Nothing But Their Validity, or All Languages in NP Have Zero-Knowledge Proof Systems, Goldreich, Micali, Wigderson (PDF)
    • How To Play Any Mental Game (PDF)

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.
• Steganographia by Johannes Trithemius (1462-1516)

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.
• Rotonym, what the heck is a rotonym, Will McGugan. A nice Rot-13 implementation in Python.
• Elliptic Curves, John Milne.
• mersenne.org
• Prime network
• Random dot org: a supply of random numbers.
• The NIST Beacon

References:

• Cryptographic Secure Psudo-Random Bit Generation: The Blum-Blum-Shub Generator, Pascal Junod.
• 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)
• MIT 6.876, Course in Cryptographic Game Theory.
• 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
• Helger Lipmaa Notes
• Van Eck radiation (security, not crypto, but an enjoyable group of pages anyway.)

This work is licensed under a Creative Commons Attribution-ShareAlike 3.0 Unported License.

author: burton rosenberg
created: 21 jan 2018
update: 18 apr 2018