Chapter 3. Knapsack Systems 4 page

11010 © 10111 =01101 = 13 = 11010+ 10111 -2-10010 = 26 + 23 - 2-18,

where we have written bit vectors without parentheses and commas. The cryptanalyst now writes the n linear equations

S_; = A(K © «_f) = A(K + R_t - 2(K * R_t)), 1 < / < n ,

for the n unknowns fe,. Unless the determinant of the system equals 0, K can be quickly computed. On the other hand, if the system happens to be singular, the knowledge of a few more triples (PL,R.) is very likely to yield a nonsingular system. In fact, if n + j triples are known, the probability of getting a nonsingular system tends very fast to 1 with j growing.

As an illustration, consider A = (2, 3,4, 5, 6, 7), yielding n = 6 and t = 5. K = 110011 is chosen as the secret key. Observe that in this cryptosystem the injectivity of A is not important because the decryption process gives the items of A to be summed up and, hence, the knapsack problem need not be solved at all.

Encrypt the plaintext P, = 01010 by choosing R_i = 101010. Now =011001, whence S, = 3 + 4 + 7 = 01110 and Q =00100101010. (The index 1 in S, points out the interconnection with R₁.) Knowing P_l and C,, the cryptanalyst may immediately compute Si = 00100 0 01010 = 01110. But the knapsack problem (A, 14) has to be solved in order to obtain K © R_t from which K results because K ® Ri ® R_t = K. is of course immediate from C,. Thus, the knowledge of the pair (P,, Cj) does not give much information for the decryption of the cryptotexts

C₂ = 11110010101, C₃ = 01110111101, C₄ = 00111011110 ,

C₅ = 11110001010, C₆ = 00111011011 .

Assume, however, that the cryptanalyst knows the six pairs (P,-, C,), 1 < i < 6, where

P₂ = 10011, P₃ = 00001, P₄= 10101, P₅ =01110, P₆ = 00001.

(It is no coincidence that the plaintexts P₂ — P₆ represent the numerical encoding of SAUNA.) Then a system of 6 linear equations can be written for the unknown /c,'s. Consider i = 1. As above, we infer that

Sj = 14 = AR_t + A(K - 2(K*Ri)),

whence

2 = — 2/cj + 3k₂ - 4k₃ + 5/c₄ - 6k₅ + lk₆ ,

and similarly from the equations for S₂ — S₆

-2 = 2fc, - 3/c₂ + 4k₃ - 5/c₄ + 6k_s - lk₆ ,

- 6 = - 2k_t - 3fc₂ - 4k₃ - 5+ 6k₅ - lk_b ,

0 = 2ki- 3k₂ - 4k₃ - 5k₄ - 6k₅ + lk₆ ,

6 = 2/c, + 3k₂ - 4k₃ + 5k₄ - 6k₅ + 1 k₆ ,

- 14 = 2k_x - 3k₂ - 4k₃ + 5/c₄ - 6k₅ - lk_b .

This system of 6 equations is clearly singular. However, it gives a unique solution for K. In fact, the third and fifth equations yield k₃ = 0, and the second and fifth equations /c, = 1. The remaining considerations are based on the fact that the k-s are bits. Parity check shows immediately that exactly one of k₂,k₄, k₆ equals 0. The last equation, with the values inserted for /c, and k₃, reads

- 16= -3k₂ + 5k₄-6k_s-lk₆,

which shows that fc₄ has to be the one equaling 0. This means that the remaining bits must equal 1.

As in this example, a unique solution in bits is obtained although there is no unique solution over rational numbers. The cryptanalytic method bears resemb­lance to the one used in connection with Hill's system in Example 1.2.

Next we'll discuss a notion somewhat weaker than that of r-hyper-reachability. The public key will be a knapsack vector obtained by a succession of strong modular multiplications from some knapsack vector, not necessarily a super- increasing one. The moduli and multipliers constitute the secret trapdoor informa­tion. This information is sufficient for the legal recipient to decrypt using a system of linear equations.

We now present the details. The cryptosystem designer chooses an arbitrary injective knapsack vector A₁ = (a\, . . . a multiplier r, and a modulus m_{ satisfying the conditions of strong modular multiplication, that is,

n

1 < t, <m„ (f,,w₁)= 1, m, > X a' •

i= I

Assume that A₂ = (af, . . . ,al) results from A, by strong modular multiplication with respect to (m^ fj). Then t₂ and m₂ are chosen such that the conditions of strong modular multiplication (for A₂) are satisfied. Let A₃ = (aj, . . . ,a;J) be the vector resulting from A₂ by strong modular multiplication with respect to (m₂, (₂). The procedure is continued until a vector A„ = (a", . . . resulting by strong modular multiplication from A_n-_X with respect to (m„_,, f„ J, is reached. The cryptosystem designer (who is in this case the same as the legal recipient of messages) publicizes the vector A„ as the encryption key but keeps the pairs (m,, fj, 1 < i < n — 1, as the secret trapdoor.

From the secret trapdoor the inverse of t_f (modmj), 1 < i < n — 1, can be immediately computed. After receiving a cryptotext a„, the legal recipient has to find n bits x_l5 . . . , x„ such that

(*) £«?*! = «„■

i= 1

By n — 1 modular multiplications numbers a, satisfying

a_f = (u,a_j+1, mod m,), 1 < i < n — 1 ,

are found. These numbers a, constitute the right sides of the equations obtained from (*) by successive modular multiplications using the inverse multipliers. Originally only congruences (mod m,) are obtained but the congruences reduce to equations by the argument of Lemma 3.1. Thus, the legal recipient obtains the system of n linear equations

n

X a{x_i = otj, j = 1, . . . ,n . i - 1

From this system the unknowns x, can be computed, with the reservations concern­ing singularity mentioned above. The reservations are mild because we have the additional knowledge of the x,'s being bits. However, if the start vector A, is not injective, all ambiguities are preserved by (strong) modular multiplications and, hence, are present in every equation of the system. A cryptanalyst has difficulties in trying to apply algorithms of the types considered in Sections 3.2 and 3.3 because there is no vector, such as a super-increasing one, to look for.

As a simple illustration, consider

A_l =(3,2,6), t₁ = 13, m₁ = 19 ,

A₂ — (1, 7, 2), t₂ = 2, m₂ = 11 ,

=(2, 3,4), publicized.

Now u₂ = 6 and u₁ = 3. The cryptotext 6 leads to the system of equations

2[1]! + 3x₂ 4- 4X₃ = 6 ,

^xi + 7x₂ + 2X₃ = 3 ,

3x, + 2x₂ 4- 6x₃ = 9 ,

from which the unique bit vector 101 is obtained, although the system is singular and possesses the general solution x₂ = 0, x, = 3 — 2x₃.

The subsequent knapsack system is suitable for authentication, that is, (elec­tronic) signatures in the sense discussed already in Section 2.3. The two main requirements of cryptography, privacy and signature generation, are somewhat conflicting and, therefore, it is hard to satisfy them both in a really strong fashion by the same system. Most of the variants of knapsack systems are intended to satisfy the requirement of privacy. The following is especially suitable for generat­ing signatures. The emphasis is on speed and simplicity. Both signing and verifica­tion can be carried out by performing only additions and subtractions.

We need the following modification of the knapsack problem, also easily shown to be /VP-complete.

Given, for some n>3,n + 2 positive integers a_t, ... a_n, a and m with a, being distinct and m > max{a, | 1 < i < «}, find (if possible) some solution (c_l5. . . ,c„) for the congruence

n

We are now ready to present the formal details, as seen from the point of view of the legal sender who in this case is the cryptosystem designer. Consider a prime number m whose binary representation possesses t bits. (Typically, t = 200.) Let H = {hjj) be a t x 2f matrix whose entries are randomly chosen bits and A a 21- dimensional column vector satisfying the following t congruences:

(mod m) .

There are only t congruences in 2t unknowns, that is, the components of A. We may basically choose t components of A at random and compute the remaining components. The computation can be done fast and the probability of getting stuck is minimal because some of the randomly chosen components may be altered whenever necessary. We choose 0 < i < t — 1 and 1 < j < It as the indices of the rows and columns.

The components a, of A will be random-looking (t-bit) integers such that any power of 2 between 2° and 2' ~¹ can be expressed as the sum (mod m) of some of them.

The items A and m are publicized, whereas H is kept as a secret trapdoor information. Messages a are numbers in the closed interval [1, . . . ,/n — 1], The signature for a is a vector C = (c_b . . ., c_2l) satisfying (*) where we have n = It.

Signatures can immediately be verified by checking (*). Forging of signatures will be difficult because of reasons explained above. Essentially, one has to solve the N/"-complete modular knapsack problem.

On the other hand, signing will be easy if we are in the possession of the secret trapdoor information H. In order to sign a message a, we write a as a sum of powers of 2:

« = 'z b,2- . i = 0

Thus, b_t is the (i + l)st bit from the right in the binary representation of a. t bits will suffice because of the agreement about the range of a. We claim that we can choose

Cj = l' b,h_lP 1 <j <2t .

i = 0

Then Cj does not exceed the number t of bits of m, as required in (*). Moreover,

I-l I-'l 21

a= I b,T = X b_t I ajh_u i = 0 i = 0 j= 1 21 /I-l \ 21

= I I ^bi ^hU )^aJ = Z ^cJ^aj (^mod • j=l \i = 0 / j= 1

Only addition is needed for generating and verifying signatures.

The above system is not even intended for concealing because messages are sent in plaintext. As regards the security of the signing procedure, an attack based on linear algebra is possible. When sufficiently many message-signature pairs are known, the matrix H can be computed. The situation is the same as in connection with the first system presented in this section, as well as with Hill's system discussed in Example 1.2.

This insecurity problem can be solved by randomizing the bits of a before signing a. This can be done, for instance, by subtracting a randomly chosen subset of the a- s from a:

X rjaj,

j= i

where/? = (r_1; . . . , r₂,)isarandom vector of bits. We first find the signature C' for a' by the method described above. Then C' + R can be used to sign a because

a = a' + RA = C'A + RA = (C 4- «)/! (mod m).

The components of the new signature are still within the allowed interval. The random vector R need not be known even for the legal recipient.

Example 3.5. Consider the modulus m = 29 expressible in five bits 11101. Hence, H will be a 5 x 10 random matrix. Choose

/ 1 0 1 101 1 100\ 'OlOlllOOlO* 1110 0 0 0 111 0 0 1 1 0 1 0 0 0 1 1 11110 0 0 0 1

We may take, for instance,

A =(14, 15, 19, 16, 3, 24, 10,5,2, 7)

and the five congruences will be satisfied. The third congruence has the form

14+15 +19+ 5 + 2 + 7 = 62 = 4 (mod 29).

The message a = 22 is written in reverse binary notation as 01101, from which the signature C = 2322210122 is obtained immediately using H. The correctness of the signature is verified by

CA = 196 = 22 (mod 29) .

Similarly, the plaintexts, 9, 8, 20 and 1 have signatures

1022021101, 0011010001, 2221100112 and 1011011100.

The plaintexts may be viewed as numerically encoded letters. This means that the word VIHTA has a signature obtained by writing the five signatures one after the other. No confusion will arise even if boundary markers are not used.

Consider, finally, a randomized signature for a = 22. Choose the ten random bits as follows: R = 1011010000. We obtain a' = (22 73, mod 29) = 7. The signa­ture for a' is 2222121221 and, hence, the randomized signature for a is 3233131221. The reader might want to generate randomized signatures for the other plaintext letters I,H,T,A. Observe that the same plaintext has several randomized signa­tures. I i

The final cryptosystem presented in this section hides in a very simple way the fact that the start vector A is super-increasing. The hiding is accomplished by adding some random noise to the components of A so that the new components do not form a super-increasing sequence, only some segments of their binary repres­entations do. After scrambling by strong modular multiplication, these segments are not any more visible.

We now describe the details. As usual, let n be the number of components of the knapsack vectors considered. Denote g = [ log₂ n] + 1. Consequently, n < 2^g. Let and r₂ be arbitrary positive integers. Choose random integers R\ and R'₂ satisfy­ing 0 < R) < 2^r>, 1 <7 < 2, 1 < i < n. Define

a. = R[ + 2^{g + r2 + i}~^l + R'₂ .

The a,'s can be depicted as follows, 1 < i < n.

The purpose of R\ is to disguise the fact that the a-s are super-increasing - the fact becomes immediately visible if each R\ equals 0. The contribution of the other random block, R'₂, is buried in the outcome of the strong modular multiplication.

The g-block of 0's is a guard zone for the addition of the numbers R'₂ : it keeps the sum from overflowing into the n-bit identity block expressing the super- increasing property. Indeed,

n

£ R'₂ < n2^r2 < 2^9+ri . i= t

Let t and m satisfy the conditions of strong modular multiplication for

A = (a,, . . . ,a_n). Then the vector B = (b₁............... b_n) resulting from A by strong

modular multiplication with respect to the pair (t, m) is publicized as the encryption key. The numbers t, m, r_t, r₂ constitute the secret trapdoor. (The number g is public because it is defined in terms of ri). Decryption is trivial for the legal recipient who knows the trapdoor. Let u be the inverse of t (mod m). For a cryptotext /?, denote

a = (u/i, mod m) .

Then the plaintext corresponding to P is simply the «-bit block in the binary representation of a, obtained by omitting the r₂ + g last bits and taking in reverse order the «-bit block from the end of the remaining part. (We could have introduced a guard zone also for the sequences R\ but it is not actually needed.)

That the legal decryption is simpler than for the basic knapsack system of Section 3.1 is due to the fact that now the super-increasing vector consists of powers of 2 and, consequently, the sum vector gives directly the correct sequence of bits. We have discussed here only the basic variant, where the super-increasing vector is the simplest possible. The general case of an arbitrary super-increasing vector is cumbersome to handle with because then the components require several bits for their representation. An algorithm of the type presented in Section 3.2 does not work for cryptosystems of this kind.

Example 3.6. Choose n = 5, whence g = 3. The public encryption key is

B = (62199, 61327, 13976, 16434, 74879).

The legal recipient knows also the trapdoor

m = 75000, u = 22883 (f = 1547), r₂ = 4 .

Assume that the cryptotext 151054 is received. When it is multiplied by 22883 and reduced modulo 75000, the number 43682 results. The binary representation of this number is

43682 =1010 10101 010 0010.

where the four different blocks are visible. The recipient removes r₂ + g = 7 bits from the end. The next five bits give the plaintext 10101. We may still check: 62199 + 13976 + 74879 = 151054.

Similarly, modular multiplication applied to the cryptotext 75303 yields 33549 or, in binary notation,

33549 =1000 00110 000 1101.

The plaintext is now 01100, which shows also that we take, after removing 7 bits, the 5-bit sequence from the end in the reverse order. This is just a technicality caused by the fact that we are reading here the super-increasing part in the wrong order. Thus, now 75303 is the sum of the second and third components of B as it should be.

We still write down the original vector A, together with the binary representa­tions divided into blocks.

Although rj = 3, in our examples the initial random segment is of length 4 because of overflow. This means that the binary representations have 16 bits. The max­imum length of the initial random segment is 5 in this example. The legal recipient does not even look at this segment, so it is not necessary for him/her to know r,.

Date: 2015-02-16; view: 699