Dense Knapsacks

The underlying knapsack in the basic variant of a public-key cryptosystem is of low density, meaning that the components are very scarce in comparison with the number of them. This is not the case as regards the cryptosystem discussed in this section: the underlying knapsack is dense or of high density. A formal definition of these notions will be commented on later.

Earlier in this section we have been using ordinary integer arithmetic or modular arithmetic, where all numbers are reduced with respect to certain modulus. In this section, the arithmetic used will be based on finite fields or Galois fields. The basic notions of finite fields are contained in Appendix B. We present here in somewhat more details some notions and a lemma needed in this section.

A finite field has always p^h elements, where p is a prime number and h > 1. Such a finite field is often denoted F{p^h). We describe a convenient way of representing elements of F(p^h).

We may speak of the base field F(p), that is, the subfield of F(p'¹) consisting of the elements 0, 1,... ,p — 1. In the base field we consider ordinary arithmetic modulo p. Every element 0 possesses an inverse. An element a is algebraic of degree h over F(p) iff a satisfies in F(p) a polynomial equation P(x) = 0 of degree h but no polynomial equation of a lower degree. (This implies that the polynomial P(x) in question must be irreducible in F(p).) The p^h elements of F(p^h) can be represented in the form

£ CjCt', 0 < Cj < p - 1, 0 < i < h - 1 .

In the arithmetic the "coefficients" are reduced modulo p, while any power a', i > h, can be replaced by a lower power using the equation P(a) = 0.

For instance, let p = 3 and a satisfy the equation x² — x — 1 = 0. The elements of the resulting field F(p^H) = F(9) can be expressed as

0, 1, 2, a, a + 1, a + 2, 2a, 2a + 1, 2a + 2 . In the arithmetic higher powers of a are reduced by the equation a² = a + 1. Thus, (a + 2) (2a + 1) = 2a² + 5a + 2 = 2a + 2 + 5a + 2 = a + 1 .

Given an element # 0 of F(p^h), we may consider powers /?'. It is clear that we have never /?' = 0. However, it might be the case that when i runs through the numbers i = 1,2, . .. ,p^h — 1, then fi' runs through the nonzero elements of F(p^h). In such a case /? is referred to as a generator of F*(p^h), the set (in fact, the multiplicative group) of nonzero elements of F(p^h). A generator can be viewed as a base for logarithms. To compute a logarithm of an element y of F(p^h) means computing a number a such that j}" = y. Logarithms of this kind are often referred to as discrete logarithms. Their computation is believed to be intractable. It is known to be as hard as factorization (see Appendix B).

Returning to the example above, we first write down the powers of a.

From this table we observe that a is a generator. The table can be arranged also as a table of logarithms, where the elements y of F(p^h) are listed in some easily retrievable (such as alphabetic) order.

The table of logarithms can be applied to aid multiplication and division in the customary way. The logarithms are reduced modulo p^h — 1. For instance,

log (a 4- 2) (2a + 1) = log (a + 2) + log (2a + 1) = 10 = 2 , implying (a + 2) (2 a + 1) = a + 1. Similarly,

log((a + l)/(2a+ 1)) = 2 — 3 = 7 , implying (a + l)/(2a + 1) = a + 2.

Also 2a + 1 is a generator of F*(9), with the table of logarithms

It is easy to verify that also a + 2 and 2a are generators but there are no further generators. Clearly, /? is a generator iff i = p^h — 1 is the smallest positive exponent satisfying [}' = 1. Therefore, the number of generators equals <p(p^h — 1), where the Euler function <p(x) stands for the number of positive integers i < x satisfying (/, x) = 1. In our example <p(8) = 4.

It is very important to observe that the arithmetics defined above is different from modular arithmetics. The two coincide only if h = 1.

In cryptosystems, where the underlying knapsack is super-increasing, de­cryption is always unique. This follows because super-increasing knapsacks are injective.

The following question concerning the existence of sequences with unique Mold sums was raised already in 1936. Given positive integers n and h, is there a vector A = (a. . . ,a„) with distinct nonnegative a- s such that all sums of exactly h components of A, where repetitions are allowed, are distinct. It is easy to construct /l's satisfying this condition, where the a-s grow exponentially, for instance, a, = /)'"¹,1 < i < n. This corresponds to knapsacks of low density such as the super-increasing ones. But what about the case of high density knapsacks: can one satisfy this condition with the a,'s growing only polynomially in n. Bose and Chowla, [BC], gave a solution which is presented in the following lemma in a form more suitable for the cryptosystem we have in mind. It should be emphasized that the vectors obtained will not necessarily be injective because only sums of h compo­nents are considered. In fact, the number of components in the sums will be < h because repetitions of the same component are allowed. Contrary to our custom­ary notation, we denote by p the total number of components in A, to emphasize the primality.

Lemma 3.8. Let p be a prime and h > 2 an integer. Then there is a knapsack vector A = (a,, ... ,a_p) satisfying the following conditions (i) and (ii).

(i) 1 < a_t < p^h - 1 for 1 < i < p.

(ii) Let x, and y_; be nonnegative integers and consider

p p

(*) (jc,, . . . ,x„) # (y,, . . . ,y_p) where Z ^x- = ^{h and} Z ^ = ^h ■

i = 1 i = 1

Then

p p

(**) Z ^xi^ai * Z y&i ■

i = 1 i = 1

Proof. Consider the finite field F(p^h). Let a be an element algebraic of degree h over F(p) and g a generator of F*(p^h). Define

a, = log_g(a + / - 1), 1 <i<p.

It is obvious that (i) is satisfied because it expresses only the range of discrete logarithms. To show that also (ii) is satisfied, assume the contrary: there are x, and

y_t satisfying (*) but, instead of (**) we have

p p

(**)' Z ^xi^ai = Z y>^ai ■

i= 1 i = 1

Then equality results also when g is raised to the power expressed by each side of (**)'. Taking into account the definition of a_{, this equality resulting from (**)' can be written

(**)" (a + 0)*' . . . (a + p - If" = (a + Ofi ...(« + p - If" .

When both sides of (**)" are expressed as polynomials of a, the highest powers of a must coincide on both sides because of (*). Moreover, also by (*), the exponent in the highest power must be equal to h. When the right side of (**)" is subtracted from the left side, a nonzero (because of (*)) polynomial in a results whose degree is < h — 1. Hence, a satisfies a polynomial equation with degree < h — 1 and, consequently, cannot be algebraic of degree h. This contradiction shows that (**)' cannot hold. □

The proof is the same if p is a power of a prime. The proof shows also that (**) could be replaced by the stronger condition

p p

Z ^xi^ai £ Z y&i (^mod P" - !) i = 1 i = 1

We still need one auxilliary result before presenting the details of the crypto­system based on dense knapsacks. According to this cryptosystem, the plaintext consists of p-bit blocks such that there are exactly h bits 1 in each block. Arbitrary binary plaintext cannot be divided into such blocks. However, it is intuitively clear that arbitrary, somewhat shorter blocks can be first encoded as blocks satisfying the required condition. This will be shown in the following lemma. Of the many known constructions, all of them computationally easy, we have chosen the one easiest to describe.

Lemma 3.9. Consider positive integers n > 3 and h < n. Then there is an injective mapping of the set of all [log₂(J)]-/wt sequences into the set of all such n-bit sequences that the number of l's in each sequence equals h.

Proof We view the [log₂ (!)]-bit sequences as binary representations of numbers a. Arrange the n-bit sequences, containing h l's each, in alphabetic order where 0 precedes 1. Thus, in the first sequence according to this ordering all the l's are at the end and, in the last sequence, at the beginning. We map the binary sequence representing the number a into the (a + l)st sequence in the ordering constructed. This mapping is clearly injective. Moreover, we do not run out of sequences of the latter type because they are (J) in number, and there are altogether 2* x-bit sequences. In most cases the brackets make the number smaller. □

As an illustration, let n = 5, h = 2. Then

[log₂(X)] = 3

and, thus, we may encode 3-bit sequences. The encoding used in the above proof is given below. The first column lists the 3-bit sequence, and the second column the corresponding 5-bit sequence with exactly 2 l's

Observe that there is no use for the sequences 10100 and 11000. Choose next n — 7, h = 2. Using the above technique, we could encode only all 16 2-bit sequences.

However, the 7-bit sequences with exactly 2 l's in them are 21 in number. In the following encoding 21 letters of the English alphabet are given a representation.

We are now ready to describe the cryptosystem. We do it from the point of view of the system designer who will be also the legal recipient of messages.

Make first a judicious choice of p (a prime power) and h < p such that you are able to compute efficiently discrete logarithms in the finite field F(p^h). (This step is somewhat tricky. Some algorithms work well in special cases, for instance, the case where p^h — 1 has only small prime factors.)

Choose next an element a, algebraic of degree h over F(p), as well as a generator g of F* {p^h). There are many possibilities for the pair (a, g). Of course, a need not be the element used in the definition of F(p^h). In what follows we assume this to be the case, for simplicity.

Compute

(*) a, = log, (a + i - 1), 1 < i < p ■

This is the crucial step in the system design.

Scramble the numbers a, by a random permutation n of the numbers I,... ,p, and add (mod p^h — 1) a randomly chosen d, 0 < d < p^h — 2, to the result. Let B = (fcj, . . . ,b_p) be the vector thus obtained. (The scrambling by n and d is not essential. We have included it in order to make the system coincide with the one presented in [Cho].)

The public encryption key consists of B, p and h. The secret trapdoor consists of a, g, k and d.

Let C be a sequence of p bits such that exactly h of them equal 1. C, viewed as a column vector, is encrypted by taking the smallest positive remainder of BC (mod p" - 1).

If h is close to p, we may encrypt in the same way p-dimensional vectors C with components summing to h. The uniqueness of decryption due to Lemma 3.8 remains valid.

The decryption by the legal recipient knowing the trapdoor works as follows. Subtract (mod p^h — 1) the number hd from the cryptotext x, yielding the number y.

Compute in F(p^h) the power g^y. It will be a polynomial of degree at most h — 1 in a. On the other hand, a satisfies an equation a* = r(a), where r(a) is a polynomial of degree at most h — 1. The polynomial

5(a) = a^h + g" - r(a)

splits into linear factors over F(p) because s(a) is a product of powers of g, each exponent being of the form (*). The subtraction of hd from the cryptotext reverses the effect of adding the random noise d. The linear factors are found by testing through the numbers 0, 1, ... ,p — 1. Thus, we obtain

s(a) = (a + i, — 1)... (a + i_h — 1).

The correct positions of the l's in the plaintext vector are found out by applying the inverse permutation n~¹ to the numbers i_l, .. ., i_h. Lemma 3.8 guarantees that the result of the decryption procedure is always unique.

A cryptanalyst faces essentially a general (modular) knapsack problem. Algo­rithms such as the one presented in Section 3.2 do not work because they assume that the underlying knapsack is of low density. It might be possible in this case to develop a reachability theory independent of the density. Cryptanalysis when something is known is discussed in Problem 44. In general, the density of a knapsack vector A = (a_t,. . . , a„) is defined by

d{A) — n/log₂ max A .

For a super-increasing A, we have a_n> 2"~¹ and, consequently, d(A) < n/(n — 1). Usually the density is much lower than n/(n — 1) in the super-increasing case. Since we have max A > n, for every knapsack vector A, we have always d(A) < n/log₂n. For instance, for A =(1,2,3,. . . ,128), we have d(A) = 128/7 = 18.2857. Al­though there is an upper bound for d(A) in terms of n, there is no positive lower bound for d(A) in terms of n.

Example 3.7. In the following two illustrations no scrambling using n and d is applied. The illustrations are necessarily so small that direct cryptanalysis (that is, solving the knapsack problem) is easy. Without scrambling the essential idea of cryptosystems based on dense knapsacks becomes more visible.

We consider first the example F(9) presented above, where a satisfies the equation x² = x + 1 irreducible in F(3). We choose the generator 2a 1 com­puted above. Since the logarithms of a, a + 1 and a + 2 are 3, 6 and 5, obtain the public encryption key A = (3, 6, 5).

Plaintexts are 3-dimensional vectors with the components summing to 2. Consider the plaintexts (2, 0,0) and (0, 1,1). They are encrypted as numbers 6 and 3. (Recall that we are working with the modulus p^h — 1 = 8.) To decrypt, the legal recipient first computes the powers

(2a + l)⁶ = a + 1 and (2a + l)³ = a .

(Here it is convenient to use the table of logarithms. When a² — a — 1 is added to both of these powers, the resulting polynomials will be

a² and a² - 1 = (a + 1) (a + 2),

yielding immediately the original plaintexts (2,0,0) and (0,1,1).

We remark in passing that it is not possible in Lemma 3.8 to replace in (*) the two equality signs by the sign < . Otherwise, the vector A = (3,6,5) constructed exactly as in the lemma and the two vectors (2,0,0) and (0,1,0) would constitute a counter example. (Lemma 3.8 appears in this wrong form, for instance, in [Cho].)

Let us still consider the same example but scramble A by the circular permuta­tion n\ 1 -»2,2 -* 3, 3 1 and by adding noise d = 7. The resulting vector is B = (5,4,2). The items B, p — 3 and h = 2 constitute the public encryption key, whereas n, d, the polynomial x² - x — 1 defining a and the generator 2a + 1 form the secret trapdoor. The plaintext (0,1,1) is encrypted as 6. The legal recipient takes at first care of the noise by computing the smallest positive remainder 8 of 6 — 2-7 (mod 8). He/she then computes

a² + (2a + l)⁸ - a - 1 = a² - a = a(a + 2).

This gives the vector (1,0,1), from which the original plaintext (0,1,1) results by the

inverse permutation 7c^{_ 1}: 1 -> 3, 2 —► 1, 3 —► 2.

Our final illustration deals with the finite field (64) = F(2⁶). In order to make

the exposition readable, we do not consider the example in its full generality. Thus,

p = 2, h = 6. This contradicts our earlier convention h < p but does not invalidate

any of the arguments we are using. We could also choose, for instance, p = 8, h = 2.

The polynomial x⁶ — x — 1 is irreducible over F(2). (This follows because

neither 0 nor 1 make this polynomial equal to 0.) Thus, F(2⁶) can be represented in

terms of a root a of this polynomial. More specifically, the 64 elements of F(2⁶) can

be represented in the form £ *i^a6~'> where x_; = 0, 1. We represent the elements

;= i

simply by the 6-bit sequences of the x,'s. Thus, a⁵ + a⁴ 4- a³ + a² + a + 1, a⁴ + a² + a and 1 are represented by 111111,010110 and 000001, respectively. We choose a also as a generator of F(2⁶). Then the table of logarithms looks as follows. We may view each element of F(2⁶) also as a binary number as indicated.

With the noise d = 60 the publicized vector will be B = (61, 3). (This is not, in fact, a knapsack vector because p = 2.) Plaintexts are vectors (x, y) with x + y = 6. Using the public encryption key B, p = 2, h = 6, the plaintext (1,5) is encrypted as 13. The legal recipient computes the number

(13 — 6-60, mod 63) = 31 .

The following results are immediate from the table of logarithms.

a³¹ = a⁵ + a² + 1, a⁶ + a³¹ - a - 1 = a⁶ + a⁵ + a² + a = a (a + l)⁵ ,

from which the plaintext (1,5) is visible. Similarly, the plaintext (6,0) is encrypted as 51. By removing the noise the legal recipient obtains the number 6. This yields the polynomial a⁶, corresponding to the plaintext (6,0). The reader might want to try other examples, as well as modifications with a different p (for instance, p = 8, h = 2), and consider also some permutation n.

Chapter 4. RSA

Date: 2015-02-16; view: 561