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:
- Bruce Schneier, "Applied Cryptography," 2nd edition, John Wiley &
Sons, 1986 (on reserve) [Schneier]
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford
Stein, "Introduction to Algorithms," 2nd edition, The MIT Press, 2001 (on
reserve) [CLRS]
- Simon Singh, "The Code Book," Anchor, 1999 (non-technical).
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:
- 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.
- Knowledge of modern programming languages with support for cryptographic
applications.
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 |
ASSIGNMENTS
- Assignment
One
(solve the cipher first before you solve any of the following
problems;
MA questions: 1.6, 1.7, 1.8, 1.10, 1.11, 1.12, 1.13, 1.14, 1.15.
Optional: 1.20, 1.22, 1.27)
MISCELLANEOUS RESOURCES:
- Java at Sun
Microsystems.
- NTL package.
- Crypto ePrint archive.
- Dana Angluin's "Lecture
Notes on the Complexity of Some Problems in Number Theory", Technical
Report 243, August 1982, Department of Computer Science, Yale University.
- Carl Pomerance, "A Tale of Two
Sieves," Notices of the AMS, vol. 12, 1996.
- J.-J. Quisquater et al., "How to Explain
Zero-Knowledge Protocols to Your Children," Proc. Advances in Cryptology,
pp. 628-631, 1989.
- Don Coppersmith, "DES and its
strengths against attacks," IBM Research Journal.
- Dan Boneh, "Twenty Years of
Attack on the RSA Cryptosystem," Notices of the American Mathematical
Society, vol. 46, no.2 (1999), 203-213.
- Dan Boneh's Number Theory Fact
Sheet.
- Handbook of Cryptography: link (thx: Pat Wilbur).
- Crypto blunders
