Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
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 ?
Doesn't this reduce the search space for the primes
PandQby 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.
