A self-taught programmer just solved MIT’s 20-year-old forgotten crypto puzzle that supposed to take almost 35 years to answer

A 20-year-old forgotten cryptographic puzzle by MIT’s Computer Science and Artificial Intelligence Laboratory (CSAIL) has been solved by Bernard Fabrot, a self-taught programmer from Belgium. The time capsule containing items contributed by the likes of Bill Gates and Tim Berners-Lee  and was locked using a cryptographic puzzle that supposed to take almost 35 years to answer.

Fabrot solved the puzzle 15 years earlier than MIT scientists expected. According to MIT, “Bernard Fabrot spent the last three and a half years computing the solution to a puzzle first announced by MIT researchers in 1999.” Separately, another team led by tech executive Simon Peffers is nearing completion of computing a solution.

The puzzle was designed to foil attempts of a solver to exploit parallel or distributed computing to speed up the computation. The computation required to solve the puzzle is “intrinsically sequential”.

The puzzle essentially involves doing roughly 80 trillion successive squarings of a starting number, and was specifically designed to foil anyone trying to solve it more quickly by using parallel computing. According to the original puzzle description, “The problem is to compute 2^(2^t) (mod n) for specified values of t and n. Here n is the product of two large primes, and t is chosen to set the desired level of difficulty of the puzzle.”

Fabrot and Peffers took very different approaches to the puzzle. Fabrot used a simple Intel Core i7-6700 found in consumer PCs, and computed the solution using the GNU Multiple Precision Arithmetic Library (GMP). Meanwhile, Peffers’ team used a novel squaring algorithm (designed by Erdinç Öztürk from Sabanci University) to run on a programmable hardware accelerator called an FPGA. The team, which is working as part of a collaboration called Cryptophage, is on track to finish the puzzle on May 11 after only two months of computation.

“There have been hardware and software advances beyond what I predicted in 1999,” says MIT professor Ron Rivest, who first announced the puzzle in April 1999 tied to a celebration of 35 years of research at MIT’s Laboratory for Computer Science (now CSAIL). “The puzzle’s fundamental challenge of doing roughly 80 trillion squarings remains unbroken, but the resources required to do a single squaring have been reduced by much more than I predicted.”

Below is a smaller example of the puzzle provided by MIT.

“Suppose n = 11*23 = 253, and t = 10. Then we can compute:
2^(2^1) = 2^2 = 4 (mod 253)
2^(2^2) = 4^2 = 16 (mod 253)
2^(2^3) = 16^2 = 3 (mod 253)
2^(2^4) = 3^2 = 9 (mod 253)
2^(2^5) = 9^2 = 81 (mod 253)
2^(2^6) = 81^2 = 236 (mod 253)
2^(2^7) = 236^2 = 36 (mod 253)
2^(2^8) = 36^2 = 31 (mod 253)
2^(2^9) = 31^2 = 202 (mod 253)
w = 2^(2^t) = 2^(2^10) = 202^2 = 71 (mod 253)
Thus, the “w” value computed for the puzzle is 71 (decimal), which is 47 (hex). If we have a “z” value for the puzzle of 13 (hex), then the “secret message” for the example is (47 xor 13) = 54 (hex). (The secret message should then be interpreted in ascii at 8 bits per character.)”

MIT also provided a Java code for generating the puzzle, and the actual puzzle itself.

You can read more about Bernard Fabrot’s solution at MIT Computer Science & Artificial Intelligence Lab.