MIT : Crypto puzzle solved 15 years too early

A crypto puzzle created in 1999 by RSA co-inventor Ron Rivest, which was designed to perform a lengthy calculation, has been resolved. Rivest had originally expected that a solution would take much longer.

It was 15 years earlier than expected: the Belgian Bernard Fabrot has solved the crypto puzzle LCS35.

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.

SOURCEMIT
SHARE
Previous article350 Apache Software Foundation projects are on Github
Next articleApple: sales and profits shrank, iPhone sales are weakening
Amit Kumar
Amit Kumar is editor-in-chief and founder of Revyuh Media. He has been ensuring journalistic quality and shaping the future of Revyuh.com - in terms of content, text, personnel and strategy. He also develops herself further, likes to learn new things and, as a trained mediator, considers communication and freedom to be essential in editorial cooperation. After studying and training at the Indian Institute of Journalism & Mass Communication He accompanied an ambitious Internet portal into the Afterlife and was editor of the Scroll Lib Foundation. After that He did public relations for the MNC's in India. Email: amit.kumar (at) revyuh (dot) com ICE : 00 91 (0) 99580 61723