3
$\begingroup$

I know the public modulus is the product of two primes. For key with length L, the public modulus N should be such 2^(L-1) <= N < 2^L.

However this implies that the most significant bit will be always 1. Doesn't this reduce the search space for the primes P and Q by half?

Shouldn't N be between 2^(L-2) and 2^L ?

|improve this question
$\endgroup$
  • $\begingroup$ Halving the search space only reduces security by a maximum of one bit, even if this reasoning would hold. Loosing one bit of security only makes a difference for desperately small keys. $\endgroup$ – Maarten Bodewes♦ Jul 7 '15 at 22:34
5
$\begingroup$

Doesn't this reduce the search space for the primes P and Q by half?

I can't see how it does. After all the attacker can see $N$, and so can determine what bits are set. Allowing, say, a 2047 bit composite (rather than a 2048 bit) doesn't make his job any harder; he can see whether the composite in front of him is either 2047 or 2048 bits long.

What you might mean is that we generally pick the two prime factors to be both precisely $L/2$ bits long; you could try to say that reduces the attackers search space (because, for example, he doesn't have to search for a factor thats, for example, $L/2 - 10$ bits. However, that line of reasoning doesn't appear to work out; there are far too many primes of length $L/2$ (for any $L$ that we're interested in) for anyone to search through; and the practical factoring algorithms against numbers this size (NFS, ECM) can't take advantage of knowledge of the length of the factors.

|improve this answer
$\endgroup$

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.