CS456/CS556 Cryptography

CS456/CS556 Cryptography (Spring 2026)

Pre-requisites: CS142, MA211.
Programming skills and mathematical curiosity.

Instructor: Christino Tamon
Lecture: TR 8:00-9:15 (SC162)
Office hours: TR 9:15-11:15, W 1-3 (SC373).

SYLLABUS
Cryptography is the study of secure communication over insecure channels. We will study the basic methods and concepts in cryptography along with their applications. The course will look at well-known modern cryptographic systems such as RSA, Diffie-Hellman, and elliptic curve cryptography.

Most of these topics require background in number theory and probability theory. The first part of the course will be spent on developing the necessary background in these areas. The second part of the course is spent on the applications of these to building cryptographic tools.

An underlying theme of this course is the rise and "fall" of the RSA system. Theoretical properties and improvements of the RSA system will be discussed in detail. Then a discussion of Shor's quantum algorithm for factoring will be described. Finally, a brief look at quantum cryptography will be given.

GRADING: Assignments and Quizzes (40%), Midterm (20%), Final (40%).

TEXT: (recommended but not required)
A. Menezes, van Oorschot, S. Vanstone, Handbook of Applied Cryptography, CRC Press. link.

OTHER:
D. Boneh, V. Shoup, A Graduate Course in Applied Cryptography, link.
D. Angluin, "Lecture Notes on the Complexity of Some Problems in Number Theory", Technical Report #243, Yale University, 1982.

OBJECTIVES/OUTCOMES:
The objective of this course is to learn fundamental issues and important algorithms involved in the field of cryptography.

The specific outcomes are as follows:

Knowledge of some secret-key cryptographic systems.
Knowledge of important ideas in public-key cryptographic systems.
Knowledge of basic ideas in number theory that are relevant to cryptography.
Knowledge of various cryptographic protocols for implementing different types of communication that requires secrecy and protection.
Knowledge of modern programming languages with support for cryptographic applications.

REQUIREMENTS/POLICIES:

Students are responsible for all course materials covered in lectures and any exams given during class periods. Students that need to make up missing course work must provide the required Clarkson official exempt form. All students must submit their own work; the exchange of ideas are encouraged but ultimately the submitted work must be the student's own. Please refer to the Clarkson University Regulations for more guidelines on academic integrity and related matters.

Schedule (updated regularly)

Secret-key systems: One-time pad. Unconditional security.
Public-key system: RSA (sample). Modular exponentiation (encryption and decryption). Random prime generation. Pairs of complementary keys. ElGamal (sample). Elliptic Curve ElGamal (sample). Quadratic Residue (sample). Lattice cryptography (GGH system).
Number theoretic tools: primes, modular arithmetic, division algorithm, Euclid's theorems (abundance of primes, recursive algorithm for GCD), Aryabhata's Pulverizer, Chinese Remainder Theorem, Fermat's Little Theorem (Euler's generalization).
Quantum cryptography and algorithms: BB84 key exchange protocol, Shor's algorithm (Deutsch-Josza, Bernstein-Vazirani, Simon).
Reference: S. Gudder, "Quantum computation", The American Mathematical Monthly, 2003.

Optional Notes (based on notes for a course taught at Harvey Mudd)

0: One-time Pad
1: Shannon's Theory
2: Basic Number Theory
3: RSA PKCS
4: ElGamal PKCS
5: Elliptic Curves
6: PKCS Based on Quadratic Residues
7: Miscellaneous Protocols
8: DES & AES
9: Quantum Ideas

Schedule (tentative)

Jan 6	Jan 8 One-time pad: shared random string symmetric, secret-key. Unconditionally secure.
Jan 13 RSA: protocol. Number theory is useful.	Jan 15 RSA: protocol. Random primes, integer multiplication, modular exponentiation. The mysterious Pulverizer of Aryabhata. Alice, Bob and Eve in RSA-land.
Jan 20 RSA: basic number theory. Extended Euclidean algorithm (Pulverizer of Aryabhata): recursive vs iterative (space-efficient).	Jan 22 RSA: basic number theory. Modular arithmetic. Inverses modulo prime.
Jan 27 RSA: Fermat's Little Theorem.	Jan 29 RSA: Miller-Rabin primality testing. Nontrivial square roots of unity.
Feb 3 RSA: correctness (wrong proof via Euler-Fermat). Chinese Remainder Theorem (correct proof): parallel decryption. Exercise: worksheet.	Feb 5 RSA: summary.
Feb 10 RSA: weaknesses and attacks.	Feb 12 RSA: weaknesses and attacks.
Feb 17 Discrete Logarithm: Diffie-Hellman.	Feb 19 Short break.
Feb 24 ElGamal: probabilistic public-key. Sample problem.	Feb 26 ElGamal: Finding generators.
Mar 3 ElGamal: Elliptic Curves. Sample problem.	Mar 5 Midterm (in class).
Mar 10 Block cipher: Modes of encryption: ECB, CBC, OFB, CFB. DES. Feistel cipher.	Mar 12 Block cipher:AES AES: polynomials over finite fields. Pulverizer over polynomials.
Mar 17 Spring break.	Mar 19 Spring break.
Mar 24 Beyond RSA: Rabin: modular square root (is equivalent to factoring). Quadratic residues: Legendre and Jacobi symbols. Euler's criterion. Reference: notes by Angluin.	Mar 26 Goldwasser-Micali cryptosystem. Semantic security. Quadratic Residuosity.
Mar 31 Blum-Goldwasser cryptosystem. Blum integers: primes congruent to 3 mod 4. Reading: sample.	Apr 2 Blum-Blum-Shub pseudorandom bit generator.
Apr 7 Protocol: Zero-knowledge proofs (Goldwasser-Micali-Rackoff). Fiat-Shamir's Quadratic Residue protocol. Reading: Tompa.	Apr 9 Protocols: coin tossing, oblivious transfer, bit commitment. Yao's millionaiers problem. Secret sharing. Exercises: sample (sol)
Apr 14 Post-quantum: Lattice cryptography. Source: notes (Peikert).	Apr 16 Lattice cryptography: LLL algorithm. Source: notes (Peikert).
Apr 21 Quantum cryptography	Apr 23 BB84: quantum key distribution protocol

ASSIGNMENTS

Assignment 0
Assignment 1 . (RSA-4096)
Assignment 2 . (SaferRSA-4096) clue?
Assignment 3 . (ElGamal-safe1024 [halfmask,cipher])
Assignment 4 . (Elliptic-Curve-ElGamal-1024 [cipher,halfmask])

Topics

Real-world: SSL, [Georgiev et al] (attack); SSH; GNU PGP, PGPi, MIT site, Zimmerman; Logjam attack.
Secure Hash Algorithm (SHA): RFC, Schneier; SHA-3 (Keccak). Hashing: [Halevi et al];
RSA: PKCS#11; [Brumley-Boneh] (timing attacks); [Bleichenbacher] (attack on PKCS#1).
Elliptic curves: [Lauter]; [Koblitz et al] (survey); Sage support; J2ME;
Lattice cryptography: [Nguyen-Regev] (attack on signature scheme), [Nguyen]; talk by Peikert; Quanta article.
Homomorphic encryption: [Gentry] (PhD thesis), [Lauter et al] (practicality), [Gentry-Halevi], github.
Zero Knowledge Proofs: [Feige-Fiat-Shamir]; [Blum et al.] (non-interactive ZKP).
Quantum Cryptography: BB84; ACM Survey (Bruss et al); Shor-Preskill;
Bell nonlocality: [Buhrman-Cleve-Massar-deWolf]; [Hanggi-Renner-Wolf]
Byzantine agreement: [Arora] (Rabin's algorithm); [Lamport] (leaderless).
Miscellany: McEliece cryptosystem (quantum-resistant). Merkle-Hellman cryptosystem (precursor to Diffie-Hellman). Authentication protocols.
More: Mental Poker. Identity-based encryption.

RESOURCES/LINKS:

Crypto programming support: Java, NTL, Python.
Crypto archive: arXiv.
Miscellany: blunders; cartoon guide to AES; ACM Turing award; Quantum: IBMQ.
A few crypto sources:
1. S. Gudder, "Quantum computation", The American Mathematical Monthly, March ,2003.
2. D. Coppersmith, "Cryptography", IBM J. Res. Develop., vol. 44, no. 1/2, 2000.
3. S. Landau, "Standing the test of time: The Data Encryption Standard", Notices of the AMS, vol. 47, no. 3, pp341-349, 2000.
4. D. Angluin, "Lecture Notes on the Complexity of Some Problems in Number Theory", TR #243, 1982, Yale.
5. C. Pomerance, "A Tale of Two Sieves," Notices of the AMS, vol. 12, 1996.
6. J. Quisquater et al., "How to Explain Zero-Knowledge Protocols to Your Children," Advances in Cryptology, pp. 628-631, 1989.
7. D. Boneh, "Twenty Years of Attack on the RSA Cryptosystem," Notices of the AMS, vol. 46, no. 2, 203-213, 1999.
8. M. Agarwal, N. Kayal, N. Saxena, "PRIMES in P" (appeared in Annals of Mathematics).
9. K. Lauter, "The advantages of elliptic curve cryptography for wireless security," IEEE Wireless Communications, vol. 11, no. 1, 62-67, 2004.
10. Elliptic curves: Sage examples. NIST .