Space needed to store an RSA private key

Question

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?

Answer 1

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.