StartseiteCipherbrain

The Top 50 unsolved encrypted messages: 48. Ron Rivest’s timelock cryptogram

Von / 15. Februar 2017 / 22 Kommentare
Mehr

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:

LCS-35-bar

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
077270195712892488554730844605575320651361834662884894808866
350036848039658817136198766052189726781016228055747539383830
826175971321892666861177695452639157012069093997368008972127
446466642331918780683055206795125307008202024124623398241073
775370512734449416950118097524189066796385875485631980550727
370990439711973361466670154390536015254337398252457931357531
765364633198906465140213398526580034199190398219284471021246
488745938885358207031808428902320971090703239693491996277899
532332018406452247646396635593736700936921275809208629319872
7008292431243681

 

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-2016

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:

427338526681239414707099486152541907807623930474842759553127
699575212802021361367225451651600353733949495680760238284875
258690199022379638588291839885522498545851997481849074579523
880422628363751913235562086585480775061024927773968205036369
669785002263076319003533000450157772067087172252728016627835
400463807389033342175518988780339070669313124967596962087173
533318107116757443584187074039849389081123568362582652760250
029401090870231288509578454981440888629750522601069337564316
940360631375375394366442662022050529545706707758321979377282
989361374561414204719371297211725179287931039547753581030226
7611143659071382

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

Linkedin: https://www.linkedin.com/groups/13501820
Facebook: https://www.facebook.com/groups/763282653806483/

Subscribe to Blog via Email

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

Stichworte:
Mehr

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

    @schlappohr:
    >Assuming someone found such a prime factorization
    >of n. How would this help to find the value of w?
    Using Euler’s theorem (https://en.wikipedia.org/wiki/Euler%27s_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.

    TWO

  4. #4 TWO
    16. Februar 2017

    How does the 2 2 t part work?

    TWO

  5. #5 Klaus Schmeh
    16. Februar 2017

    @TWO:
    >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?

    TWO

    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 (https://en.wikipedia.org/wiki/Euler%27s_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

    Klaus,

    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): https://en.wikipedia.org/wiki/Modular_multiplicative_inverse

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

    @Klaus

    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,

    TWO

  14. #14 Klaus Schmeh
    21. Februar 2017

    @TWO:
    >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

    @Klaus

    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

    @TWO:
    >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
    Paris
    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):
    197015459039049106476021348277755946667848
    555565501606488007619331468164870213850380
    722508190369711897202622205287100463819046
    402586336244909474434552490193612237798197
    135880945060553291240481546207512093762750
    181391634987142720536035737825837540796455
    332259950630596625797887285547037453339707
    321262781196538986411722940027137702956838
    123522722309309549331697647206883470627289
    257544318521559181594102166186570018688288
    851384679131599915389500911098813114363924
    816841401734127726820003917959477974998503
    904928905064664092305835193031310875932399
    140322477018395624123735000463816419611913
    5688676584768228718794512562

  21. #21 Narga
    15. Mai 2017

    @YuL:
    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
    France
    15. Mai 2017

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