CS456/MA456 Cryptography (Fall 2008)

Pre-requisites: MA211 or MA346, good programming skills and/or mathematical curiosity.
Instructor: Christino Tamon
Lecture: Science Center 344 TR 1:00-2:15pm
Office hours: TR 9:15-11am, 2:15-3pm, Science Center 373
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%, Test(s) 40%, Project 20%

Douglas R. Stinson, "Cryptography: Theory and Practice," 3rd edition, Chapman & Hall/CRC, 2006.


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:

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.

Schedule (updated regularly)

Tuesday Thursday
August 26

Course administration. Introduction: one-time pad.

Reading: Chapter 1.
Assignment 1 is out.

August 28

RSA public-key cryptosystem.

Reading: Chapter 5 (5.1 and 5.2)
Picture: RSA

September 2

Computational problems: easy and hard.
Algorithms for RSA: multiplication, division, exponentiation.

Reading: Chapter 31 in Cormen et al.
Complexity Zoo

September 4

Extended Euclidean algorithm: public and secret RSA exponents, multiplicative inverses. The pulverizer of Aryabhata.

Picture: Euclid, Aryabhata

September 9

Fermat's little theorem. Chinese Remainder theorem.

Reading: Chapter 5 of Stinson and Chapter 31 in Cormen et al.
Picture: Pierre de Fermat

September 11

Lab: Java and NTL

September 16

RSA proof of correctness.

September 18

no class.

September 23

Primality testing. Weaknesses of RSA. Types of attacks.

September 25

Quadratic residues. Legendre symbol. Euler's criterion. Hardness of Quadratic Residuosity, Composite Square Root, and Factoring Blum Integer problems.

Septeber 30

short break.

October 2

Discrete Logarithm. Diffie-Hellman key exchange.
ElGamal PPKC.

October 7

Goldwasser-Micali and Blum-Goldwasser PPKC.
Blum-Blum-Shub pseudorandom bit generator.
Semantic security (also: see RSA chapter in Stinson)

October 9

Quiz 1.

October 14

October 16

Primality testing. Miller-Rabin's proof of correctness. Lagrange Theorem (group theory).

October 21

Miller-Rabin's proof (continued).
Zero-knowledge proof systems (Goldwasser-Micali-Rackoff): completeness, soundness, zero-knowledge.

October 23

ZK proofs (continued): Fiat-Shamir quadratic residuosity protocol.

October 28

DES continued. Differential cryptanalysis (Biham-Shamir).

October 30

AES: finite fields, irreducible polynomials.

November 4

AES continued. Modes of Operations: ECB, CBC, CFB, OFB.

November 6

Cryptographic hash function: Chaum-van Heijst-Pfitzmann.

November 11

Cryptographic protocols: Oblivious transfer, Multiparty secure computation, Yao's millionaire's problem.

November 13

Introducing quantum computation.

November 18

Quantum computation (continued).
Reading: J. Watrous's notes on Shor's factoring algorithm.

November 20

Thanksgiving break.