3
$\begingroup$

How much space is actually needed to store a $4096$-bit RSA private key? I originally assumed $0.512$ kB since $\frac{4096}{8} = 512$, but then I started to wonder whether it was in hex.

Simply, what's the size of a $4096$-bit private key, and how does it compare to the public key?

$\endgroup$
  • $\begingroup$ Are you talking about the value $d$, all the RSA parameters, or an actual RSA key file (probably ASN.1 encoded)? $\endgroup$ – Sergio Andrés Figueroa Santos Apr 9 '16 at 12:53
  • $\begingroup$ @ArtjomB., if you store the two primes and the public exponent you are close to 4096. $\endgroup$ – otus Apr 9 '16 at 13:26
  • $\begingroup$ If popular algorithms for generation of p and q and selection of e are used, thanks to static bits, even little less than 4096 bits will suffice. $\endgroup$ – user4982 Apr 9 '16 at 13:45
  • 1
    $\begingroup$ Actually, if you use a fixed algorithm to generate the key (say, a specific algorithm from FIPS 186-3), you could just store the seed and the key size. Yes, this would make the process of recovering p, q, d rather expensive; however it makes the stored private key quite small... $\endgroup$ – poncho Apr 9 '16 at 18:53
4
$\begingroup$

What's the size of a 4096 bit private key?

It depends.

The range goes from 512 bytes (only $d$, no formatting, no encoding) up to 5632 (full parameter set, maximal $e$ size, no formatting, hexadecimal encoding) bytes for two-prime RSA. If you also consider multi-prime RSA, the range is much wider.

So what influences the size of the stored private key then?

  1. How do you encode the stored data?
    1. No encoding, this will give no increase in storage need
    2. Base64 encoding, this encodes 3 bytes of data into 4 bytes of encoded data
    3. Hexadecimal encoding, this will encode 1 byte of data into 2 bytes of encoded data
  2. How do yo format your data?
    1. No formatting, this also means no overhead
    2. ASN.1, this will give some overhead to make the structures parseable and the overhead will increase if you use XER instead of DER, the relevant standard is PKCS#1 (PDF) here as well as PKCS#8 for containers and PKCS#12 (PDF via Archive.org) as additional wrapper.
    3. PEM, this will give you some overhead for internal structure and the header and footer of the data block
  3. How much data are you storing?
    1. The absolute minimum $p$, which will allow you to factor $n$ using simple division and will allow you to later derive $d$ "the usual way". This approach provides optimal storage requriments, assuming you're not willing to run the algorithms from 3. which would reduce the need for stored bits of $p$.
    2. Only the private exponent $d$, which will give you a good storage characteristic, but also requires external supply of the public modulus $n$ and the public exponent $e$ for proper operation
    3. A complete minimalistic approach $(n,p',e)$, this will require you to store $e$, but you can optimize it by hard-coding it as $F_4$. The technique is to store only a minimalistic amount of information of $p$, but enough to recover $p,q$ as per "On Factoring Arbitrary Integers with Known Bits" by Herrman and May (PDF) and "Small Solutions to Polynomial Equations, and Low Exponent RSA Vulnerabilities" by Coppersmith (PDF) . This reduces the storage requirement to 5120 bits, however I do no recommend this as it is highly non-standard and will give you large interoperability problems for a marginal storage saving.
    4. The smallest (trivial) complete set $(p,q,e)$ which will allow you to recover $n$ using standard multiplication and will allow you to recover $d$ the usual way.
    5. A middle-ground minimum $(n,d)$, this will not allow you to factor $n$ without external supply of $e$ (which may be an agreed-upon constant), but is enough to decrypt messages "classically"
    6. Only the bare minimum $(n,e,d)$, this will allow you factor $n$ somewhat quickly if needed and it will allow you to do all operations without external data supply
    7. A middle ground amount of data $(n,e,d,p,q)$, this will take away the "heavy" step of factoring $n$ but still leaves some computations to be done if you want that speed-up from the CRT.
    8. The full set $(n,e,d,p,q,d_p,d_q,q_{\text{inv}})$, this allows you to load the data and outright start with the computations, including the CRT speed-up

How does it compare to the public key?

Look at the above list of influencial factors and adapt the third major point, a public key "only" has the option $(n,e)$ there, meaning it can be larger than the private key or it can be significantly smaller, if you include the associated data in the private key.

$\endgroup$
  • $\begingroup$ This paper gives better storage size. ​ ​ $\endgroup$ – user991 Apr 9 '16 at 13:29
  • $\begingroup$ @RickyDemer, so, am I reading this right that you want to store $n$ and a very small part of $p$ and / or $q$ to use the proposed advanced algorithm to recover $p,q$ and hence $d$? $\endgroup$ – SEJPM Apr 9 '16 at 15:17
  • $\begingroup$ No, I'm just saying one can do that. ​ ​ $\endgroup$ – user991 Apr 9 '16 at 15:18
  • 1
    $\begingroup$ Why are you calling storing $d$ optimal? Since you assume knowledge of the public key, you might as well just store $p$, which halves the space requirements compared to $d$ (and as Ricky points out this could be optimized further, but that adds complexity). If you don't assume knowledge of the public key, I'd store $e,p,q$. $\endgroup$ – CodesInChaos Apr 10 '16 at 9:37
  • 1
    $\begingroup$ I'd call PEM an encoding (of DER), extending base64. My alternatives for format would be PGP (mostly bitcount+unsigned, P Q Pinv (because Q>P) but not dP dQ, usually encrypted) and recent OpenSSH (header including some strings then bytecount+signed, similarly except Qinv, usually encrypted, all in PEM), and under ASN.1 also PKCS#8 containing PKCS#1 sometimes encrypted -- and maybe even PKCS#12 containing PKCS#8 containing PKCS#1 (almost) always encrypted. $\endgroup$ – dave_thompson_085 Apr 12 '16 at 9:03

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.