Lesson plan

LCS35

LCS35 is a cryptographic challenge and a time-lock puzzle set by Ron Rivest in 1999. The challenge is to calculate the value w=2^{2^t} \pmod n where t is a specific 14-digit (or 47-bit) integer, namely 79685186856218, and n is a specific 616-digit (or 2048-bit) integer that is the product of two large primes (which are not given). The value of w can then be used to decrypt the ciphertext z, another 616-digit integer. The plaintext provides the concealed information about the factorisation of n, allowing the solution to be easily verified. The idea behind the challenge is that the only known way to find the value of w without knowing the factorisation of n is by t successive squarings. The value of t was chosen so that this brute-force calculation would require about 35 years using 1999 chip speeds as a starting point, taking into account Moore's law. Rivest notes that "just as a failure of Moore's Law could make the puzzle harder than intended, a breakthrough in the art of factoring would make the puzzle easier than intended." The challenge was set at (and takes its name from) the 35th anniversary celebrations of the MIT Laboratory for Computer Science, now part of MIT Computer Science and Artificial Intelligence Laboratory. The LCS35 challenge was solved on April 15, 2019, twenty years later, by programmer Bernard Fabrot.…

Back to article

Article summary

LCS35 is a cryptographic challenge and a time-lock puzzle set by Ron Rivest in 1999. The challenge is to calculate the value w=2^{2^t} \pmod n where t is a specific 14-digit (or 47-bit) integer, namely 79685186856218, and n is a specific 616-digit (or 2048-bit) integer that is the product of two large primes (which are not given). The value of w can then be used to decrypt the ciphertext z, another 616-digit integer. The plaintext provides the concealed information about the factorisation of n, allowing the solution to be easily verified. The idea behind the challenge is that the only known way to find the value of w without knowing the factorisation of n is by t successive squarings. The value of t was chosen so that this brute-force calculation would require about 35 years using 1999 chip speeds as a starting point, taking into account Moore's law. Rivest notes that "just as a failure of Moore's Law could make the puzzle harder than intended, a breakthrough in the art of factoring would make the puzzle easier than intended." The challenge was set at (and takes its name from) the 35th anniversary celebrations of the MIT Laboratory for Computer Science, now part of MIT Computer Science and Artificial Intelligence Laboratory. The LCS35 challenge was solved on April 15, 2019, twenty years later, by programmer Bernard Fabrot.…

Key claims

  1. publication date: 2034 — source: Wikipedia · confidence 0.95

Discussion questions

  1. Summarise the article in your own words. Which single claim would you verify first, and why?
  2. The record states that the publication date is "2034". What evidence would count against this claim?
  3. Which claim in this article is most likely to be revised as the sources update? How would you check its current status?
  4. If two sources disagreed about one of these facts, what would you need in order to trust one over the other?

Bibliography

  1. Wikipedia https://en.wikipedia.org/w/index.php?oldid=1298742166

Key claims and bibliography are generated from the same tracked claims and sources as the article page.