Sebery J.Cryptography.An introduction to computer security.1989

s s

0 0

1 1

2 3

3 4

4 5

5 6

6 7

7 2

Table 3.17. An example of S-box

4 PUBLIC-KEY CRYPTOSYSTEMS

In 1976 DiÆe and Hellman [152] described the framework for public-key cryptography. It was not until 1978 that three designs for public-key cryptosystems were were published. Rivest, Shamir and Adleman [432] showed how the discrete logarithm and factorization problems could be used to construct a public-key cryptosystem. This is the well-known RSA cryptosystem. Merkle and Hellman [340] used the knapsack problem in their construction. McEliece [330] built a system based on error correcting codes. Later in 1985 ElGamal [163] designed a public-key cryptosystem using the discrete logarithm problem. Koblitz [284] and Miller [347] suggested the use of elliptic curves in the design of public-key cryptosystems. Nowadays, there are quite a few more suggestions as to how design public-key cryptosystems, but none so popular as RSA and ElGamal cryptosystems.

In Section 4.1, we introduce the notion of public-key cryptography. In the next four sections we discuss the basic implementations of RSA, MH, McEliece and ElGamal cryptosystems. Section 4.7 presents probabilistic encryption. Section 4.8 studies the hierarchical structure of public-key security levels and their impact on public-key design.

4.1 Concept of Public-Key Cryptography

In private-key cryptosystems, both encryption and decryption apply secret keys. Typically, both keys are the same or the knowledge of one of them is enough to determine the other. That is why private-key systems are also called symmetric. Public-key cryptosystems use two di erent keys. One is public while the other is kept secret. Clearly, it is required that computing the secret key from the public key has to be intractable. Public-key cryptosystems are also called asymmetric. As public-key cryptosystems use two keys, it is possible to make public either the encryption or decryption key. If the encryption key is

Fig. 4.1. Diagram of a public-key cryptosystem

public, we deal with cryptosystem in which anybody can encrypt a message (plaintext) into a cryptogram (ciphertext) but only the receiver can decrypt the cryptogram. The system can be used for secrecy only. If the decryption key is public, anybody can read cryptograms, but only the holder of the secret encryption key can generate meaningful cryptograms { the system can be used for authenticity only. In this chapter we will concentrate on secrecy systems in which encryption keys are public.

A cryptosystem with a public encryption key is depicted in Figure 4.1. Sets of messages, cryptograms and keys are M, C and K, respectively. The setup of the system is done by the receiver Bob who generates a pair of keys (e; d) 2 K. Bob broadcasts the encryption key e and keeps the decryption key d secret. Assume that Alice wants to communicate secretly a message m 2 M to Bob. She uses the known encryption algorithm E : K M ! C and the public key to compute the cryptogram c = Ee(m) 2 C. The cryptogram is sent over the insecure channel to Bob. Bob now applies his secret key d together with the decryption algorithm D : K C ! M to recover the message m = Dd(c). The cryptosystem has to be eÆcient and secure. The eÆciency requirement can be translated into the following conditions:

1.Calculation of the pair (the public key e, the secret key d) can be done by the receiver in polynomial time.

2.The sender, knowing the public key e and a message m, can determine in polynomial time the corresponding cryptogram,

3.The receiver, knowing the cryptogram c and the secret key d, can compute the original form of m in polynomial time,

The security requirement is equivalent to the following conditions:

1.The task of computing the secret key d from the public key e must be intractable for any instance of the public key.

2.Any attempt to recover the message m from the pair (e; c) must be equivalent to solving an intractable instance of a suitable problem.

Assume that for a parameter n 2 N , we have a set of encryption functions

E(n) = fEe j Ee : n ! (n)g

where (n) is a polynomial in n. Every element of the set E(n) is indexed by the public key e 2 K. So the set E(n) consists of all encryption functions which can be used in the system for the xed n. The family

describes the public encryption. The integer n is also called the security parameter as it indicates the size of the message and cryptogram spaces. Now we can de ne two search problems. The rst problem is called the public encryption and has the following form:

Name: Public encryption

Instance: Given a security parameter n 2 N , public-key scheme with the family

E = fE(n) j n 2 Ng of encryption functions, public key e 2 K and message m 2 n.

Question: What is the cryptogram c = Ee(m) 2 (n) where Ee 2 E(n)?

The second problem called the public decryption has the form: Name: Public decryption

Instance: Given a security parameter n 2 N , public-key scheme with the fam-

ily E = fE(n) j n 2 Ng of encryption functions, public key e 2 K and cryptogram c 2 (n).

Question: What is the message m = Ee 1(c) 2 n ?

Clearly, the public encryption must belong to the class P while the public decryption should belong to NP-hard. NP-hardness of decryption is necessary

176 4 PUBLIC-KEY CRYPTOSYSTEMS

but not suÆcient for security of public-key cryptosystems. Ideally, for a large enough n, we would hope that all instances of the public decryption are intractable or hard. In practice, we may have to accept that some instances of the public decryption are easy with the caveat that the probability of occurrence of such instances is negligible. The pair of the public encryption and decryption problems uses the family of encryption functions E. The family is an example of a one-way function. For a large enough security parameter n and a message m, it is easy to compute c = Ee(m) while computing m = Ee 1(c) is hard.

Public-key cryptography works on the assumption that potential users have access to authentic public keys. By encrypting a message using a public key, the sender creates a ciphertext that can be decrypted by the holder of the corresponding secret key only. Therefore, any mistake while choosing public keys, results in unintentional change of the destination in which the cryptogram can be decrypted. The Public Key Infrastructure (PKI) provides a mechanism for users to obtain authentic public keys together with the unique identi er of the owner of the corresponding secret key [132, 448].

4.2 RSA Cryptosystem

The RSA system applies the factorization problems as the underlying intractable problem. In the system, messages, cryptograms and keys (public and secret) belong to the set ZN . The integer N is the product of two distinct primes p and q, i.e. N = p q. The set ZN along with addition and multiplication modulo N creates a ring. For a given public key e and message m, the encryption function is

Clearly, the encryption and decryption process should allow to recover the original message m so

m = Dd(Ee(m)):

Substituting (4.4) and (4.5), we get:

The congruence must be true for all messages. It is known that the Congruence (4.6) has a solution if and only if

This follows from a standard application of Fermat's little theorem. The system is set up by the receiver Bob who

{ chooses two large enough primes p and q,

q while keeping the factors p; q secret,

{selects at random the key e 2R ZN which is coprime to lcm(p 1; q 1) and makes it public,

{computes the secret key d according to Congruence (4.7).

The sender, Alice, encrypts a message m using Congruence (4.4) and sends the corresponding cryptogram to Bob. Upon receiving the cryptogram, Bob applies Congruence (4.5) to recover the message.

RSA cryptosystem

Problems Used: Factorization.

Consider a simple example. Assume that Bob intends to create an instance of the RSA cryptosystem. First, Bob selects integers p = 7 and q = 11. Next, he calculates lcm(6; 10) = 30, and randomly selects the public key e = 13. Subsequently, he nds the secret key by solving the Congruence (4.7) so,

13 d 1 (mod 30) ) d = 7

The above congruence can be solved using the Euclid algorithm (see Section 2.1.1). The pair (N = 77; e = 13) is published. If Alice now wants to transmit the message m = 36, she calculates the cryptogram,

178 4 PUBLIC-KEY CRYPTOSYSTEMS

c = me = 3613 71 (mod 77)

and forwards it to Bob. Since Bob knows the secret key d, he recreates the message according to the following congruence:

m = cd = 717 36 (mod 77)

The above system is an instance with a very low security parameter and is insecure because anybody can guess the factors of the modulus. Given p; q, an adversary can recover d from e using Congruence (4.7).

To have a \secure" instance of the RSA system, we have to pick up large modulus N so both an instance of the public decryption problem and an instance of the factorization problem (factorization of N), are intractable. The primes p and q used in the RSA system have to be at least 100 decimal digit long. Thus the modulus N has 200 decimal digits and the best known factoring and discrete logarithm algorithms take 1023 steps each. On the other hand, the implementation of public encryption can be done by using the fast exponentiation algorithm from Section 2.1.3. As the holder of the secret key knows factors of N, decryption can be sped up by using the fast exponentiation independently for the moduli p and q and merging the results using CRT.

There are many RSA implementations in hardware. Their speed depends on the length of the moduli used. A typical VLSI chip for RSA handles 512bit long moduli and processes plaintext/ciphertext at the rate 64 kilobits per second which is roughly 1000 times slower than for DES. More secure hardware implementations use moduli of length 768, 1024 or 2048 bits [301].

4.2.1 Variants of RSA

In some circumstances, senders may have limited computational power. This usually happens when the encryption is being done by a smart card which has limited memory and CPU power. Clearly, we can reduce the number of computations by restricting the value of the public key.

Rabin [422] suggested an RSA variant with the public key e = 2. This is the smallest nontrivial exponent. The public encryption is

where N as before is the product of two primes p and q. The receiver, who knows the factorization of N, can decrypt c by solving two following congruences: pc

4.2 RSA Cryptosystem 179

m1 (mod p) and pc m2 (mod q). In fact, the rst congruence has two possible solutions m1 and so does the second m2. To compose the original message m using the Chinese Remainder Theorem, the receiver needs to guess correctly the signs of m1 and m2. Rabin's system has 4:1 ambiguity in the decrypted message.

Williams [532] showed how to improve Rabin's scheme. He observed that the decryption process can be simpli ed for all messages m whose Jacobi symbol 1 is

In William's modi cation, the receiver Bob selects two Blum primes p and q

Finally, the cryptogram is computed for m0 according to (4.8), and Alice for-

as the message m0 is even. The enciphering and deciphering processes described above are illustrated in the following example.

180 4 PUBLIC-KEY CRYPTOSYSTEMS

the sender Alice while the key d = 8 is kept secret.

If Alice wishes to transmit the message m = 54, she rst calculates the

Finally, Alice forwards the triple (c; c1; c2) = (67; 0; 0) as the cryptogram. After obtaining the triple, Bob computes:

mt = cd = 678 23 (mod 77)

As c2 = 0, the message m must be even so m = N mt = 54.

Williams [533] considered the cryptosystem for which the public key is xed and equal to 3 (e = 3). He showed its construction and proved that it is as diÆcult to break as it is to factor the modulus N. Another modi cation of the basic RSA system for e 3 (mod 18) has been presented by Loxton, Khoo, Bird and Seberry [307] who recommend that it should be used for those e whose binary representation has many zeros. Their cryptosystem is de ned in the ring Z[!], where ! is a primitive cube root. They also showed that their system is as diÆcult to break as factoring N.

4.2.2 Primality Testing

To set up RSA, the receiver has to generate two long primes p and q. In Section 2.1.2 the prime-counting function (x) was introduced. It approximates the number of primes in the interval (0; x]. If we want to choose prime at random from the interval (0; 10100], then the probability that the selected integer is prime, is

This means that on average, every 230th integer is prime. Hence, there is a good chance that after 230 consecutive tries, there is at least one prime. In order to exploit this, we need an eÆcient primality test.