3

For the RSA digital signature scheme , Alice has a pair of public and private keys as denoted by

Public key : (e,n)

Private key : (d,n)

Assuming Alice wants to send a message M to Bob , she would produce an encrypted message EM = Me mod n.

e would have to be chosen such that gcd( e,(p-1)(q-1) ) = 1. My lecturer states that to give it additional security , e should also be safe prime where e = 2q + 1 , q is also prime

  1. Is it really necessary to use safe prime for e , is it alright to just use gcd( e,(p-1)(q-1) ) = 1, what would happen if we don't use a safe prime?
  2. Why do safe prime provide additional security?
  3. Can this be applied to RSA encryption scheme?
7

The need for a "safe prime" is a piece of old lore that is now obsolete, but is still taught, because of what can only be described as generalized apathy.

Historically, the "safe primes" are called "safe" because of Pollard's p-1 factorization algorithm.

The core idea of Pollard's algorithm is the following: when we compute things modulo n (n = pq for two big primes p and q), we are actually doing the computation modulo p and modulo q (that's the gist of the Chinese Remainder Theorem). So we will do computations modulo n and hope for things to go sour: we want to do things that yield a value of zero modulo p but not modulo q, because, when working modulo n (as we do), such a situation implies that we got some integer x that is not invertible modulo n; such an x is a multiple of p but not of q; thus, a simple GCD between n and x yields p, and n is factored.

In this case, Pollard says: let's suppose that p-1 is "smooth", meaning that it is a product of only small prime factors. For instance, suppose that the largest prime factor of p-1 is smaller than some bound B (we would then say that p-1 is "B-smooth"). Then, take a random value z modulo n and do this:

  • Replace z with z2k mod n, where k is the largest integer such that 2k < p.
  • Replace z with z3k mod n, where k is the largest integer such that 3k < p.
  • Replace z with z5k mod n, where k is the largest integer such that 5k < p.
  • ... and so on, in due succession, for all primes up to B.

If p-1 is indeed B-smooth, then, at that point, z is necessarily equal to 1 modulo p (because all the exponentiations have collectively raised z to an exponent u that is a multiple of p-1). Thus, z-1 is a multiple of p. But if q is not B-smooth, then z-1 is not a multiple of q. Therefore, a GCD between z-1 and n yields p, and n is factored.

(Note that everything here is about factoring n, which is sufficient to break the RSA key generally, regardless of whether you use it for signing or for encrypting.)

To avoid falling into the situation where p-1 is B-smooth for a B small enough for the algorithm above to be practical, some people have said: let's generate our p such that p = 2⁠r + 1 (for some prime r). Such a p is B-smooth only for B at least as large than r, i.e. almost as large as p; this is way too large for Pollard's p-1 algorithm to work in any non-ridiculous amount of time. We well thus deem such primes "safe". Neat, isn't it ? Not so fast.

"Safe" primes are not safe, or at least not safer than randomly generated primes. The first blow came in 1982, eight years after Pollard's publication, when Williams invented the p+1 factorization algorithm. It is a generalization of Pollard's algorithm, that works whenever p-1 or p+1 is B-smooth for a small enough B. This means that if you want your p to be "safe", then you must ensure that both p-1 and p+1 are the product of a large enough prime; you would need to generate p such that p = 2⁠r + 1 and p = 2⁠r' - 1 for two primes r and r'.

Then the notion of "safe prime" for factorization was killed in 1987 when Lenstra published the ECM factorization method. It can be viewed as a generalization of Pollard's p-1 algorithm. We work modulo n; we define a random elliptic curve of equation Y2 = X3 + aX + b for two random integers a and b modulo n. Then we take a random point G on that curve; and we multiply that point repeatedly, with 2k, 3k, 5k... and so on, up to bound B (each "k" being adjusted so that the multiple is not greater than p).

These point multiplications are really the analogous of the exponentiations in Pollard's algorithm. Our hope is that the curve order modulo p is B-smooth, i.e. that all these point multiplications will send our point to the "point at infinity" when considering it modulo p. There again, when we do elliptic curve computations modulo n, we are actually working over two curves at the same time, one modulo p and one modulo q. If we reach the "point at infinity" on the curve modulo p (but not modulo q), this will show up as non-invertible coordinates X and Y modulo n, and, again, a simple GCD then reveals the factorization.

The crucial point, for the discussion at hand, is that ECM will work if the curve order (for the curve "modulo p") is B-smooth. That curve order is "close" to p, but still fairly randomly distributed in a range of size 4·sqrt(p), which is quite large (if we are talking about 1024-bit primes, then the range has size at least 2512...). Therefore, a RSA modulus will resist ECM factorization only because a random 1024-bit integer in a large range has only negligible probability of being B-smooth for a small enough B.

Remember that the notion of generating a "safe prime" comes from the fear that a randomly generated prime p could turn out to be such that p-1 is B-smooth. Fortunately, the probability of such an occurrence with normal-sized primes (say, 1024 bits for RSA-2048) is abysmally small. But some people say that they want to "take no risk" and they insist on verifying that p-1 is not B-smooth. The ECM method shows that it is flawed thinking: regardless of how you select p, you are still relying on the very small probability of a random integer to be B-smooth.

Summary: there is no reason to single out p-1 as needing a big enough prime factor. For security, you need random integer generation to be "safe enough" (not B-smooth for too small a B); and if a random integer is fine, then it is fine. Insistence on using "safe primes" for RSA is just being stuck in the past; it made sense between 1974 and 1987, but no longer.


Notes:

  • Though "safe primes" are a useless notion for RSA, they still have some use in Diffie-Hellman, since they allow the use of a small integer as generator (typically 2), which has some (slight) performance benefits.

  • Regardless of all of the above, confronting your lecturer is socially and politically a poor move. If he (she) is a nice open-minded guy (or gal), you might want to send him (her) to me, i.e. point him (her) to that answer. But in student-teacher relationships, the best strategy for a student is to watch, learn, and bide his time.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.