1
$\begingroup$

Why do we want the factors $p,q$ of $n$ to be of size half the bit length of $n$ in RSA?

I know $p,q$ need to be large so that it is harder to factor $n$ and if one of $p,q$ is small, then it is more likely to find a factorization by brute force. But why half the bits of $n$ (i.e., $p,q$ must be in range $[2^{(n-1)/2} \dots 2^{n/2}]$)? Is it just that for $p,q$ to be the largest possible they both need to be of size half the bit length of $n$?

$\endgroup$
  • $\begingroup$ Where did you read this or who told you that? Can you add a source for your information. $\endgroup$ – mikeazo Nov 27 '17 at 12:27
2
$\begingroup$

They don't need to be restricted to that range. It's just a safe and convenient choice with no downsides.

  • Having a small p or q enables easier factorization using the elliptic curve method. To avoid ECM being faster than GNFS you need the primes to be larger than about 30% of the modulus (depends on the key size).
  • Having a large p or q reduces performance, because the Chinese remainder theorem based speedup becomes less efficient.
  • Having a nice power-of-two size for both factors is convenient for the implementer, especially in hardware
  • If you restrict them to the range $[2^{(n-1)/2} ... 2^{n/2}]$, you get the nice property that you can generate p and q independently and get modulus of exactly the desired size.
  • It only marginally reduces the number of available primes, which has no security impact.

Personally I'd go even one step further and restrict to $[\frac{3}{4} \cdot 2^{n/2} ... 2^{n/2}]$ because it simplifies key generation (just set the two most significant bits to 1)

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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