Outline for February 24, 2003
Reading: text, §9.39.4, 10.110.2, 10.4 (except 10.4.1),
10.5.2, 10.6, 11.1, 11.3, 11.4.1
Discussion Problem
It has often been said tha the only way to decipher a message that has
been enciphered using RSA is to factor the modulus n used by the
cipher. If you were told that an enciphered message was on a computer
that you controlled, and that the message was enciphered using RSA with
an n of 1024 bits (about 309 decimal digits), how would you find
the encrypter's private key?
Outline for the Day

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
 Cryptographic Checksums
 y = h(x): easy to compute y given x; computationally infeasible to compute x given y
 Variant: given x and y, computationally infeasible to find a second x' such that y = h(x').
 Keyed vs. keyless
 Key Exchange
 NeedhamSchroeder and Kerberos
 Public key; maninthemiddle attacks
 Cryptographic Key Infrastructure
 Certificates (X.509, PGP)
 Certificate, key revocation
 Digital Signatures
 Judge can confirm, to the limits of technology, that claimed signer did sign message
 RSA digital signatures: sign, then encipher
 Types of attacks
 Forward searches
 Misordered blocks
 Statistical regularities (repetitions)
 Networks and ciphers
 Where to put the encryption
 Link vs. endtoend
 Example protocol: PEM
 Design goals
 How it was done
 Differences between it and PGP