Take the 2-minute tour ×
Information Security Stack Exchange is a question and answer site for Information security professionals. It's 100% free, no registration required.

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.

share|improve this question

1 Answer 1

up vote 9 down vote accepted

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.

share|improve this answer
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 '11 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 '11 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 '11 at 18:32

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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