4
$\begingroup$

Short version: When generating a prime number of N bits, should I draw random numbers from the range $[0 , 2^n]$, or $[2^{(n-1)} , 2^n]$?

Context: I'm trying to implement a toy-version of RSA as a hobby, with a Miller-Rabin test to generate primes. Initially, my function to generate the keys had the following signature:

$$generateKeys :: (Range, Seed) \rightarrow (PublicKey, PrivateKey)$$

where Range is the range of numbers in which to generate random numbers to search for primes, which initially I had set to $[2^{16}, 2^n]$ to avoid the $[0-2^{16}]$ range, given that RSA implementation guides recommend avoiding using small primes.

But I started wondering if instead I should specify the number of bits of the

$$generateKeys :: (BitsToUse, Seed)\rightarrow (PublicKey, PrivateKey)$$

And this in turn got me wondering exactly what does a "N bit prime" mean, ie, exactly which range from which to pick the prime is generally desired, specially since the range $[2^{(n-1)}, 2^n]$ is "only" half the size of $[0 , 2^n]$, although I guess primes are a bit less dense in that range.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
4
$\begingroup$

In the context of RSA, when we say an "N bit prime", we mean that it's a prime in the range $[2^{n-1}, 2^n)$.

In addition, when we say an RSA key is an "N bit key", we mean that it's in the range $[2^{n-1}, 2^n)$. What this means that if you pick two random $N/2$ bit primes, and multiply them together, you'll get an $N-1$ bit modulus about half the time. To avoid this, one common practice is to select the primes from the range $(\sqrt{2}\cdot 2^{n/2-1}, 2^{n/2})$ - that way, when we multiply the two primes together, we'll always get an N-bit key.

If you're worried that restricting the primes to this range will make guessing them easier, well, that's actually not a concern. If we're generating a 1024 bit key (which by today's standards is cutting it close), there are approximately $10^{151}$ primes in the range $(\sqrt{2}\cdot 2^{511}, 2^{512})$-- it's unlikely anyone will happen to guess either one.

Improve this answer
$\endgroup$
7
  • $\begingroup$ Excellent! Yes, I was a little unsure. 1) The range $[0,2^{n-1})$ contains smaller numbers, for which I guess attacks are easier, so it though it might be good to leave it out, I just lose one bit of keyspace, given that $|[2^{n-1},2^n)|=\frac{1}{2}|[0,2^n)|$ 2) On the other hand, I though then what's actually the difference between $[0, 2^{n-1})$ and $[2^{n-1},2^n)$? since there's clearly a biyection between them. So why should attacks be easier if it is the same range modulo $2^{n-1}$? 3) Given that prime density decreases with n, maybe it did count, but you're right, it's still a lot. $\endgroup$
    – Pepe Mandioca
    Commented Sep 22, 2014 at 21:33
  • $\begingroup$ Also keep in mind that even if you chose out of the full range of integers, the chance that you would get one of those "small" primes is very low. You get a number less than $2^{n-k}$ with probability only $2^{-k}$. So you are overwhelmingly likely to end up with a prime that is "almost" $n$ bits, even if you choose in the range $[0,2^n)$. $\endgroup$
    – Travis Mayberry
    Commented Sep 23, 2014 at 12:28
  • $\begingroup$ @facuq: it's not really "key space" in the sense of, say, AES; the way you attack RSA isn't pick a prime and see if it's a factor of the modulus. Instead, you attempt to factor the modulus using, say, Number Field Sieve, and that 's more difficult with larger modulii. On the other hand, that's not really why we insist on modulii of precisely $n$ bits and not $n-1$; that's more definitional; we have defined $n$ bit modulii to be a certain size; and so one one-bit smaller doesn't meet the definition. $\endgroup$
    – poncho
    Commented Sep 23, 2014 at 12:42
  • $\begingroup$ Personally I'd approximate the $\sqrt{2}$ by 1.5, which results in the simple algorithm of setting the two most significant bits to 1. $\endgroup$
    – CodesInChaos
    Commented Sep 24, 2014 at 11:28
  • $\begingroup$ So effectively an N-bit modulus has exactly N significant binary digits. So how is that, for example, a 2048 bit key can encrypt a 2048 bit message? If the message must be strictly less than the modulus for it to be encrypted/decrypted properly, then wouldn't the modulus need to be at least one bit longer? For example: let's say I have an 8 bit key and I got the modulus 251. An 8 bit key should mean that I can encrypt an 8-bit message, but this is not true, as if I choose anything between 251 and 255 it would be larger than or equal to the modulus and can't be encrypted. What am I missing? $\endgroup$
    – Cedric Mamo
    Commented Sep 7, 2017 at 13:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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