Outline for April 28, 1997

1. Greetings and Felicitations
2. Public Key Ciphers
   1. 2 keys, public k and private p; public key published, private key kept secret
   2. Requires:
      1. given k, computationally infeasible to compute p;
         
      2. immune to chosen plaintext attack (as adversary can generate any amount of ciphertext);
         
      3. given C and k, computationally infeasible to find M
   3. Show confidentiality, authenticity; emphasize integrity is by-product of authenticity, except that one needs to keep the order of blocks correct
   4. Some ciphers do confidentiality and authenticity, others do only one
3. Do RSA
   1. Exponentiation cipher: C = m mod n, M = C^d mod n; d is private key, (e, n) is public key; must choose d first, then e so that ed mod PHI(n) = 1.
   2. Why? as ed mod PHI(n) = 1, ed = tPHI(n) + 1 for some integer t. Then
      C^d mod n = (M^e mod n)^d mod n
      = M^ed mod n
      = M^{tPHI(n) + 1} mod n
      = M(M^tPHI(n) mod n) mod n
      = M(M^PHI(n) mod n)^t mod n
      = M(1)^t mod n
      = M mod n
      by Fermat's Little Theorem
   3. Example: p = 5, q = 7, n = 35, f(n) = 24; choose e = 11, then d = 11. HELLO WORLD is 07 04 11 11 14 22 14 17 11 03; enciphering is C = 07¹¹ mod 35 = 28, etc. so encipherment is 28 09 16 16 14 08 14 33 16 12.
4. Do Knapsack
   1. Problem: Given a positive integer C and a vector A = (a₁, ..., a_n) of positive integers, find a subset of the elements of A that sum to C; that is, find a binary vector M = (m₁, ..., m_n) such that C = AM. This is NP-complete.
   2. If A is superincreasing (that is, a_i > a₁ + ... + a_i-1), this is linear time. Such knapsacks are called simple knapsacks.
   3. Key: pick a superincreasing knapsack and make it look like an ordinary one; ordinary one here is called trapdoor knapsack.
   4. To do: pick simple knapsack A' = (a₁', ..., a_n') and some integer u with u > 2a_n'. Then pick w such that (w, u) = 1. Compute w^-1 such that w^-1w mod u = 1. The trapdoor knapsack elements are a_i = wa_i' mod u.
   5. Given C, determining M such that C = AM is intended to be computationally infeasible; but knowing w^-1 and u:
      C' = w^-1C mod u = w^-1AM mod u = w^-1(wA')M mod u = A'M mod u = A'M.
   6. Example: A' = (1, 3, 5, 10), u = 20, w = 7; then w^-1 = 3 and
      A = (7x1 mod 20, 7x3 mod 20, 7x5 mod 20, 7x10 mod 20) = (7, 1, 15, 10)
      If M = 13 = (1, 1, 0, 1) [13 in binary is 1101], C = (7, 1, 15, 10)*(1, 1, 0, 1) = 18. Deciphering: C' = w^-1C mod u = 3x18 mod 20 = 14; then solving for M in the obvious way gives 14 = (1, 3, 5, 10)*(1, 1, 0, 1) or 13.