8

I have a safe prime generator I'd like to speed up. I can benefit from a significant performance gain if the high order bit in the returned prime can be either 1 or 0. The returned prime would be randomly either 2048- or 2047-bit.

Would this be a problem? Is the possibility of a 2047-bit prime less secure enough to be concerned about?

This is not for RSA; I will not be multiplying the prime with another. It's more along the lines of Diffie-Hellman.

Improve this question

1 Answer 1

Reset to default
9

Strictly speaking, a 2047-bit prime (with regards to discrete logarithm and the Diffie-Hellman problem) is theoretically very slightly weaker than a 2048-bit prime, since resistance to discrete logarithm increases with the prime size. However, both 2047 and 2048 bits are sizes in the range of "cannot break now, cannot break in 15 years either" (unless a new major, qualitative scientific discovery is done, whose existence and consequences cannot be, by nature, predicted). Stating that 2048 bits are stronger than 2047 bits implicitly assumes that 2047 bits can be attacked in some way, which is not the case. In other words, you cannot compare infinites.

A prime generation algorithm which cannot target a given, specific bit length is strange, though.

Improve this answer
3
  • 5
    It's a safe prime generator. Safe primes are primes where (p-1)/2 is also prime. Once I test p for primality, if 2p + 1 is prime then 2p + 1 is a safe prime. If (p-1)/2 is prime, then p is a safe prime. So I can't predict whether the answer will be p or 2p + 1.
    – jnm2
    Jun 14, 2011 at 15:23
  • 2
    @jnm2: ooh, it's neat. Indeed, it should give you a 2x factor compared to the basic method (test for p, then for (p-1)/2, loop).
    – Thomas Pornin
    Jun 14, 2011 at 15:47
  • @jnm2's method does introduce a bias into the set of primes chosen. (For provable security, this might break some security proofs.) However, for practical purposes, this bias probably doesn't matter, so @jnm2's scheme seems clever and useful.
    – D.W.
    Jun 16, 2011 at 18:32

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.