Outline for February 21, 2003
Reading: text, §9.2.39.3
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

DES

PublicKey Cryptography

Basic idea: 2 keys, one private, one public

Cryptosystem must satisfy:

given public key, CI to get private key;

cipher withstands chosen plaintext attack;

encryption, decryption computationally feasible [note: commutativity
not required]

Benefits: can give confidentiality or authentication or both

RSA

Provides both authenticity and confidentiality

Go through algorithm:
Idea: C = M^{e} mod n,
M = C^{d} 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) = (p1)(q1).

Example:
p = 5, q = 7; n = 35,
φ(n) = (51)(71) = 24.
Pick d = 11. Then de mod φ(n) = 1,
so choose e = 11.
To encipher 2,
C = M^{e} mod n = 2^{11} mod 35 =
2048 mod 35 = 18, and
M = C^{D} mod n = 18^{11} mod 35 = 2.

Example:
p = 53, q = 61, n = 3233,
φ(n) = (531)(611) = 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