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:

Fri, Dec 5:

Final exam: 2:00pm–4:30pm

Mon, Nov 24:

Meet by Zoom; topic: final review; See Slack for the invite.

Fri, Oct 16:

Midterm histogram

Fri, Oct 10:

Midterm review (answers on slack)

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)
2. Chapters 3, 4 (but not 4.6) and 5 (but not 5.4) in Katz and Lindell (2nd ed. numbering).
3. Sections 7.4, 7.5 and 7.6 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.
• Execise 3: Public Key Cryptosystems
  Due: Wednesday, 26 of November. (thanksgiving break)

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)

• There is no substitution for an old cipher.
• 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

Pseudorandomness and Symmetric Encryption

• This course is so pseudorandom …
• 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
  • A review of Big-Oh notation. (bjr 2007)
  • Simple, Simon and Sage discuss complexity classes.
  • Composites are in RP.
  • Perfect Secrecy & Adversarial Indistinguishability
• Theoretical Fondations of Encryption
  • Pseudorandomness and stream ciphers (the Vernon cipher, a.k.a. OTP)
  • Pseudorandom Functions and CPA Security
  • Authentication and Chosen Ciphertext Attacks
  • Equivalence of PRG, PRF and PRP's.

Practical Symmetric Encryption

• You are going to make a hash of it!
• CPA-Secure ciphers
  • No deterministic encryption is CPA secure
  • Initial vectors
  • Modes of operation for multiblock messages
    • Encryption: CBC, CFB, OFB
    • Decryption: CBC
    • Counter mode
• CCA-Secure ciphers
  • No malleable encryption on its own is CCA secure
  • Message Authentication Codes (MAC)
    • Existential Unforgeability under Chosen Message Attack
    • Encrypt-then-MAC
    • MAC-then-Encrypt
    • Encrypt-and-MAC
  • CBC-MAC, GCM
  • Length extension attacks
• Hashing
  • Hash function notes (in progress)
  • The Random Oracle model
  • Collision free, 2nd pre-image resistance, pre-image resistance.
  • Keyed Hash functions: Encrypting with a Hash function
  • PRP to Hash functions: Davis-Meyer construction.
  • Merkle-Damgard construction
  • MAC with hash functions: HMAC

Public Key Cryptography

• We will have to go public with this.
• Introduction to Public Key
  • The New Directions paper.
  • GCHQ, James Ellis, Clifford Cocks and Malcolm Williamson.
  • Perfect secrecy is impossible
  • Deterministic public key schemes are insecure under any model.
  • Ease-dropping security is the same as CPA security.
• Discrete Log Systems
  • Quadratic Residue attacks, and extensions to other prime powers (python)
  • Diffie-Hellman Key Exchange
  • El Gamal encryption, and reduction of El Gamal to DDH
  • Elliptic curves
  • Signatures
  • Fujisaki-Okamoto CCA transformation
• RSA Systems
  • Integer factoring and the RSA hardness assumption.
  • OAEP
• KEM/DEM (EAV secret scheme is sufficient)
• The adversary round-up.

Zero Knowledge Proof Systems

• You had to be there.
• Interactive proofs and zero-knowledge
• Interactive Proof systems
  • Completeness, and soundness
  • Graph Non-isomorphism is in IP
• Zero knowledge
  • ZK proof for Graph Isomorphism
  • Simulator of the View, and consequences
• Zero Knowledge proof of Knowledge
  • Quadratic residues and the complexity of taking roots.
  • Fiat-Shamir zero-knowledge identification system
• Bit commitment (Notes)
  • Perfect binding.
    • Blum-Micali-Naor commitments
    • ElGamal commitments
  • Perfect hiding: Pedersen commitments
  • All of NP in Zero Knowledge: 3-colorability

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:

• IP and Zero Knowledge
  • 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,
    Goldreich, Micali, Wigderson (SToC 1987)
• 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: 26 sep 2025