Twenty years ago, a cryptographic puzzle was included in the construction of a building on the MIT campus. The structure that houses what is now MIT’s Computer Science and Artificial Intelligence Laboratory (CSAIL) includes a time capsule designed by the building’s architect, [Frank Gehry]. It contains artifacts related to the history of computing, and was meant to be opened whenever someone solved a cryptographic puzzle, or after 35 years had elapsed.
The puzzle was not expected to be solved early, but [Bernard Fabrot], a developer in Belgium, has managed it using not a supercomputer but a run-of-the-mill Intel i7 processor. The capsule will be opened later in May.
The famous cryptographer, [Ronald Rivest], put together what we now know is a deceptively simple challenge. It involves a successive squaring operation, and since it is inherently sequential there is no possibility of using parallel computing techniques to take any shortcuts. [Fabrot] used the GNU Multiple Precision Arithmetic Library in his code, and took over 3 years of computing time to solve it. Meanwhile another team is using an FPGA and are expecting a solution in months, though have been pipped to the post by the Belgian.
The original specification document is a fascinating read, for both the details of the puzzle itself and for [Rivest]’s predictions as to the then future direction of computing power. He expected the puzzle would take the full 35 years to solve and that there would be 10Ghz processors by 2012 when Moore’s Law would begin to tail off, but he is reported as saying that he underestimated the corresponding advances in software.
Header image: Ray and Maria Stata Center, Tafyrn (CC BY 3.0)