A programmer has just solved a forgotten coding puzzle for up to 20 years

In early April 1999, a “time capsule” was delivered to renowned architect Frank Gehry with instructions to integrate it into his blueprints for a whole house that would later become a place. “Capital” of MIT’s Computer Science and Artificial Intelligence Laboratory (abbreviated as CSAIL). This “time capsule” is basically a museum of the early history of computers, containing 50 memorabilia contributed by people like Bill Gates and Tim Berners-Lee.

“Time capsule” cannot be opened within the next 35 years – unless someone breaks the encoded puzzle inside its design. This puzzle was designed by Ron Rivest, who was named after the “R” in RSA – one of the most important encryption protocols ever created. He said that puzzles are not complicated. Instead, Rivest creates a puzzle and estimates that it takes almost exactly 35 years to calculate the answer.

On April 15 last, nearly 20 years after Rivest announced that sentence, Bernard Fabrot, a Belgian self-study programmer, has solved! The original instruction of the puzzle says that the solution must be sent to the director of the Computer Science Laboratory, but Fabrot said he was surprised to learn that the lab no longer exists (it was imported). MIT AI lab in 2003 to create CSAIL). Fabrot said that CSAIL manager Daniela Rus didn’t even know the existence of the puzzle when he told her about the solution.

Rivest’s puzzle basically revolves around figuring out the number obtained from performing squared calculations nearly 80 trillion times. For example, if you start by calculating the square of 2, you will be 4, then the square of 4 to be 16, and repeat this process 80 trillion again. Then you get the results and run a math equation using that number and a given number in the puzzle guide. This equation will give a new number that can be translated into a congratulatory phrase (Rivest and Fabrot refuse to reveal what this phrase is exactly, and they will announce it when opened. ” time capsule “on May 15 next).

The key to this puzzle is that it requires performing a series of continuous calculations, which means that you cannot find a faster answer by using parallel computing. You need to perform the squared calculation process in a sequential manner, ie the previous calculation must have a new result to continue the next calculation – so use more computers, or assign this decoding task For a supercomputer, it doesn’t solve the problem either. Based on Moore’s law and the amount of time it takes to run squared calculations in 1999, Rivest estimates that the answer to that question must take approximately 35 years.

Ron Rivest

Fabrot, now an independent developer, said he accidentally met this puzzle in 2015. Although Rivest originally released the code of that sentence in the language of Java, Fabrot realized that it could be solved faster. If you use GNU Multiple Precision Arithmetic Library, a free software written in C language specifically for performing precise arithmetic operations. So Fabrot has reserved one of many CPU cores on his desktop to run squared calculations to solve that sentence. He said his computer ran calculations 24/7, except when he was traveling or had a power outage.

“ For many years, I didn’t tell anyone about trying to solve the riddle, except for very dear friends. I know I have a chance, but if I tell people, they can use a more powerful CPU to overcome me, ” said Fabrot.

Three and a half years later, Fabrot finally completed more than 80 trillion squared calculations and obtained a solution for that sentence. Although Fabrot does not know, there is a group of computer scientists and encryption experts who are also working on a project called Cryptophage, which uses specialized hardware designed specifically for sentence decoding. That MIT quiz.

Led by former Intel engineer, Simon Peffers, the Cryptophage team is now studying verifiable deferral functions as a security mechanism for blockchain like Ethereum. The verifiable delay functions are a more modern form of Rivest’s primitive time-delay coding method, and their solutions can only be obtained through sequential calculations. In the course of the study, Peffers said the team met the puzzle of Rivest and commented that this seems to be a good example for testing their research.

In mid-March, the group began running an algorithm designed by Erdinc Ozturk, a researcher at Sabanci University, optimized to reduce the delay between squared calculations. This algorithm is implemented on a “field programmable port array” (FPGA), a multifunctional chip programmed to run a single specific algorithm, making it more efficient than a mass-market CPU. often. Using Ozturk’s algorithm, this FPGA runs 10 times faster than a high-end commercial CPU running unoptimized software.

Thanks to the ability to calculate the efficiency of the chip, the Cryptophage team calculated that they would have the correct solution for the MIT puzzle on the evening of May 10, just two months after the start of the calculation process. But when they contacted MIT to announce that the results were coming, Rivest informed them that Fabrot was one step ahead!

” No one contacted us until those two appeared on the same day to announce that ‘we have solved your problem'” – Rivest said – ” What a coincidence amazing”.

Rivest quickly admitted that he had overestimated the difficulty of the puzzle he set. Making predictions about improvements in technology is difficult to consider over such a long period of time, and Rivest said he did not expect technological breakthroughs, such as FPGA chips – one entry. At that time, it was not as complicated and widespread as it is today.

Although the Cryptophage group is not the first to solve the puzzle, Peffers said they will still attend the opening ceremony of the “time capsule” on May 15. Only the “capsule” designers know its entire content, even though it contains contributions from Tim Berners-Lee, inventor of the World Wide Web; Bob Metcalfe, the inventor of ethernet; and Bill Gates, who contributed the original version of Altair BASIC, Microsoft’s first product. Fabrot said he was excited to see an original copy of one of the first PC games, Zork, which was stored in a “capsule”.

Reference: Wired