The Kryptos Sculpture, Langley, VA.

CSC507/609-C: Cryptography

by: burt rosenberg
at: university of miami
semester: fall 2023 (241)
time: MWF 10:10am–11:00am
location: Dooly Memorial 203 107.

Calendar:

Dec 13:

Final (Wednesday) 11:00–1:30

Oct 20:

Midterm

Sep 1:

Zoom link for Friday's class Zoom!

Aug 30:

Zoom link for Wednesday's class.

TA's hours are announced (see Syllabus)

Aug 28:

Zoom link for monday's class.

Aug 23:

Meet on slack (abridged meeting)

Aug 21:

Zoom link for monday's class.

Join the class slack channel csc-courses.slack.com, #csc507-241.

The academic calendar

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. Read the notes Perfect Secrecy and Adversarial Indistinguishability
3. Please read chapter 3 in Katz and Lindell (2nd ed. numbering) through section 3.5.
4. Read the notes Pseudorandomness and Stream Ciphers
5. Read the notes Pseudorandom Functions and CPA Security
6. Please read section 3.7 and chapter 4, except 4.4 and 4.6.
7. Read the notes Authentication and Chosen Ciphertext Attacks
8. Please read sections 3.6 and 4.4.
9. Please read chapter 5.
10. Read the notes The Euclidean algorithm and its consequences
11. Please read section 8.1.
12. Please read section 8.2.
13. Please read section 8.3; review chapters 11.1–11.3; and read chapaters 11.4–11.5.
14. Read the notes Signatures and Zero Knowledge proofs
15. Please read chapter 12.

Frightful Fridays:

• Frightful October 6: Blockchain

Assignments:

• Project 1: Coding Vigenere.
  Due: Friday, Sept 1. (extended grace period until Wednesday)
• Project 2: Breaking Vigenere.
  Due: Wednesday, Sept 20. (to resubmit for the secret word: Oct 4).
• Project 3: Adversarial Indistinguishability.
  You will receive a github classroom invitation for this assignment.
  Due: Wednesday, Oct 4 Wednesday, Oct 11.
• Midterm: Friday, Oct 20.
• Final: Wednesday, Dec 13, 11:00–1:30.

Syllabus:

• This is a first course on formal cryptography with the goal of answering important questions about the "why" of cryptographic techniques.
• Computational models are presented of both the "good guys" and the "bad guys" and techniques for reasoning about the models and their interactions.
• The nature of randomness, information and knowledge is explored, and computational and informational model variants are introduced.
• The course emphasizes a computational approach where programming exercises practice the conceptual and mathematical framework.

• Textbooks and slack:
  • 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 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.
  • Join us on slack and post to #csc507-241.
• Homework and Grading:
  • Homework: Programming assignments count for 30% of the grade. Due at midnight local time.
  • Lateness of Programming: deduct 1 point after 3 days, a 2nd point after 10 days, etc.
  • Midterm: The midterm counts for 30% of the grade.
  • Final: An in-class final counts for 40% of the grade.
• Computer Needs:
  • The computer work will use jupyter, python, make and git and github.
  • Install anaconda.
  • To work with github, OSX and Linux users can you the command line.
  • For windows users, I find gitbash the easiest. That's because it gives a bash shell, that I am familiar with.
  • There is also GitHub desktop, but I am less familiar with that.
• 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:
  • Our TA is Satyarth Arora, sxa1654@miami.edu; Tuesday 3:30–6:00 and Thursday 4:00–5:30.

Class Notes:

• Monday, 28 aug.
  • Shannon's model of the cryptographic channel;
  • the entropy equation and some consequences;
  • and the relationship between information, entropy and secrecy.
  • I mentioned that the shannon model is like "bottling privacy". Reminds me of the Cone of Silence.

Classical Encryption

• 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

Complexity based cryptography

• Perfect Secrecy and Adversarial Indistinguishability.
  • Shannon perfect secrecy definition
  • Equivalence of Adversarial Indistinguishability
  • Eavesdropping model; "knowledge" and the Bayesian probability framework.
  • One Time Pad
  • Shannon's theorem for perfect secrecy.
• Pseudorandom Generators
  • Adversarial indistinguishability games
  • The eaves-dropper attack model
  • Pseudorandomness and PPT distinguisher games
  • Stream Ciphers
  • Multiple message attacks and malleability
• Practical CPA-Security
  • Implementation of CPA strong cipher
  • Initial vectors
  • Security reduction proofs
    • Definition of pseudorandom permutation
    • Perfect security when using a random permutation
    • Reduction of breaking PRP Discrimination to breaking CPA Inv.
  • 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
• 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.
  • Analysis of the popular linear congruential generator
  • The Boxentriq site and its Cryptogram solver

Hashing and Blockchains

• 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
• Blockchain
  • The (Real) Blockchain mini-course
  • Lecture 1 Bimetalism and the Free Silver Movement
  • Lecture 2 If Blockchain is so good, why is everyone in jail?
  • Lecture 3 The mechanics of Bitcoin (The Audacity of Nope)
  • Lecture 4 The impossible and doing the impossible
  • Lecture 5 Authorizing the transaction
  • Lecture 6 The strange and twisty math
  • Lecture 7 Alt Coins
  • Lecture 8 Proof of Stake
• References
  • Bitcoin.it
    • Block hash algorithm
    • transactions
  • The Genesis Block
  • Mastering Bitcoin
  • Princeton Bitcoin

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.

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

author: burton rosenberg
created: 21 jan 2018
update: 4 dec 2023