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.

Click here for the complete top 50 list

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.


The ciphertext

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


Subscribe to Blog via Email

Enter your email address to subscribe to this blog and receive notifications of new posts by email.

Kommentare (22)

  1. #1 schlappohr
    16. Februar 2017

    “unless one knows the factorization of n, which is the product of two large prime numbers.”

    Assuming someone found such a prime factorization of n. How would this help to find the value of w? Ok, w contains the solution of how to factorize n, so we do not need w anymore if we found this factorization before. But this is just an intelligent joke of Rivest. Generally w may contain an arbitrary message.

  2. #2 Klaus Schmeh
    16. Februar 2017

    >Assuming someone found such a prime factorization
    >of n. How would this help to find the value of w?
    Using Euler’s theorem ( it is possible to find a number a, for which the following holds: 2^(2^t) * a = 1 (mod n). This means that w*a=1 (mod n) or w=1/a (mod n).

  3. #3 TWO
    16. Februar 2017

    Maybe a silly observation : the first number can not be a zero.


  4. #4 TWO
    16. Februar 2017

    How does the 2 2 t part work?


  5. #5 Klaus Schmeh
    16. Februar 2017

    >How does the 2 2 t part work?
    What do you mean? It’s 2^(2^t), not (2^2)^t, otherwise it would be easy.

  6. #6 TWO
    16. Februar 2017

    So the answer is an even number?


    P.S. Sanborn is a math genius compared to me.

  7. #7 TWO
    18. Februar 2017

    Am I the only one who is thinking that Ron Rivest is pulling some kind of a joke here?

    This is supposed to be encrypted with a math problem that is supposed to take 35 years to solve?

    So how does Ron know the answer to this problem?

  8. #8 Klaus Schmeh
    18. Februar 2017

    @TWO: Ron Rivest knows the answer because he knows the two factors of n.

  9. #9 TWO
    20. Februar 2017

    Dear Klaus,

    That may be true but it seems he also knows the result of t part of the puzzle or am I missing something here?

  10. #10 Klaus Schmeh
    20. Februar 2017

    @TWO: With the knowledge of the factors of n it is possible to easily compute 2^(2^t) (mod n), according to Euler’s theorem ( This means that Rivest knows the value of w, while others have to compute w the long way.

  11. #11 TWO
    20. Februar 2017


    My brain is not wired for Euler’s theorem.

    Let’s try again with a simple example

    I read this as follows :

    result of the t operation is 8. lets make n 10, we get 10 / 8 = 1 remainder =2 result 12.

    And probably that is not how I should read Ron’s formula?

  12. #12 Klaus Schmeh
    20. Februar 2017

    @TWO: n=10 doesn’t work in this case, as n needs to be relatively prime to 2. Let’s take the following example:

    Let n=21. n is the product of the prime numbers 3 and 7. Let t=2. Then we get:

    w = 2^(2^t) (mod 21)
    = 2^(2^2) (mod 21)
    = 16 (mod 21)

    This is easy to compute, but if t=79685186856218 it becomes extremely hard. However, there’s a shorter way using Euler’s theorem. This theorem states (in a special case that is relevant here):

    a^((p-1)*(q-1))=1 (mod n) for every a relatively prime to n. p and q are the prime factors of n. In our example this means:

    a^((3-1)*(7-1)=1 (mod 21) for every a relatively prime to n
    => a^12=1 (mod 21) for every a relatively prime to n

    If a=2 this means: 2^12=1 (mod 21). This can be used to compute w in a way that is easier than doing all the exponentiations. I think this method is described here (sorry for not going into the details):

  13. #13 TWO
    a parking lot at 39° 6′ 25″ N, 76° 44′ 35″ W
    21. Februar 2017


    First of all thank you for your time and effort trying to explain the numbers magic to me.

    Main culprit seems to be that I read the mod N as being similar to the assembly language mod instruction which works as I described before.

    Instead it is a seperate operation that has to be performed, bit out my league that Eulers theorem.

    Better make that a couple of miles.

    The 2^(2^t) part can be done by using an arithmetic shift which usually is only a few clock cyles.
    Multiplying by 2 is equal to shifting the byte(s) one bit position to the left or right depending if your CPU uses Intel or Motorola “notation” better read that as words of memory.

    In essence you get a 1 followed by a lot of zeroes, somebody smart with math can probably figure out how many zeroes there are by just looking at t

    I’m numbers blind, but I would be surprised it that takes more than an hour of CPU time with optimized code.

    If I did the math correct (lol) you need about 9.5 Gig of Ram to do it without virtual memory.
    That would have been a lot of time consuming disk swapping back in 1999.

    Back in 1999 the Intel Pentium 4 was the hot rod, now it seems to be the Sparc M6 or the Intel 14 nm stuff.

    Correct me if any of the above is incorrect please.

    your friend,


  14. #14 Klaus Schmeh
    21. Februar 2017

    >The 2^(2^t) part can be done by using an
    >arithmetic shift which usually is only a few clock cyles.
    This is certainly correct, but 2^(2^t) with t = 79685186856218 is a huge number. I don’t think you can do this within a CPU hour.

  15. #15 TWO
    22. Februar 2017


    yes it is a huge number but that is all it is.

    I doubt it would even take an hour with a modern CPU.

    But that was said by the guy who is numbers blind.

    Ron is making his own version of the old 10 = 2 joke here. (1000000000000000000000000000000000000000 etc.)

  16. #16 Klaus Schmeh
    24. Februar 2017

    >I doubt it would even take an hour with a modern CPU.
    I really don’t think so. If it is, maybe someone will come up with the solution.

  17. #17 TWO
    24. Februar 2017

    Well, the answer is a binary 1 followed by 79685186856218 binary zeroes…

  18. #18 TWO
    24. Februar 2017

    and that you apply to the second stage of the 2^part

  19. #19 TWO
    26. Februar 2017

    and all of the above is wrong, here is in Ron Rivest own words how it works :

    Here is a smaller example of the puzzle.
    Suppose n = 11*23 = 253, and t = 10. Then we can compute:
    2^(2^1) = 2^2 = 4 (mod 253)
    2^(2^2) = 4^2 = 16 (mod 253)
    2^(2^3) = 16^2 = 3 (mod 253)
    2^(2^4) = 3^2 = 9 (mod 253)
    2^(2^5) = 9^2 = 81 (mod 253)
    2^(2^6) = 81^2 = 236 (mod 253)
    2^(2^7) = 236^2 = 36 (mod 253)
    2^(2^8) = 36^2 = 31 (mod 253)
    2^(2^9) = 31^2 = 202 (mod 253)
    w = 2^(2^t) = 2^(2^10) = 202^2 = 71 (mod 253)
    Thus, the “w” value computed for the puzzle is 71 (decimal), which is
    47 (hex). If we have a “z” value for the puzzle of 13 (hex), then the
    “secret message” for the example is (47 xor 13) = 54 (hex). (The secret
    message should then be interpreted in ascii at 8 bits per character.)

    Given the fact that w has to be 616 bits (77) bytes to XOR it with the cryptext which is also 616 bits long AND the fact that n is ALSO 616 bits long we can deduce that the first number of the calculated w has to be lower than 6 else we end up with 615 bits or less as a result.

    Since the cryptext describes the factoriaztion of n it is logical to assume that the actual numbers used are in the cryptext.

    If that is the case those numbers can not be bigger than 615 bits (worst case scenario) .

    Makes you wonder if the factorization of n is easier to deduce than the math involved with w.

    Of interest is the fact that n ends with the number 1.

    According to my poor math skills that can only be the the result of 1 * 1 or 3 * 7 or 9 * 9

    Not sure if the use of prime numbers is mandatory or not.

  20. #20 YuL
    14. Mai 2017

    I quickly wrote a piece of C++ code to perform the
    computation of w(m) = 2^(2^m) mod n
    It takes 28m17s to compute w(2^30) on my box
    which runs an Intel Core i7-5820K, so that it would
    take 4 years to compute w(t) on my box. That would
    make the problem solved by 2021 more than 10
    years before the estimated date.
    For the record here is w(2^30):

  21. #21 Narga
    15. Mai 2017

    Are you sure that you are correctly scaling up the 28 minutes for the actual value of t? For example, did you check how long w(2^29) and w(2^31) take on your computer?

  22. #22 YuL
    15. Mai 2017

    I think so. I don’t have the values you are asking for,
    I have these:
    $ time ./lcs35 1048576
    real 0m1.802s
    user 0m1.804s
    sys 0m0.004s
    $ time ./lcs35 16777216
    real 0m26.491s
    user 0m26.488s
    sys 0m0.000s