1
$\begingroup$

refers to FIPS 186-5 document, I have a question about RSA Key generation A.1.6 method, "Generation of Probable Primes with Conditions Based on Auxiliary", my understanding is that, this method sets restriction on the size of Auxiliary prime only, so it is possible to generate P and Q with different bit size. Compared to A.1.3, it sets restriction on P and Q, force P and Q be same size, and must be half size of n. Do my understanding correct? But I use OpenSSL to run the test with A.1.6 method, P and Q always return with same bit size and are half of n as well.

$\endgroup$

1 Answer 1

3
$\begingroup$

Do my understanding correct?

No; when it generates $P$ (in step 5.3) and $Q$ (in step 6.3), it passes the intended key length (nlen) to the algorithm in appendix B.9. That algorithm will find a (probable) prime in the range $$(\sqrt{2}(2^{nlen/2 - 1}), 2^{nlen/2}-1)$$

This means that both $P$ and $Q$ will be $nlen/2$ bits in length.

$\endgroup$
2
  • $\begingroup$ I am not sure how could this formula show P and Q must be nlen/2 bits size. I see it sets max boundary to 2^(nlen/2)-1, it makes sense, but why it times a sqrt(2)? Also, then my understanding is that, A.1.3 and A.1.6 have only 2 differences, (i) Different algorithm of key generation, (ii) A.1.3 only support nlen to be either 2048 or 3072, but A.1.6 supports more range of nlen. $\endgroup$
    – gx16
    Feb 8 at 4:24
  • 2
    $\begingroup$ @gx16: with both $P$ and $Q$ in $\bigl(\sqrt{2}(2^{\mathsf{nlen}/2-1}),2^{\mathsf{nlen}/2}\bigr)$, it holds $P\,Q$ in $\bigl((\sqrt{2}(2^{\mathsf{nlen}/2-1}))^2,(2^{\mathsf{nlen}/2})^2\bigr)$, that is $\bigl(2^{\mathsf{nlen}-1},2^\mathsf{nlen}\bigr)$, thus $N$ is exactly $\mathsf{nlen}$ bit. Also, for even $\mathsf{nlen}$, $P$ and $Q$ both are in $\bigl(2^{\mathsf{nlen}/2-1},2^{\mathsf{nlen}/2}\bigr)$, thus $\mathsf{nlen}/2$ bit. $\endgroup$
    – fgrieu
    Feb 8 at 7:01

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.