10.3 Public Key Encryption Systems

 <  Free Open Study  >  

In 1976, Diffie and Hellman [DIF76] proposed a new kind of system, public key encryption, in which each user would have a key that did not have to be kept secret. Counterintuitively, the public nature of the key would not inhibit the system's secrecy . The public key transformation is essentially a one-way encryption with a secret (private) way to decrypt.

Public key systems have an enormous advantage over conventional key systems: Anyone can send a secret message to a user, while the message remains adequately protected from being read by an interceptor. With a conventional key system, a separate key is needed for each pair of users. As we have seen, n users will require n * ( n “ 1)/2 keys. As the number of users grows, the number of keys increases very rapidly . Determining and distributing these keys is a problem; more serious is maintaining security for the keys already distributed, because we cannot expect users to memorize so many keys.

Characteristics

With a public key or asymmetric encryption system, each user has two keys: a public key and a private key. The user may publish the public key freely . The keys operate as inverses. Let k PRIV be a user's private key, and let k PUB be the corresponding public key. Then,

graphics/10equ05f.gif


That is, a user can decode with a private key what someone else has encrypted with the corresponding public key. Furthermore, with the second public key encryption algorithm,

graphics/10equ05g.gif


so a user can encrypt a message with a private key and the message can be revealed only with the corresponding public key. (We study an application of this second case later in this chapter, when we examine digital signature protocols.)

These two properties imply that public and private keys can be applied in either order. Ideally, the decryption function D can be applied to any argument, so we can decrypt first and then encrypt. With conventional encryption, one seldom thinks of decrypting before encrypting. With public keys, it simply means applying the private transformation first, and then the public one.

We saw in Chapter 2 that, with public keys, only two keys are needed per user: one public and one private. Thus, users B, C, and D can all encrypt messages for A, using A's public key. If B has encrypted a message using A's public key, C cannot decrypt it, even if C knew it was encrypted with A's public key. Applying A's public key twice, for example, would not decrypt the message. (We assume, of course, that A's private key remains secret.) In the remainder of this section, we look closely at three types of public key systems: Merkle “Hellman knapsacks, RSA encryption, and El Gamal applied to digital signatures.

Merkle “Hellman Knapsacks

Merkle and Hellman [MER78b] developed an encryption algorithm based on the knapsack problem described earlier. The knapsack problem presents a set of positive integers and a target sum, with the goal of finding a subset of the integers that sum to the target. The knapsack problem is NP-complete, implying that to solve it probably requires time exponential in the size of the problem ”in this case, the number of integers.

We present Merkle “Hellman in two steps, to aid understanding. First we outline the operation of the Merkle “Hellman knapsack encryption method. Then we revisit the technique in more detail.

Introduction to MerkIe “Hellman Knapsacks

The idea behind the Merkle “Hellman knapsack scheme is to encode a binary message as a solution to a knapsack problem, reducing the ciphertext to the target sum obtained by adding terms corresponding to 1s in the plaintext. That is, we convert blocks of plaintext to a knapsack sum by adding into the sum those terms that match with 1 bits in the plaintext, as shown in Figure 10-14.

Figure 10-14. Knapsack for Encryption.

graphics/10fig14.gif

A knapsack is represented as a vector of integer terms in which the order of the terms is very important. There are actually two knapsacks ”an easy one, to which a fast (linear time) algorithm exists, and a hard one, derived by modifying the elements of the easy knapsack. The modification is such that a solution with the elements of either knapsack is a solution for the other one as well. This modification is a trapdoor, permitting legitimate users to solve the problem simply. Thus, the general problem is NP-complete, but a restricted version of it has a very fast solution.

The algorithm begins with a knapsack set, each of whose elements is larger than the sum of all previous elements. Suppose we have a sequence where each element a k is larger than a 1 + a 2 + + a k 1 . If a sum is between a k and a k +1 , it must contain a k as a term , because no combination of the values a 1 , a 2 , , a k 1 could produce a total as large as a k . Similarly, if a sum is less than a k , clearly it cannot contain a k as a term.

The modification of the algorithm disguises the elements of the easy knapsack set by changing this increasing size property in a way that preserves the underlying solution. The modification is accomplished with multiplication by a constant mod n.

Detailed Explanation of the Merkle “Hellman Technique

This detailed explanation of Merkle “Hellman is intended for people who want a deeper understanding of the algorithm.

General Knapsacks

The knapsack problem examines a sequence a 1 , a 2 , , a n of integers and a target sum, T . The problem is to find a vector of 0s and 1s such that the sum of the integers associated with 1s equals T. That is, given S = [ a 1 , a 2 , , a n ], and T , find a vector V of 0s and 1s such that

graphics/10equ05h.gif


For example, consider the list of integers [17,38,73,4,11,1] and the target number 53. The problem is to find which of the integers to select for the sum, that is, which should correspond with 1s in V. Clearly 73 cannot be a term, so we can ignore it. Trying 17, the problem reduces to finding a sum for (53 “ 17 = 36). With a second target of 36, 38 cannot contribute, and 4 + 11 + 1 are not enough to make 36. We then conclude that 17 is not a term in the solution.

If 38 is in the solution, then the problem reduces to the new target (53 “ 38 = 15). With this target, a quick glance at the remaining values shows that 4 and 11 complete the solution, since 4 + 11 = 15. A solution is thus 38 + 4 + 11.

This solution proceeded in an orderly manner. We considered each integer as possibly contributing to the sum, and we reduced the problem correspondingly. When one solution did not produce the desired sum, we backed up, discarding recent guesses and trying alternatives. This backtracking seriously impaired the speed of solution.

With only six integers, it did not take long to determine the solution. Fortunately, we discarded one of the integers (73) immediately as too large, and in a subproblem we could dismiss another integer (38) immediately. With many integers, it would have been much more difficult to find a solution, especially if they were all of similar magnitude so that we could not dismiss any immediately.

Superincreasing Knapsacks

Suppose we place an additional restriction on the problem: The integers of S must form a superincreasing sequence, that is, one where each integer is greater than the sum of all preceding integers. Then, every integer a k would be of the form

graphics/10equ05i.gif


In the previous example, [1,4,11,17,38,73] is a superincreasing sequence. If we restrict the knapsack problem to superincreasing sequences, we can easily tell whether a term is included in the sum or not. No combination of terms less than a particular term can yield a sum as large as the term. For instance, 17 is greater than 1+4+11 (=16). If a target sum is greater than or equal to 17, then 17 or some larger term must be a term in the solution.

The solution of a superincreasing knapsack (also called a simple knapsack ) is easy to find. Start with T . Compare the largest integer in S to it. If this integer is larger than T , it is not in the sum, so let the corresponding position in V be 0. If the largest integer is less than or equal to T , that integer is in the sum, so let the corresponding position in V be 1 and reduce T by the integer. Repeat for all remaining integers in S . An example solving a simple knapsack for targets 96 and 95 is shown in Figure 10-15.

Figure 10-15. Example of Solving a Simple Knapsack.

graphics/10fig15.gif

The Knapsack Problem as a Public Key Cryptographic Algorithm

The Merkle “Hellman encryption technique is a public key cryptosystem. That is, each user has a public key, which can be distributed to anyone, and a private key, which is kept secret. The public key is the set of integers of a knapsack problem ( not a superincreasing knapsack); the private key is a corresponding superincreasing knapsack. The contribution of Merkle and Hellman was the design of a technique for converting a superincreasing knapsack into a regular one. The trick is to change the numbers in a nonobvious but reversible way.

Modular Arithmetic and Knapsacks

In normal arithmetic, adding to or multiplying a superincreasing sequence preserves its superincreasing nature, so that the result is still a superincreasing sequence. That is, if a > b then k * a > k * b for any positive integer k.

However, in arithmetic mod n , the product of two large numbers may in fact be smaller than the product of two small numbers, since results larger than n are reduced to between 0 and n -1. Thus, the superincreasing property of a sequence may be destroyed by multiplication by a constant mod n.

To see why, consider a system mod 11. The product 3 * 7 mod 11 = 21 mod 11 = 10, while 3 * 8 mod 11 = 24 mod 11 = 2. Thus, even though 7 < 8, we find that 3 * 7 mod 11 > 3 * 8 mod 11. Multiplying a sequence of integers mod some base may destroy the superincreasing nature of the sequence.

Modular arithmetic is sensitive to common factors. If all products of all integers are mapped into the space of the integers mod n , clearly there will be some duplicates; that is, two different products can produce the same result mod n. For example, if w * x mod n = r , then w * x + n mod n = r, w * x + 2 n mod n = r , and so on. Furthermore, if w and n have a factor in common, then not every integer between 0 and n “1 will be a result of w * x mod n for some x.

For instance, look at the integers mod 5. If w = 3 and x = 1, 2, 3, , the multiplication of x * w mod 5 produces all the results from 0 to 4, as shown in Table 10-13. Notice that after x = 5, the modular results repeat.

Table 10-13. 3 * x mod 5.

x

3 * x

3 * x mod 5

1

3

3

2

6

1

3

9

4

4

12

2

5

15

6

18

3

7

21

1

However, if we choose w = 3 and n = 6, not every integer between 0 and 5 is used. This occurs because w and n share the common factor 3. Table 10-14 shows the results of 3 * x mod 6. Thus, there may be some values that cannot be written as the product of two integers mod n for certain values of n. For all values between 0 and n “1 to be produced, n must be relatively prime to w (that is, they share no common factors with each other).

Table 10-14. 3 * x mod 6.

X

3 * x

3 * x mod 6

1

3

3

2

6

3

9

3

4

12

5

15

3

6

18

7

21

3

If w and n are relatively prime, w has a multiplicative inverse mod n . That means that for every integer w , there is another integer w 1 such that w * w 1 = 1 mod n. A multiplicative inverse undoes the effect of multiplication: ( w * q ) * w 1 = q . (Remember that multiplication is commutative and associative in the group mod n , so that w * q * w 1 = ( w * w 1 ) * q = q mod n. )

With these results from modular arithmetic, Merkle and Hellman found a way to break the superincreasing nature of a sequence of integers. We can break the pattern by multiplying all integers by a constant w and taking the result mod n where w and n are relatively prime.

Transforming a Superincreasing Knapsack

To perform an encryption using the Merkle “Hellman algorithm, we need a superincreasing knapsack that we can transform into what is called a hard knapsack. In this section we learn just how to do that.

We begin by picking a superincreasing sequence S of m integers. Such a sequence is easy to find. Select an initial integer (probably a relatively small one). Choose the next integer to be larger than the first. Then select an integer larger than the sum of the first two. Continue this process by choosing new integers larger than the sum of all integers already selected.

For example,

Sequence

Sum so far

Next term

[1,

[1,

1

2

[1,2,

1 + 2 = 3

4

[1, 2, 4,

1 + 2 + 4 = 7

9

[1, 2, 4, 9,

1 + 2 + 4 + 9 = 16

19

is such a sequence.

The superincreasing sequence just selected is called a simple knapsack. Any instance of the knapsack problem formed from that knapsack has a solution that is easy to find.

After selecting a simple knapsack S = [ s 1 , s 2 , , s m ], we choose a multiplier w and a modulus n. The modulus should be a number greater than the sum of all s i . The multiplier should have no common factors with the modulus. One easy way to guarantee this property is to choose a modulus that is a prime number, since no number smaller than it will have any common factors with it.

Finally, we replace every integer s i in the simple knapsack with the term

graphics/10equ05j.gif


Then, H = [ h 1 , h 2 ,..., h m ] is a hard knapsack . We use both the hard and simple knapsacks in the encryption.

For example, start with the superincreasing knapsack S = [1, 2, 4, 9] and transform it by multiplying by w and reducing mod n where w = 15 and n = 17.

graphics/10equ05k.gif


The hard knapsack derived in this example is H = [15, 13, 9, 16].

Example Using Merkle “Hellman Knapsacks

Let us look at how to use Merkle “Hellman encryption on a plaintext message P. The encryption algorithm using Merkle “Hellman knapsacks begins with a binary message. That is, the message is envisioned as a binary sequence P = [ p 1 , p 2 ,..., p k ]. Divide the message into blocks of m bits, P = [ p l , p 2 ,..., p m ], P 1 = [ p m +1 ,..., p 2 m ], and so forth. The value of m is the number of terms in the simple or hard knapsack.

The encipherment of message P is a sequence of targets, where each target is the sum of some of the terms of the hard knapsack H . The terms selected are those corresponding to 1 bits in P i so that P i serves as a selection vector for the elements of H. Each term of the ciphertext is P i * H , the target derived using block P i as the selection vector.

For this example, we use the knapsacks S = [1, 2, 4, 9] and H = [15, 13, 9, 16] obtained in the previous section. With those knapsacks, w = 15, n = 17, and m = 4. The public key (knapsack) is H , while S is kept secret.

The message

graphics/10equ05l.gif


is encoded with the knapsack H = [15, 13, 9,16] as follows .

graphics/10equ05m.gif


The message is encrypted as the integers 13, 40, 24, 29, using the public knapsack H = [15, 13, 9, 16].

Knapsack Decryption Algorithm

The legitimate recipient knows the simple knapsack and the values of w and n that transformed it to a hard public knapsack. The legitimate recipient determines the value w 1 so that w * w 1 = 1 mod n. In our example, 15 1 mod 17 is 8, since 15 * 8 mod 17 = 120 mod 17 = (17 * 7) + 1 mod 17 = 1.

Remember that H is the hard knapsack derived from the simple knapsack S. H is obtained from S by

graphics/10equ05n.gif


(This notation, in which a constant is multiplied by a sequence, should be interpreted as h i = w * s i mod n for all i , 1 i m .)

The ciphertext message produced by the encryption algorithm is

graphics/10equ05o.gif


To decipher, multiply C by w 1 , since

graphics/10equ05p.gif


To recover the plaintext message P , the legitimate recipient would solve the simple knapsack problem with knapsack S and target w 1 * C i for each ciphertext integer C i . Since w 1 * C i = S * P mod n , the solution for target w 1 * C i is plaintext block P i , which is the message originally encrypted.

Example of Decryption

We continue our example, in which the underlying simple knapsack was S = [1, 2, 4, 9], with w = 15 and n = 17. The transmitted messages were 13, 40, 24, and 29.

To decipher, these messages are multiplied by 8 mod 17 since 8 is 15 1 mod 17. Then we can easily solve the simple knapsacks, as shown here:

graphics/10equ05q.gif


The recovered message is thus 0100101110100101 .

Cryptanalysis of the Knapsack Algorithm

In this example, because m is 4, we can readily determine the solution to the knapsack problem for 13, 40, 24, and 29. Longer knapsacks (larger values of m ), which also imply larger values of the modulus n , are not so simple to solve.

Typically, you want to choose the value of n to be 100 to 200 binary digits long. If n is 200 bits long, the s i are usually chosen to be about 2 200 apart. That is, there are about 200 terms in the knapsacks, and each term of the simple knapsack is between 200 and 400 binary digits long. More precisely, s is chosen so that

graphics/10equ05r.gif


and so on, so that there are approximately 2 200 choices for each s i .

You can use a sequence of m random numbers, r 1 , r 2 , r 3 ,..., r m to generate the simple knapsack just described. Each r i must be between 0 and 2 200 . Then each value s i of the simple knapsack is determined as

graphics/10equ05s.gif


for i = 1, 2,..., m .

With such large terms for S (and H ), it is infeasible to try all possible values of s i to infer S given H and C . Even assuming a machine could do one operation every microsecond, it would still take 10 47 years to try every one of the 2 200 choices for each s i . A massively parallel machine with 1000 or even 1,000,000 parallel elements would not reduce this work factor enough to weaken the encryption.

Weaknesses of the Merkle “Hellman Encryption Algorithm

The Merkle “Hellman knapsack method seems secure. With appropriately large values for n and m , the chances of someone's being able to crack the method by brute force attack are slim.

However, an interceptor does not have to solve the basic knapsack problem to break the encryption, since the encryption depends on specially selected instances of the problem. In 1980, Shamir found that if the value of the modulus n is known, it may be possible to determine the simple knapsack. The exact method is beyond the scope of this book, but we can outline the method of attack. For more information, see the articles by Shamir and Zippel [SHA80] and Adleman [ADL83].

First, notice that since all elements of the hard knapsack are known, you can readily determine which elements correspond to which elements of the simple knapsack. Consider h and h 1 , the first two elements of a hard knapsack, corresponding to simple knapsack elements s and s 1 .

Let

graphics/10equ05t.gif


Since h = w * s mod n and h 1 = w * s 1 mod n , it is also true that

graphics/10equ05u.gif


Given the ratio r , determine the sequence

graphics/10equ05v.gif


For some k, k and s l will cancel each other mod n ; that is, k * (1/ s 1 ) = 1 mod n. Then

graphics/10equ05w.gif


It is reasonable to expect that s will be the smallest element of D . Once s is known, determining w , then w 1 and each of the s i are not hard.

A more serious flaw was identified later by Shamir [SHA82]. The actual argument is also beyond the scope of this book, but again it can be sketched fairly briefly . The approach tries to deduce w and n from the h i alone.

The approximate size of n can be deduced from the fact that it will be longer than any of the h i , since they have been reduced mod n ; however, n will not be substantially longer than the longest h i , since it is likely that the results after taking the modulus will be fairly evenly distributed between 1 and n.

Assume you are trying to guess w. You might iteratively try different candidate values w = 1, 2, 3,...for w. The graph of w * h i mod n as a function of w would increase steadily until a value of w * h i was greater than n . At that point, the graph of w * h i would be discontinuous and have a small value. The values of w * h i would then resume their steady increase as w increased until w * h i exceeded n again. The graph would form a progression of jagged peaks, resembling the teeth of a saw. The slope of each "tooth" of the graph is h i . Figure 10-16 displays a graphical representation of this process.

Figure 10-16. Graph of Change of Merkle “Hellman Knapsack Function.

graphics/10fig16.gif

The correct value of w = w occurs at one of the points of discontinuity of the graph of w * h i mod n . This same pattern occurs for all values h i : h 1 , h 2 , and so forth. Since w is a discontinuity point of w * h 1 mod n , it is also a discontinuity of w * h 2 mod n , of w * h 3 mod n , and so forth. To determine w * superimpose the graph of w * h 1 mod n on w * h 2 mod n , superimpose those graphs on w * h 3 mod n , and so on. Then, w will be at one of the places where all of the curves are discontinuous and fall from a high value to a low one. Two such graphs are shown in Figure 10-17. The problem of determining w is thus reduced to finding the point at which all of these discontinuities coincide.

Figure 10-17. Coinciding Discontinuities.

graphics/10fig17.gif

The actual process is a little more difficult. The value of n has been replaced by real number N. Since n and N are unknown, the graphs are scaled by dividing by N and then approximating by successive values of the real number w /N in the function ( w / N ) * h i mod 1.0. Fortunately, this reduces to the solution of a system of simultaneous linear inequalities . That problem can be solved in polynomial time. Therefore, the Merkle “ Hellman knapsack problem can be broken in reasonable time.

Notice that this solution does not apply to the general knapsack problem; it applies only to the special class of knapsack problems derived from superincreasing sequences by multiplication by a constant modulo another constant. Thus, the basic knapsack problem is intact; only this restricted form has been solved. This result underscores the point that a cryptosystem based on a hard problem is not necessarily as hard to break as the underlying problem.

Since it has become known that the Merkle “Hellman knapsack can be broken, other workers have analyzed variations of Merkle “Hellman knapsacks. (See, for example, [BRI83] and [LAG83].) To date, transformed knapsacks do not seem secure enough for an application where a concerted attack can be expected. The Merkle “Hellman algorithm or a variation would suffice for certain low-risk applications. However, because the Merkle “Hellman method is fairly complicated to use, it is not often recommended.

Rivest “Shamir “Adelman (RSA) Encryption

The RSA algorithm is another cryptosystem based on an underlying hard problem This algorithm was introduced in 1978 by Rivest, Shamir, and Adelman [RIV78]. As with the Merkle “Hellman algorithm, RSA has been the subject of extensive cryptanalysis. No serious flaws have yet been found ”not a guarantee of its security but suggesting a high degree of confidence in its use.

In this section, we present the RSA algorithm in two parts . First, we outline RSA, to give you an idea of how it works relative to the other algorithms we have studied. Then, we delve more deeply into a detailed analysis of the steps involved.

Introduction to the RSA Algorithm

On the surface, the RSA algorithm is similar to the Merkle “Hellman method, in that solving the encryption amounts to finding terms that add to a particular sum or multiply to a particular product. The RSA encryption algorithm incorporates results from number theory, combined with the difficulty of determining the prime factors of a target. The RSA algorithm also operates with arithmetic mod n .

Two keys, d and e , are used for decryption and encryption. They are actually interchangeable. (The keys for Merkle “Hellman were not interchangeable.) The plaintext block P is encrypted as P e mod n . Because the exponentiation is performed mod n , factoring P e to uncover the encrypted plaintext is difficult. However, the decrypting key d is carefully chosen so that ( P e ) d mod n = P . Thus, the legitimate receiver who knows d simply computes ( P e ) d mod n = P and recovers P without having to factor P e .

The encryption algorithm is based on the underlying problem of factoring large numbers. The factorization problem is not known or even believed to be NP-complete; the fastest known algorithm is exponential in time.

Detailed Description of the Encryption Algorithm

The RSA algorithm uses two keys, d and e , which work in pairs, for decryption and encryption, respectively. A plaintext message P is encrypted to ciphertext C by

graphics/10equ05x.gif


The plaintext is recovered by

graphics/10equ05y.gif


Because of symmetry in modular arithmetic, encryption and decryption are mutual inverses and commutative. Therefore,

graphics/10equ05z.gif


This relationship means that one can apply the encrypting transformation and then the decrypting one, or the decrypting one followed by the encrypting one.

Key Choice

The encryption key consists of the pair of integers ( e, n ), and the decryption key is ( d, n ). The starting point in finding keys for this algorithm is selection of a value for n. The value of n should be quite large, a product of two primes p and q . Both p and q should be large themselves . Typically, p and q are nearly 100 digits each, so n is approximately 200 decimal digits (about 512 bits) long; depending on the application, 768, 1024, or more bits may be more appropriate. A large value of n effectively inhibits factoring n to infer p and q.

Next, a relatively large integer e is chosen so that e is relatively prime to ( p “ 1) * ( q “ 1). (Recall that "relatively prime" means that e has no factors in common with ( p “ 1) * ( q “ 1).) An easy way to guarantee that e is relatively prime to ( p “ 1) * ( q “ 1) is to choose e as a prime that is larger than both ( p “ 1) and ( q “ 1).

Finally, select d such that

graphics/10equ05za.gif


Mathematical Foundations of the RSA Algorithm

The Euler totient function ( n ) is the number of positive integers less than n that are relatively prime to n . If p is prime, then

graphics/10equ05zb.gif


Furthermore, if n = p * q , where p and q are both prime, then

graphics/10equ05zc.gif


Euler and Fermat proved that

graphics/10equ05zd.gif


for any integer x if n and x are relatively prime.

Suppose we encrypt a plaintext message P by the RSA algorithm so that E ( P ) = P e . We need to be sure we can recover the message. The value e is selected so that we can easily find its inverse d . Because e and d are inverses mod ( n ),

graphics/10equ05ze.gif


or

graphics/10equ05zg.gif


for some integer k.

Because of the Euler/Fermat result, assuming P and p are relatively prime,

graphics/10equ05zh.gif


and, since ( p “1) is a factor of ( n ),

graphics/10equ05zi.gif


Multiplying by P produces

graphics/10equ05zj.gif


The same argument holds for q , so

graphics/10equ05zk.gif


Combining these last two results with (*) produces

graphics/10equ05zl.gif


so that

graphics/10equ05zm.gif


and e and d are inverse operations.

Example

Let p = 11 and q = 13, so that n = p * q = 143 and ( n ) = ( p “ 1) * ( q “ 1) = 10 * 12 = 120. Next, an integer e is needed, and e must be relatively prime to ( p “ 1) * ( q “ 1). Choose e = 11.

The inverse of 11 mod 120 is also 11, since 11 * 11 = 121 = 1 mod 120. Thus, both encryption and decryption keys are the same: e = d = 11. (For the example, e = d is not a problem, but in a real application you would want to choose values where e is not equal to d .)

Let P be a "message" to be encrypted. For this example we use P = 7. The message is encrypted as follows: 7 11 mod 143 = 106, so that E (7) = 106. (Note: This result can be computed fairly easily with the use of a common pocket calculator. 7 11 = 7 9 * 7 2 . Then 7 9 = 40 353 607, but we do not have to work with figures that large. Because of the reducibility rule, a * b mod n = ( a mod n ) * ( b mod n ) mod n . Since we will reduce our final result mod 143, we can reduce any term, such as 7 9 , which is 8 mod 143. Then, 8 * 7 2 mod 143 = 392 mod 143 = 106.)

This answer is correct, since D (106) = 106 11 mod 143 = 7.

Use of the Algorithm

The user of the RSA algorithm chooses primes p and q , from which the value n = p * q is obtained. Next e is chosen to be relatively prime to ( p “ 1) * ( q “ 1); e is usually a prime larger than ( p “ 1) or ( q “ 1). Finally, d is computed as the inverse of e mod ( ( n )).

The user distributes e and n and keeps d secret; p, q , and ( n ) may be discarded (but not revealed) at this point. Notice that even though n is known to be the product of two primes, if they are relatively large (such as 100 digits long), it will not be feasible to determine the primes p and q or the private key d from e . Therefore, this scheme provides adequate security for d .

It is not even practical to verify that p and q themselves are primes, since that would require considering on the order of 10 50 possible factors. A heuristic algorithm from Solovay and Strassen [SOL77] can determine the probability of primality to any desired degree of confidence.

Every prime number passes two tests. If p is prime and r is any number less than p , then

graphics/10equ05zn.gif


(where gcd is the greatest common divisor function) and

graphics/10equ05zo.gif


where J ( r , p ) is the Jacobi function defined as follows.

graphics/10equ05zp.gif


If a number is suspected to be prime but fails either of these tests, it is definitely not a prime. If a number is suspected to be a prime and passes both of these tests, the likelihood that it is prime is at least 1/2.

The problem relative to the RSA algorithm is to find two large primes p and q . With the Solovay and Strassen approach, you first guess a large candidate prime p . You then generate a random number r and compute gcd( p , r ) and J ( r, p ). If either of these tests fails, p was not a prime, and you stop the procedure. If both pass, the likelihood that p was not prime is at most 1/2. The process repeats with a new value for r chosen at random. If this second r passes, the likelihood that a nonprime p could pass both tests is at most 1/4. In general, after the process is repeated k times without either test failing, the likelihood that p is not a prime is at most 1 / 2 k .

Zimmerman [ZIM86] gives a method for computing RSA encryptions efficiently .

Cryptanalysis of the RSA Method

Like the Merkle “Hellman knapsack algorithm, the RSA method has been scrutinized intensely by professionals in computer security and cryptanalysis. Several minor problems have been identified with it, but there have been no flaws as serious as those for the Merkle “Hellman method.

El Gamal and Digital Signature Algorithms

Another public key algorithm was devised in 1984 by El Gamal [ELG84, ELG85]. While this algorithm is not widely used directly, it is of considerable importance in the U.S. Digital Signature Standard (DSS) [NIS92b, NIS94] of the National Institute of Standards and Technology (NIST). This algorithm relies on the difficulty of computing discrete logarithms over finite fields. Because it is based on arithmetic in finite fields, as is RSA, it bears some similarity to RSA.

We investigated digital signatures in Chapter 2. Recall that a digital signature is, like a handwritten signature, a means of associating a mark unique to an individual with a body of text. The mark should be unforgeable, meaning that only the originator should be able to compute the signature value. But the mark should be verifiable , meaning that others should be able to check that the signature comes from the claimed originator. The general way of computing digital signatures is with public key encryption; the signer computes a signature value by using a private key, and others can use the public key to verify that the signature came from the corresponding private key.

El Gamal Algorithm

In the El Gamal algorithm, to generate a key pair, first choose a prime p and two integers, a and x , such that a < p and x < p and calculate y = a x mod p . The prime p should be chosen so that ( p “ 1) has a large prime factor, q . The private key is x and the public key is y , along with parameters p and a .

To sign a message m , choose a random integer k , 0 < k < p “ 1, which has not been used before and which is relatively prime to ( p “ 1), and compute

graphics/10equ05zq.gif


and

graphics/10equ05zr.gif


where k 1 is the multiplicative inverse of k mod ( p “ 1), so that k * k 1 = 1 mod ( p “ 1). The message signature is then r and s . A recipient can use the public key y to compute y r r s mod p and determine that it is equivalent to a m mod p . To defeat this encryption and infer the values of x and k given r, s , and m , the intruder could find a means of computing a discrete logarithm to solve y = a x and r = a k .

Digital Signature Algorithm

The U.S. Digital Signature Algorithm (DSA) (also called the Digital Signature Standard or DSS) [NIS94] is the El Gamal algorithm with a few restrictions. First, the size of p is specifically fixed at 2 511 < p < 2 512 (so that p is roughly 170 decimal digits long). Second, q , the large prime factor of ( p “ 1) is chosen so that 2 159 < q < 2 160 . The algorithm explicitly uses H(m) , a hash value, instead of the full message text m . Finally, the computations of r and s are taken mod q . Largely, one can argue that these changes make the algorithm easy to use for those who do not want or need to understand the underlying mathematics. However, they also weaken the potential strength of the encryption by reducing the uncertainty for the attacker.

 <  Free Open Study  >  


Security in Computing
Security in Computing, 4th Edition
ISBN: 0132390779
EAN: 2147483647
Year: 2002
Pages: 129

flylib.com © 2008-2017.
If you may any questions please contact us: flylib@qtcs.net