3

I'm interested in generating RSA keys in rapid succession and am looking for the correct hardware to so. I think what I'm looking for is very similar to a brute force attack on RSA keys, but my purpose is to generate keys that contain a text string when output in ASCII / BASE58 or similar forms.

I believe I need hardware that is able to multiply (determine the square of) a given value very quickly. (I'm still learning RSA key generation, so correct me if I'm mistaken)

I'm looking at a variety of technologies such as OpenCL (for video cards etc), and possibly even FPGAs. I don't know if any ASICs are available for this purpose, but that would be ideal if they existed.

Question

So, what hardware technologies (not products) is the fastest (and available for consumers) to generate RSA keys in rapid succession ?

Improve this question
  • Product recommendations are off-topic here. – Polynomial Dec 13 '12 at 16:40
  • @Polynomial I'm interested in learning what technology is appropriate. e.g. Are stream processors in a GPU more important or is memory (to handle larger numbers), or is GPU speed in MHZ? I'm not looking for a product, just technology name. – TLDR Dec 13 '12 at 17:03
  • 1
    An FPGA is always going to be the fastest hardware at performing any task, as it is simply re-mappable silicon dedicated to the task in question. – lynks Dec 13 '12 at 18:10
  • 1
    @lynks I disagree. An ASIC would be better. FPGAs are used because they are re-mappable and readily available for cheap. I'm not saying FPGA isn't the right answer, but I wouldn't go as far as saying an FPGA is "always going to be the fastest hardware" – Alan Dec 14 '12 at 4:35
4

This question is about economics. Otherwise, there is a simple answer: whatever system you use to generate RSA key pairs, just buy two of them and you will generate twice as many key pairs per second. So your question must be:

For a given budget, which kind of technology (GPU, FPGA) will help generate the most RSA key pairs in a given time frame ?

Then we can begin to give some answers. On the paper, the FPGA will be better. Indeed, the FPGA is reconfigurable, which means that you can make a dedicated circuit and do not have to "pay" for parts you do not need. The FPGA has a fixed overhead because of its reconfigurability: namely, you cannot clock it as high as you would with a fixed, non-reconfigurable circuit (by a factor of roughly 2 or 3). On the other hand, a GPU will come with a lot of things that you do not need for RSA key pair generation, including a lot of RAM management. The really killer point is the lack of wide multiplication in GPU: RSA is about big integers and multiplications, and it really needs multipliers which can multiply, for instance, 64-bit integers, yielding 128-bit results. A basic CPU (that from a PC) can do that. GPU are optimized for floating-point operations and will be limited to, at best, 53 bits of precision for the result.

Some people have nonetheless tried to do RSA on GPU; see for instance this article (it is about RSA private key usage, not generation, but we can consider the results as roughly applicable because RSA key pair generation is mostly primality testing, which is modular exponentiation). A GPU appears to be, very roughly, about 4 times as efficient as a CPU of comparable price.

For FPGA, there are a number of documented implementations (e.g. this one) but comparisons with GPU are hard because they do not work with the same units.

GPU are consumer electronics: they really are off-the-shelf and anybody can buy some. If you want to build a machine which generate RSA key pairs, you will get a working system in much less time by using GPU than by using FPGA; however, using basic CPU (i.e. a few PC) will get you there even much faster. If you really have a hard bandwidth goal and are ready to invest quite a lot in development, then FPGA or dedicated ASIC are the way to go. That's what Hardware Security Module vendors do.

Improve this answer
1

The fastest would be purpose built hardware that implements the algorithms in hardware. It would probably be possible to implement a pretty quick algorithm on GPUs as well, but if speed really matters, then I'd recommend getting something purpose built since there could also be key leaking issues with a GPU.

Improve this answer

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.