Outline for February 24, 2003
Reading: text, §9.3-9.4, 10.1-10.2, 10.4 (except 10.4.1),
10.5.2, 10.6, 11.1, 11.3, 11.4.1
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
Provides both authenticity and confidentiality
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).
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.
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.
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
- Needham-Schroeder and Kerberos
- Public key; man-in-the-middle 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. end-to-end
- Example protocol: PEM
- Design goals
- How it was done
- Differences between it and PGP
Here is a PDF version of this document.