* Reading*: §9.3

- 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*e**d*mod Φ(*n*) = 1

Proof:*M*^{Φ(n)}mod*n*= 1 [by Fermat's theorem as generalized by Euler]; follows immediately from*e**d*mod Φ(*n*) = 1

Public key is (*e*,*n*); private key is*d*. Choose*n*=*p**q*; then Φ(*n*) = (*p*−1)(*q*−1). - Example:
*p*= 5,*q*= 7; then*n*= 35, Φ(*n*) = (5−1)(7−1) = 24. Pick*d*= 11. Then*e**d*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, b̷ = 26.

Then:*M*= RE NA IS SA NC Eb̷ = 1704 1300 0818 1800 1302 0426

So:*C*= (1704)^{71}mod 3233 = 3106; etc. = 3106 0100 0931 2691 1984 2927

You can also obtain a PDF version of this. | Version of November 16, 2006 at 3:50 PM |