The Kryptos Sculpture, Langley, VA.

CSC507/609-G: Cryptography

by: burt rosenberg
at: university of miami
semester: fall 2025 (261)
time: MoWeFr 2:30–3:20
location: Knight Physics 108.

Calendar:

Wed, Oct 8:

Midterm

Wed, Sep 17:

Exercise 2 released

Fri, Sep 5:

Exercise 1 released

Mon, Aug 18:

Class begins.

Table of Contents:

• Syllabus
• Reading Assignments
• Frightful Fridays
• Assignments
• Class Notes
• Books
• Other resources
• Attacks
• References

Reading Assignments:

1. Please chapters 1 and 2 in Katz and Lindell (2nd ed. numbering)

Frightful Fridays:

Assignments:

• Exercse 1: Bayes, Perfect Secrecy, code breaking.
  Due: Wednesday, 17-th of September.
• Exercise 2: Galois Fields and Stream ciphers
  Due: Wednesday, 1-st of October.

Syllabus:

• Textbooks:
  • Required: Introduction to Modern Cryptography, by Jonathan Katz and Yehuda Lindell. (Amazon)
    The 3ird addition is a great new edition. However, for this class, either the 3ird or the 2nd edition will be fine.
  • Additional books of interest:
    • The Theory of Hash Functions and Random Oracles, by Arno Mittelbach and Marc Fischlin
    • Cryptography Made Simple by Nigel Smart.
    • The Handbook of Applied Cryptography by Menezes, van Oorschot and Vanstone
• Slack:
  • Join us on csc-courses/slack, channel #csc507-261.
• Homework and Grading:
  • Homework: Programming assignments count for 30% of the grade. Due at midnight local time.
  • Lateness of Programming:
    • Three days grace.
    • After 3 days, 2 points lateness.
    • After 5 days, 5 points lateness.
    • No points at and after the start of the reading period.
  • Midterm: The midterm counts for 30% of the grade.
  • Final: An in-class final counts for 40% of the grade.
• Computer Needs:
  • The class uses github classroom. You will need a github account.
  • Install jupyter, python, make and git and github (Anaconda recommends. It's free.)
• Honor Code:
  • Class participants read and accept the University Honor Code, available from the Dean of Students.
  • Work resulting from an integrity violation will not be graded. A no-grade arising in this way can be numerically distinct from a zero.
• Who will help you:
  • The TA is Dewan Tauhid Rahman. He is mainly to help with technical issues, not so much content.

Class Notes:

Classical Encryption (up to WWII)

• Encryption, History, and Politics: Crypto talk
• Codes, ciphers and steganography
• Substitution, transposition, playfair
  • Cracking substitutions
  • Fun game: try the above link on the enciphered word "november" and "asdlkjvb"
  • Think about how texts shorter then a fresh keyword have ambiguous decipherings.
• Vignere
  • cracking vignere
• Playfair and example cryptanalysis
• The Enigma
• References
  • Norbert Biermann, Analysis of Giouan Battista Bellaso's cipher challenges of 1555, Cryptologia Volume 42, 2018 - Issue 5. doi.org/10.1080/01611194.2017.1422050
  • Sanborn artworks, scroll down for Kryptos.
  • Cicada 3301

Modern Symmetric Cryptography

• Shannon perfect secrecy definition
  • Eavesdropping model; "knowledge" and the Bayesian probability framework.
  • One Time Pad, a.k.a., Vernam Cipher
  • US Patent US1310719, July 22, 1919.
  • Communication Theory of Secrecy Systems by Claude E. Shannon (1949)
• Complexity based cryptography
  • Perfect Secrecy & Adversarial Indistinguishability, (bjr updated 2025)
  • Complexity classes: notes (sept 2003, updated sept 2025)
  • A review of Big-Oh notation. (bjr 2007)
  • Composites are in RP.
• Theoretical Fondations of Encryption
  • Pseudorandom vernam ciphers
  • Pseudorandom Functions and CPA Security
  • Authentication and Chosen Ciphertext Attacks
  • Equivalence of PRG, PRF and PRP's.

Authenticated Encryption and Hashing

• Hashing
  • The Random Oracle model
  • Hash functions and encryption
  • Mathematical framework and security definitions
  • Collision free, 2nd pre-image resistance, pre-image resistance.
  • Cryptographic Hash Functions: OFB and the Davis-Meyer construction.
  • Merkle-Damgard construction
• Practical CPA-Security
  • Implementation of CPA strong cipher
  • Initial vectors
  • Modes of operation
    • Encryption: CBC, CFB, OFB
    • Decryption: CBC
    • counter mode, GCM
  • The limitations of the CPA model.
    • Malleability
    • Truncation attacks, replay attacks, reordering attacks
• Practical CCA-Security
  • Chosen Ciphertext Attack
  • Message Authentication Codes (MAC)
  • Message forgery models
  • CBC-MAC
  • Authenticated Encryption
  • Implementation of CCA strong cipher
• Block ciphers and Shift ciphers

Public Key Cryptography

• Introduction to Public Key
  • The New Directions paper.
  • GCHQ, James Ellis, Clifford Cocks and Malcolm Williamson.
  • Needham-Schroeder
  • Discrete Logs
  • Diffie-Hellman Key Exchange
• El Gamal Systems
  • El Gamal encryption, and reduction of El Gamal to DDH
  • Quadratic Residue attacks, and extensions to other prime powers (python)
  • Bit Commitment
• RSA Systems
  • Integer factoring and the RSA hardness assumption.
  • OAEP
• KEM/DEM (EAV secret scheme is sufficient)
• Adversarial indistinguishability: Diagram
  • Perfect secrecy is impossible
  • Deterministic public key schemes are insecure under any model.
  • Ease-dropping security is the same as CPA security.

Zero Knowledge Proof Systems

• Schnorr Signatures and bit commitment
  • Definition, and adversary
  • Identification schemes, perfect correctness and probabilistic soundness
  • Schnorr identification, and knowledge extraction
  • Fiat-Shamir transformation and Schnorr dig-sig's
• 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
• Fiat-Shamir zero-knowledge identification system
• References
  • The Knowledge Complexity of Interactive Proof-Systems, Goldwasser, Micali and Rackoff. The FoCS (1985) paper and the final SIAM J.Comp 1(989) journal version.
  • Proofs that Yield Nothing But Their Validity, or All Languages in NP Have Zero-Knowledge Proof Systems, Goldreich, Micali, Wigderson (JACM 1991)
  • How To Play Any Mental Game (SToC 1987)

Card based cryptography (playing cards and manual methods)

• Simple demonstration of ZK with a deck of cards.
• Practical Card-based Cryptography, Takaaki Mizuki and Hiroki Shizuya
• Computations with a deck of cards, Anton Stiglic
• Multiparty computation without computers Niemi and Renvall

Books:

• Elementary Military Cryptography William F. Friedman.
• Lecture Notes on Cryptography by Goldwasser and Bellare.
• 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)
• Oorshot and Vanstone, Handbook of Applied Cryptography (Univ of Waterloo, D/L)
• Leo Marx, Between Silk and Cyanide, (Amazon)
• Frank Rowlett, The Story of Magic, Memoirs of an American Cryptologic Pioneer, (Amazon)
• Herbert Yardley, The American Black Chamber, (Amazon)
• Helen Gaines, Cryptanalysis: A Study of Ciphers and Their Solution, (Amazon)

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

Attacks:

• WEP attacks
  • FMS attack on WEP realized
  • Korek WEP flaws
  • Korek's Chopper attacks against WEP.
• Side channel attacks
  • Timing attack on an XBOX signature.
  • Timing attacks on RSA, by Paul Kocher
  • Power analysis on smart cards, also by Paul Kocher
  • Covert channel using cache hits, see e.g. Osvik, Shamir and Tromer
• Proof of the 4 square roots in an RSA modulus.
  1. Square the relation sq+rp=1.
  2. Mod pq inner terms cancel, and outer terms are invariant to signs of s and r.
  3. So all the following will square to 1: ±(sq ± rp).
  4. The non-trivial square roots of one are ±(sq − rp).

References:

• Pascal Junod, Cryptographic Secure Psudo-Random Bit Generation: The Blum-Blum-Shub Generator.
• 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 protocols, 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)
• 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
• MIT 6.876, Course in Cryptographic Game Theory.
• Van Eck radiation (security, not crypto, but an enjoyable group of pages anyway.)
• Trust agility, replace the CA system with Moxie Marklinspike and Whitfield Diffie.
• 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.
• Analysis of the popular linear congruential generator
• The Boxentriq site and its Cryptogram solver

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

author: burton rosenberg
created: 21 jan 2018
update: 10 sep 2025