2

Whether I use openssll or gnutls's certtool, I end in a single threaded part which take several minutes.
When I try to compile the libraries with auto-parallelizer advanced efficient tools. It sill stay single threaded.

I would like to understand more before diving in large part of code for manual rewrite...

user2284570
  • 1,402
  • 1
  • 14
  • 33

2 Answers2

3

This looks weird. An anemic laptop from 2005 generates 4096-bit RSA keys (i.e. huge, overkill keys) in less than 10 seconds. "Several minutes" would indicate that there is something wrong in your system. Or that you are aiming for ridiculously large RSA keys (2048 bits are very fine; 3072 bits are understandable if you have paranoiac managers or must comply with some equally paranoiac regulations; 4096 bits are over-the-top exaggerated; beyond is just plain stupid, and will also incur interoperability issues).

In any case, RSA key pair generation mostly consists in producing two random prime numbers of about half the target modulus size. Generating a prime number boils down to, mostly, trying random odd integers until a prime one is found. This is amenable to high parallelism, although it rarely matters.

One must say that generating RSA keys securely requires some good knowledge of mathematics and cryptography. There are many RSA keys out there, which were produced from poor PRNG and are, therefore, highly breakable -- and it cannot be tested. I therefore strongly urge you to reconsider fiddling with such code.

Finding out why it takes several minutes on your machine is more important.

Thomas Pornin
  • 320,799
  • 57
  • 780
  • 949
  • Maybe the fact that I'm using a BCM6358 with 32Mo of RAM? – user2284570 Dec 30 '13 at 12:30
  • Ah yeah, that may explain. Not the RAM size (RSA key generation uses very little RAM anyway, and fits in L1 cache), but the MIPS32 core in that chip is not meant for number crunching. Isn't it a monocore design ? Why talking about parallelism then ? – Thomas Pornin Dec 30 '13 at 12:37
  • because MIPS is the most well-known example of RISC, and RISC involve things like very high level vectorization or OUT-OF-ORDER execution. Also, the BCM6358 is dual core. – user2284570 Dec 30 '13 at 12:39
  • Having done a fair bit of low-level development, in particular optimization of cryptographic functions, on some MIPS32 (a BCM3306 in my case), I think I can tell that you are quite mistaken on what that means about vectorization and out-of-order execution; in fact, out-of-order execution is a very non-RISC characteristic. With RISC, the _C compiler_ is supposed to do the work of putting the opcodes in the optimal sequence, and it does. Also, there is no "vector instruction" in the MIPS32 instruction set. – Thomas Pornin Dec 30 '13 at 13:04
  • The two cores may be used, though. OpenSSL's code is mono-threaded. At best, you could hope for an average 2x speed improvement on RSA key pair generation. If you really need to generate a lot of key pairs (an unusual requirement), then you might want to investigate elliptic curve cryptography (ECDSA, ECDH...) where private key generation is hundreds to thousands of time faster than RSA. – Thomas Pornin Dec 30 '13 at 13:06
  • Unfortunately, There's some problem with ECC based key generations with openssl (Not a real implementation). And I couldn't find how to it with gnutls (I prefer certtool but I don't really mind using other programs ([except for openssl](http://security.stackexchange.com/a/47601/36301))). – user2284570 Dec 30 '13 at 13:17
  • let us [continue this discussion in chat](http://chat.stackexchange.com/rooms/12211/discussion-between-user2284570-and-thomas-pornin) – user2284570 Dec 30 '13 at 13:41
1

Checking for primality of the two required primes usually takes the longest. Note that the time required to find a prime depends a lot on luck. If the prime is close to the starting point it can be almost instantaneous. If it is much further away it may take quite a bit of time.

There is however one other component that may be completely detrimental towards performance: if the random number generator requires entropy it may block until it has found enough. This is particularly an issue with headless architectures without a spinning disk. Some RSA generators directly use /dev/random as well, which is the main source of said entropy. This is one of the reasons why Intel incorporates a DRBG directly in the processor (using thermal noise as entropy source).

So lack of entropy may completely destroy performance. Note that you should be able to distinguish between a blocking thread and a running thread by looking at the CPU-time that was used.

Note that most embedded processors are embarrassingly slow with regards to RSA key pair generation. A desktop processor will very easily outperform it by a large factor. Even smart cards - which have a dedicated co-processor for this kind of task - are much slower than desktop processors.

Maarten Bodewes
  • 4,562
  • 15
  • 29
  • Steps for parallelization I finally found is using separate pools for p and q along Openᴍᴘ. I definitely don’t have any entropy problems with ᴄʟʀɴɢᴅ. – user2284570 Apr 14 '16 at 19:55
  • Ah that's a pretty cool solution I have to say. I'm going to check if I can do something similar in Java for sure! Java 9 creates a 2048 bit key pair in 1.88 seconds though :) – Maarten Bodewes Apr 14 '16 at 19:58
  • I also guess nothing is faster than Miller/Rabin for checking arbitrary numbers. – user2284570 Apr 14 '16 at 20:03