In 1999 cryptographer Ron Rivest published an encrypted text that was designed to take 35 years to break. Apparently, it has now been solved.
Two years ago, I blogged about the so-called LCS35 cryptogram, a cryptographic challenge created by cryptographer Ron Rivest in 1998. It is listed at position 48 on my Top 50 unsolved encrypted messages list. This challenge depends on the following equation:
To solve the challenge, one needs to calculate the value of w, which is the key that can be used to decrypt the actual cryptogram. The values of t and n are the following:
t = 79685186856218
n = 631446608307288889379935712613129233236329881833084137558899
The LCS35 challenge was developed by Ron Rivest, known as the “R” in RSA. I took the following picture of him at the RSA Conference 2015 in San Francisco:
Ron Rivest published this challenge on the occasion of the 35th birthday of MIT’s Laboratory for Computer Science (LCS) in 1998. The main design goal was that it would take approximately 35 years to solve it. It is therefore referred to as “LCS35 challenge” or “LCS35 cryptogram”. I wrote my first blog article about it in 2014 (in German).
The LCS35 challenge uses ideas described in the paper Time-lock puzzles and timed-release Crypto by Rivest, Adi Shamir (the “S” in RSA), and David Wagner. To the extent known, the value of w can only be calculated sequentially, which means that it is not possible to parallelize the calculation process. The puzzle can be solved by performing t successive squarings modulo n. There is no known way to perform this computation more quickly, unless one knows the factorization of n, which is the product of two large prime numbers.
Rivest chose the value of t taking into consideration the growth in computational power due to Moore’s Law. He estimated that the puzzle would require 35 years of continuous computation to solve, with the computer used being replaced every year by the fastest model available.
Once one has found out the value of w, one has to exclusive-or it with the following ciphertext:
The result is the plaintext, which provides information about the factorisation of n. This allows the solution to be easily verified.
There’s one important problem Rivest mentions in his LCS35 description: If there’s an error in the computation, all the following work will be useless.
Crypto experts will note that there is a relationship between the LCS35 challenge and the RSA algorithm (co-invented by Rivest, Shamir and Leonard Adleman). Both can be broken by factorizing a large prime number product. In this case, the product has 2048 bits. The longest prime number product ever publicly factorized is 768 bits long. It is therefore as good as impossible to attack a 2048 prime number product, which means that the RSA algorithm with a 2048 public key is secure and that the LCS35 challenge can only be solved via the squaring method described above.
In my 2017 article I wrote: “I am not aware of anyone, who is currently working on the LCS35 challenge. According to Rivest’s LCS35 description, the solution will be publicly announced in 2033. My expectation is that nobody will come up with the solution before.”
Apparently, I was wrong.
Blog readers Jon Paul and George Lasry have informed me that a Belgian computer programmer named Bernard Fabrot has now found the solution. Fabrot sent his solution to CSAIL, the successor of MIT’s Laboratory for Computer Science, which has confirmed its correctness.
The solution of LCS35 has received considerable media coverage. Among others, Wired (English) and Golem (German) have published articles about it. I have never heard of Bernard Fabrot before. I don’t think he has ever been active in the crypto scene. However, he is not a no-name, as he has written a couple of Linix books in French.
Instead of 35 years, as expexted by Rivest, Fabrot needed only three-and-a-half years for solving LCS35. As it seems, he was only about two weeks faster than a US group named Cryptophage, who worked on the LCS35 challenge, too.
For his computations, Fabrot used the GNU Multiple Precision Arithmetic Library, a free software library written in C for doing precise arithmetic. Fabrot dedicated one of the CPU cores on his home PC to solve the challenge. Wired quotes him: “During all these years I told no one I was trying to solve the puzzle except very close friends. I knew I had a chance, but if I told anyone they could have used a more powerful CPU to overtake me.”
The solution, i.e., the value of w and the plaintext, will be published on May 15th.
Edited to add: Meanwhile I have established contact with Bernard. I will ask him for details.
Further reading: The Top 50 unsolved encrypted messages: 45. The World Record Challenge