5
$\begingroup$

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?

$\endgroup$
  • 3
    $\begingroup$ Are you talking about the public key or the private key? $\endgroup$ – Aleph Oct 31 '15 at 22:56
15
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Since a 2048-bit RSA key is commonly said to be "112-bit equivalent", we could even lower the seed length to 112 bits with no loss in security. We may even scrape a few bits because each try in brute force attack would require, on average, a few hundreds of GCD with big integers, and that's not exactly cheap. On the other hand, take note that regenerating the key from the seed will be rather expensive, likely intolerably so in many embedded systems. $\endgroup$ – Thomas Pornin Nov 1 '15 at 21:49
12
$\begingroup$

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).

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ @fgrieu i think what kaspard meant is that the primality tests takes most of the time. Furthermore the chance of hitting a prime should be equal for random numbers as for subsequent numbers. So you could just keep generating randoms with a new random seed instead of iterating and testing. This of course requires more entropy and yet another change in the RSA key generation but it should work (just as you suggestion, but that requires a few more bits of storage). That said, storing two seeds also requires more space. You could probably use a combination of the two approaches. $\endgroup$ – Maarten Bodewes Nov 2 '15 at 10:14
  • $\begingroup$ @MaartenBodewes My approach does indeed require storing two seeds. But after choosing the very first seed to be tried, successive seeds can simply be chosen by increasing the previously tried seed by one. Then it is sufficient to store one seed and a delta between the two seeds. Additionally, the generation of prime candidate from PRNG can be done in ways that have better probability of producing a prime than just choosing a random integer in the given range. For example only trying numbers of the form $12n-1$ could make sense. $\endgroup$ – kasperd Nov 2 '15 at 10:47
  • $\begingroup$ @kasperd: my mistake ! Your method does not increase the number of primality tests in the generation procedure. I removed my erroneous comment. $\endgroup$ – fgrieu Nov 2 '15 at 12:18

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.