20-year-old Cryptographic Puzzle Solved

Published on 12.06.2019 12:06

MIT’s Computer Science and Artificial Intelligence Laboratory (CSAIL) announced that a 20-year-old cryptographic puzzle was just solved by two different teams. The puzzle first announced by MIT faculty member Ron Rivest in 1999, and forecasted to take 35 years to be solved, was solved 15 years in advance.

 

Mühendislik ve Doğa Bilimleri Fakültesi Öğretim Üyesi Erdinç Öztürk

 

Faculty of Engineering and Natural Sciences Member Erdinç Öztürk

The first person to report a solution was Bernard Fabrot, a self-taught programmer from Belgium. Fabrot ran a code he wrote to solve the puzzle for three and a half years. 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, a team led by Simon Peffers from the US-based company Supranational used a novel squaring algorithm (designed by Sabancı University Faculty Member Erdinç Öztürk) to run on a programmable hardware accelerator called an FPGA (Field Programmable Gate Array). The team is on track to finish the puzzle on May 11 after only two months of computation.

Güler Sabancı: We have been looking into the future for 20 years

Sabancı Üniversitesi Kurucu Mütevelli Heyeti Başkanı Güler Sabancı

Sabancı University Founding Chairman of the Board of Trustees Güler Sabancı 

Speaking on the achievement, Sabancı University Founding Chairman of the Board of Trustees Güler Sabancı noted that Erdinç Öztürk was not only a member of faculty, but also one of the first graduates of the university, continuing: 

 “Since our university was established 20 years ago, we have been looking into the future with an eye for making a difference and becoming a global university. We have considered it our responsibility to make a positive contribution to our country through scientific achievements and pioneering technologies that will shape the future. The fact that our faculty member, and one of our first graduates, Erdinç Öztürk and his team have solved MIT's cryptographic puzzle 15 years ahead of their projections is solid proof that we are on the right path. It is a tremendous academic achievement that Sabancı University is behind one of the only two scholars worldwide who have been able to solve this puzzle. As a university and a country, we are proud of this resounding international success that will no doubt light the way for new scientific inventions. On behalf of the Sabancı University Board of Trustees, I heartily congratulate the entire project team for their brilliant endeavor."

What is the LCS35 Time Capsule Crypto-Puzzle?

MIT professor Ron Rivest, one of the designers of the open-key encryption algorithm RSA (Rivest, Shamir, Adleman), designed a time capsule in April 1999 tied to a celebration of 35 years of research at MIT’s Laboratory for Computer Science (now CSAIL). The capsule was sealed during the ceremony and slated to be opened in 2034. At the same time, Rivest designed a cryptographic puzzle that he thought would take 35 years to solve (LCS35 Time Capsule Crypto-Puzzle, https://people.csail.mit.edu/rivest/lcs35-puzzle-description.txt). MIT LCS later became part of MIT's (Massachusetts Institute of Technology) Computer Science and Artificial Intelligence Laboratory (CSAIL).

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.  The FPGA-based hardware designed by Erdinç Öztürk performs a single 2048-bit squaring operation some 20 times faster than software designed using GMP libraries.