1
$\begingroup$

In a 2048 bit RSA key. Are $P, Q$, exponent $P$, exponent $Q$, and the coefficient guaranteed to be half of the length of the modulus (128 bytes)?

$\endgroup$
  • $\begingroup$ Yes, the length of the primes is half that of the modulus. What do you mean by "the coefficient"? $\endgroup$ – Geoffroy Couteau Jan 30 '18 at 9:49
  • 1
    $\begingroup$ qinv. The crypto library I use refers to it as coefficient. $\endgroup$ – cdn Jan 30 '18 at 10:19
3
$\begingroup$

No, it is not guaranteed that in a 2048-bit RSA key, the prime factors $p$ and $q$ of the modulus are exactly half of the length of the modulus or 128 octets; much less so for $d_p$, $d_q$, and $q_\text{inv}$ .

In particular, PKCS#1v2.2 allows almost total freedom on size of $p$ and $q$ (and even allows more than two prime factors for the public modulus). $p$ and $q$ being of exactly equal size however follows from requirements mandated by some common standards, in particular FIPS 186-4, which requires $p$ and $q$ to be in the interval $(2^{1023.5},2^{1024})$ for a 2048-bit modulus. This can be traced to its ancestor on RSA matters, ANSI X9.31 (1998).

While having $p$ and $q$ of exactly half the modulus is definitely common, there are implementations around which generate $p$ and $q$ of different size, and even standards like ETSI TS 102 176-1 with recommendation that clearly allow that, and have been interpreted as favoring it:

$p$ and $q$ should have roughly the same length, e.g. set a range such as $0,1 < | \log_2p - \log_2q | < 30$;


Even if $p$ and $q$ are exactly 1024-bit, this does not insure that $d_p$, $d_q$, and $q_\text{inv}$ are exactly 1024-bit or 128-octet. They are often slightly smaller: the high order bits of $q_\text{inv}$ behave about as if $q_\text{inv}$ was random in interval $(0,p)$, thus $q_\text{inv}<2^{1016}$ with probability I guess at least $1/256$ (I welcome a proof or refutation of the estimate, or/and a better one).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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