Now that the LCS35 time-lock puzzle has been solved, cryptographer Ron Rivest has published a new challenge of the same kind. This time, he estimates that it’s going to take 15 years to find the solution.
The LCS35 cryptogram is listed at position 48 on my Top 50 unsolved encrypted messages list. All you need to do to solve it, is to find the value of w in the following equation:
w is the key that can be used to decrypt the actual cryptogram.
The old puzzle: LCS35
From a mathematical point of view, it is not especially difficult to solve such an equation. However, Ron Rivest, the creator of LCS35, chose the values of n and t especially large when he designed this puzzle in 1999. He estimated that it would take 35 years to compute the solution – provided that a powerful PC worked on it 24 hours a day and 365 days a year. As the calculations can’t be parallelized, a distributed computing project would be of no help.
As readers of this blog know, Rivest’s estimation proved wrong. Bernard Fabrot from Belgium solved LCS35 within 3,3 years. He published the solution earlier this month. A US project led by Simon Pfeffers needed only two months. It was completed only a few days after Fabrot’s success.
The new puzzle: CSAIL2019
Now that LCS35 is solved, Ron Rivest has published a new puzzle of the same kind. It is called CSAIL2019 (named for the MIT department CSAIL, the successor of LCS). Rivest expexts that it will take 15 years of uninterrupted computing to solve it. The same equation is used as for LCS35, but this time, of course, the parameters are higher. For comparison, here is t, as defined for LCS35:
t = 79685186856218
And here’s the new value of t:
t = 2^56 = 72057594037927936
The CSAIL2019 value of t is about 1000 times larger in magnitude than the LCS35 value.
n used to be defined as follows:
n = 631446608307288889379935712613129233236329881833084137558
The CSAIL value of n is the following:
n = 474809754727201286617503413061677388505126074492005644486
This means that n is now 3072 bits in length, instead of about 2048.
While the full puzzle requires a solution for t = 2^56, CSAIL2019 is also interested in solutions for t = 2^k for 28<=k<56; these are called “milestone versions” of CSAIL2019.
As mentioned in my last blog post about LCS35, a time capsule with artefacts provided by Bill Gates, Tim Berners-Lee and other notable IT people was buried with the publication of the puzzle. It was opened after Bernard Fabrot had found the solution. For the CSAIL2019 puzzle, a new time capsule has been created.
In his description of CSAIL2019 Ron Rivest writes:
Anyone who believes to have solved the puzzle, or to have computed a solution to a “milestone version” of the puzzle, should first check the CSAIL web site (or contact CSAIL) to see if the solution is new. If it is, then they should submit the solution to CSAIL. If they have solved the full version, then they should also submit the resultant English sentence along with the factorization of n and relevant solution notes to the Director of CSAIL.
For a solution to a milestone version of the puzzle, please also submit an argument that the result is correct. […] Upon verification of the solution, the CSAIL Director will unseal the capsule at a ceremony set up for that purpose. If no solution is established by September 2033, then the CSAIL Director will unseal the capsule at CSAIL’s 31st birthday celebration in 2034, or at suitable alternate event. In the absence of a CSAIL Director, the President of MIT will designate another official or individual. Good luck!
Others puzzles of this kind
I am currently writing a comprehensive article about LCS35 and CSAIL2019 for a German computer magazine. In this article, I want to include a list of similar puzzles. The World Record Challenge and the DCT Reloaded Challenge are good candidates for this list. If a reader knows other challenges of this kind, please let me know.
Further reading: The Bonus 22 challenge