MIT Cryptographers Are No Match For A Determined Belgian

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)

9 thoughts on “MIT Cryptographers Are No Match For A Determined Belgian

  1. Quiz question;
    Who said: Moore’s law will tail off in 5 years or so when we hit the physical limitations of computing. But such a statement might sound ridiculous five years from now. And why didn’t he actually say “moore’s law”?

    Answer:
    It was John von Neumann. He did not name Moore’s law because the quote predates Moore’s law by 18 years. The almost-quote dates from 1947.

      1. That depends on “which” Moore’s Law.
        The first time I heard of Moore’s Law (early 1970’s), it applied to hot rods, it basically stated, “If this much is enough, too much will be just right!”.
        B^)

  2. In the original announcement, LCS promised that, if a correct solution was uncovered, they would open a special “time capsule” designed by architect Frank Gehry and filled with historical artifacts from the likes of Web inventor Tim Berners-Lee, Ethernet co-inventor Bob Metcalfe, and Microsoft founder Bill Gates. (Gates donated the original Altair BASIC that represented Microsoft’s first-ever product, which they developed for MITS in 1975.)

  3. ” 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.”

    Never underestimate the influence of economics on history.

Leave a Reply to Ren Cancel reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.