Outline for February 22, 2006
Reading: text, §9.3–9.4
- Greetings and felicitations!
- Puzzle of the day
- Public-Key Cryptography
- Basic idea: 2 keys, one private, one public
- Cryptosystem must satisfy:
- Given public key, computationally
infeasible to get private key;
- Cipher withstands chosen plaintext attack;
- Encryption, decryption computationally feasible
[note: commutativity not required]
- Benefits: can give confidentiality or authentication
- Use of public key cryptosystem
- Normally used as key interchange system to exchange
secret keys (cheap)
- Then use secret key system (too expensive to use PKC
- Provides both authenticity and confidentiality
- Go through algorithm:
Idea: C =
with ed mod ϕ(n) = 1
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 = 5, q = 7;
then n = 35,
ϕ(n) = (5−1)(7−1) = 24.
Pick d = 11.
Then ed mod ϕ(n) = 1,
so e = 11.
To encipher 2, C =
mod n = 211 mod 35 = 2048 mod 35 = 18,
and M =
mod n = 1811 mod 35 = 2.
p = 53, q = 61;
then n = 3233,
ϕ(n) = (53−1)(61−1) = 3120.
Pick d = 791.
Then e = 71.
To encipher M = RENAISSANCE, use the mapping
A = 00, B = 01, ..., Z = 25, ␢ = 26. Then:
M = RE NA IS SA NC E␢ =
1704 1300 0818 1800 1302 0426
C = (1704)71 mod 3233 = 3106; etc.
= 3106 0100 0931 2691 1984 2927
- Cryptographic Checksums
- Function y =
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 =
- Keyed vs. keyless
Version of February 21, 2006 at 9:45 PM
You can also obtain a PDF version of this.