Attack and Defense

We discussed already in the preceding section how to meet an attack by a forger of signatures. In general, many cryptanalytic attacks have been proposed against RSA cryptosystems. None of these attacks has turned out to be serious. In this section we discuss some typical ones of them and mention also a few other aspects one should be aware of in order to prevent certain rather obvious attacks.

Consider first the choice of p and q. They should be random primes and not, for instance, primes contained in some table of primes. To factorize, one can always check through the table or run through the sequence of primes of the specific form. The two primes should also not be close to one another. If they are close to one another (and p > q), then (p — q)/2 is small and (p + q)/2 is only slightly larger than sfn. Moreover,

(p + qfj4 - n = (p - q)²/4

and, hence, the left side is a perfect square. To factorize n, one tests integers x > _v/ri, until one finds one such that x² — n is a perfect square, say y². Then p = x + y and

q = x - >-.

For instance, for n = 97343, we have ^Jn = 311.998. Now 312² — n = 1, which gives directly p = 313, q = 311. In general, it is advisable that the bit representa­tions of p and q differ in length by a few bits.

Also cp{n) should be considered in the choice of p and q. Clearly both p — 1 and q — 1 are even, implying that <p(n) is divisible by 4. Assume that (p — 1, q — 1) is large and, consequently, the least common multiple u of p — 1 and — 1 is small in comparison with cp(n). Then any inverse of e modulo u will work as a decryption exponent. Since in this case it is much easier to find d simply by testing, p — 1 and q — 1 should have no large common factor.

The extreme possibility is that one of p — 1 and q — 1, say q — 1, divides the other. Now it suffices to consider inverses of e modulo p — 1. Take again an example. Let n = 11041 and e = 4013. Now any inverse of 4013 modulo 180 can be used as the decryption exponent. This follows because the least common multiple of p — 1 and q — 1 happens to be 180. Thus, we obtain d = 17.

The cryptosystem designer should also avoid the situation where (p(n) has only small prime factors. Assume that all prime factors r of <p(n) are less than some integer k. Since [log_rn] is the exponent in the highest power of r that can possibly divide q>(n), it is computationally feasible to construct all candidates v for cp(n) and test the cryptotext raised to the power (p+ l)/e, provided this exponent is an integer.

A way to overcome both of the difficulties mentioned as regards q>(n) is to consider "safe" primes only. By definition, a prime p is safe iff also (p — l)/2 is prime. Examples of safe primes are 83, 107 and 10¹⁰⁰ — 166517. It is obvious that the generation of safe primes p and q in the system design is much harder than the generation of ordinary primes. It is an open problem whether or not there are infinitely many safe primes.

There are other properties of p, q and <p(n) that might ease factorization and decryption. An RSA cryptosystem designer has to take such properties, also the ones that might be discovered in the future, into account. Indeed, the most obvious among such properties have been taken into account in existing RSA hardware.

The choice of p and q is also important in view of a possible attack based on iterated encryptions. This means that one begins with the cryptotext c₀ and computes numbers

Cj = (cf_ i, mod n), i = 1,2, ... ,

until one finds a meaningful c,. A little reflection will show that the probability for such an attack to succeed is negligible if p — 1 and q — 1 have large prime factors p' and q', and also p' — 1 and q' — 1 have large prime factors. It is also easy to estimate the probability in terms of the sizes of the prime factors mentioned.

Assume that p and q have been chosen, and consider the choice of e and d. Their choice is not independent because one of them determines the other. Especially d should not be so small that it can be found by testing. This is the reason why we fixed d first and then computed e in the cryptosystem design.

However, also a small e can be a security risk as shown, for instance, in [Wie]. If the same message is sent to several parties, cryptanalysis might become possible. Assume that A, B, C have all the public encryption exponent 3, whereas the moduli are n_A, n_B, n_c. (We assume also that no two moduli possess a common nontrivial factor.) Thus, the messages

(w³, modn,), i = A,B,C,

are transmitted. A cryptanalyst who intercepts these messages can compute the number

wj = (w³, mod n_An_Bn_c)

by the Chinese Remainder Theorem. Since w is less than each of the individual moduli, we must have w³ = w,. This means that the cryptanalyst can find w by extracting the cubic root of w_l.

If n_A = 517, n_B = 697, n_c = 667 and the three intercepted messages are 131,614 and 127, then the cryptanalyst computes first the inverses mf¹ (mod n,), i = A, B, C, where m, is the product of the two other moduli. In this case the products are 464899, 344839, 360349, and the inverses are 156, 99, 371. Hence,

w, = 131 • m_A • m_A ¹ + 614-m_B- m_B ¹ 4- \21m_cmc ¹ (mod n_An_Bn_c).

Since n_An_Bn_c = 240352783, the cryptanalyst concludes that

w, = w³ = 91125000 ,

from which the plaintext w = 450 is obtained.

Although it is desirable from the point of view of security that both e and d are large, exactly the opposite is the case if encryption or decryption execution time is considered. Small exponents are particularly advantageous when there is a large difference in computing power between the two communicating parties. A typical example is when RSA is used in communications between a smart card and a large computer. Then it is very desirable for the smart card to have a small d and for the large computer to have a small e. In situations like this a compromise between security and available computing power has to be made.

We mention finally as a curiosity that in every RSA cryptosystem some plaintext blocks are encrypted into themselves. In fact, there are at least four plaintext blocks satisfying both of the conditions E(w) = w and (w, n) = 1. Clearly,

(l^e, modp) = (l^c, modq) = 1 and ((p - l)^e, mod p) = p - 1 , ((q- l)^e, mod q) = q - 1 ,

the latter equations being a consequence of the fact that e is always odd. We obtain by the Chinese Remainder Theorem a simultaneous solution to the congruences

x = a (mod p) and x = b (mod q).

When we let a and b assume independently the values ± 1, we obtain four numbers w satisfying

(w^e, mod n) = w .

In the first illustration in Example 4.1, the four numbers w are 1, 21, 34, 54. They correspond, in this order, to the pairs (a, £»): (1,1), (1, — 1), ( — 1,1) and (— 1, — 1).

If the assumption (w, n) = 1 is dropped and also w = 0 is allowed to be a plaintext, then there are at least nine numbers w with E(w) = w. This is seen exactly as before except that now also 0 is a possible value for a and b. In Example 4.1 we get the following five additional values: 0, 45, 10, 11, 44.

The discussion above shows that certain plaintexts should be avoided. Also certain encryption exponents e should be avoided. If e — 1 is a multiple of both p — 1 and q — 1, then every w satisfies E(w) = w. This is immediately seen by Euler's Theorem. Thus e = <p(n)/2 + 1 is an especially bad choice, although it lies in the customary range for e.

Date: 2015-02-16; view: 690