In early April 1999, a time capsule was delivered to the famed architect Frank Gehry with instructions to incorporate it into his designs for the building that would eventually host MIT’s Computer Science and Artificial Intelligence Lab, or CSAIL. The time capsule was essentially a museum of early computer history, containing 50 items contributed by the likes of Bill Gates and Tim Berners-Lee.
The time capsule wasn’t meant to be opened for another 35 years—unless someone could crack the cryptographic puzzle that was included in its design. The puzzle was designed by Ron Rivest, whose name lends the “R” to RSA, arguably one of the most important cryptographic protocols ever created. He says it wasn’t designed to be complicated. Instead, Rivest created the puzzle so that it should take almost exactly 35 years to compute the answer.
On April 15, almost 20 years to the day after Rivest announced the puzzle, Bernard Fabrot, a self-taught Belgian programmer, solved it. The puzzle’s original instructions dictated that the solution be sent to the director of the Laboratory for Computer Science, but Fabrot says he was surprised to learn that the lab no longer exists. (It was merged with MIT’s AI lab in 2003 to create CSAIL.) In fact, Fabrot says CSAIL director Daniela Rus wasn’t even aware of the puzzle’s existence when he told her he had the solution.
Rivest’s puzzle basically involved finding the number that results from running a squaring operation nearly 80 trillion times. For example, if you start with squaring 2 you’d get 4, then square 4 to get 16, and then repeat this process 80 trillion more times. You then take the number you arrive at and run a mathematical operation that uses that number and a number given in the instructions to the puzzle. Doing so spits out a new number that can be translated into a short congratulatory phrase. (Rivest and Fabrot declined to reveal the exact phrase, which will be announced at the opening of the time capsule on May 15.)
The key to this puzzle is that it requires sequential operations, which means you can’t get to the answer faster by using parallel computing. You need to go through the squaring process one step at a time, building on the previous answers, to arrive at the solution, so using more computers or throwing a supercomputer at the problem won’t help. Based on Moore’s law and how long it took to run the squaring operation in 1999, Rivest estimated that computing the answer to the puzzle should take approximately 35 years.
Fabrot, who works as an independent developer, says he stumbled upon the puzzle by accident in 2015. Although Rivest initially released the puzzle’s code in Java, Fabrot realized it could be solved faster if he used the GNU Multiple Precision Arithmetic Library, free software written in C for doing “precise arithmetic.” So Fabrot dedicated one of the CPU cores on his home desktop computer to running squaring operations in an attempt to solve the puzzle. He says his computer was running the operation 24/7, except when he would have to leave on vacation or there was a power outage.
“During all these years I told no one I was trying to solve the puzzle except very close friends,” Fabrot says. “I knew I had a chance, but if I told anyone they could have used a more powerful CPU to overtake me.”
Three-and-a-half years later, Fabrot finally completed approximately 80 trillion squaring operations and had derived the solution to the puzzle. It couldn’t have been better timing. Although Fabrot didn’t know it, a group of computer scientists and cryptography experts were working on a project called Cryptophage, which was using specialized hardware meant specifically to solve the MIT puzzle.