- Greetings and Felicitations
- Public Key Ciphers
- 2 keys, public
*k*and private*p*; public key published, private key kept secret - Requires:
- 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*

- given
- 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

- 2 keys, public
- Do RSA
- Exponentiation cipher:
*C*=*m*mod*n*,*M*=*C*mod^{d}*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*=*t*PHI(*n*) + 1 for some integer*t*. Then

*C*mod^{d}*n*= (*M*mod^{e}*n*)mod^{d}*n*

=*M*mod^{ed}*n*

=*M*^{tPHI(n) + 1}mod*n*

=*M*(*M*^{tPHI(n)}mod*n*) mod*n*

= M(*M*^{PHI(n}) mod*n*)mod^{t}*n*

=*M*(1)mod^{t}*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*= 07^{11}mod 35 = 28,*etc*. so encipherment is`28 09 16 16 14 08 14 33 16 12`.

- Exponentiation cipher:
- Do Knapsack
- Problem: Given a positive integer
*C*and a vector*A*= (*a*_{1}, ...,*a*) of positive integers, find a subset of the elements of_{n}*A*that sum to*C*; that is, find a binary vector*M*= (*m*_{1}, ...,*m*) such that_{n}*C*=*AM*. This is NP-complete. - If
*A*is superincreasing (that is,*a*>_{i}*a*_{1}+ ... +*a*_{i-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*' = (*a*_{1}', ...,*a*') and some integer_{n}*u*with*u*> 2*a*'. Then pick_{n}*w*such that (*w*,*u*) = 1. Compute*w*^{-1}such that*w*^{-1}*w*mod*u*= 1. The trapdoor knapsack elements are*a*=_{i}*wa*' mod_{i}*u*. - Given
*C*, determining*M*such that*C*=*AM*is intended to be computationally infeasible; but knowing*w*^{-1}and*u*:

*C*' =*w*^{-1}*C*mod*u*=*w*^{-1}*AM*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*^{-1}*C*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.

- Problem: Given a positive integer

Notes by Doug Johnson:

You can get this document in Postscript, ASCII text, or Framemaker version 5.1.

Send email to cs253@csif.cs.ucdavis.edu.

Department of Computer Science

University of California at Davis

Davis, CA 95616-8562