**Reading**: *text*, §10 handout; 10 in text

**Due**: Homework 2, due February 5; Project progress report, due February 8

- RSA
- Provides both authenticity and confidentiality
- Go through algorithm:

Idea:*C*=*M*mod^{e}*n*,*M*=*C*mod^{d}*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*mod^{e}*n*= 2^{11}mod 35 = 2048 mod 35 = 18, and*M*=*C*mod^{d}*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,`␢`= 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`

- Elliptic curve cryptography
- Elliptic curve is
*y*^{2}=*x*^{3}+*ax*+*b*mod*p*,*a*,*b*, and*p*parameters; interested in points where*x*and*y*are integers (called*integer points*) - Points
*P*_{1},*P*_{2}; define- When
*P*_{1}&neq;*P*_{2},*m*= (*y*_{2}−*y*_{1}) / (*x*_{2}−*x*_{1}) - When
*P*_{1}=*P*_{2},*m*= (3*x*_{1}^{2}+*a*) / (2*y*_{1})

*P*_{3}= (*m*^{2}−*x*_{1}−*x*_{2},*m*(*x*_{1}−*x*_{3}) −*y*_{1}) - When
- Private key:
*k*; public key,*Q*=*kP*=*P*+ … +*P*, adding*P*to itself*k*times - Example:
*y*^{2}=*x*^{3}+ 4*x*+ 14 mod 2503; take*P*= (1002, 493)

Choose*k*_{Alice}= 1379 as private key, then public key*K*_{Alice}=*k*_{Alice}*P*mod*p*= (1041, 1659)

Similarly, private key*k*_{Bob}= 2001 gives public key*K*_{Bob}= (629, 548)

Then Alice computes*k*_{Alice}*K*_{Bob}mod*p*= 1379(629, 548) mod 2503 = (2075, 2458)

And Bob computes*k*_{Bob}*K*_{Alice}mod*p*= 2011(1041, 1659) mod 2503 = (2075, 2458)

- Elliptic curve is
- 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

- Function
- Key exchange protocols

You can also obtain a PDF version of this. | Version of February 4, 2016 at 10:46PM |