### CS456/CS656 Cryptography
Spring 2000
**Instructor**: Christino Tamon **Lecture**: Science Center
340 MWF 15:00 **Office hours**: Science Center 373 **Pre-requisites**:
MA211 or MA346, good programming skills, and a healthy mathematical curiosity.
**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. Concepts such as
one-way functions and trapdoor permutations (functions that are easy to
compute but computationally hard to invert), pseudorandom sequence 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 a fact without revealing its proof). Most
of the 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.
**Grading scheme**
- Assignments and Quizes 40%
- Midterm 20%
- Final exam 40%
**Required texts**:
- Undergraduate: Schneier, Bruce.
*Applied Cryptography*. John
Wiley and Sons, Second edition, 1996.
- Graduate: Goldreich, Oded.
*Modern Cryptography, Probabilistic Proofs,
and Pseudorandomness*. Springer-Verlag, 1999.
**Recommended references**
- Cormen, Leiserson, and Rivest.
*An Introduction to Algorithms*.
MIT Press. (highly recommended)
- Kernighan and Ritchie.
*The C Programming Language*. Second edition.
Prentice-Hall, 1988.
### Topics covered (outline from Spring 1999)
- General framework of
**cryptographic system**: Alice, Bob, and
Eve. **One-time XOR pad** (unconditionally secure). Problems with
reusing the XOR pad. Types of **attacks** on cryptosystems: ciphertext-only,
known-plaintext, chosen-plaintext, adaptive chosen-plaintext, chosen-ciphertext.
- The
**RSA** cryptosystem:
*Original reference*: Ronald L. Rivest, Adi Shamir, Leonard
M. Adleman. A Method of Obtaining Digital Signatures and Public-Key
Cryptosystem. Communications of the ACM, vol. 21, no. 2, 1978, pp
120-126.
- Number-theoretic background to understand RSA: see Chapter 33
of Cormen, Leiserson, and Rivest's text.
- Assumptions and weaknesses of RSA:
**deterministic** property.
multiplicative property. hardness of **Factoring** and computing
the **Euler-Totient** function.
- The
**Goldwasser-Micali** *probabilistic* Public-Key cryptosystem:
*Original reference*: Shafi Goldwasser and Silvio Micali.
Probabilistic Encryption. Journal of Computer and System Sciences,
vol. 28, no. 2, 1984, pp 270-299.
- Number-theoretic background:
**quadratic residues**, **Blum
integers**. computing square roots modulo a Blum integer. **Legendre**
and **Jacobi** symbols.
- Assumptions and inefficiencies: hardness of the
**Quadratic Residuosity
Problem**. sending 1-bit messages as large random *pseudosquares*.
- Security: semantically secure (not covered).
- The
**Blum-Blum-Shub** *pseudorandom bit generator*:
*Original reference*: Lenore Blum, Manuel Blum, Michael Shub.
A Simple Unpredictable Pseudo-Random Number Generator. SIAM Journal
of Computing, vol. 15, no.2, 1993, pp 364-383.
- Universal tests: concept defined by Blum, Micali, and Yao.
- Assumptions: hardness of extracting square roots modulo Blum integers.
- Period and security:
*coming up*
- The
**Blum-Goldwasser** *probabilistic* Public-Key cryptosystem:
*Original reference*: Manuel Blum and Shafi Goldwasser. An
Efficient Probabilistic Public-Key Encryption Scheme Which Hides
All Partial Information. Advances in Cryptology: Proceedings of
CRYPTO'84, Springer-Verlag, 1985, pp 289-299.
- An improvement on the Goldwasser-Micali cryptosystem based on
a one-time pad using the BBS pseudorandom generator.
- Number-theoretic background:
**principal square roots** modulo
Blum integers. the squaring function is a permutation over the quadratic
residues.
Number theory and notes. ### Assignments
- Assignment 1: cryptogram (only in paper form).
Out: 1/14/00. Due: 1/21/00.
** Links ** |