Take the 2-minute tour ×
Information Security Stack Exchange is a question and answer site for Information security professionals. It's 100% free, no registration required.

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

share|improve this question
add comment

1 Answer

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.

share|improve this answer
    
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
show 2 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.