Instructor: Christino Tamon
Lecture: Science Center 340 MWF 12pm
Office hours: Science Center 373 MW 9-11am, F 10-11am
Pre-requisites: MA211 or MA346, good programming skills and/or mathematical curiosity.
Cryptography is the study of secure communication over insecure channels.
We will study the basic methods and concepts in theoretical cryptography
along with their applications. The course will look at concepts such as
one-way functions and trapdoor permutations
(functions that are easy to compute but computationally hard to invert),
(devices that produces sequences that are computationally random),
(secure systems that require no secret agreement),
one-way hash functions
(tools to authenticate messages and to verify data integrity),
(mechanisms for signing documents),
(convincing a party of an undeniable fact without revealing its proof).
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, mainly number theory. The second part of the course is spent on
the applications of these to building cryptographic tools.
An alternative underlying theme of the course is the rise and fall of the RSA
cryptographic 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 simple quantum cryptography will
- Assignments and Quizzes 40%
- Midterm 20%
- Final exam 40%
- Bruce Schneier. Applied Cryptography. 2nd edition. Wiley, 1996.
- Thomas Cormen, Charles Leiserson, Ronald Rivest, Clifford Stein. An Introduction to Algorithms. 2nd edition. The MIT Press, 2001 (strongly recommended).
- David Bressoud Factorization and Primality Testing. Springer-Verlag, 1989.
- Jonathan Knudsen. Java Cryptography. O'Reilly, 1998. (in ERC library)
- Scott Oaks. Java Security. O'Reilly, 1998. (in ERC library)
Objectives and 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.
- Proficient in Java and its basic support for cryptographic applications.
Requirements and Policies
Although attendance is not mandatory, 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.
- General framework of a cryptographic system:
Alice, Bob, and Eve. One-time XOR pad (unconditionally secure).
Problems with reusing the XOR pad.
Secret- vs Public-key systems.
Types of attacks on cryptosystems:
ciphertext-only, known-plaintext, chosen-plaintext, adaptive chosen-plaintext, chosen-ciphertext.
- The rise of the RSA public-key cryptographic system
- Number Theory (Chapter 33 of Cormen, Leiserson, and Rivest's text).
- Assumptions and weaknesses of RSA: deterministic and multiplicative properties;
Hardness of FACTORING and computing the Euler function.
- A probabilistic PKCS (Goldwasser-Micali)
Quadratic residues, Blum integers;
Computing square roots modulo a Blum integer. Legendre and Jacobi symbols;
Hardness of the Quadratic Residuosity Problem;
Sending 1-bit messages as large random pseudosquares;
- A secure pseudo-random bit generator (PRBG) (Blum-Blum-Shub)
Universal tests: next-bit test and distinguishability test;
Hardness of extracting square roots modulo Blum integers;
Period and security, connection to the Carmichael function.
- A more efficient probabilistic PKCS (Blum-Goldwasser)
An improvement on the Goldwasser-Micali cryptosystem based on a one-time pad idea
using the Blum-Blum-Shub generator;
Principal square roots modulo Blum integers;
Squaring is a permutation over the quadratic residues.
- The fall of the RSA cryptosystem (in the quantum world)
- Fast Fourier Transform and its applications in computer science.
- Shor's quantum algorithm for Factoring
- Recent developments.
- Quantum cryptographic protocols
- Quantum bits: 2-dimensional complex vectors, unitary matrices, measurement operators.
The Pauli matrices, the Hadamard gate. No-cloning theorem. Information gain implies
- Key Distribution: Bennett-Brasssard's protocol (1988);
- Recent developments.
- Other topics: (time permitting)
Coin flipping protocols (Blum-Rabin);
Oblivious transfer (Rabin);
Cryptographic hashing (Chaum-van Heijst-Pfitzmann);
Zero Knowledge Proofs and Identification Schemes (Fiat-Shamir).
[Cryptography in practice: DES and Feistel ciphers].