How faster could a dedicated chip do sequential squaring modulo operations to break a time crypto capsule?

Question

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?

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

Answer 2

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.