2
$\begingroup$

RFC 2313 has this specific callout:

    1.   An RSA private key logically consists of only the
         modulus n and the private exponent d. The presence of the
         values p, q, d mod (p-1), d mod (p-1), and q-1 mod p is
         intended for efficiency, as Quisquater and Couvreur have
         shown [QC82]. A private-key syntax that does not include
         all the extra values can be converted readily to the syntax
         defined here, provided the public key is known, according
         to a result by Miller [Mil76].

Mil76 is G.L. Miller. Riemann's hypothesis and tests for primality. Journal of Computer and Systems Sciences, 13(3):300-307, 1976.

2313 was obsoleted by RFC 2437. 2437 was obsoleted by 3447. 3447 might have been obsoleted by 8017 but does anyone use it?

2437 makes no mention of this caveat, that the other components can be "converted to this format" if the 'n', 'd' and public key (mod and public exp) are known.

Anyone know why? First option is that the Miller reference was wrong, second option is that the RFC editors were misquoting, misreading or misrepresenting Miller's stuff.

I know that conventional (ie, there are StackOverflow questions on this) wisdom is that the modulus and the private exponent are all that is needed to use an RSA private key, assuming the public key components are known.

Is that (when you get really down to it) correct conventional wisdom?

Or is 'n' and 'd' insufficient?

Any reason (other than performance) that the other components (p, q, et al) are necessary for confidence in the key?

tyia.

$\endgroup$

2 Answers 2

4
$\begingroup$

There are probabilistic algorithms to factor $n$ into $p$ and $q$ from $n$, $e$, $d$. It's then easy to rebuild the full private key $(n,e,d,p,q,d_p,d_q,q_\text{inv})$. One such algorithm is there. A similar one is in OpenSSL key import, and other libraries. The time it takes in practice is acceptable (comparable to key generation). Doing that with side-channel resistance would be hard (and unstudied AFAIK), but not an issue in many contexts.

the modulus $n$ and the private exponent $d$ are all that is needed to use an RSA private key

Yes that's sufficient to evaluate the RSA private key transformation $x\mapsto y=x^d\bmod n$. But if you care about making that operation three times faster or so, you want to use the Chinese Remainder Theorem method, which disregards $d$ and use $n$, $p$, $q$, $d_p=e^{-1}\bmod(p-1)$, $d_q=e^{-1}\bmod(q-1)$, $q_\text{inv}=q^{-1}\bmod p$ to compute the same $y\,$; and you want $e$ for reasons detailed later.

Or is $n$ and $d$ insufficient?

Yes, for performance in particular, see above. $n$ and $d$ are not sufficient to reconstruct the full form of the private key (for arbitrary odd unknown large $e$ as allowed by PKCS#1 and FIPS 186-5). The RFC 2313 quote is correct in including "provided the public key is known" because $e$ is in the public key, not included in the $(n,d)$ format of the private key, and necessary together with $d$ to factor $n$ if $p$ and $q$ are unavailable. And it is is correct in making reference to the Miller article that lays the basis for the methods actually used.

That's part of RSA folklore. I have no idea why it was removed, and if it's still in some modern documents.

Update: On the other hand, RSA usually uses a small $e$, and small values can be guessed and checked. If $r^{e\,d}\bmod n=r$ for small prime $r$ (e.g. $r=2$) then most likely a guess of $e$ is right. It's worth trying the usual values of $e$: 65537, 3, 5, 17, 257 which are the Fermat primes $F_i=2^{(2^i)}+1$, 37 which is also common. And we can find small $e$ systematically: compute $g_1=2^d\bmod n$, then $g_2={g_1}^2\bmod n$, then $g_e=g_2\,g_{e-2}\bmod n$ for successive odd $e$, until we find one $g_e=2$. Most likely, that gets us $e$. We can then check $r^{e\,d}\bmod n=r$ for a few odd primes $r$ to be sure. And further: by using methods similar to baby-step/giant-step or collision search, we can find medium $e$ with in the order of $2\sqrt{e_\max}$ modular multiplications.

Any reason (other than performance) that the other components ($p$, $q$, et al) are necessary for confidence in the key?

It is important to have $e$ in the private key for at least two reasons beyond performance:

  • $e$ allows masking to resist side channel attacks: to compute $y=x^d\bmod n$, we can draw a random $r$, compute $s=r^e\bmod n$, then $t=x\,s\bmod n$, then $u=t^d\bmod n$, then $y=(r^{-1}\bmod n)\,u\bmod n$. Because $t$ and $u$ are different and random-like from one execution to the other, some attacks are thwarted.
  • $e$ allows checking the result to resist fault attacks: we check that $y^e\bmod n=x$. Many errors induced in the calculation, or in the storage of $n$ or $d$, are caught by this check.

The other components $p$, $q$, $d_p$, $d_q$, $q_\text{inv}$ are only useful for performance reasons.

Update: occasionally, with HSMs or crypto-accelerators, the hardware for modular exponentiation may have a width limitation that makes it unusable for computation modulo $n$, but usable modulo $p$ and $q$. If this is the case, not having $p$ and $q$ has a huge performance hit, or could even make use of $(n,d)$ impossible for lack of an implementation.

$\endgroup$
6
  • 1
    $\begingroup$ Thank you -- "n and d are not sufficient" is what I was hoping for, without coming out and stating the question in a way that led to confirmation bias/leading the answer. PKCS8 for a private key allows either the n & d or the full component version, and our impl. is being handed a P8 with n & d, and being told by the source that "according to (note in) RFC 2313 we should be able to recreate all the remaining components"... but we aren't given the public key, only the P8, and I'm trying (again... sigh) to restate our case, that the inputs are, in fact, insufficient... merci beaucoup! $\endgroup$
    – rip...
    Dec 6, 2023 at 14:37
  • $\begingroup$ @rip... In this situation, for random 256-bit odd $e$ (as allowed by FIPS 186-5), I know nothing we can do. On the other hand, RSA usually uses a small $e$, and small values can be guessed. We compute $g_1=2^d\bmod n$, then $g_2={g_1}^2\bmod n$, then $g_e=g_2\,g_{e-2}\bmod n$ for successive odd $e$, until we find one $g_e=2$ (or give up, e.g. when $e>65555$). Most likely, that gets us $e$. We can check $r^{ed}\bmod n=r$ for a few odd primes $r$ to be sure. [Update] The answer now includes this, and some more. $\endgroup$
    – fgrieu
    Dec 6, 2023 at 15:06
  • $\begingroup$ I can make assumptions about the e, but I'd rather not. Also, the stated requirement is ingest some rando P8 (n, d), store it, then export it back out at some point in the future. Our systems accept the P8 without error, but on export we exception out, because the key is (for our use/implementation) incomplete, we expect/store/use the crt component kind. the underlying complaint is "we just want to use your HSM as a temporary key store and it doesn't work for that", because we are processing the key on use, and finding out that it doesn't fit our assumptions, and rejecting the operation. $\endgroup$
    – rip...
    Dec 6, 2023 at 15:23
  • 1
    $\begingroup$ The underlying pain I feel is from this idea that "the P8 is safer stored in the HSM" but... Dude -- the P8 already exists outside the HSM! It is by definition no longer secure because it existed someplace in plain, outside an HSM, long enough to generate the P8, so ... why are we even bothering? Shoving it into an HSM temporarily doesn't fix the underlying conceptual issues here. $\endgroup$
    – rip...
    Dec 6, 2023 at 15:28
  • $\begingroup$ It is possible to test that the resulting $e$ value is correct (e.g. using a sign / verify). Code that I have written first used Wiener's attack to find $e$ and then proceeded to find the CRT parameters. This works fine for e.g. $e$ up to 32 bits (which is, for instance, the maximum for unmanaged Microsoft implementations of RSA). Usually it is set to 0x010001 so you might first check values 0x010001 and 3 as they are most commonly used - in that order. Maybe test 17 as well (another Fermat prime). $\endgroup$
    – Maarten Bodewes
    Dec 7, 2023 at 13:57
5
$\begingroup$

2313 was obsoleted by RFC 2437. 2437 was obsoleted by 3447. 3447 might have been obsoleted by 8017 but does anyone use it?

The version history on PKCS#1 v2.2 reads:

Version 2.2 updates the list of allowed hashing algorithms to align them with FIPS 180-4 [SHS], therefore adding SHA-224, SHA-512/224, and SHA-512/256.

Most developers will happily ignore it for the simple fact that these hash functions are relatively useless and should not have been standardized and haven't been included in all libraries. Of course it is possible to argue that applications are still compliant if they adhere to the obsoleted RFC 3447 or even RFC 2437 so in that sense it is being used.

Anyone know why? First option is that the Miller reference was wrong, second option is that the RFC editors were misquoting, misreading or misrepresenting Miller's stuff.

"efficient" is a big word here. It takes quite a few of computations and it is a relatively complex algorithm to implement (I've done so). It is more likely that it has been removed because it is not very practical even though it is mathematically correct.

I know that conventional (ie, there are StackOverflow questions on this) wisdom is that the modulus and the private exponent are all that is needed to use an RSA private key, assuming the public key components are known.

That is correct, a "plain" RSA implementation is - besides the padding and "plumbing" - just modular exponentiation, and that is perfectly fine to calculate given the modulus and exponent, as anybody that implemented this algorithm in any cryptography class can attest to.

Is that (when you get really down to it) correct conventional wisdom?

Absolutely. CRT is mainly there for the ~4 x speedup of private key operations.

Any reason (other than performance) that the other components (p, q, et al) are necessary for confidence in the key?

The only thing that might be interesting is that I've seen plain RSA implementations that were vulnerable against side channels while the CRT implementations were not.

This is also a big reason not to include the knowledge about generating the CRT parameters in the field. It would be tricky to ensure they are not vulnerable against side channels attacks. It doesn't make much sense to calculate the CRT parameters for each private key calculation either - the calculations are simply not that efficient.

So what we have here is a small oddball piece of knowledge that might be interesting if you ever receive an RSA key that doesn't include the parameters. Now if you really want then you can in that case re-generate them. But it is perfectly possible to perform the RSA private key operation anyway.

So given that a system normally manages its own private keys - they aren't relayed at all - then this trick is not needed. If the system needed CRT parameters then it would probably have been designed to keep them - it is mostly standard way of generating key pairs anyway. And if not it is usually possible and probably more secure to simply generate a new key pair and use that instead of mucking about with the existing one.

This is especially true if the private key (i.e. the private exponent) is stored securely in hardware. It may not be directly available to software in the first place.

If you really want to minimize storage then storing $p$ and $q$ is likely more efficient (or storing a 128 bit seed if you don't mind the inefficiency of finding primes and all the other issues associated with deterministically performing these calculations).


To be honest, I've never actually used my implementation and would not be able to find it. But sure, there will probably have been another implementation that has performed the necessary calculations and it might have gotten some engineers out of a tight spot where they really really needed the CRT parameters. The world is large, and this might well have happened.

$\endgroup$
3
  • $\begingroup$ If you store the seed of a pseudo-random number generator (PRNG) to regenerate $p$ and $q$ deterministically, then you can also store some little precalculated extra information like the offsets to be added to the two outputs of your PRNG to make them prime. $\endgroup$
    – garfunkel
    Dec 5, 2023 at 12:53
  • $\begingroup$ @garfunkel Great idea. I do wonder which RSA key pair generators would allow you access to the values. In that sense it is mainly useful if you have full control over the way the primes are found in the code (edited). $\endgroup$
    – Maarten Bodewes
    Dec 5, 2023 at 19:00
  • $\begingroup$ @MaartenBodewes: An $n-$bit random number is prime with probability $\frac{1}{n\cdot \log(2)}$, so a 16-bit offset is plenty to get $2048$-bit primes. $\endgroup$
    – garfunkel
    Dec 11, 2023 at 14:07

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.