8
$\begingroup$

Assume there is a hypothetical situation where one would need to generate hundreds of millions of public key pairs of reasonable strength in a limited time.

What would be required in terms of entropy and how long would it take? Could it be acheived on a single computer? How few computers could one get away with?

If the demand for the public keys was not uniform, how many keys could be generated in a burst?

What effect would different algorithms (RSA, DSA, EC) have?

$\endgroup$
4
  • 2
    $\begingroup$ More computers always helps. $\endgroup$
    – SEJPM
    Aug 23 '15 at 17:23
  • $\begingroup$ You'd only want to generate keys and use shared parameters (common practice) with ECDSA and DSA? $\endgroup$
    – SEJPM
    Aug 23 '15 at 17:28
  • $\begingroup$ @SEJPM Definately more computers would help. I guess I should rephrase as "how few could one get away with" $\endgroup$
    – Huckle
    Aug 23 '15 at 17:46
  • $\begingroup$ my computer can generate 25 million ECDH pairs (curve25519) in 8 hours using my own code, which is not nearly as fast as it could be, it can easily generate 1 billion key pairs in 8 hours with optimized code, and can do the same for EdDSA pairs $\endgroup$ Aug 24 '15 at 7:49
11
$\begingroup$

It is feasible to generate 300 million public key pairs of reasonable strength in 8 hours on a single computer, easily with ECDSA using a single core/thread, and even with DSA using quite a common multi-core computer.

RSA would require many standard computers (baring hardware accelerators for modular exponentiation), assuming all the public keys are made public (see Poncho's answer otherwise, applicable for example if you wanted to generate a single PGP RSA key pair of reasonable security and having the same 32-bit key id as one in 6 pre-existing PGP keys, which is likely achieved with 800 million randomly generated keys).


Generating an ECDSA keys pair is as simple a generating a random private key (of e.g. 256 bits for the common P-256 parameters), and doing one point multiplication. These benchmarks show ecdonaldp256 key generation requires about 300 thousands cycles on a single core and thread of a 3.5GHz CPU, giving more than 10 thousands keys per second, over twice the requirement. And then ed25519 is more than 4 times faster.

Entropy is not an issue, we can even use manual dice throws to seed a CSPRNG, and discard the seed. Also, many modern CPUs have built-in hardware RNG with high throughput, and we can use this if we frown at having all the keys depending on the same seed (but then we still have all the keys depending on the integrity of the same computer, and what's connected to it, which is more of a security concern IMHO).

We can use several cores in parallel, and/or several computers (we can use the same seed on each job, just use the job number as an extension of the seed).

DSA key generation is significantly slower for comparable security, mostly because we need 2048-bit modulus, when P-256 works with 256-bit modulus (and only a few times more such operations). The same benchmarks show donald2048 about 4 times slower than ecdonaldp256 for key generation, and reaching the performance goal with a single computer will require some level of parallelization, but we still reach about twice the stated goal with all 4 cores of some of the CPUs benchmarked. And then high-end single-board servers may have 8 CPUs each with 18 cores.

RSA key generation is much slower for comparable security. The same benchmarks show ronald2048 as more than 1000 times slower than ecdonaldp256 for key generation. That's mostly because RSA key generation requires generating random primes, thus trial and error. Effort is dominated by failed primality tests, and attempts to reduce these. If we pre-select for testing integers not divisible by any of the 54 primes less than 256, that is about $1/10$ of integers, we still need to test about $1024\log(2)/10\approx71$ integers to find a 1024-bit prime. That 1024-bit prime generation algorithm will be dominated by about 75 executions of $x\gets a^d\bmod n$ steps in Miller-Rabin tests, each costing a 1024-bit exponentiation to nearly 1024-bit exponent; so key generation will be in the order of 75 times as costly as the exponentiations dominating an RSA signature using CRT.

$\endgroup$
4
  • 1
    $\begingroup$ Well, that machine only had one CPU with only four cores. Theoretically machines can be built with eight CPUs, each having 18 physical cores (=144 cores / MB) and using graphics cards and other stuff will also speed up. $\endgroup$
    – SEJPM
    Aug 23 '15 at 21:03
  • 1
    $\begingroup$ @fgrieu, I can't see how "cycles" could mean anything but cycles on a single core. However, using four cores might not give you 4x the speed if it's e.g. bandwidth limited. $\endgroup$
    – otus
    Aug 24 '15 at 6:44
  • 1
    $\begingroup$ @otus, I think they measured it by running the code and measuring the time and the figure out the number of cycles needed. See for example their AES benchmark, where it should be ~3.5 cycles per byte if single-threaded, but they get 0.83 (~3.5 / 4). $\endgroup$
    – SEJPM
    Aug 24 '15 at 20:29
  • 2
    $\begingroup$ @SEJPM: all the benchmarks quoted are purely single core (and single thread); bench.cr.yp.to/supercop.html states: benchmarks on multiple-core CPUs use just one core. $\endgroup$
    – fgrieu
    Aug 26 '15 at 12:19
8
$\begingroup$

For RSA, the answer whether it is feasible for a single computer depends on the reason your generating them (and specifically, whether they need to remain secure if you publish a number of them).

For example, if you're generating the RSA keys to search for some criteria (e.g. the hash of the public key has a specific pattern), and you'll discard the ones that don't meet this criteria, you can do this. On the other hand, if you happen to decide to give each citizen of the United States (which has approximately 300 million citizens) their own private RSA key, well, you might need a bit more compute power than a single CPU to do this.

To generate 300 million private keys quickly, one method would be to generate 25,000 primes of the right size (and $\ne 1 \bmod e$ for the public exponent you choose); there are $25000 \times 24999 / 2 = 312,487,500$ distinct pairs, and thus over 300 million private keys. A modern CPU can easily find 25,000 primes in the time allotted. It may be difficult to compute the 300 million private exponents within the time budget (as each private key would require a modular inversion); however if you keep or discard them based on what the public key looks like, you wouldn't actually need to compute the private key until you hit one you accept.

The chief objection to this method is that if you publish several of these keys, then it becomes possible that several of the keys happen to share prime factors (and hence would be easy to factor); that's why it's not applicable to "generate a key for each of my 300 million closest friends" scenario. However, it does show that a system that is based on the difficultly of generating huge number of RSA keys may not be as secure as you'd expect from standard RSA key generation times.

In fact, if your willing to tweak the key generation method, you can go even faster. One obvious thing would be to generate "multiprime keys", where each key has 3 or more prime factors. This makes things go even faster, because of having $\binom{n}{2}$ keys from $n$ primes, you get $\binom{n}{3}$ or $\binom{n}{4}$ keys, and that's a lot more bang-for-your-buck.

$\endgroup$
2
  • 1
    $\begingroup$ The "reasonable strength" requirement in the question had dissuaded me of even thinking of sharing primes. Your "generating the RSA keys to search for some criteria" is a nice justification for this unusual way of doing things. Do you have some (semi-)real use case for this, perhaps some attack ? $\endgroup$
    – fgrieu
    Aug 24 '15 at 2:18
  • 2
    $\begingroup$ @fgrieu: One reason this may come up is if you're trying to generate an RSA private/public key where the public key has a specific fingerprint. $\endgroup$
    – poncho
    Aug 24 '15 at 2:50

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.