Self-taught Belgian bloke cracks crypto conundrum that was supposed to be uncrackable until 2034

A cryptographic puzzle proposed two decades ago that involves roughly 80 trillion squarings has been cracked much earlier than expected – in just three and a half years.

We say cryptographic because it involves a verifiable delay function [PDF], a moderately hard cryptographic function.

The conundrum was set by Ronald Rivest in 1999, the R in RSA and a computer science professor at MIT's Computer Science and Artificial Intelligence Laboratory (MIT CSAIL). Here's how he described the problem:

And t, n, and z are given, and are very large numbers: t is 79685186856218, and the other two have 616 digits each.

In announcing his challenge, Rivest promised to reveal the contents of a time capsule around 2033 – some 70 years after the opening of MIT’s Artificial Intelligence Laboratory, which has been revamped to MIT CSAIL, or when the puzzle has been solved, whichever is sooner.

The contents of the time capsule is mostly a secret. Bill Gates contributed some paraphernalia from Microsoft’s ancient Altair BASIC programming language, Redmond’s first product developed in 1975. Other people that stashed stuff in the capsule, including Sir Tim Berners-Lee and Robert Metcalfe, both pioneers of the internet and computer networking.

On Monday, the puzzle was solved by Bernard Fabrot, a self-taught independent Java developer from Belgium. The time capsule will, thus, be cracked open by Rivest for the world to see on May 15, and the secret message revealed.

Big problems require smart solutions

The puzzle involves computing 2^2t (mod n), where n is a 2048-bit product of two prime numbers. You can try to solve the equation directly, but that would take too long. The mathematical enigma is also designed in a way that prevents the use of parallel computing to brute force the solution, since it’s impossible to compute it quickly without knowing the factorization of n. And it's a given you can't factorize n.

Instead, you can use successive squarings modulo n, starting with the number two. In other words, set W(0) = 2 W(i+1) = (W(i)²) (mod n) for i>0, and compute W(t), where t is the above big number. Here’s an example of the calculation, using much smaller numbers for demonstration purposes: n is 253 (11 * 23) and t is 10. Then we can compute:

2⁽²¹⁾ = 2² = 4 (mod 253)

2⁽²²⁾ = 4² = 16 (mod 253)

2⁽²³⁾ = 16² = 3 (mod 253)

2⁽²⁴⁾ = 3² = 9 (mod 253)

2⁽²⁵⁾ = 9² = 81 (mod 253)

2⁽²⁶⁾ = 81² = 236 (mod 253)

2⁽²⁷⁾ = 236² = 36 (mod 253)

2⁽²⁸⁾ = 36² = 31 (mod 253)

2⁽²⁹⁾ = 31² = 202 (mod 253)

w = 2^(2t) = 2⁽²¹⁰⁾ = 202² = 71 (mod 253)

A middle finger to Moore's Law

So, there you have it, 71 is the magic factorisation for the problem when n is 253 and t is 10. Now repeat this exercise with the actual numbers. Rivest predicted that the problem would be solved by 2034 judging by the amount of hefty compute required and the effect of Moore’s Law.

“The value of t was chosen to take into consideration the growth in computational power due to Moore's Law,” he wrote in setting the challenge.

“Based on the SEMATECH National Technology Roadmap for Semiconductors (1997 edition), we can expect internal chip speeds to increase by a factor of approximately 13 overall up to 2012, when the clock rates reach about 10GHz. After that improvements seem more difficult, but we estimate that another factor of five might be achievable by 2034. Thus, the overall rate of computation should go through approximately six doublings by 2034.”

He believed that a single computer would have to be running for 35 years continuously, where the hardware would have to be upgraded every year to the next fastest chip available. But he underestimated the progression of hardware, as the problem has been solved earlier than expected.

Fabrot wrote the equation in a few lines of C code and called upon the GNU Multiple Precision Arithmetic Library, a free mathematical software library to run the computation over 79 trillion times. He used a bog standard PC with an Intel Core i7-6700 processor, and took about three and a half years to finally complete over 79 trillion calculations.

“The computation in itself is 'easy' for some definition of easy: it is 'just' 79 trillion times the same operations,” Fabrot told El Reg. “So the code for a software based approach is very small. But I think it's not easy to have the patience to run such a computation for 3 and a half years. It requires some discipline to relaunch the computation, to follow the progress, to not just give up.”

A company called Supranational, led by CEO Simon Peffers, meanwhile, is on course to crack the puzzle in just 61 days. Peffers and the gang, who were unaware of Fabrot's efforts, took a different approach, preferring to crank out the numbers using a squaring algorithm optimized for a Xilinx VU9P chip, an FPGA.

“Basically, we optimized circuits for an FPGA toward low latency which allows us to perform each individual squaring operation much faster than a general purpose CPU could do,” Peffers told The Register. “Between the algorithmic improvements and the specialized hardware it is about 10x faster versus a software approach.” ®