Dust seal 20 years of cryptography problems, solved by unknown programmers for 3 years

In April 1994, as the celebration of the 35th anniversary of the MIT Computer Science Laboratory, then the laboratory director Michael Dertouzos designed an "innovation time capsule."

He included the innovations of a series of computer leaders and prepared them to be taken out 35 years later as a gift for the 70th anniversary of the laboratory.

But the question is, how can we guarantee that it will be taken out just 35 years later? This is hard to beat the top scientists at MIT, who have designed a "password lock" for the time capsule, which is a cryptographic problem .

At the same time, they also very rigorously considered the speed of computer computing in the future, and specifically increased the difficulty, making the cryptography problem at least 35 years to crack .

• WSM Destruction: How is the world's second largest dark market market collapsed?
• What is the valuation and rising logic of Ethereum?
• Four words explain why bullish bitcoin: from now 50 years, that monetary base will be it

The cryptography of the industry is also very clear, the cryptographic problems given by the Massachusetts Institute of Technology is certainly not a joke, so it is not a waste of time. Ever since, this cryptography problem has been dusty for 20 years .

In April of this year, a programmer successfully solved the cryptography problem of MIT. What's more, this programmer did not use it for 20 years. He discovered this cryptographic problem by accident in 2015. In other words, it took him only three years to crack.

How did he do that? What kind of embarrassment does he have? Let us walk into the legend of this programmer.



RSA algorithm inventor designed a dusty 35-year cryptography puzzle

The hero of the story is Bernard Fabrot, a self-taught Belgian programmer. Before telling him how to solve the problem, let's first look at the cause of the story from the beginning.

In early April 1999, the famous architect Frank Gehry received a time capsule, which is a representative item of modern inventions that will be placed in a container, sealed and buried deep underground, in the future. Always open. According to the instructions, this time capsule will be placed in the building of the Massachusetts Institute of Technology "Computer Science and Artificial Intelligence Laboratory" (CSAIL).

This time capsule can be said to be a museum of early computer history, which contains 50 pieces of computer history that were donated by computer leaders such as Microsoft founder Bill Gates and the Turing Award winner, the father of the World Wide Web, Sir Tim Berners-Lee. Collection .

Among them, it is likely to include the Altair BASIC editor developed by Microsoft for MIT in 1975, and the first product ever made by Microsoft (Bill Gates and Paul Allen wrote the BASIC interpreter that was later Microsoft). Basic, also the basis of MS-DOS, has evolved into today's Visual Basic).

As the name suggests, time capsules need to have time to precipitate to become more meaningful. So this time capsule, which is closely related to computer science, adopts the computer science method and designs a cryptography problem. Only when this problem is solved can the time capsule be opened. This cryptographic problem can only be solved by sequential calculations.

Considering the speed of computer computing, it takes at least 35 years to solve this problem.

This ingenious design comes from Ron Rivest, and you may not be familiar with Rivest, but you may find it a bit familiar to the famous asymmetrically encrypted RSA algorithm. That's right, Rivest is the "R" of the three inventors of the RSA algorithm (the RSA algorithm is named after the initials of the three inventors' surnames).

Ronald Linn Rivest, American cryptographer; one of the inventors of the RSA encryption algorithm

At the same time, Rivest also wrote a book, the Introduction to Algorithms, which is called the compulsory course for programmers. The RSA algorithm can be said to be one of the most important cryptographic algorithms in history. The brilliance of today's cryptocurrencies is also inseparable from the support of its underlying RSA encryption algorithm .

Although Rivest says the cryptographic puzzle is not complicated, in fact, it takes at least 35 years to calculate the answer to this puzzle. Even when Fabrot, the protagonist of today's story, sent the answer to the question to MIT, the responsible person has forgotten the existence of the problem.

On April 15 this year, 20 years after Rivest proposed this cryptography puzzle, self-taught Belgian programmer Bernard Fabrot solved the problem.

In accordance with the instructions in the official cryptographic puzzle, Fabrot is ready to send the solution to the director of the Massachusetts Institute of Technology Computer Science Laboratory, but he is surprised to find that the lab no longer exists. As early as 2003, the lab The MIT Artificial Intelligence Laboratory merged to form the current MIT Computer Science and Artificial Intelligence Laboratory.

Even more shocking is the fact that this newly established laboratory has long forgotten the existence of this cryptographic problem. Fabrot said that Daniela Rus, the current director of the Computer Science and Artificial Intelligence Laboratory at the Massachusetts Institute of Technology, had a fog when receiving the solution. Water, because she simply doesn't know what the cryptography puzzle is all about.

 "Simple" MIT cryptography puzzle

So, what exactly is this cryptographic puzzle set by Rivest?

Simply put, the challenge is to find the result of running nearly 80 trillion square operations . For example, if you start from 2, you get 4 after squaring, and then 4 to get a square calculation. You need to repeat 80 trillion times.

The MIT cryptography puzzle is in a very simple form.

Of course, after each square calculation, you need to calculate the modulus value for a large number n, that is, divide the remainder after n , and finally calculate the result and mathematically calculate a number given in the puzzle, you will Get a new number, which is the answer to this cryptography puzzle .

Although the current cryptography puzzle has been cracked, the author Rivest and the creator Fabrot refused to give the exact answer . They are preparing to hold a ceremony to open the time capsule on May 15th, at which time the answer will be announced at the ceremony.

You may think that this doesn't look too difficult. Isn't it possible to use more computers to increase your computing power? In fact it is not that simple. The key to this cryptography puzzle is that it requires sequential operations, which means that you need to perform the square calculation of this step based on the results of the previous step. This means that you can only get the results step by step , but not through the current ones. Parallel computing to get answers faster.

Ron Rivest gave examples of problem solving ideas in the description of the year.

So using more computers or supercomputers will not help. Considering "Moore's Law" (Intel founder Gordon Moore's: microprocessor performance doubled every 18 months), and the time required to perform a square operation in 1999, Rivest estimates only by calculation It takes at least 35 years for the answer to the cryptographic puzzle.

As an independent developer, Fabrot accidentally discovered this cryptography problem in 2015. Rivest originally developed code to solve puzzles using the Java language.

Later, he realized that if you use the GNU Multiple Precision Arithmetic Library, an accurate computing tool written in C, you can speed up the problem.

So Fabrot immediately set about doing it. He split a CPU core on the desktop computer at home to run the square calculation. During this time, except for his vacation or home power outage, Fabrot's computer was running all day .

"In these years, apart from a few close friends, I have not revealed to anyone that I am solving this cryptography problem," Fabrot said. " I believe I can do it, and I know if I tell Others, they may use a more powerful CPU to surpass me ."

After three and a half years, Fabrot finally completed a calculation of about 80 trillion squares, which was the result of a cryptographic problem.

The solver is not only one of Fabrot

Fabrot is very fortunate, although he doesn't know, but at this time a group of computer scientists and cryptographers are also working on a project called Cryptophage (literally: cryptophage), the main target of the project is hardware, the goal is to use specialized hardware. To solve the cryptographic problems raised by MIT , and when Fabrot got results, the Cryptophage team's solution was on the verge.

Led by former Intel engineer Simon Peffers, the Cryptophage team was studying the possibility of using verifiable delay functions as blockchain security mechanisms such as Ethereum.

The verifiable delay function is a further extension of Rivest's early delay encryption work, and their solutions can only be derived from sequential operations. Peffers said that during the course of the research, the Cryptophage team encountered a cryptographic challenge from Rivest, which seemed to be a "exam" tailored to their research.

In mid-March, the Cryptophage team began researching algorithms designed by Erdinc Ozturk, a researcher at Sabanci University in Turkey. This algorithm is specifically optimized to reduce the delay between square operations, and the algorithm can be run on a Field-Programmable Gate Array (FPGA).

A field-programmable gate array, a versatile chip that can be optimized for running specific algorithms, is therefore more efficient than a general-purpose CPU. By using Ozturk's algorithm optimization, this cryptographic challenge is about 10 times faster on field programmable gate arrays than on high-end commercial CPUs without software-level optimization.

Based on the computational power of the field-programmable gate array, the Cryptophage team concluded that they would get the correct answer to the MIT cryptography puzzle on the evening of May 10 (that is, two months after they started calculating) .

However, when they contacted the Massachusetts Institute of Technology to share the joy that the puzzle was about to be overcome, they were greeted with a cold water, and the subject Rivest told them that Fabrot had already gotten ahead .

“No one has been looking for us during these two decades, until the two men told us on the same day: “We have solved your cryptography problem,” said the author Rivest. “This is a Surprising coincidence. ”

At the same time, Rivest quickly admitted that he overestimated the difficulty of cryptography. Rivest said that predicting technological advances over a long period of time was a difficult task. At the time, he did not anticipate the breakthrough in computing power of field-programmable gate arrays, and at that time the chips were not as complex as they are now. Not so extensive.

Although the Cryptophage team is not the first to solve cryptographic problems, Peffers said they will still participate in the May 15 opening ceremony.

Some of the time capsules are known only to its designer, Michael Dertouzos, but it is currently possible to determine which of the Turing Award winners, the father of the World Wide Web, Sir Tim Berners-Lee, the father of Ethernet, Bob Metcalfe, the founder of Microsoft and the first product of Microsoft. Altair BASIC developer Bill Gates and several other computer pioneers donated innovations.

But Fabrot said that his biggest expectation for the time capsule is the original version of the world's first computer game, Zork.

Image source: Wikipedia

Official description of the MIT cryptography puzzle:

Https://people.csail.mit.edu/rivest/lcs35-puzzle-description.txt

 

Source | WIRED

Compilation | Guoxi

Editor | Aholiab

Produced | Blockchain Base Camp (blockchain_camp)

We will continue to update Blocking; if you have any questions or suggestions, please contact us!