The cryptography of computers: hashes, AES and HMAC, RSA and its weak keys, Diffie–Hellman, Shor and Grover on a quantum computer, ML-KEM, BB84, Shamir’s shares, time locks, passwords.
Time-Lock Puzzle
Locks a message behind t squarings in a row modulo a 2,048-bit number, after Rivest, Shamir and Wagner (1996): the maker, who knows its factors, takes the shortcut through φ(n); the opener must square, which no number of computers makes faster, checked as it goes by Shamir’s trick modulo c·n. LCS35, Rivest’s puzzle of 1999 solved in 2019, is opened by the shortcut from the seed its message names.
About this tool
History
In 1996 Ronald Rivest, Adi Shamir and David Wagner proposed time-lock puzzles, a way to “send information into the future”: a message no one, its sender included, can read before a chosen time has passed. In April 1999 Rivest set LCS35 for the 35th birthday of MIT’s Laboratory for Computer Science, meant to take about 35 years. On 15 April 2019 Bernard Fabrot solved it after three years and three months of squaring in software, and a team with an FPGA weeks later, after two months.
How it works
The maker multiplies two random primes of 1,024 bits into n and sets t, the number of squarings, by the opener’s speed. Knowing φ(n), she reduces 2^t modulo φ(n) and finds b = a^(2^t) mod n in milliseconds; a random key K locks the message with AES-256-GCM, where the paper names RC5, and C_K = K + b mod n. The capsule is n, a, t, C_K and the ciphertext; p and q are dropped. The opener has no shortcut: t squarings, one after another, in the background, done modulo c·n for a prime c of 50 bits, so that Shamir’s check can test every stretch modulo c.
How it was checked
Rivest’s small example comes out as printed: 4, 16, 3, 9, 81, 236, 36, 31, 202 and 71, and 47 hex xor 13 gives 54. His program, run again, gives LCS35’s t of 79,685,186,856,218 from 3,000 squarings a second and its growth by Moore’s law. From the seed the solved message gives, his own rule finds a prime that divides n, and the shortcut then reads “!!! Happy Birthday LCS !!!” and the same seed, so the puzzle checks itself. Puzzles made here give the same b by squaring as by the shortcut, a run stopped and continued gives it too, a changed capsule is refused, and a corrupted value fails Shamir’s check.
Limits
A time lock counts squarings, not time: a faster device opens it sooner, and the estimate is this device’s, measured at the size it squares at. Opening needs the page kept open, and a stopped run continues only while it stays. The maker’s factors open it at once, and the puzzle is only as safe as factoring a 2,048-bit number is hard. The paper’s other way, trusted agents who release secrets on a schedule, is not built.
- Ronald L. Rivest, Adi Shamir and David A. Wagner, “Time-lock puzzles and timed-release Crypto”, MIT/LCS/TR-684 (revised 10 March 1996)
- Ronald L. Rivest, “Description of the LCS35 Time Capsule Crypto-Puzzle” (4 April 1999), with the puzzle and his program
- Ronald L. Rivest, “LCS35 Time-Lock Crypto Puzzle”, slides (15 May 2019): the two solutions
- The solved message with its seed, mersenneforum.org, post 24 (16 May 2019)