CS456/MA456 Cryptography (Fall 2009)

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
SYLLABUS
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%

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

Recommended Reading:

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:

REQUIREMENTS/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.

Schedule (updated regularly)

Tuesday Thursday
August 25

Course administration. Introduction: one-time pad.

Reading: Chapter 1.
Assignment 1 is out.

August 27

RSA public-key cryptosystem.

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

September 1

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

Reading: Chapter 31 in Cormen et al.
Complexity Zoo

September 3

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

Picture: Euclid, Aryabhata

September 8

Chinese remainder theorem; Fermat's Little theorem
Example: RSA encryption and decryption.
Reading: Chapter 5 of Stinson and Chapter 31 in Cormen et al.

September 10

Quiz 1

September 15

Software for crypto: Java, NTL (C++), Scheme, Python.
Quadratic residues; factoring using square roots.
Example: coin-flipping protocol (Blum-Rabin).

September 17

Primality testing (Miller-Rabin); fast exponentiation

Gary Miller;
Michael Rabin

September 22

Miller-Rabin: proof (Lagrange Theorem)
RSA weaknesses: multiplicative property (chosen ciphertext attack), Euler totient.

September 24

ElGamal PKCS: DISCRETE LOGARITHM.

September 29

Short break.

October 1

Rabin PKCS (non-deterministic): MODULAR SQUARE ROOT; Goldwasser-Micali PKCS: QUADRATIC RESIDUOSITY.

Shafrira Goldwasser

October 6

Improved Goldwasser-Micali: Blum-Goldwasser PKCS; Blum-Blum-Shub PRBG.

Manuel Blum; Lenore Blum; Manuel and Lenore Blum;
Michael Shub

October 8

Recap: PKCS Blum_Goldwasser, Goldwasser-Micali and ElGamal; PRBG Blum-Blum-Shub.

October 13

Quiz 2

October 15

ASSIGNMENTS

Quiz 3 is in the course public directory (PDF format). Due date: Monday 11/16/2009 noon

Test: Thursday Nov 19, 5:30pm, ITL

Final Talks: Thursday Dec 10, 9am, ITL

PROJECT

  1. Choose a project topic of interest; you may work in groups of up to three.
    Indicate your topic and group before the Thanksgiving break by email.

  2. Submit a term-paper (hardcopy) that contains at minimum the following separate sections:
    • Abstract (follow the What-Why-How plotline if possible).
      Provide this on a separate page.
    • Background information and literature: what has been done, what is the state-of-the-art ideas or methods in the area.
      Include proper and complete bibliography (at the end of the document) for your sources; see examples of some journal papers listed below or see Chicago's Manual of Style.
    • Identify at least two possible ideas that can be done but has not been addressed in the literature.
      This can be either an improvement on implementation or on a mathematical idea.

  3. Prepare a 15-minute talk to be delivered either during Dead Week or Finals Week.
    Submit by email your talk slides (should be in PPT, PDF, or other similar formats).
    Sign-up sheet will appear soon once a common time is found for everyone to attend.

  4. Submit any other items, if any, related to your project (code, etc) by email.
Topics (under construction)

MISCELLANEOUS RESOURCES: