2
$\begingroup$

Looking specifically at RSA and EC algorithms which imply doing operations on integers >= 256 bits (>> 64 bits), I have noticed (from my limited experience) that 99% of the software for crunching big numbers is designed for CPU. For example, there appears to be no actively maintained CUDA package for big-number operations (arbitrary length or even 256-512 bit numbers for EC calculations).

Is there a reason for big number calculations (and thus RSA and EC calculations) to remain on CPU? Is it sub-optimal to run such computations on GPU (I understand that GPUs are not optimized for big number calculations because there is no such requirement in graphics, but can't it be efficiently done anyway)? Will this change in the future or will RSA & EC remain on CPU?

$\endgroup$
5
  • $\begingroup$ Does every platform have CUDA? How reliable the CUDA platform? And, actually, RSA factoring and ECC discrete log use CUDA in their implementation. $\endgroup$
    – kelalaka
    Mar 15, 2021 at 16:15
  • $\begingroup$ Well CUDA was an example, as stated. There's the AMD version and I imagine others as well. Yet CUDA is unless mistaken the largest platform and I'm unaware of an existing maintained package (same true, to my knowledge, for the AMD version). Not sure what you mean by "in their implementation" and if that means those operations are performed on GPU? $\endgroup$
    – Jean Monet
    Mar 15, 2021 at 16:20
  • 2
    $\begingroup$ On 16 June 2020, Aleksander Zieniewicz (zielar) and Jean Luc Pons (JeanLucPons) announced the solution of a 114-bit interval elliptic curve discrete logarithm problem on the secp256k1 curve by solving a 114-bit private key in Bitcoin Puzzle Transactions Challenge. To set a new record, they used their own software [39] based on the Pollard Kangaroo on 256x NVIDIA Tesla V100 GPU processor and it took them 13 days $\endgroup$
    – kelalaka
    Mar 15, 2021 at 16:51
  • $\begingroup$ @kelalaka thanks for this, it's a great resource to study. $\endgroup$
    – Jean Monet
    Mar 15, 2021 at 17:08
  • $\begingroup$ I don't feel confident to write up an answer, but I saw the paper "Parallel modular exponentiation using load balancing without precomputation" (Lara, Borges, Portugal & Nedjah). It uses CPU cores instead of GPU, but from their RSA-1024 benchmarks (p. 581), the speedup tops out at about 1.9x already at 5-8 cores. GPUs provide lots of parallelism which I would guess wouldn't be an additional advantage, and latency which would be a disadvantage. $\endgroup$ Mar 15, 2021 at 21:56

1 Answer 1

3
$\begingroup$

If you run RSA speed tests in OpenSSL you'll see that many operations are pretty fast, with the possible exception of RSA key pair generation. However, for that reason key pair generation is generally not used very often - RSA is generally not used to provide forward security in transport protocols, for instance.

CPU's have been upgraded as well, and they can perform up to 512 bit operations on large numbers nowadays - see e.g. Intel's AVX-512. Although those still come with some drawbacks I would expect that those disappear as the technology matures.

Using GPU instructions has the following drawbacks:

  • for top performance you generally need vendor specific code;
  • not all (security minded) servers will have fast GPU support;
  • the CPU instructions used for the asymmetric primitives are generally not the bottleneck - bulk encryption would take much more CPU power.

Furthermore, latency introduced by the PCIe bus makes the GPU most applicable for parallel operations, and the amount of parallelism for e.g. performing private key operations is usually limited.

Of course, I would imagine that e.g. a double ratchet that uses a lot of (EC)DH operations could still benefit from CUDA. But it would be a lot of work to create, to secure and to maintain.

Note: that said, I didn't perform or lookup any benchmarks for GPU's - I do run OpenSSL speed tests now and then - if just to test the new hardware that I buy.

$\endgroup$
1
  • 2
    $\begingroup$ The security is definitely harder. There are a LOT more side-channels when you're dealing with RAM + Cache + CPU + GPU + GPU RAM + PCIe Bus than when you're only dealing with RAM + Cache + CPU. Do GPU drivers even have a way to clear sensitive data after use, or are they in a situation the way C programmers were before OSes added ways to securely zero memory? Etc. $\endgroup$ Mar 16, 2021 at 2:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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