Return to Answer

If we want to compact an existing RSA private key expressed as $(N,e,d,p,q,d_p,d_q,q_\text{inv})$, we can reduce it to $(e,p,q)$ and easily recompute the rest as:

$\begin{align} N&=p\cdot q\\ d&=e^{-1}\bmod\operatorname{lcm}(p-1,q-1)\;\text{ or }\;d=e^{-1}\bmod((p-1)\cdot(q-1))\\ d_p&=d\bmod(p-1)\;\text{ or equivalently }\;d_p=e^{-1}\bmod(p-1)\\ d_q&=d\bmod(q-1)\;\text{ or equivalently }\;d_q=e^{-1}\bmod(q-1)\\ q_\text{inv}&=q^{-1}\bmod p \end{align}$

It is possible to gain a few more bits; for example the low order bits of $p$, $q$ and $e$ are known to be set and need not be stored; further we know that $p\bmod6$ is either $1$ or $5$, thus it is enough to store $\lfloor p/6\rfloor$ and an extra bit, etc.. All in all, any RSA private key with $k$-bit public modulus $N$ and common (small) $e$ can be stored in about $k$ bits.

If we want a compact representation of private keys that we are free to choose, we can fix $e$ (removing need to store it) and decide to generate keys using some well defined deterministic procedure employing some Cryptographically Secure Pseudo Random Number Generator, and store the seeds of that CSPRNG, rather than the private keys. Whenever we need a private key, we (re)generate it from its seed. That has a performance issue, with workaround, see kasperd's answer.

If we'll generate $k$ keys of a certain size, without salt, we want to use use a (truly random) seed of at least $n+\log_2(k)$ bits, where $n$ is the security level corresponding to the public key size (perhaps $n\approx 112$ for 2048-bit RSA): we need to guard against the adversary enumerating seeds, generating the corresponding public modulus, and testing if it matches one of the public keys, which is expected to succeed after enumerating about $1/k$ of the seeds.

We can also use a passphrase, salt (user identifier), and a password-based key generation function, see this answer.

If we want to compact an existing RSA private key expressed as $(N,e,d,p,q,d_p,d_q,q_\text{inv})$, we can reduce it to $(e,p,q)$ and easily recompute the rest as:

$\begin{align} N&=p\cdot q\\ d&=e^{-1}\bmod\operatorname{lcm}(p-1,q-1)\;\text{ or }\;d=e^{-1}\bmod((p-1)\cdot(q-1))\\ d_p&=d\bmod(p-1)\;\text{ or equivalently }\;d_p=e^{-1}\bmod(p-1)\\ d_q&=d\bmod(q-1)\;\text{ or equivalently }\;d_q=e^{-1}\bmod(q-1)\\ q_\text{inv}&=q^{-1}\bmod p \end{align}$

It is possible to gain a few more bits; for example the low order bits of $p$, $q$ and $e$ are known to be set and need not be stored; further we know that $p\bmod6$ is either $1$ or $5$, thus it is enough to store $\lfloor p/6\rfloor$ and an extra bit, etc.. All in all, any RSA private key with $k$-bit public modulus $N$ and common (small) $e$ can be stored in about $k$ bits.

If we want a compact representation of private keys that we are free to choose, we can fix $e$ (removing need to store it) and decide to generate keys using some well defined deterministic procedure employing some Cryptographically Secure Pseudo Random Number Generator, and store the seeds of that CSPRNG, rather than the private keys. Whenever we need a private key, we (re)generate it from its seed. That has a performance issue, with workaround, see kasperd's answer.

If we'll generate $k$ keys of a certain size, without salt, we want to use use a (truly random) seed of at least $n+\log_2(k)$ bits, where $n$ is the security level corresponding to the public key size (perhaps $n\approx 112$ for 2048-bit RSA): we need to guard against the adversary enumerating seeds, generating the corresponding public modulus, and testing if it matches one of the public keys, which is expected to succeed after enumerating about $1/k$ of the seeds.

We can also use a passphrase, salt (user identifier), and a password-based key generation function, see this answer.

If we want to compact an existing RSA private key expressed as $(N,e,d,p,q,d_p,d_q,q_\text{inv})$, we can reduce it to $(e,p,q)$ and easily recompute the rest as:

$\begin{align} N&=p\cdot q\\ d&=e^{-1}\bmod\operatorname{lcm}(p-1,q-1)\;\text{ or }\;d=e^{-1}\bmod((p-1)\cdot(q-1))\\ d_p&=d\bmod(p-1)\;\text{ or equivalently }\;d_p=e^{-1}\bmod(p-1)\\ d_q&=d\bmod(q-1)\;\text{ or equivalently }\;d_q=e^{-1}\bmod(q-1)\\ q_\text{inv}&=q^{-1}\bmod p \end{align}$

It is possible to gain a few more bits; for example the low order bits of $p$, $q$ and $e$ are known to be set and need not be stored; further we know that $p\bmod6$ is either $1$ or $5$, thus it is enough to store $\lfloor p/6\rfloor$ and an extra bit, etc.. All in all, any RSA private key with $k$-bit public modulus $N$ and common (small) $e$ can be stored in about $k$ bits.

If we want a compact representation of private keys that we are free to choose, we can fix $e$ (removing need to store it) and decide to generate keys using some well defined deterministic procedure employing some Cryptographically Secure Pseudo Random Number Generator, and store the seeds of that CSPRNG, rather than the private keys. Whenever we need a private key, we (re)generate it from its seed. That has a performance issue, with workaround, see kasperd's answer.

If we'll generate $k$ keys of a certain size, without salt, we want to use use a (truly random) seed of at least $n+\log_2(k)$ bits, where $n$ is the security level corresponding to the public key size (perhaps $n\approx 112$ for 2048-bit RSA): we need to guard against the adversary enumerating the possible seeds, generating the corresponding public modulus, and testing if it matches one of the public keys.

We can also use a passphrase, salt (user identifier), and a password-based key generation function, see this answer.

If we want to compact an existing RSA private key expressed as $(N,e,d,p,q,d_p,d_q,q_\text{inv})$, we can reduce it to $(e,p,q)$ and easily recompute the rest as:

$\begin{align} N&=p\cdot q\\ d&=e^{-1}\bmod\operatorname{lcm}(p-1,q-1)\;\text{ or }\;d=e^{-1}\bmod((p-1)\cdot(q-1))\\ d_p&=d\bmod(p-1)\;\text{ or equivalently }\;d_p=e^{-1}\bmod(p-1)\\ d_q&=d\bmod(q-1)\;\text{ or equivalently }\;d_q=e^{-1}\bmod(q-1)\\ q_\text{inv}&=q^{-1}\bmod p \end{align}$

It is possible to gain a few more bits; for example the low order bits of $p$, $q$ and $e$ are known to be set and need not be stored; further we know that $p\bmod6$ is either $1$ or $5$, thus it is enough to store $\lfloor p/6\rfloor$ and an extra bit, etc.. All in all, any RSA private key with $k$-bit public modulus $N$ and common (small) $e$ can be stored in about $k$ bits.

If we want a compact representation of private keys that we are free to choose, we can fix $e$ (removing need to store it) and decide to generate keys using some well defined deterministic procedure employing some Cryptographically Secure Pseudo Random Number Generator, and store the seeds of that CSPRNG, rather than the private keys. Whenever we need a private key, we (re)generate it from its seed. That has a performance issue, with workaround, see kasperd's answer.

If we'll generate $k$ keys of a certain size, without salt, we want to use use a (truly random) seed of at least $n+\log_2(k)$ bits, where $n$ is the security level corresponding to the public key size (perhaps $n\approx 112$ for 2048-bit RSA): we need to guard against the adversary enumerating seeds, generating the corresponding public modulus, and testing if it matches one of the public keys, which is expected to succeed after enumerating about $1/k$ of the seeds.

We can also use a passphrase, salt (user identifier), and a password-based key generation function, see this answer.

If we want to compact an existing RSA private key expressed as $(N,e,d,p,q,d_p,d_q,q_\text{inv})$, we can reduce it to $(e,p,q)$ and easily recompute the rest as:

$\begin{align} N&=p\cdot q\\ d&=e^{-1}\bmod\operatorname{lcm}(p-1,q-1)\;\text{ or }\;d=e^{-1}\bmod((p-1)\cdot(q-1))\\ d_p&=d\bmod(p-1)\;\text{ or equivalently }\;d_p=e^{-1}\bmod(p-1)\\ d_q&=d\bmod(q-1)\;\text{ or equivalently }\;d_q=e^{-1}\bmod(q-1)\\ q_\text{inv}&=q^{-1}\bmod p \end{align}$

It is possible to gain a few more bits; for example the low order bits of $p$, $q$ and $e$ are known to be set and need not be stored; further we know that $p\bmod6$ is either $1$ or $5$, thus it is enough to store $\lfloor p/6\rfloor$ and an extra bit, etc.. All in all, any RSA private key with $k$-bit public modulus $N$ and common (small) $e$ can be stored in about $k$ bits.

If we want a compact representation of private keys that we are free to choose, we can fix $e$ (removing need to store it) and decide to generate keys using some well defined deterministic procedure employing some Cryptographically Secure Pseudo Random Number Generator, and store the seeds of that CSPRNG, rather than the private keys. Whenever we need a private key, we (re)generate it from its seed. That has a performance issue, with workaround, see kasperd's answer.

We can safely use a (truly random) 160-bit seed: enumerating the possible seeds, generating the corresponding key, and testing if it matches one of the public keys, will remain virtually impossible, and more costly than factoring (for common RSA keys sizes, and billions public keys). We can even use a passphrase, salt (user identifier), and a password-based key generation function, see this answer.

If we want to compact an existing RSA private key expressed as $(N,e,d,p,q,d_p,d_q,q_\text{inv})$, we can reduce it to $(e,p,q)$ and easily recompute the rest as:

$\begin{align} N&=p\cdot q\\ d&=e^{-1}\bmod\operatorname{lcm}(p-1,q-1)\;\text{ or }\;d=e^{-1}\bmod((p-1)\cdot(q-1))\\ d_p&=d\bmod(p-1)\;\text{ or equivalently }\;d_p=e^{-1}\bmod(p-1)\\ d_q&=d\bmod(q-1)\;\text{ or equivalently }\;d_q=e^{-1}\bmod(q-1)\\ q_\text{inv}&=q^{-1}\bmod p \end{align}$

It is possible to gain a few more bits; for example the low order bits of $p$, $q$ and $e$ are known to be set and need not be stored; further we know that $p\bmod6$ is either $1$ or $5$, thus it is enough to store $\lfloor p/6\rfloor$ and an extra bit, etc.. All in all, any RSA private key with $k$-bit public modulus $N$ and common (small) $e$ can be stored in about $k$ bits.

If we want a compact representation of private keys that we are free to choose, we can fix $e$ (removing need to store it) and decide to generate keys using some well defined deterministic procedure employing some Cryptographically Secure Pseudo Random Number Generator, and store the seeds of that CSPRNG, rather than the private keys. Whenever we need a private key, we (re)generate it from its seed. That has a performance issue, with workaround, see kasperd's answer.

If we'll generate $k$ keys of a certain size, without salt, we want to use use a (truly random) seed of at least $n+\log_2(k)$ bits, where $n$ is the security level corresponding to the public key size (perhaps $n\approx 112$ for 2048-bit RSA): we need to guard against the adversary enumerating the possible seeds, generating the corresponding public modulus, and testing if it matches one of the public keys. 

We can also use a passphrase, salt (user identifier), and a password-based key generation function, see this answer.