2

I'm facing a very real problem and, sadly, I cannot find the answer on my own: I'm hitting my limit as a programmer because my hardware knowledge is not sufficiently advanced at all.

It's an issue I'm encountering during the development of the system (I need to find safe parameters value which depends on the answer to the question I'm asking here) (maybe crypto.SE would be better but crypto.SE seems more about theoretical questions about math/cryptography).

For a project I'm working on I need to use a "time capsule cryptosystem". More specifically the following one, invented by Rivest (the 'R' in 'RSA'):

Rivest's time capsule crypto puzzle

It is an inherently sequential operation: parallelization here is of no use. An attacker could use a botnet of million computers: it wouldn't help. One million ASIC chips wouldn't help either. The solution can only be found sequentially, by design.

Now I need to approximate (one or two orders of magnitude off is ok: an approximation 10x faster/slower or even 100x faster/slower ain't really an issue) how much faster could a dedicated chip solve that puzzle compared to a fast CPU (a fast core, really).

Basically solving that puzzle consists in doing a lot of squarings modulo n. Let's consider there's no "attack" on that puzzle: I've chosen bit enough RSA integers etc.

Would a GPU help compared to a CPU here? A FPGA? Would a dedicated chip like some ASIC chip help?

If any of these would help, how can I determine how much faster it could be than a fast CPU?

I'd need some back-of-the-envelope calculation and, as I stated previously, an approximation about 10x or 100x the actual answer ain't that a big problem.

I guess my question boils down to something like (but feel free to rewrite if I'm mistaken): knowing that the problem is inherently sequential and consists in repeated squaring modulo n operation, can you build/program some hardware to only do sequential squaring modulo operations and how much faster would it be than an actual CPU?

  • It mentions in the definition that by design the majority of the work will take place in the last few years due to the (assumed) exponential rise in computing power. An FPGA running at a thousand times the speed of the best CPU available today won't be a fraction of the computing power of 35 years hence's pocket calculator. – Phoshi May 21 '14 at 14:19
  • 2
    you CAN use distribution by having each node pick a random starting value and starting from there, when a node comes to a value that another node started from the paths are appended and the node pick another value, but that isn't really useful – ratchet freak May 21 '14 at 14:27
  • if you can do 1 squaring per milli second then it will take 2500 years for the t in the link – ratchet freak May 21 '14 at 15:34
  • 1
    @ratchetfreak not in this universe. n has 616 decimal digits so is of the order of 10^616, there are about 10^80 atoms in the universe, so if every atom was a result mod n you're still only covering 1/10^536 of the cases. – Pete Kirkham May 22 '14 at 12:21
  • @PeteKirkham that's why the final remark of it not being useful, the search space would be too large to store – ratchet freak May 22 '14 at 12:23
1

I don't have a definitive answer because it would take a bit of analysis. It also depends on the CPU, how many bits etc. But for a ballpark number.

FPGA's have been built that will do a divide operation in 1 clock cycle. A general purpose CPU/ALU can take 20 to 100 clock cycles. DSP processors will likely take less clock cycles. So we can say a FPGA is 100x faster.

That's just the divide operation (which gives you the modulo also).

You would still have to account for memory transfers. Would a dedicated FPGA need to do this? A general purpose CPU would definitely need to do it. This makes the FPGA all the more faster if it could eliminate most of its memory transfers. At this point 1000x improvement seems realistic.

However, I didn't read the algorithm but I'm guessing there's some table updates/lookups, this would probably require memory transfers to/from the FPGA, which slows down the FPGA processing to be more equivalent to the CPU processing. Even if the FPGA has dedicated extra fast memory, this would still cause that 1000x guesstimate to drop somewhat.

Anyways, my estimate would be a 100x-1000x speed improvement with an FPGA in the best of circumstances.

UPDATE

I came across this article http://research.microsoft.com/apps/pubs/default.aspx?id=70636 (a little dated 2008) but probably still applicable. It is called "Where's the Beef? Why FPGAs are so fast" They did various timing comparisons including 128-bit AES encryption. For the AES encryption they were able to get about a 4000 times increase from the simplistic software implementation to a highly optimized FPGA. Although, I think there were also software optimizations that could be made that reduced that 4000 times number.

I don't know if the state-of-the-art FPGA/Custom Hardware has improved dramatically compared to state-of-the-art CPUs of today, so I don't know how applicable this info is any longer. But, I still think the 100x to 1000x is a good estimate as I would assume that the software would be optimized.

  • The algorithm is literally just squaring and reduction modulo some large n. That only requires the values of n, t (peanuts, a few thousand bits each). Perhaps the multiplication and modulo algorithms used require some tables, but if so you could probably hard-code them into the FPGA program. – user7043 May 21 '14 at 15:47
  • @Dunk: thanks a lot, this helps me a lot. The 100x to 1000x ballpark is very interesting and so is your detailed explanation. – Cedric Martin May 22 '14 at 13:10
1

CPU:

The problem really does depend on the speed of the CPU. We already have diverged from the ballpark range presented in the article, as in 2012 we did not have commercially available 10GHz CPUs. In this case, it would be rather difficult because we're dealing with several factors:

  • CPU speed
  • L1 and L2 cache size
  • Bus speed
  • Algorithm optimization
  • Available CPU architecture
  • Memory speed
  • Cache misses

So I'm going to stick with the "35 year algorithm" based off their original prediction.

GPU:

A GPU isn't going to help in this case. These devices are all about paraellelization and aren't going to help with this kind of algorithm.

FPGA/ASIC:

In this scenario, it's entirely possible to design an FPGA/ASIC that would do an entire operation in one tick. Since we don't care about the actual division result, and only care about the result mod N, we could theoretically make this fairly fast. However it's extremely difficult to estimate the exact speed we could achieve. This would be based off many factors:

  • The algorithm we use.
  • The size/speed of the components.
  • The actual hardware components used.
  • The quality of the components used.
  • The build process used.

If we could estimate that our FPGA/ASIC would run at 1 MHz, which would complete the problem in ~2.53 years.

On another hand, if we could somehow develop and FPGA/ASIC that would run at 1 GHz, then we would complete the problem in ~22 hours.

  • High-end FPGAs have clocks >1GHz. 1MHz would be many cycles per algorithm step. – Pete Kirkham May 22 '14 at 12:27
  • The last part was really geared towards ASICs, but FPGAs are similar enough. – Thebluefish May 22 '14 at 14:17

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.