Outline for April 28, 1997

1.	Greetings and Felicitations

2.	Public Key Ciphers

a.	2 keys, public k and private p; public key published, private key kept secret

b.	Requires: (1) given k, computationally infeasible to compute p; (2) immune to cho-
sen plaintext attack (as adversary can generate any amount of ciphertext); (3) 
given C and k, computationally infeasible to find M

c.	Show confidentiality, authenticity; emphasize integrity is by-product of authenticity, 
except that one needs to keep the order of blocks correct

d.	Some ciphers do confidentiality and authenticity, others do only one

3.	Do RSA

a.	Exponentiation cipher: C = me mod n, M = Cd mod n; d is private key, (e, n) is pub-
lic key; must choose d first, then e so that ed mod f(n) = 1.

b.	Why? as ed mod f(n) = 1, ed = tf(n) + 1 for some integer t. Then
Cd mod n = (Me mod n)d mod n
		= Med mod n
		= Mtf(n) + 1 mod n
		= M(Mtf(n) mod n) mod n
		= M(Mf(n) mod n)t mod n
		= M(1)t mod n
		= M mod n
by Fermat¼s Little Theorem

c.	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 = 0711 mod 35 = 28, 
etc. so encipherment is 28 09 16 16 14 08 14 33 16 12.

4.	Do Knapsack

a.	Problem: Given a positive integer C and a vector A = (a1, ..., an) of positive inte-
gers, find a subset of the elements of A that sum to C; that is, find a binary vector 
M = (m1, ..., mn) such that C = AM. This is NP-complete.

b.	If A is superincreasing (that is, ai > a1 + ... + ai‚1), this is linear time. Such knap-
sacks are called simple knapsacks.

c.	Key: pick a superincreasing knapsack and make it look like an ordinary one; ordi-
nary one here is called trapdoor knapsack.

d.	To do: pick simple knapsack A¼ = (a1¼, ..., an¼) and some integer u with u > 2an¼. 
Then pick w such that (w, u) = 1. Compute w‚1 such that w‚1w mod u = 1. The 
trapdoor knapsack elements are ai = wai¼ mod u.

e.	Given C, determining M such that C = AM is intended to be computationally infea-
sible; 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.

f.	Example: A¼ = (1, 3, 5, 10), u = 20, w = 7; then w‚1 = 3 and
A = (7€1 mod 20, 7€3 mod 20, 7€5 mod 20, 7€10 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 = 3€18 mod 20 = 14; then solving for M in the obvi-
ous way gives 14 = (1, 3, 5, 10) (1, 1, 0, 1) or 13.