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
899077270195712892488554730844605575320651361834662884894808
866350036848039658817136198766052189726781016228055747539383
830826175971321892666861177695452639157012069093997368008972
127446466642331918780683055206795125307008202024124623398241
073775370512734449416950118097524189066796385875485631980550
727370990439711973361466670154390536015254337398252457931357
531765364633198906465140213398526580034199190398219284471021
246488745938885358207031808428902320971090703239693491996277
899532332018406452247646396635593736700936921275809208629319
8727008292431243681
The CSAIL value of n is the following:
n = 474809754727201286617503413061677388505126074492005644486
710 619636071042455814765425270760494101231177589201256757906
462 053687463338505591900116762157771031136607205702942170513
568 430393481139013793780209643316395921689235118482669118001
605 519886679653623008552320068354906699567215583904228295559
156 849460306111329203904475384384648480711222838920423958171
293 110891982025021858635204389730623887202537819314111150742
631 144461349873631561421830476173554162699783903651772800068
839 401561061817976886834207039510014762029561669583444089424
114 790556556780829814902466852704523965014586209290411941287
400 776304104231428760477287686129441766402083279620913558718
182 645823558000382582372423580085016028485080973720098370355
217 935469186387604444337782243983407931357802908565807857573
129 024477859561522947241132683150266742576852000637175296327
429 629450606318225806436204878833839252826635151130492184785
475 0642192694541125065873977
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.
Follow @KlausSchmeh
Further reading: The Bonus 22 challenge
Linkedin: https://www.linkedin.com/groups/13501820
Facebook: https://www.facebook.com/groups/763282653806483/
Kommentare (1)