Lecture: Snell 129 TR 4:00-5:15pm
Science Center 373 TR 10:45-12:15, 15:00-16:00
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), pseudorandom generators (devices
that produces sequences that are computationally random), public-key
cryptosystems (secure systems that require no secret agreement), one-way hash
functions (tools to authenticate messages and to verify data integrity), digital
signatures (mechanisms for signing documents), and zero-knowledge proofs
(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 be given.
GRADING: Assignments and Quizzes 40%, Midterm 20%, Final 40%
Bruce Schneier, "Applied Cryptography," 2nd edition, Wiley (1996)
Recommended: Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest,
and Clifford Stein, "Introduction to Algorithms," 2nd edition, The MIT Press
(2001) (on reserve)
Other references: David M. 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)
The objective of this course is to learn
fundamental issues and important algorithms involved in the field of
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
- 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.
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:
minimal cast of characters. 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 Rivest-Shamir-Adleman
(RSA) public-key cryptographic system (PKCS):
- Number Theory (Chapter 31 of Cormen-Leiserson-Rivest-Stein). Extended
Euclid (Aryabhata's Pulverizer), Chinese Remainder Theorem, Miller-Rabin
fast probabilistic primality testing. Recent result on primality testing: PRIMES in P.
- Assumptions and weaknesses of RSA: deterministic and multiplicative
properties; Hardness of FACTORING;
computing the Euler Totient function. Pollard's
rho method and (p-1) methods for Factoring.
- A probabilistic PKCS of Goldwasser-Micali:
residues, Blum integers; Hardness of computing MODULAR SQUARE ROOTS over a
Blum integer. Legendre and Jacobi symbols; Hardness of the QUADRATIC
RESIDUOSITY problem; Semantically secure.
- A more efficient probabilistic PKCS of Blum-Goldwasser:
pseudo-random bit generator (PRBG) (Blum-Blum-Shub). One-time pad
public-key system via the BBS generator; Principal square roots
modulo Blum integers; Squaring is a permutation over the quadratic residues.
- Alternatives to RSA:
exchange protocol. El Gamal discrete-logarithm based public-key
rho method for discrete logarithms.
Miscellany: Miller-Rabin success probability proof.
Properties of the Carmichael numbers; Continued fractions and the Euclidean
algorithm; Design of iterative binary extended Euclidean algorithm (Stein's
method); Period of the Blum-Blum-Shub generator; The cyclic theorem for
multiplicative groups modulo primes; Infinity proofs for primes: Euclid's
proof, of special forms 4k+3 or 4k+1 (Dirichlet's theorem), safe primes;
Computing square roots modulo any prime. What about cube roots?
- The fall of the RSA cryptosystem
- Fast Fourier Transform and polynomial multiplication (Chapter 30 of
Cormen et al's book).
- Quantum information and computation: basics (see Stan Gudder, "Quantum
Computation", The American Mathematical Monthly, Volume 110, No. 3, March
2003, pages 181-201).
- The quantum factoring (prize-winning)
algorithm of Shor (see also
Gudder's article above).
- Other topics: (time permitting)
Coin flipping protocols
(Blum-Rabin); Bit commitment; Oblivious transfer (Rabin); Cryptographic
hashing (Chaum-van Heijst-Pfitzmann); Zero Knowledge Proofs and
Identification Schemes (Fiat-Shamir). DES.
D. Boneh's cryptography
course at Stanford; there are some useful handouts at the end.
J. Watrous's QFT
talk at MSRI.