# Outline for February 21, 2003

## Discussion Problem

Analyzing a cipher requires being able to spot patterns. See how good you are. What is the pattern in the following?

## Outline for the Day

1. DES
2. Public-Key Cryptography
1. Basic idea: 2 keys, one private, one public
2. Cryptosystem must satisfy:
1. given public key, CI to get private key;
2. cipher withstands chosen plaintext attack;
3. encryption, decryption computationally feasible [note: commutativity not required]
3. Benefits: can give confidentiality or authentication or both
3. RSA
1. Provides both authenticity and confidentiality
2. Go through algorithm:
Idea: C = Me mod n, M = Cd mod n, with ed mod φ(n) = 1.
Proof: Mφ(n) mod n = 1 [by Fermat's theorem as generalized by Euler]; follows immediately from ed mod φ(n) = 1.
Public key is (e, n); private key is d. Choose n = pq; then φ(n) = (p-1)(q-1).
3. Example:
p = 5, q = 7; n = 35, φ(n) = (5-1)(7-1) = 24. Pick d = 11. Then de mod φ(n) = 1, so choose e = 11. To encipher 2, C = Me mod n = 211 mod 35 = 2048 mod 35 = 18, and M = CD mod n = 1811 mod 35 = 2.
4. Example: p = 53, q = 61, n = 3233, φ(n) = (53-1)(61-1) = 3120. Take d = 791; then e = 71. Encipher M = RENAISSANCE: A = 00, B = 01, ..., Z = 25, blank = 26. Then:
M = RE NA IS SA NC Eblank = 1704 1300 0818 1800 1302 0426
C = (1704)71 mod 3233 = 3106; etc. = 3106 0100 0931 2691 1984 2927