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.
Douglas R. Stinson, "Cryptography: Theory and Practice," 3rd edition, Chapman & Hall/CRC, 2006.
The specific outcomes are as follows:
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.
Course administration. Introduction: one-time pad.
Reading: Chapter 1.
RSA public-key cryptosystem.
Reading: Chapter 5 (5.1 and 5.2)
Computational problems: easy and hard.
Reading: Chapter 31 in Cormen et al.
Extended Euclidean algorithm: public and secret RSA exponents, multiplicative inverses. The pulverizer of Aryabhata.
Fermat's little theorem. Chinese Remainder theorem.
Reading: Chapter 5 of Stinson and Chapter 31 in Cormen et al.
Lab: Java and NTL
RSA proof of correctness.
Primality testing. Weaknesses of RSA. Types of attacks.
Quadratic residues. Legendre symbol. Euler's criterion. Hardness of
Quadratic Residuosity, Composite Square Root, and Factoring Blum Integer
Discrete Logarithm. Diffie-Hellman key exchange.
Goldwasser-Micali and Blum-Goldwasser PPKC.
|October 14||October 16
Primality testing. Miller-Rabin's proof of correctness. Lagrange Theorem (group theory).
Miller-Rabin's proof (continued).
ZK proofs (continued): Fiat-Shamir quadratic residuosity protocol.
DES continued. Differential cryptanalysis (Biham-Shamir).
AES: finite fields, irreducible polynomials.
AES continued. Modes of Operations: ECB, CBC, CFB, OFB.
Cryptographic hash function: Chaum-van Heijst-Pfitzmann.
Cryptographic protocols: Oblivious transfer, Multiparty secure computation, Yao's millionaire's problem.
Introducing quantum computation.
Quantum computation (continued).