Is it possible to reduce the size of an RSA key?

Question

The details about what an RSA key is made up of are explained succinctly here.

Is it possible to reduce the amount of data that's usually packaged with the (private) key and then derive it later?

Answer 1

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.

Answer 2

You can use a seed to start a PRNG. Then you can use that PRNG to generate the two (or more) primes required to generate the key pair. Now if you save that seed you can regenerate the key pair, which means you don't have the store the modulus, CRT components or private exponent.

So yes, it is possible to reduce the size, but this approach does have drawbacks:

• the key pair generation technique should remain static - if the input random values are treated any differently then a different key pair may be generated (there are multiple approaches, and no requirements on cryptographic libraries to keep using the same one);
• the library must accept a specific PRNG, and it should not add seed information;
• the PRNG used should remain the same (again, not all PRNG's are well defined);
• RSA key pair generation takes time, especially finding the primes, which means that this approach is very inefficient with regards to private key operations.

Using this approach you can just store the seed, some 128 bits should be sufficient.

All in all, you may be better off choosing Elliptic Curve Cryptography, which uses a pretty small private key value to begin with (you can just use a specific curve, so you would not need to store all the parameters).

Answer 3

The method mentioned in the answer by Maarten will allow you to reduce the private key size for any public key algorithm by regenerating the key from a random seed, each time you need it.

The drawback is the performance. Each time you need to use the key you need to spend as much CPU time for regenerating the key as you used for generating it the first time. However by analyzing how the CPU time is spent during RSA key generation, it is possible to improve performance.

In order to find a suitable prime the RSA key generation tries many different numbers - most of which have to be discarded because they are not primes. And each candidate requires CPU time to decide whether it is prime.

Once the first candidate has been generated using a specific seed and found not to be prime, you can continue generating another candidate using the next random numbers from the PRNG. A better approach however is to simply discard the seed which did not produce a suitable prime immediately. Instead continue trying new seeds until a suitable prime has been found.

This procedure can be repeated until two seeds have been found, which each produce a suitable prime as the very first candidate. Now storing those two seeds will be sufficient to work as secret key.

The advantage is that when using the private key there is no need to run the primality test because the seeds are already known to produce primes as the first candidate. This will not be much slower to use than an ordinary RSA secret key.