Description of the LCS35 Time Capsule Crypto-Puzzle by Ronald L. Rivest April 4, 1999 As part of the celebration of the 35th birthday of MIT's Laboratory for Computer Science, LCS Director Michael Dertouzos will present an "LCS Time Capsule of Innovations" to architect Frank Gehry. The Time Capsule will reside in the new building, designed by Gehry, that will house LCS. The time capsule will be unsealed on the earlier of 70 years from the inception of the Laboratory (on or about 2033), or upon solution of a cryptographic puzzle, described herein. This puzzle is designed to take approximately 35 years to solve. It uses the ideas described in the paper "Time-lock puzzles and timed-release Crypto" by myself, Adi Shamir, and David Wagner. A copy of this paper can be found at http://theory.lcs.mit.edu/~rivest/RivestShamirWagner-timelock.ps. The puzzle is designed to foil attempts of a solver to exploit parallel or distributed computing to speed up the computation. The computation required to solve the puzzle is "intrinsically sequential". The problem is to compute 2^(2^t) (mod n) for specified values of t and n. Here n is the product of two large primes, and t is chosen to set the desired level of difficulty of the puzzle. Note that the puzzle can be solved by performing t successive squarings modulo n, beginning with the value 2. That is, set W(0) = 2 W(i+1) = (W(i)^2) (mod n) for i>0, and compute W(t). There is no known way to perform this computation more quickly without knowing the factorization of n. The value of t was chosen to take into consideration the growth in computational power due to "Moore's Law". Based on the SEMATECH National Technology Roadmap for Semiconductors (1997 edition), we can expect internal chip speeds to increase by a factor of approximately 13 overall up to 2012, when the clock rates reach about 10GHz. After that improvements seem more difficult, but we estimate that another factor of five might be achievable by 2034. Thus, the overall rate of computation should go through approximately six doublings by 2034. We estimate that the puzzle will require 35 years of continuous computation to solve, with the computer being replaced every year by the next fastest model available. Most of the work will really be done in the last few years, however. An interesting question is how to protect such a computation from errors. If you have an error in year 3 that goes undetected, you may waste the next 32 years of computing. Adi Shamir has proposed a slick means of checking your computation as you go, as follows. Pick a small (50-bit) prime c, and perform the computation modulo cn rather than just modulo n. You can check the result modulo c whenever you like; this should be a extremely effective check on the computation modulo n as well. In order to allow the LCS director in the year 2034 (or whenever) to verify a submitted solution, we have arranged things so that solving the puzzle also enables the solver to factor the modulus n, as described below. Of course, one way to break the puzzle is to factor the modulus n directly. But we have chosen a 2048-bit modulus, which is unlikely to be factored in the given time frame without a breakthrough in the art of factoring. 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. 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.) Attached below is the Java code for generating the puzzle, and the actual puzzle itself. Anyone who believes to have solved the puzzle, should submit the resultant English sentence along with the factorization of n and relevant solution notes to the Director of LCS. Upon verification of the solution, the LCS Director will unseal the capsule at a ceremony set up for that purpose. If no solution is established by September 2033, then the LCS Director will unseal the capsule at the Laboratory's 70th anniversary celebration, or at a suitable alternate event. In the absence of an LCS Director, the President of MIT will designate another official or individual. Good luck! (Thanks to Scott Contini, Dimitri Antoniadis, Tom Knight, Steve Senturia, Adi Shamir, David Wagner, and Michael Dertouzos for their assistance!) ============================================================================== /* Program to create "Time-Lock Puzzle" for LCS35 Time Capsule Ronald L. Rivest April 2, 1999 */ import java.io.*; import java.util.Random; import java.math.BigInteger; import java.lang.Math; public class TimeLockPuzzle { public TimeLockPuzzle () {} static BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); static public void main(String args[]) throws IOException { System.out.println("Creating LCS35 Time Capsule Crypto-Puzzle..."); CreatePuzzle(); System.out.println("Puzzle Created."); } static public void CreatePuzzle() throws IOException { // Compute count of squarings to do each year BigInteger squaringsPerSecond = new BigInteger("3000"); // in 1999 System.out.println("Assumed number of squarings/second (now) = "+ squaringsPerSecond); BigInteger secondsPerYear = new BigInteger("31536000"); BigInteger squaringsFirstYear = secondsPerYear.multiply(squaringsPerSecond); System.out.println("Squarings (first year) = "+squaringsFirstYear); int years = 35; BigInteger t = new BigInteger("0"); BigInteger s = squaringsFirstYear; for (int i = 1999;i<=1998+years;i++) { // do s squarings in year i t = t.add(s); // apply Moore's Law to get number of squarings to do the next year String growth = new String(""); growth = "12204"; // ~x13 up to 2012, at constant rate if (i>2012) growth = "10750"; // ~x5 up to 2034, at constant rate s = s.multiply(new BigInteger(growth)).divide(new BigInteger("10000")); } System.out.println("Squarings (total)= " + t); System.out.println("Ratio of total to first year = "+ t.divide(squaringsFirstYear)); System.out.println("Ratio of last year to first year = "+ s.divide(squaringsFirstYear.multiply(new BigInteger("10758")) .divide(new BigInteger("10000")))); // Now generate RSA parameters int primelength = 1024; System.out.println("Using "+primelength+"-bit primes."); BigInteger twoPower = (new BigInteger("1")).shiftLeft(primelength); String pseed = getString("large random integer for prime p seed"); BigInteger prand = new BigInteger(pseed); String qseed = getString("large random integer for prime q seed"); BigInteger qrand = new BigInteger(qseed); System.out.println("Computing..."); BigInteger p = new BigInteger("5"); // Note that 5 has maximal order modulo 2^k (See Knuth) p = getNextPrime(p.modPow(prand,twoPower)); System.out.println("p = "+p); BigInteger q = new BigInteger("5"); q = getNextPrime(q.modPow(qrand,twoPower)); System.out.println("q = "+q); BigInteger n = p.multiply(q); System.out.println("n = "+n); BigInteger pm1 = p.subtract(ONE); BigInteger qm1 = q.subtract(ONE); BigInteger phi = pm1.multiply(qm1); System.out.println("phi = "+phi); // Now generate final puzzle value w BigInteger u = TWO.modPow(t,phi); BigInteger w = TWO.modPow(u,n); System.out.println("w (hex) = "+w.toString(16)); // Obtain and encrypt the secret message // Include seed for p as a check StringBuffer sgen = new StringBuffer(getString("string for secret")); sgen = sgen.append(" (seed value b for p = "+prand.toString()+")"); System.out.println("Puzzle secret = "+sgen); BigInteger secret = getBigIntegerFromStringBuffer(sgen); if (secret.compareTo(n) > 0) { System.out.println("Secret too large!"); return; } BigInteger z = secret.xor(w); System.out.println("z(hex) = "+z.toString(16)); // Write output to a file PrintWriter pw = new PrintWriter(new FileWriter("C:\\puzzleoutput.txt")); pw.println("Crypto-Puzzle for LCS35 Time Capsule."); pw.println("Created by Ronald L. Rivest. April 2, 1999."); pw.println(); pw.println("Puzzle parameters (all in decimal):"); pw.println(); pw.print("n = "); printBigInteger(n,pw); pw.println(); pw.print("t = "); printBigInteger(t,pw); pw.println(); pw.print("z = "); printBigInteger(z,pw); pw.println(); pw.println("To solve the puzzle, first compute w = 2^(2^t) (mod n)."); pw.println("Then exclusive-or the result with z."); pw.println("(Right-justify the two strings first.)"); pw.println(); pw.println("The result is the secret message (8 bits per character),"); pw.println("including information that will allow you to factor n."); pw.println("(The extra information is a seed value b, such that "); pw.println("5^b (mod 2^1024) is just below a prime factor of n.)"); pw.println(" "); pw.close(); // Wait for input carriage return to pause before closing System.in.read(); } final static BigInteger ONE = new BigInteger("1"); final static BigInteger TWO = new BigInteger("2"); static String getString(String what) throws IOException { // This routine is essentially a prompted "readLine" StringBuffer s = new StringBuffer(); System.out.println("Enter "+what+" followed by a carriage return:"); for (int i = 0;i<1000;i++) { int c = System.in.read(); if (c<0 || c == '\n') break; if (c != '\r') // note: ignore cr before newline s = s.append((char)c); } return(s.toString()); } static BigInteger getBigIntegerFromStringBuffer(StringBuffer s) throws IOException { // Base-256 interpretation of the given string BigInteger randbi = new BigInteger("0"); for (int i = 0;i