In 1999 cryptographer Ron Rivest published an encrypted text that was designed to take 35 years to break. 18 years later it is still unbroken.
The unsolved encrypted message I am writing about today depends on a simple equation. Here it is:
All you need to do is calculate the value of w. This value can then be used to decrypt a ciphertext. The values of t and n are the following:
t = 79685186856218
n = 631446608307288889379935712613129233236329881833084137558899
The LTC35 challenge
The cryptogram described above was developed by Ron Rivest, known as the “R” of RSA. I took the following picture of him at last year’s RSA Conference 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. This puzzle is designed to take approximately 35 years to solve. 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 this 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 cleartext, 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 this 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.
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.
Further reading: Three new episodes of Chief Security Officer