3
$\begingroup$

Is it a security risk - or perhaps, how big of a security risk is it - if an attacker knows the length of the values of P and Q used when deriving a value for the parameter N in the RSA encryption algorithm?

I've been doing some reading on implementations of RSA and I see that some require P and Q to be the same length, while others have a minimum length for P or Q - so with this in mind, it is probably worth asking if there is a minimum length that P or Q must be when using RSA (in practice)?

$\endgroup$
1

2 Answers 2

14
$\begingroup$

It is not a security risk at all for the length of $P$ and $Q$ to be known. In fact, the length of $P$ and $Q$ is usually known, because most standards require $P$ and $Q$ to have the same length and for the public modulus $N = P \cdot Q$ to have double the length (which excludes values of $P$ and $Q$ which are both $n$-bit number whose product is between $2^{2n-2}$ and $2^{2n-1}$).

So if you know that $2^{2n-1} < N < 2^{2n}$ and the key was generated by a typical implementation, then $2^{n-1} < P < 2^n$ and $2^{n-1} < Q < 2^n$. In fact, some implementations even force the two leading bits of the primes to be 1, i.e. $3 \cdot 2^{n-2} < P,Q < 2^n$, which guarantees that $N \ge 2^{2n-1}$ and doesn't reduce the private key space significantly.

An RSA key can only be as strong as the smallest prime, so it doesn't really make sense for the primes to have different sizes. Having a prime larger than the other makes the computation slower without improving security.

You can see the minimum key lengths for RSA (“factoring modulus”) recommended by some authorities on keylength.com. Divide by two to get the size of the two primes.

$\endgroup$
2
  • 1
    $\begingroup$ ...typical implementation, then 2n−1<P<2n and 2n−1<P<2n.... Shouldn't it be 2n-1<Q<2n once? $\endgroup$ Dec 9, 2021 at 10:11
  • 2
    $\begingroup$ Having a prime larger than the other makes the computation slower without improving security Well one of the primes better be smaller than the other, and if they're too close there's a simple attack that undermines the system. Might help to clarify that you're just talking about bit-length, the primes should be well separated. $\endgroup$
    – Steve Cox
    Dec 9, 2021 at 13:23
7
$\begingroup$

Gilles answered your first question, so I'll address your second:

it is probably worth asking if there is a minimum length that P or Q must be when using RSA (in practice)?

Yes; there are factorization algorithms that take time based on the shortest factor, and which work considerably faster than trial factorization. The best one is the Elliptic Curve Method (ECM); using it, someone found a 276 bit factor of a large composite ($7^{337}+1$); hence, it would be considered wise to make sure that the smaller factor is considerably larger than that.

$\endgroup$

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.