Outline for April 28, 1997
- Greetings and Felicitations
- Public Key Ciphers
- 2 keys, public k and private p;
public key published, private key kept secret
- given k, computationally infeasible to compute p;
- immune to chosen plaintext attack (as adversary can generate any
amount of ciphertext);
- given C and k, computationally infeasible to find M
- Show confidentiality, authenticity; emphasize integrity is by-product
of authenticity, except that one needs to keep the order of blocks correct
- Some ciphers do confidentiality and authenticity, others do only one
- Do RSA
- Exponentiation cipher: C = m mod n,
M = Cd mod n;
d is private key, (e, n) is public key;
must choose d first,
then e so that ed mod PHI(n) = 1.
- Why? as ed mod PHI(n) = 1,
ed = tPHI(n) + 1
for some integer t. Then
Cd mod n =
(Me mod n)d mod n
= Med mod n
= MtPHI(n) + 1 mod n
= M(MtPHI(n) mod n) mod n
= M(MPHI(n) mod n)t mod n
= M(1)t mod n
= M mod n
by Fermat's Little Theorem
- 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.
- Do Knapsack
- Problem: Given a positive integer C and a vector A =
(a1, ..., an) of positive integers,
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.
- If A is superincreasing (that is, ai >
a1 + ... + ai-1),
this is linear time. Such knapsacks are called simple knapsacks.
- Key: pick a superincreasing knapsack and make it look like an
ordinary one; ordinary one here is called trapdoor knapsack.
- 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.
- Given C, determining M such that C = AM is
intended to be computationally infeasible; but knowing w-1
C' = w-1C mod u
= w-1AM mod u
= w-1(wA')M mod u
= A'M mod u = A'M.
- 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.
Notes by Doug Johnson:
You can get this document in
Send email to
Department of Computer Science
University of California at Davis
Davis, CA 95616-8562
Page last modified on 4/4/97