Lecture 13: October 23, 2019
Reading: text, §10.3–10.4
Due: Lab 2, due November 6, 2019; Homework 2, due October 21, 2019
- Greetings and felicitations!
- Puzzle of the Day
- 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 public key cryptosystem for this)
- 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
Public key is (e, n); private key is d.
Choose n = pq;
then φ(n) = (p−1)(q−1).
- Example: 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 = 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; 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,
␢ (space) = 26.
Then: M = RE NA IS SA NC E␢ =
1704 1300 0818 1800 1302 0426
So: C = 1704^{71} mod 3233 = 3106;
… = 3106 0100 0931 2691 1984 2927
- Cryptographic Checksums
- Function 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
- Digital Signatures
- Judge can confirm, to the limits of technology, that claimed signer did sign message
- RSA digital signatures: sign, then encipher, then sign