Chapter 2. The Idea of Public Keys

2.1 Some Streets Are One-Way

Think about any of the cryptosystems presented in Chapter 1, or any other similar systems. There will be no difficulties in the decryption process for a cryptanalyst who has learned the encryption method. The encryption and decryption keys coincide even in such a sophisticated system as DES. So you give away your secrets if you work with one of the systems mentioned and publicize your encryption method.

This is not necessarily the case. There are systems in which you can safely publicize your encryption method. This means that also the cryptanalyst will know it. However, he/she is still unable to decrypt your cryptotext. This is what public- key cryptography is all about: the encryption method can be made public.

The idea was presented by Diffie and Hellman [DH], Although revolutionary, the idea is still very simple. Why was such a simple idea presented so late-in the middle 70's-during the very long history of cryptography? What does safety in giving away the encryption method actually mean? How can one realize the beautiful idea?

The answer to the first question is easy: complexity theory was developed only recently. The theory gives us information about the complexity of various com­putations, say, how much time computations will take with best available com­puters. Such information is crucial in cryptography.

This brings us to the second question. Of course, the encryption method gives away the decryption method in a mathematical sense because the two are "in­verses" of each other. Suppose, however, that it will take hundreds of years for the cryptanalyst to compute the decryption method from the encryption method. Then we don't compromise anything by publicizing the encryption method. This is how "safety" in the second question is to be understood.

As regards the question about the realization of the idea of public keys, a lot of details will be presented in the sequel. Let us make here some initial observations.

In mathematics, as well as in real life, there are some one-way streets. It is easy to go along the street from A to B, whereas it is practically impossible to go from B to A. Encryption is viewed as the direction from A to B. Although you are able to go in this direction, this does not enable you to go in the opposite direction: to decrypt.

Take the telephone directory of a big city. It is easy to find the number of any specific person. On the other hand, it is hard - one might say hopeless! - to find the person who has a certain specified number. The directory consists of several thick volumes. In principle, you have to go through all of them carefully.

This gives an idea for a public-key cryptosystem. The encryption is context-free: letter by letter. For each letter of the plaintext, a name beginning with that letter is chosen at random from the directory. The corresponding telephone number constitutes the encryption of that particular occurrence of the letter in question. Thus, the system is polyalphabetic: two different occurrences of the same letter are very unlikely to be encrypted in the same way. The encryption of the plaintext COMETOSAUNA might be as follows.

Thus, the whole cryptotext is obtained by writing, one after the other, all numbers appearing in the right column. Of course, the numbers are written in the order indicated.

Observe that the encryption method is nondeterministic. Enormously many cryptotexts result from one and the same plaintext. On the other hand, each cryptotext gives rise to only one plaintext.

A legal receiver of the plaintext message should have a directory listed accord­ing to the increasing order of the number:. Such a directory makes the decryption process easy. According to the terminology discussed in more detail in the sequel, the reverse directory constitutes the secret trapdoor known only to the legal users of the system.

Without knowledge of the trapdoor, i.e., without possessing a copy of the reverse directory, the cryptanalyst will have a hard time. This in spite of the fact that the encryption method has been publicized, and so the cryptanalyst knows, in principle, how he/she should interpret the number sequence intercepted.

Exhaustive search is likely to take too long. Of course, the cryptanalyst might also try to call the numbers in the cryptotext and ask the names. The success of this method is questionable - the cryptanalyst might get an angry answer or no answer at all in too many cases. Besides, the method becomes nonapplicable if a reason­ably old directory is used.

The system based on telephone directories is intended to be only an initial illustration, rather than a cryptosystem for serious use. After all, the "reverse" directories are not so hard to come by.

The idea of public-key cryptography is closely related with the idea of one-way functions. Given an argument value x, it is easy to compute the function value /(x), whereas it is intractable to compute x from f(x). Here "intractable" is understood in the sense of complexity theory, see Appendix A. The situation is depicted in Fig. 2.1.

easy

* ■ /(*) intractable

Fig. 2.1

We have referred to /(x) as a function. However, Fig. 2.1 is to be understood in a broader sense that includes also nondeterministic encryption methods, such as the telephone directory example.

Moreover, the computation of x from /(x) should be intractable for the cryptanalyst only. The legal receiver should have a trapdoor available. Let us use the term cryptographic to refer to such one-way functions.

It is to be emphasized at this point that no cryptographic one-way functions are known. Many cryptographic functions /(x) are known such that

(i) It is easy to compute f(x) from x;

(ii) Computation of x from f(x) is likely to be intractable.

However, no proof is known for the intractability claimed in (ii). This reflects the fact that it is very hard to obtain lower bounds in complexity theory. It is very hard to show that, no matter what algorithm we use, a certain computational task is intractable.

From the point of view of public-key cryptography, functions satisfying (i) and (ii) are quite sufficient. In a typical public-key cryptosystem only the straightfor­ward cryptanalysis is based on computing x from /(x). There might be other, more ingenious, cryptanalytic methods, where this computation is avoided. Thus, the cryptanalyst might be successful even if we could show that the computation of x from f(x) is intractable.

These issues will be discussed further in the following example.

Example 2.1. Let us first be more specific in the definition of one-way functions. A problem is termed intractable if there is no algorithm for the problem, operating in polynomial time. If there is such an algorithm, the problem is termed tractable. Easy refers to problems possessing an algorithm operating in low polynomial time, preferably in linear time. NP-complete problems are considered intractable. This is all standard terminology from complexity theory. The reader is referred to Appendix A for further details. It should be observed that traditional complexity theory is by no means ideal from the point of view of cryptography. Traditional complexity theory is all about the worst-case complexity: How hard can the nastiest instance be? Since such nasty instances might be extremely rare, information about the average complexity would be much more essential for cryptography.

A function /(x) being one-way means that the transition from x to /(x) is easy, whereas the reverse transition from f(x) to x is intractable. The second require­ment is often replaced by a milder condition: the reverse transition is likely to be intractable. (This is the condition (ii) above.)

Our example is based on the knapsack problem. An n-tuple

{a_t,a₂, . . . , a„) = A

of distinct positive integers, as well as another positive integer k, are given. The problem is to find, if possible, such integers a, whose sum equals k.

The intuitive picture is that k indicates the size of a knapsack and each of the numbers a, indicates the size of a particular item that can be packed into the knapsack. The problem is to find such items that the knapsack will be full.

As an illustration, consider the 10-tuple

(43, 129, 215, 473, 903, 302, 561, 1165, 697, 1523) as well as the number 3231. We observe that

3231 = 129 + 473 + 903 + 561 + 1165 . Thus, we found a solution. The situation is depicted in Fig. 2.2.

Fig. 2.2

In principle a solution can always be found by checking through all subsets of A and finding out whether one of them sums up to k. In our illustration this means 2¹⁰ = 1024 subsets. (This count includes even the empty subset.) This is certainly manageable.

But what about if there are several hundreds of the numbers a_;? Our illustration is small to aid the readability of the presentation. A more realistic illustration would have, say, 300 a,'s. The point is that no essentially better algorithm than exhaustive search is known. A search through 2³⁰⁰ subsets is unmanageable. Indeed, the knapsack problem is known to be /VP-complete.

Our n-tuple A defines a function f(x) as follows. Any number x in the interval 0 ^ x ^ 2" — 1 can be given a binary representation consisting of n bits - we add initial zeros if necessary. Thus, 1, 2 and 3 are represented as 0 . . . 001, 0 . . . 010 and 0 ... 011, whereas 1 ... 111 is the representation for 2" — 1. We now define /(x) to be the number obtained from A by summing up all numbers a_; such that the corresponding bit in the binary representation of x equals I. Thus,

/(I) =/(0 . . . 001) = a„ ,

/(2) =/(0 . . . 010) = a„-1 ,

/(3)=/(0...011) = a„_₁ +a„,

and so forth. Using vector multiplication, we may write

f(x) = AB_X ,

where B_x is the binary representation of x, written as a column vector.

Our previous equation (see also Fig. 2.2) can now be written in the form

/ (364) = /(0101101100) = 129 + 473 + 903 + 561 + 1165 = 3231 .

Further function values determined by the same 10-tuple are: /(609) = /(1001100001) = 43 + 473 + 903 + 1523 = 2942 , /(686) = /(1010101110) = 43 + 215 + 903 + 561 + 1165 + 697 = 3584 , /(32) =/(0000100000) = 903 ,

(46) =/(0000101110) = 903 + 561 + 1165 + 697 = 3326 , /(128) =/(0010000000) = 215 , /(261) = /(0100000101) =129 +1165 + 1523 = 2817 , /(44) =/(0000101100) = 903 + 561 + 1165 = 2629 , /(648) = /(1010001000) = 43 + 215 + 561 = 819 .

These particular values will be needed below.

The function f(x) was defined using the n-tuple A. Clearly, if we are able to compute x from f(x) then essentially the same amount of work will solve the knapsack problem: x yields immediately its binary representation which, in turn, gives the items of A that sum up to /(x). On the other hand, the computation of /(x) from x is easy. Since the knapsack problem is /VP-complete, /(x) is a good candidate for a one-way function. Of course it is assumed that n is reasonably large, say, at least 200. The function /(x) is also cryptographic, as will be seen below.

Let us first see how "knapsack vectors" A can be used as a basis for a crypto­system. The plaintext is first encoded into bits and divided into blocks consisting of n bits each. If necessary, the last block is "filled" by adding some zeros to the end.

Each of the n-bit blocks is then encrypted by computing the value of the function / for that particular block.

If the plaintext is in English, a natural way of encoding is to replace each letter by the number of the letter in the alphabet, written in binary notation. Five bits are needed for this purpose. In the following table, the numbering of the letters begins from 1, whereas the space between two words is given the number 0.

Consider our previous 10-tuple and the plaintext SAUNA AND HEALTH. Since the blocks to be encrypted consist of 10 bits each, the block division of our plaintext is as follows:

SA UN Aspace AN Dspace HE AL TH

The corresponding eight sequences of bits are:

1001100001 , 1010101110 , 0000100000 , 0000101110 , 0010000000 , 0100000101 , 0000101100 , 1010001000 .

But these sequences are exactly the argument values of / discussed above. Hence, the cryptotext is the 8-tuple

(2942, 3584,903, 3326,215,2817, 2629,819).

So far our cryptosystem based on the knapsack function /(x) is not public-key. Indeed, we can use it as a classical system. Then the cryptanalyst has to find the basic n-tuple A and, after that, still solve the knapsack problem.

If the cryptanalyst can use the setup "chosen plaintext" then it is easy to find A : the cryptanalyst uses plaintexts with exactly one occurrence of 1.

But also the legal receiver has to solve the knapsack problem in order to decrypt. This means that the decryption is equally difficult (and calls for the solution of an AfP-complete problem) both for the cryptanalyst and the legal receiver. This state of affairs is highly undesirable and shows that, as such, the cryptosystem is very bad. In a good cryptosystem decryption should be immensely harder for the cryptanalyst than for the legal receiver.

Let us raise one further issue before we try to improve the cryptosystem and also to convert it into a public-key system. There should never be two plaintexts coming from the same cryptotext. This means that no two different sums formed from the entries of A should be equal. The sums may have the same or a different number of summands but each entry may be used only once. It can be shown that the 10-tuple discussed above has this property. But the 5-tuple (17,103, 50, 81, 33) does not have this property. According to this 5-tuple, the cryptotext

(131,33,100,234,33)

can be decrypted both as SAUNA and FAUNA - a rather high degree of ambi­guity! Further decryptions of the same cryptotext would result if we had a plaintext character encoded as the bit sequence 11011.

Let us now convert the cryptosystem based on the n-tuple A into a public-key one. We begin with some general remarks, and then return to our numerical illustration.

There are classes of easy knapsack problems. One such class results from superincreasing n-tuples A. An n-tuple

A = (a_ua₂,. . . , a_n) is termed superincreasing if each number exceeds the sum of the preceding

62 2. The Idea of Public Keys numbers-that is,

j-i

dj > Yj ^ai for 7 = 2,. . . , n .

i= i

Exhaustive search is not needed to solve the corresponding knapsack problem-it suffices to scan through A once from righ to left. Given k (the size of the knapsack), we first find out whether or not k7z a„. If the answer is "no", a_n cannot belong to the sum we are looking for. If the answer is "yes", a_n must belong to the sum. This follows because all of the remaining a₍'s cannot sum up to k. We define

_{k =} f k if k < a„ , ¹ \ k - a„ if k £ a,

and carry out the same procedure for k_i and a„-_t. We are through when we reach a,. The algorithm shows also that, for any k, the knapsack problem has at most one solution, provided A is superincreasing.

If we publicize a superincreasing A as the basis of our cryptosystem, then decryption will be equally easy for both the cryptanalyst and the legal receiver. In order to avoid this, we "scramble" A in such a way that the resulting B is not any more superincreasing but rather looks as an arbitrary knapsack vector. In fact, it only looks like one because very few knapsack vectors can be obtained in this fashion: the scrambling we use is modular multiplication. Indeed, we used modular arithmetic many times already in Chapter 1. A reader unfamiliar with the congru­ence notation should consult Appendix B.

An integer m > Za,- is chosen. Since A is superincreasing, m is large in compari­son with all numbers in A. Another integer t, with no common factors with m, is chosen, m and t are referred to as the modulus and the multiplier. The choice of t guarantees that there exists another integer t ~¹ such that f f ~¹ = 1 (mod m). The integer t~' can be regarded as the inverse off. It can be easily computed from t and m.

We now form the products fa,, /' = 1, . . . , n, and reduce them modulo m: let b_t be the least positive remainder of ta_{ modulo m. The resulting vector

is publicized as the encryption key. The encryption method for blocks of plaintext consisting of n bits each is the one described above.

The items f, f ~ ¹ and m are kept as the secret trapdoor. Before comparing the situation from the point of view of the cryptanalyst and the legal receiver, let us return to our previous numerical illustration.

It is easy to see that our previous 10-tuple (now denoted by B)

B = (43, 129,215, 473, 903, 302, 561, 1165, 697, 1523)

is obtained by modular multiplication with m = 1590 and t = 43 from the super- increasing knapsack vector

A =(1,3, 5, 11,21,44,87, 175, 349, 701) . Let us verify this in detail.

The first five numbers in B are obtained from the corresponding numbers in A by a direct multiplication with 43-no reduction with respect to the modulus is needed. (In a real-life situation not even the first numbers should be too small because then the multiplier can be easily detected.) The following calculations yield the remaining five numbers in B.

43-44 = 1892 = 1590 + 302,

43-87 = 3741 = 2-1590 + 561 ,

43-175 = 7525 = 4-1590 + 1165 ,

43-349 = 15007 = 9-1590 + 697,

43-701 = 30143 = 18-1590 + 1523 .

We observe further that t and m have no common factors. In fact,

43-37 = 1591 = 1 (mod 1590).

Hence, f"¹ =37.

Let us now find out an easy decryption method for the legal receiver. Consider first the general case, where A is a superincreasing vector and B is obtained from A by multiplying each number in A with t (mod m). Since the legal receiver knows and m, he/she is able to find A from the public key B. After receiving a cryptotext block c\ which is an integer, the legal receiver computes t"V and its smallest positive remainder c (mod m). To decrypt, he/she solves the easy knapsack problem defined by A and c. The solution is a unique sequence p of n bits. It is also a correct block of the plaintext because any solution p' of the knapsack problem defined by B and c' must equal p. Indeed,

c = f~^l c' = f"¹ Bp' = t~^ltAp' = Ap' (mod m).

Observe now that Ap' < m because m > a, + a₂ + . . . + a_n. This implies that the above congruence can be reduced to the equation c = Ap'. Since the knapsack problem defined by A and c cannot have several solutions, we must have p' = p. Thus, how should the legal receiver handle the cryptotext

(2942, 3584, 903, 3326, 215, 2817, 2629, 819)

obtained earlier? Multiplying by f^¹ = 37 he/she obtains first

37 • 2942 = 108854 = 68 • 1590 + 734 = 734 (mod 1590) .

Continuing in the same way, he/she gets the 8-tuple

(734, 638, 21, 632, 5, 879, 283, 93).

The number 734 and the superincreasing A yield the 10-bit sequence 1001100001. Indeed, since 734 > 701, the last bit must be 1. The numbers in A are now compared with the difference 734 — 701 = 33. The first number, from right to left, smaller than 33 is 21. The next number 11 is smaller than the difference 33 — 21 = 12. Finally, the first number 1 equals the difference 12— 11. The positions of 1, 11, 21 and 701 in A are 1, 4, 5 and 10, respectively.

The numbers 638, . . . , 93 yield in the same way the other seven 10-bit se­quences listed above. By decoding all eight sequences the legal receiver obtains the plaintext SAUNA AND HEALTH. □

The above Example 2.1 constitutes the main part of this section. The general principles for the construction of public-key cryptosystems will be stated explicitly in the next section. The cryptosystem based on superincreasing knapsack vectors serves as a simple and yet detailed illustration of these principles. On the other hand, the cryptosystem as such is not very reliable: a polynomial-time algorithm for breaking it will be discussed in Chapter 3. The algorithm is based on the fact that it is not necessary for the cryptanalyst to find the correct multiplier t and modulus m, that is, the ones actually used by the cryptosystem designer. It suffices to find any t' and m' such that the multiplication of the publicized vector by t''¹ (mod m') yields a superincreasing vector. Thus, the cryptanalyst may actually break the system by preprocessing, that is, after the encryption key has been publicized. Since the public encryption keys are used for some time, there is often plenty of time for preprocessing, whereas the cryptanalyst is in a hurry after intercepting important encrypted messages.

One-way streets-that's what public-key cryptography is all about. The reader might think of examples of one-way streets within different realms of life. Here is one very typical example. The device depicted in Fig. 2.3 is a trap used for fishing, especially in the nordic countries.

Fig. 23

It is very easy for a fish to enter the cage. The shape of the entrance guides the fish in-for further encouragement there might be some small fish in the cage as a bait. On the other hand, it is very hard for a fish to find its way out, although in principle an escape is possible. The legal receiver, that is the fisherman, takes the fish out by opening the trapdoor on top of the cage.

2.2 How to Realize the Idea

This section will contain some general principles about the construction of public- key cryptosystems. The knowledge of the encryption key E_k should not give away the decryption key D_k. More specifically, the computation of D_k from E_k should be intractable, at least for almost all keys k.

The following mechanical analog depicts the difference between classical and public-key cryptosystems. Assume the information is sent in a box with clasp rings. Then, encryption according to a classical cryptosystem corresponds to the locking of the box with a padlock and sending the key via some absolutely secure channel, such as using an agent in the James Bond class. Key management is always an essential issue, and often constitutes a difficult problem, when one uses classical cryptosystems.

Public-key cryptography corresponds to having open padlocks, provided with your name, freely available in places such as post offices. A person who wants to send a message to you closes a box with your padlock and sends it to you. Only you have a key for opening the padlock.

Fig. 2.4

The following modification of the basic public-key procedure is suitable for classical cryptosystems as well. Denote by E_A,E_B,... the encryption procedures used by A, B, ... . Denote the decryption procedures similarly by D_A, D„, Assume further that the cryptosystem is commutative: in any composition of E_A, E_B, D_a, D_b, ... the order of the factors is immaterial. If A wants to send a message w to B, then the following protocol is used:

(i) A sends E_A{w) to B .

(ii) B sends E_B(E_A(w)) to A .

(hi) A sends D_A(E_B(E_A(w))) = D_A(E_A(E_B(w))) = E_B(w) to B .

(iv) B decrypts D_B(E_B(w)) = w .

Coming back to our illustration with padlocks, open padlocks need not be distributed in advance if this protocol is followed. First, A sends the box to B, locked with /l's padlock. Then, B sends the box back to A, now locked also with B's padlock. Next, A opens the padlock E_A and sends the box back to B. Now B can open it. Thus, the box is always protected by at least one padlock. There is no problem in the key management: the keys are not distributed at all. See Fig. 2.4.

The protocol described above is secure against passive eavesdroppers. How­ever, an active eavesdropper C might masquerade him/her as B. Then A has no way of knowing who the other party actually is. By a passive eavesdropper we mean a cryptanalyst who tries only to obtain all possible information in order to decipher important messages. An active eavesdropper masquerades him/her as the intended receiver of a message and returns information to the original sender accordingly.

We are now ready to list the general principles behind the construction of public-key cryptosystems.

Step 1: Start with a difficult problem P. P should be intractable according to complexity theory: there is no algorithm that solves all instances of P in polynomial time with regard to the size of the instance. Preferably, not only the "worst- instance" complexity but also the average complexity of P is high.

Step 2: Pick up an easy subproblem P_easy of P. P_easy should be in polynomial time, preferably in linear time.

Step 3: "Shuffle or scramble" P_easy in such a way that the resulting problem F*shuffie does not resemble the problem P_easy any more. The problem P_shuff,_e should at least look like the original intractable problem P.

Step 4: Publicize P_shuffle, describing how it should be used as an encryption key. The information concerning how P_easy can be recovered from P_shuffle is kept as a secret trapdoor.

Step 5: Construct the details of the cryptosystem in such a way that decryption will be essentially different for the cryptanalyst and the legal receiver. While the former has to solve P_shuff_ie (looking like the intractable P), the latter may use the trapdoor and solve only P_easy.

Of course, our description of the Steps 1-5 is still on a very abstract level. The quality of the resulting public-key cryptosystem depends on how the details can be filled in. There are many questions to be answered. How is P_si,_Uffi_e used as a basis for encryption? How easy is P_easyl What constitutes the trapdoor? In particular, is it possible for the cryptanalyst to find the trapdoor by preprocessing? Can an instance of P_shuffle be easy to crack just accidentally? And so forth. We will return below to the theoretical problems involved.

Let us now recall Example 2.1 from the preceding section. It serves as a very typical illustration of Steps 1-5. The knapsack problem is A^-complete - so it is a very suitable choice for the basic intractable problem. The superincreasing knapsack problem is an easy enough subproblem of P. Modular multiplication constitutes a reasonable way of shuffling. We still return in Chapter 3 to the problem of how reasonable it actually is. This discussion will also deal with the possibilities of the cryptanalyst, as well as with some modified cryptosystems. In general, knapsack vectors form a natural and useful method for encryption.

What is very interesting about the basic Steps 1-5 of public-key cryptography has something to do with their universality: the subject matter or the area of the problems is not specified in any way. In principle, the problems can be almost about anything. Examples will be seen in later chapters. However, so far the problems most suitable as a basis for a public-key cryptosystem have dealt with number theory. We have already seen an example: the knapsack problem. So far the most widely studied public-key cryptosystem, RSA, is also based on number theory. The product of two large prime numbers can be publicized without giving away the primes themselves. The one-way function, or the trapdoor, can be formulated in these terms. Details will be presented in Chapter 4.

It is maybe intrinsic in the nature of public-key cryptography that very little or nothing is known about the underlying problems. Thus, RSA has been very successful although the complexity of the underlying problem, factorization, has not been adequately characterized. On the other hand, some public-key crypto­systems based on provably intractable problems (/VP-complete, etc.) have turned out to be failures.

For future reference, we now list some very fundamental number-theoretic problems that have so far defied all attempts to classify their complexities. Indeed, none of the subsequent problems is known either to possess a deterministic polynomial time algorithm, or to be complete for any natural complexity class. The problems have turned out to be very useful for many aspects of public-key cryptography. Some mutual reductions among the problems are also known: which of them are "easier" and which are "harder".

FACTOR(n). Find the factorization of n.

PRIMALITY(n). Decide whether or not n is prime.

FIND-PRIME( > n). Find a prime number >n.

SQUAREFREENESS(n). Decide whether or not a square of a prime

divides n.

QUAD-RESIDUE(a,n). Decide whether or not x² = a (mod n) holds for some x.

SQUAREROOT(a,n). Find, if possible, an x such that x² = a (mod n).

DISCRETE-LOG (a, b,ri). Find, if possible, an x such that a^x = b (mod n).

A number-theory minded reader might want to think of some natural reduc­tions among the problems mentioned. For instance, if we are able to factor n, we are also able to tell whether or not n is prime. In fact, the primality problem is essentially simpler than factorization because there are many easily computable criteria to the following effect: if n is prime then a certain condition A (for instance, a congruence) is satisfied. Hence, if A is not satisfied then we are able to conclude that n is composite, without being able to factorize n.

From the theoretical point of view it would be desirable to be able to formally establish some lower bounds for the amount of work the cryptanalyst has to do in order to break a public-key cryptosystem. Unfortunately, no such theoretical lower bounds are known for the most widely used public-key cryptosystems. For in­stance, FACTOR(n) might be in low polynomial time, which would mean that RSA and related systems would collapse. On the other hand, it is not likely that FACTOR(w) is in low polynomial time. After all, people have investigated FACTOR(n) (more or less intensely) already for more than two thousand years.

We will now discuss some issues of complexity theory that shed some light on the state of affairs: there are no provable lower bounds for the amount of work of a cryptanalyst analyzing a public-key cryptosystem. In fact, our previous Golden rule can be extended to concern public-key cryptosystems as follows.

Golden Rule for Designers of Public-Key Cryptosystems. Test your system in practice from various points of view. Do not expect to prove remarkable results concerning the security of your system.

Again, a reader not familiar with the basics of complexity theory should consult Appendix A. It is generally believed that P 4= NP. This implies that /VP-complete problems are intractable. Hence, if we can show that the cryptanalysis of a public- key cryptosystem is NP-complete, we would have established its intractability. However, the following argument shows that this is not likely to be the case.

The encryption key is public. Combine this fact with the requirement posed for any cryptosystem, classical and public-key alike: the encryption is easy once the encryption key and the plaintext are known. (Otherwise, the cryptosystem would be very cumbersome to use!) It follows that in any reasonable public-key cryptosys­tem the cryptanalysis problem is in NP. Given a cryptotext, the cryptanalyst first guesses the plaintext and then encrypts it, finding out whether it leads to the given cryptotext. Even if the publicized encryption method is nondeterministic, the whole procedure is still clearly in NP.

The cryptanalysis problem is also in Co-NP. If the encryption method is determinis­tic, then this is obvious because one can proceed exactly as before: find out that the given plaintext-candidate does not yield the given cryptotext. In the general case, independently of whether the encryption method is deterministic, we argue as follows. We are given a triple

(w, k, c),

where w is a candidate for the plaintext, k is the public encryption key and c is the cryptotext. We are supposed to accept the triple exactly in case w is not the plaintext giving rise to c. Clearly there is only one such plaintext; otherwise, decryption would be ambiguous.

Our algorithm first guesses the plaintext p, then finds out (in nondeterministic polynomial time) whether p gives rise to c according to k. Only in case of a positive answer the algorithm continues, comparing p and w letter by letter. If a difference is found, the algorithm accepts.

We are viewing the cryptanalysis problem in the obvious fashion: find the plaintext when the cryptotext and the public key are known. Along similar lines one can show that several analogous problems are in the intersection NP n Co-NP, for instance, the following ones. In each case we assume that the public encryption key and the cryptotext are given.

(i) Does a given word appear as a prefix (resp. a suffix) in the plaintext?

(ii) Does a given word appear as a subword in the plaintext?

(iii) Is a given word obtained by considering only the letters in the positions 5, 10, 15,. .. in the plaintext?

Thus, the cryptanalysis problem for a public-key cryptosystem is in the inter­section NP n Co-NP. Hence, if the cryptanalysis problem C would be NP-com­plete, we would have NP = Co-NP. This is seen by the following simple argument. Consider any L in NP. Since C is /VP-complete, L is polynomial time reducible to C. Consequently, also the complement of L is polynomial time reducible to the complement of C, which is in NP, by our assumption. This implies that L is in Co-NP and, hence, NP is included in Co-NP. By this inclusion, the reverse inclusion is obvious. Take any L in Co-NP. The complement of L is in NP and, consequently, in Co-NP. This implies that L is in NP.

We have shown that if the cryptanalysis problem for a public-key cryptosystem is /VP-complete, then NP = Co-NP. This implies that it is highly unlikely that the cryptanalysis problem for a public-key cryptosystem is NP-complete or higher up in the complexity hierarchy. We can look for examples optimal from the point of view of complexity theory.

Example 2.2. (Due to [Kar 1].) Consider wlTpc's (see Appendix A) with variables in X u Y, where X and Y are disjoint. Every such wffpc is built from variables using propositional connectives v , a and ~ . We allow also the truth-values T and F to appear in a wffpc.

Let a be an assignment of truth-values for the variables in X, and p₀ and p, two wffpc's such that p₀ assumes the truth-value 7" and p₁ the value F (or vice versa) for every assignment of truth-values for variables in X u Y that uses a for the variables in X. Thus, if a is used for X, the truth-values of p₀ and p_t are independent of the truth-values assigned for the variables in Y. The pair (p₀, p_l) constitutes the public encryption key, whereas a is the secret trapdoor.

As an illustration, consider X = {x_u x₂} and Y = {yi,y₂}- Define a by

a(x,) = F and <x(x₂) = T.

One can then choose

p₀ = ~ y_x A y₂ A x₂ A (>>! V X, V y₂ A X₂)) ,

Pl = (y₂ V x₂) A (^ v X, V y, A x₂)).

It is easy to see that, independently of the values for y_l and y₂,p₀ assumes the value F and p, the value T for a.

To encrypt a particular occurrence of the bit i in the plaintext, one assigns in p_f truth-values for the variables in Y in an arbitrary fashion and shuffles the resulting wffpc (with variables in X) randomly according to the standard rules of the propositional calculus (introduction and elimination of T and F, associativity, commutativity, distributivity, idempotence). If we assign the values F and 7 for y_l and y₂ in our illustration, p₀ reads

~ F a T a x₂ a (F v x₁ v T a x₂)) ■

This can be shuffled to x₂ a x,. Consequently, x₂ a Xj is one possible encryption for the bit 0.

Legal decryption is immediate because a is known. Using the iVP-completeness of the satisfiability problem, the following result can be obtained. Assume that we may consult an oracle who, given the public key and a cryptotext, tells us the bit the cryptotext is obtained from. (Oracles will be discussed in more detail in Chapter 4.) Then for every language in the intersection of NP and Co-NP, there is a deterministic polynomial time algorithm using the oracle for determining whether or not a given word is in the language. The result means that the cryptanalysis of any public-key cryptosystem can be reduced to the cryptanalysis of the system described above. Thus, the system is optimal in the sense that any cryptanalytic method to break it can be used to break any other public-key cryptosystem as well.

Unfortunately, the same result can be obtained for the following degenerate system. In the public key (p₀, pj, exactly one of the p's, say p_k, is satisfiable. The index k constitutes the secret trapdoor. An occurrence of the bit i is encrypted by first assigning truth-values for the variables in p, in an arbitrary fashion. If the resulting truth-value for p, is T, i is encrypted as #, otherwise i is encrypted as i itself.

In the legal decryption one simply maps # to k and leaves 0 and 1 unchanged. On the other hand, a cryptanalyst can find out the meaning of # by generating assignments until either p₀ or p_t becomes true. If p_k is rarely true, then # occurs rarely in the cryptotext. Thus, the degenerate system is intuitively very weak. The paradox of the system being optimal is explained by the fact that we have considered worst case rather than average complexities. □

In the discussion above the setup for cryptanalysis has been: given cryptotext and public encryption key. For the setup "encryption key only" the cryptanalysis problem is still in NP for any public-key cryptosystem. Interestingly enough, the system given in Example 2.2 is optimal also as regards the cryptanalytic setup "encryption key only": the cryptanalysis problem is /VP-complete.

It is obvious that no similar upper bounds for cryptanalytic complexity can be given for classical cryptosystems. Essentially, this due to the fact that because everything is kept secret then the easyness of the encryption and decryption for legal users cannot lead to any consequences as regards the world of the cryptanalyst.

A final rather strange observation can be made from the point of view of complexity theory. A public-key cryptosystem can always be viewed as a sequence of pairs (£, , D_f), / = 1, 2, . . . , where E_i is an encryption key and D_t the correspond­ing decryption key. Both keys are completely determined by i: they can be given by some verbal description. Preprocessing proceeds now as follows. After an encryp­tion key E_k has been publicized, the sequence (£,, £>,) is generated, until the correct £,(= the one verbally coinciding with E_k) is found. This may involve a huge (computationally intractable) amount of work. But still: this amount is a constant independent of the length of the cryptotext. From this point of view, the complexity of the cryptanalytic setup "cryptotext and encryption key" is n + c, where c is a constant! Of course, from a practical point of view, this does not say much because c is huge.

2.3 Obvious Advantages of Public Keys

The advantages of public-key cryptography are tremendous, provided the idea can be realized without any too harmful side-effects. The most far-reaching innovation due to public keys concerns key management: how to handle and send keys.

Consider any classical (that is, symmetric) cryptosystem. The encryption key gives away the decryption key and, hence, the former cannot be publicized. This means that the two legal parties (sender and receiver) have to agree in advance upon the encryption method. This can happen either in a meeting between the two parties, or else by sending the encryption key via some absolutely secure channel.

If a public-key cryptosystem is used, the two parties do not have to meet - they do not even have to know each other or be in any kind of previous communication! This is a huge advantage, for instance, in the case of a big data bank, where there are numerous users and some user wants to communicate only with a specific another user. Then he/she can do so just by applying the information in the data bank itself.

One can compare classical and public-key cryptosystems also as regards the length of a key. Since every key has to be described somehow, the description being a sequence of letters of some alphabet (that is, a word), it is natural to talk about the length of a key. There is a remarkable difference between classical and public-key cryptosystems.

Consider first a classical cryptosystem. If the key is longer than the plaintext, nothing has really been achieved. Since the key has to be transmitted securely, one could transmit the plaintext instead of the key via this secure channel. Of course, in some situations the key is transmitted earlier to wait for the crucial moment.

Consider next a public-key cryptosystem. The length of the encryption key is largely irrelevant. The key is publicized anyway. This means that also the length of the decryption key is largely irrelevant: the receiver only has to store it in a secure place.

The easiness of key management can justly be regarded as the chief advantage of public-key cryptography. Let us now consider some other advantages. The central issues raised will be discussed also later on.

One of a computer system's central strongholds is the password file. The following might be an entry in such a file.

login: JOHNSON password: KILLER

If the password file is exposed - accidentally or otherwise-to an inspection by an intruder, then the intruder will have free access, for instance, to Mr. Johnson's electronic mail. We assume here that the mail is not encrypted and, thus, security is provided only by the passwords.

Suppose now that one-way functions / are used in connection with the pass­word file. The entry mentioned above is now as follows.

login: JOHNSON password: KILLER function: f_}

Here /, is a description of a one-way function. The idea is that KILLER is Mr. Johnson's "public" password, whereas only Mr. Johnson knows his "secret" pass­word PURR such that

fj(PURR) = KILLER .

In fact, he "publicized" the password KILLER after computing^,(PURR).

Mr. Johnson types in the secret password PURR, after which the computer checks whether or not f_} applied to PURR gives the correct result KILLER. The computer does not store PURR in any way. The password file may now be inspected by an intruder without loss of security because the function fj cannot be inverted.

The one-way functions / need not be cryptographic: a trapdoor for inverting them is useless in this case. It is even possible to have the same function for all users. The reader might suggest in what respect such a common function is weaker than individual functions.

Authentication is an important issue. How do we know that a message planted in a communication channel or information system is authentic? How do we generate such an electronic or digital signature? Let us first state more explicitly what we want.

Consider two parties A and B, possibly with conflicting interests. Typically, the parties could be a bank and its customer, or the two superpowers. When A sends a message to B, the message should be signed in such a way that the parties get the following two kinds of protection.

(i) Both A and B should be protected against messages addressed to B but fed in the information system by a third party C, who pretends to be A.

(ii) A should be protected against messages forged by B, who claims to have received them from A, properly signed.

Of course, if B sends a message to A then A and B should be interchanged in (ii).

One may visualize (i) and (ii) by thinking B as an American agent in Moscow, A as his/her boss in Washington, and C as a Russian agent. The importance of (i) should be obvious, (ii) is required, for instance, in case B initiates some operation without any authorization from A. The operation turns out to be a failure. However, B claims to have acted according to the instructions given by A in a properly signed message!

Conditions (i) and (ii) are somewhat contradictory and, therefore, hard to satisfy simultaneously. According to (i), B should know something about 4's signature. According to (ii), B should not know too much about /l's signature. It is to be emphasized that electronic signatures usually change the whole text, rather than just being an addition to the end of the text.

If a good classical cryptosystem is used, then requirement (i) can be satisfied in a reasonable fashion: A and B agree upon an encryption key known only to them. A message is signed by encrypting it according to the key. The key and preferably also the cryptosystem have to be changed reasonably often. Once C finds out the key, he/she can start sending properly signed messages.

Requirement (ii) is apparently more difficult to satisfy because, as we already pointed out, B should know something about the way A generates the signature, and yet it should be impossible for B to generate /Ts signature. Observe also that if we are dealing with a big network of communicating parties (such as a network of mail users) then it is impractical to use a distinct secret method of signing for every pair of users.

If a public-key cryptosystem is used, then both (i) and (ii) can be satisfied, at least in principle. As before, we denote by E_A,E_B, . . . (resp. D_A,D_B, . . .) the encryption (resp. decryption) key used by A, B, ... . First, A sends the message w to B in the form E_B(D_A( w)). Then, B can recover D_A(w) by his/her secret decryption key D_g. From D_A(w), B can recover w by the publicly known E_A. Observe that E_A and D_a are inverses.

Now both (i) and (ii) are satisfied. Only A knows D_A and, hence, neither C nor B can forge /l's signature. This is the case at least if plaintexts are meaningful passages of some natural language. Then the probability is negligible that some text not obtained by D_A from a meaningful plaintext would translate into some­thing meaningful. By this reason, A can also not deny sending the message to B.

If only signature (but not the encryption of the message) is important, then it suffices that A sends B the pair (w, D_A(w)). Requirements (i) and (ii) are satisfied as before.

The basic procedures of authentication described above are vulnerable, especially as regards attacks by active eavesdroppers. The seriousness of attacks depends on the details, in particular, on the possibilities of the eavesdropper to plant false messages in the system. The basic procedures can be strengthened by applying a protocol. This means that /Ts sending a message to B consists of several communication steps between A and B. A first communicates something to B. Depending on the contents of this communication, B communicates something back to A. And so forth.

In general, a protocol involves a sequence of message exchanges. The number of communicating parties may be also greater than two. A specific, usually public-key, cryptosystem is used. The security of a protocol usually means protection against a passive or an active eavesdropper but often also protection against cheating by some of the parties. In the latter case a protocol may provide for arbitration procedures if the parties happen to disagree about their adherence to the protocol. Protocols are no more secure than the cryptosystem applied. It is difficult to prove that a specific cryptosystem possesses certain security properties. It is also difficult to prove that if the underlying cryptosystem satisfies certain security conditions then the protocol possesses certain security properties.

Many of the issues involved will be dealt with in the sequel, especially in Chapter 6. Here we briefly mention some examples of problems and tasks for which protocols have been successfully applied.

Handshaking is in general slightly more complicated than authentication. The problem is that A and B want to establish a secure communications channel in a certain communications environment without any prior exchange of information. In our previous example the American agent in Moscow and the boss in Washington had to agree beforehand at least about something: how in principle signatures are generated and where the public keys are available. (We assume that they used the basic procedure described above.) This is not actually much and can be included in the common instructions provided for the users of an information system. Hence, the situation is very close to handshaking.

Very often handshaking is understood to imply that the parties trust each other. Thus requirement (ii) becomes unnecessary.

Suppose elections are held over a computer network. A protocol should make it impossible for non-registered voters to vote although they might be legal users of the network. Furthermore, ballots should be kept secret and the publicized out­come of the elections should be fair.

Also some new types of secret votings can be carried out using appropriate protocols. Such protocols seem to open new vistas for confidential communication.

Some members of a council might have the right of veto. When an appropriate protocol is followed, nobody knows whether a negative decision is based on the majority, or somebody using the veto-right, or on both!

Let us consider a specific example. The parties A, B, C,, . . . , C„ want to make a yes or no decision. All parties can vote yes or no. Moreover, A and B have two additional votes, super-yes and super-no. Such a voting may be visualized as arising in the United Nations, with A and B being the two superpowers. If no supervotes are cast, the majority decides. If at least one supervote is cast, then the ordinary votes have no significance. The decision is yes in case of a draw. After the voting all parties know the decision but nobody knows why the decision was made. Was it due to a supervote, majority, or to both? Of course, it is possible to construct a voting machine to satisfy the requirements. But nobody would trust such a machine: it could be tampered to leak information and/or announce a false outcome for the voting.

In the next example a specific protocol is suggested.

Example 2.3. Two persons A and B want to play poker by telephone without any third party acting as an impartial judge. We consider the basic variant of the game, where five cards are dealt. As regards most of the other variants, the protocol is essentially the same. It is obviously necessary for A and B to exchange information in encrypted form in order to "deal" cards in a proper way.

A proper deal should satisfy the following requirements.

(i) All hands (sets of five cards) are equally likely.

(ii) The hands of A and B are disjoint.

(iii) Both players know their own hand but have no information about the opponent's hand.

(iv) It is possible for each of the players to find out the eventual cheating of the other player.

We now propose a protocol. A cryptosystem, classical or public-key, is used. However, neither the encryption methods E_A and E_g nor the decryption methods D_a and D_B are publicized. Moreover, commutativity is assumed: in any composition of E's and D's the mutual order is immaterial. Before the actual play, A and B agree on the names w_l, . . . , w₅₂ of the 52 cards. The names are chosen in such a way that the cryptosystem is applicable in the sense needed in the sequel. For instance, if E_A and E_B operate on integers within a certain range then each w, should be an integer within this range.

We are now ready to describe the protocol. A acts as the dealer but the roles of A and B can be interchanged. The protocol consists of the following four steps.

Step 1: B shuffles the cards, encrypts them using E_B, and tells the result to A. This means that B tells A the items Eg^), . . . , E_B(w_S2) in a randomly chosen order.

Step 2: A chooses five of the items £_fl(w,) and tells them to B. These items are B's cards.

Step 3: A chooses another five of the items £_B(w,), encrypts them by E_A, and tells the result to B.

Step 4: After receiving five items of the form E^Egiw^) in Step 3, B applies D_B to them and tells the result to A. These five items represent ,4's cards.

Let us now see how the requirements (i)-(iv) are satisfied. Clearly both players know their own cards. In particular, A receives in Step 4 five items of the form £)_b(£_/1(£_b(w_i))). Because of commutativity,

D,(E_A(E_b(W,))) = E_A(D_B(E_B(_Wi))) = E_a(wi) ,

and hence A has only to use D_A. The hands will also be disjoint: B can immediately check that the items given in Step 3 differ from those given in Step 2.

No conclusive evidence can be presented as regards the other requirements (i)-(iv). The matter depends largely on how truly one-way functions the E's actually are. For instance, it might be impossible to find w_f on the basis of EgiwJ but, still, some partial information about w, could be found. For instance, if w, is a sequence of bits, the last bit could be found from E_B(w,.). Such partial information could tell A that all aces are within a certain proper subset of E_B(w_l), . . . , E_B(w₅₂). Then A would surely deal B only cards outside this subset and for himself/herself only cards from this subset. In this case (i) and the second part of (iii) would be violated.

The cryptosystem cannot be public-key in the normal sense. A could simply compute all the values E_B(\V[) and deal the cards accordingly: a good hand for B but slightly better for himself/herself!

Some of the issues in this example are of general nature and will be discussed also later. In fact, a public-key cryptosystem can never have a small plaintext space, such as only 52 plaintexts. Then all of them can be encrypted using the public key, and decryption amounts to a search through all resulting cryptotexts.

The possibility of obtaining partial information is also one of the central issues in public-key cryptography. For some cryptosystems, such as RSA, it has been shown that if partial information can be obtained then the whole system can be broken. This means that if you are convinced about the security of the cryptosystem, then you also know that the system does not leak partial information. □

We conclude this chapter by mentioning three problems that require crypto­graphic protocols for their solution. The protocols devised for these problems are often used as a part of a protocol for a more complicated problem. Thus, the protocol given in [GM] for the problem of Example 2.3 uses coin flipping.

A and B want to flip a coin by telephone without any impartial judge. As always, both parties should at some later stage be able to check that the other party did not cheat. This may happen after the result of the coin flipping has been used for some other purpose.

An oblivious transfer allows A to transfer a secret to B with probability 2- After the completion of the protocol, B knows whether or not the secret was transferred successfully, but A does not know.

Two or more parties want to share a part of their secrets but do not want to give away their secrets entirely. For instance, two people want to find out who is older without learning anything else about each other's age. After going through the protocol both know who is older but neither one knows how much older.

Date: 2015-02-16; view: 597