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