# Chor-Rivest knapsack encryption

The Chor-Rivest scheme is the only known knapsack public-key encryption scheme that does not use some form of modular multiplication to disguise an easy subset sum problem.

8.41 Algorithm Key generation for Chor-Rivest public-key encryption

SUMMARY: each entity creates a public key and a corresponding private key.

Each entity A should do the following:

- 1. Select a finite field F
_{g}of characteristic*p,*where*q = p*and for which the discrete logarithm problem is feasible (see Note 8.45(ii>).^{h}, p > h, - 2. Select a random monic irreducible polynomial
*f(x)*of degree*h*over*Z*(using Algorithm 4.70). The elements of F,_{p}_{;}will be represented as polynomials in*Z*of degree less than_{p}[x]*h,*with multiplication performed modulo*f{x).* - 3. Select a random primitive element
*g(x)*of the field F,_{;}(using Algorithm 4.80). - 4. For each ground field element
*i*€ Z_{p}, find the discrete logarithm a, = log_{g}(_{X})*(x +**i)*of the field element*{x + i)*to the base*g(x).* - 5. Select a random permutation я on the set of integers {0,1,2,...
*,p -*1}. - 6. Select a random integer
*d,*0 <*d < p*^{h}- 2. - 7. Compute с, =
*(a*_{n}(.*) +*d)*mod*(p*^{h}—*1)**,0 <**i**< p —**1.* - 8. A’s public key is ((со, c
_{b}... , c_{p}^j),p, /г);*A’s*private key is (*f(x),g(x*),*n, d).* - 8.42 Algorithm Chor-Rivest public-key encryption

SUMMARY: *В* encrypts a message *m* for *A,* which *A* decrypts.

- 1.
*Encryption. В*should do the following:- (a) Obtain A’s authentic public key ((со, ci,... , c
_{p}_i),p,*h).* - (b) Represent the message
*m*as a binary string of length [lg (£)J, where (}') is a binomial coefficient (Definition 2.17). - (c) Consider
*m*as the binary representation of an integer. Transform this integer into a binary vector M = (Mo, Mi,... , M_{p}_i) of length*p*having exactly*h*l’s as follows:

- (a) Obtain A’s authentic public key ((со, ci,... , c

i. Set *h.*

ii. For *i* from 1 to *p* do the following:

Ifm > *(Pj ^{1})* then set M,_i<—1,

*m-s—m -*(

^{p}J^{l}),

*U-l -*1. Otherwise, set Mf_i«-0. (Note: (”) = 1 for

*n >*0; (°) = 0 for / > 1.)

- (d) Compute c = M
^{c}; mod*(p*1).^{h}— - (e) Send the ciphertext c to A.
- 2.
*Decryption.*To recover plaintext*m*from c, A should do the following:- (a) Compute r = (c —
*hd)*mod*(p*1).^{h}— - (b) Compute
*u(x) = g(x)*mod^{r}*f(x)*(using Algorithm 2.227). - (c) Compute .s(:r) =
*u(x) + f(x),*a monic polynomial of degree*h*over*Z*_{p}. - (d) Factor
*s(x)*into linear factors over*Z*= П?=1_{p}. s(x)*(*^{x}*+*^{where}*Ь*€ Z_{p }(cf. Note 8.45(iv)). - (e) Compute a binary vector
*M =*(M_{0}, Mi,... , M_{p}_i) as follows. The components of*M*that are 1 have indices 7r^{-1}(fj), 1 <*j < h.*The remaining components are 0. - (f) The message
*m*is recovered from*M*as follows:

- (a) Compute r = (c —

i. Set *m<—* 0, *l<—h.*

u. For *i* from 1 to *p* do the following:

If M,_i = 1 then set m<-m + (^{p}{"‘) and *l*-l -* 1.

*Proof that decryption works.* Observe that

Since П?=о *( ^{x}* + 7r(*))

^{Mi}and s(a) are monic polynomials of degree

*h*and are congruent modulo /(a), it must be the case that

Hence, the *h* roots of *s(x)* all he in *Z _{p},* and applying тг

^{-1}to these roots gives the coordinates of

*that are 1.*

**M**8.43 Example (*Chor-Rivest public-key encryption with artificially small parameters')*

*Key generation.* Entity *A* does the following:

- 1. Selects
*p =*7 and*h*= 4. - 2. Selects the irreducible polynomial /(a)
*=*a^{4}+ За^{3}+ 5a-^{2}+ 6a + 2 of degree 4 over Z_{7}. The elements of the finite field F_{7}4 are represented as polynomials in Z_{7}[a] of degree less than 4, with multiplication performed modulo*f(x).* - 3. Selects the random primitive element
*д(х) =*За^{3}+ За^{2}+ 6. - 4. Computes the following discrete logarithms:

- 5. Selects the random permutation 7r on {0,1,2,3,4,5,6} definedby л-(О) = 6,7г(1) = 4, 7г(2) = 0,7г(3) = 2, 7г(4) = 1, 7г(5) = 5,7г(6) = 3.
- 6. Selects the random integer
*d =*1702. - 7. Computes

8. A’s public key is ((cq, ci, C2, сз, c_{4}, c_{5}, ce),p = 7 *,h =* 4), while *A’s* private key is (*f(x),g(x),n,d*).

*Encryption.* To encrypt a message *m* = 22 for Л, *В* does the following:

- (a) Obtains authentic A’s public key.
- (b) Represents m as a binary string of length 5: m = 10110. (Note that |_lg (
_{4})J = 5.) - (c) Uses the method outlined in step 1(c) of Algorithm 8.42 to transform
*m*to the binary vector*M =*(1,0,1,1,0,0,1) of length 7. - (d) Computes
*с*= (со + сг + сз + ее) mod 2400 = 1521. - (e) Sends c = 1521 to
*A.*

*Decryption.* To decrypt the ciphertext c = 1521, *A* does the following:

- (a) Computes
*r*= (c -*lid)*mod 2400 = 1913. - (b) Computes
*u(x) =*1913 mod*f(x)*=*x*+ 3x^{3}^{2}+*2x +*5. - (c) Computes
*s(x) = u(x)*+*f(x) = x*+^{4}+ 4x^{3}*x*+^{2}*x.* - (d) Factors s(a;) =
*x(x*+ 2)(ж + 3)(a: + 6) (so*t*= 0, i_{2}= 2,*t$*= 3, t_{4}= 6). - (e) The components of
*M*that are 1 have indices 7г^{_1}(0) = 2,7г^{_1}(2) = 3,7r^{_1}(3) = 6,

and 7г^^{х}(6) = 0. Hence, *M =* (1,0.1,1,0,0.1).

(f) Uses the method outlined in step 2(f) of Algorithm 8.42 to transform *M* to the integer

m = 22, thus recovering the original plaintext. □

- 8.44 Note
*(security of Chor-Rivest encryption)* - (i) When the parameters of the system are carefully chosen (see Note 8.45 and page 318), there is no feasible attack known on the Chor-Rivest encryption scheme. In particular, the density of the knapsack set (co,ci,... ,
*c*{) is_{p }*p/*lg(maxcj), which is large enough to thwart the low-density attacks on the general subset sum problem (§3.10.2). - (ii) It is known that the system is insecure if portions of the private key are revealed, for example, if
*g(x)*and*d*in some representation of F,_{;}are known, or if*f(x)*is known, or if я- is known. - 8.45 Note
*(implementation)* - (i) Although the Chor-Rivest scheme has been described only for the case
*p*a prime, it extends to the case where the base field*Z*is replaced by a field of prime power order._{p} - (ii) In order to make the discrete logarithm problem feasible in step 1 of Algorithm 8.41, the parameters
*p*and*h*may be chosen so that*q = p*- 1 has only small factors. In this case, the Pohlig-Hellman algorithm (§3.6.4) can be used to efficiently compute discrete logarithms in the finite field F^{h}_{4}. - (iii) In practice, the recommended size of the parameters are p w 200 and
*h*« 25. One particular choice of parameters originally suggested is*p =*197 and*h =*24; in this case, the largest prime factor of 197^{24}- 1 is 10316017, and the density of the knapsack set is about 1.077. Other parameter sets originally suggested are {p = 211,*h =*24}, {p = 3^{5},*h =*24} (base field F_{3}s), and {p = 2®,*h =*25} (base field F_{2}s). - (iv) Encryption is a very fast operation. Decryption is much slower, the bottleneck being the computation of
*u(x)*in step 2b. The roots of*s(x)*in step 2d can be found simply by trying all possibilities in*Z*_{p}. - (v) A major drawback of the Chor-Rivest scheme is that the public key is fairly large, namely, about
*(ph ■*lgp) bits. For the parameters p = 197 and*h =*24, this is about 36000 bits.

(vi) There is message expansion by a factor of lg *p ^{h} /* lg (£). For

*p*= 197 and

*h =*24, this is 1.797.