The programmer Bernard Fabrot has solved a puzzle, which was devised in 1999 by cryptographer Ron Rivest at MIT. The so-called LCS35 puzzle was about performing a large number of squarings in a row. Rivest had estimated that computers would be fast enough for someone to provide a solution by 2034. Rivest had thus clearly misjudged.
How exactly Fabrot has solved the mystery is still unclear, but from MIT’s message it appears that he was using C code with the GMP library. GMP is a standard library for mathematical operations and free software.
Other teams would have had solution in May
Bad luck had a group called Cryptohage, who had also tried at almost the same time to solve the puzzle, and to use optimized FPGAs for this purpose. The Cryptohage team thought it would be able to solve the mystery with the help of the special hardware until May. The team was just overhauled by Fabrot.
The concept of the puzzle is comparatively simple: you should squared the number 2 many times, a total of about 80 trillion times. After each step, the result should also be reduced by a modulus.
Rivest assumed that there was no meaningful way to parallelize this calculation. Although one could calculate in parallel within the squaring algorithm, each squaring would have to be done individually. This was to prevent anyone with many parallel computers from solving the puzzle. The puzzle is thus an example of a so-called verifiable delay function (VFD).
With prime factors you can solve the puzzle faster
Another special feature: The modulus is a composite number consisting of two prime factors. If you know the prime factors, you can calculate the solution faster using a special algorithm. But at first they only know the creators of the riddle. The backgrounds are explained in a paper published in 1996.
The modulus number is 2,048 bits. Instead of performing the many squared ones, one could also factor that number, but that’s even harder. There is also a connection to the coding algorithm developed by Rivest RSA: If one were able to factorize this number, one could also attack RSA. But Rivest gave the one who solves the puzzle a chance to experience the prime factors. He encoded a short message with the result of the puzzle and shared this as well.
As part of the mystery, in 1999 some items from IT history were packed into a time box. This should be opened either in 2034 or at the time the puzzle is solved, and contains objects contributed by IT greats such as Bill Gates and Tim Berners-Lee. The time box is to be opened on 15 May. Then Fabrot also wants to reveal details about his solution.
