Outline for February 3, 2016

Reading: text, §10 handout; 10 in text
Due: Homework 2, due February 5; Project progress report, due February 8

1. RSA
   1. Provides both authenticity and confidentiality
   2. 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).
   3. 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¹¹ mod 35 = 2048 mod 35 = 18, and M = C^d mod n = 18¹¹ mod 35 = 2.
   4. 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)⁷¹ mod 3233 = 3106; … = 3106 0100 0931 2691 1984 2927
2. Elliptic curve cryptography
   1. Elliptic curve is y² = x³ + ax + b mod p, a, b, and p parameters; interested in points where x and y are integers (called integer points)
   2. Points P₁, P₂; define
      • When P₁ &neq; P₂, m = (y₂ − y₁) / (x₂ − x₁)
      • When P₁ = P₂, m = (3x₁² + a) / (2y₁)
      Then sum P₃ = (m² − x₁ − x₂, m(x₁ − x₃) − y₁)
   3. Private key: k; public key, Q = kP = P + … + P, adding P to itself k times
   4. Example: y² = x³ + 4x + 14 mod 2503; take P = (1002, 493)
      Choose k_Alice = 1379 as private key, then public key K_Alice = k_AliceP mod p = (1041, 1659)
      Similarly, private key k_Bob = 2001 gives public key K_Bob = (629, 548)
      Then Alice computes k_AliceK_Bob mod p = 1379(629, 548) mod 2503 = (2075, 2458)
      And Bob computes k_BobK_Alice mod p = 2011(1041, 1659) mod 2503 = (2075, 2458)
3. Cryptographic checksums
   1. Function y = h(x): easy to compute y given x; computationally infeasible to compute x given y
   2. Variant: given x and y, computationally infeasible to find a second x′ such that y = h(x′)
   3. Keyed vs. keyless
4. Key exchange protocols