Description of the CSAIL2019 Time Capsule Crypto-Puzzle
by Ronald L. Rivest
May 14, 2019
We describe a "refreshed" version of the LCS35 time-lock crypto
puzzle, to extend the puzzle out to the year 2034 (since the original
LCS35 puzzle was solved in 2019 by Bernard Fabrot).
See the description of the LCS35 puzzle given here:
http://people.csail.mit.edu/rivest/pubs.html#Riv99b
for explanation and details of the original puzzle.
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, t is chosen to set
the desired level of difficulty of the puzzle, and "^" denotes
exponentiation. This overall structure is retained in the refreshed
version 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=1, 2, ...
and compute W(t).
There is no known way to perform this computation more quickly than to
perform the t squarings sequentially, unless the factorization of n is
known.
In the original (LCS35) version of the puzzle, the number n was about
2048 bits long, and the number t was about 80 trillion. We estimated
that the puzzle would take 35 years of continuous computation to
solve, with the computer being replaced every year by the next fastest
model available.
Since the puzzle has now been solved, however, we provide here
"refreshed" values of n and t, that should restore the puzzle to
having its intended difficulty (that is, it is estimated to require
until about 2034 to solve).
One change is that the modulus n is now 3072 bits in length, instead
of about 2048.
The new version of the puzzle also specifies that
t = 2 ^ 56 = 72057594037927936,
which is about 1000 times larger in magnitude than t for the original
LCS35 puzzle.
While the full puzzle requires a solution for t = 2 ^ 56, CSAIL is
also interested in solutions for t = 2 ^ k for 56/2 <= k < 56; these
are called "milestone versions of the puzzle".
In order to allow the CSAIL 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.
Here is a smaller example of the puzzle.
Suppose n = 11*23 = 253, and t = 16 = 2^4. Then we can compute:
2^(2^0) = 2^1 = 2 (mod 253)
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)
2^(2^10) = 202^2 = 71 (mod 253)
2^(2^11) = 71^2 = 234 (mod 253)
2^(2^12) = 234^2 = 108 (mod 253)
2^(2^13) = 108^2 = 26 (mod 253)
2^(2^14) = 26^2 = 170 (mod 253)
2^(2^15) = 170^2 = 58 (mod 253)
2^(2^16) = 58^2 = 75 (mod 253)
The values 2^(2^8) = 31 and 2^(2^4) = 9 are solutions to "milestone versions"
of this toy puzzle, as 16 = 2^4, 8 = 2^3, and 4 = 2^2.
Thus, the "w" value computed for the puzzle is 75 (decimal), which is
4a (hex). If we have a "z" value for the puzzle of 13 (hex), then the
"secret message" for the example is (4a xor 13) = 47 (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 refreshed puzzle itself.
Anyone who believes to have solved the puzzle, or to have computed a
solution to a "milestone version" of the puzzle, should first check
the CSAIL web site (or contact CSAIL) to see if the solution is new.
If it is, then they should submit the solution to CSAIL. If they have
solved the full version, then they should also submit the resultant
English sentence along with the factorization of n and relevant
solution notes to the Director of CSAIL. For a solution to a
milestone version of the puzzle, please also submit an argument that
the result is correct. (See the "small prime" of Shamir described in
the original paper, for example, or use a more sophisticated
verifiable delay function proof.)
Upon verification of the solution, the CSAIL Director will unseal the
capsule at a ceremony set up for that purpose. If no solution is
established by September 2033, then the CSAIL Director will unseal the
capsule at CSAIL's 31st birthday celebration in 2034, or at suitable
alternate event. In the absence of a CSAIL Director, the
President of MIT will designate another official or individual.
Good luck!
==============================================================================
/* Program to create "Time-Lock Puzzle" for LCS35 Time Capsule
Ronald L. Rivest
March 30, 1999 (revised May 14, 2019 for CSAIL 2019 puzzle)
*/
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 CSAIL2019 Time Capsule Crypto-Puzzle...");
CreatePuzzle();
System.out.println("Puzzle Created.");
}
final static BigInteger ONE = new BigInteger("1");
final static BigInteger TWO = new BigInteger("2");
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 s = secondsPerYear.multiply(squaringsPerSecond); // first year
// System.out.println("Squarings (first year) = "+s);
// int years = 15; // was 35 for orignal LCS 35 puzzle
// double Moore =
// 1.58740105197; // = 2^(2/3) Moore's Law constant per year (used for LCS35 puzzle)
// 1.1000; // Estimate from Simon Peffers
// (Note that this is also in code in a few lines as a constant.)
// Method used for computing t for LCS35
// BigInteger t = new BigInteger("0");
// for (int i = 1;i<=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
// s = s.multiply(new BigInteger("11000")).divide(new BigInteger("10000"));
// }
// Method for 2019 puzzle: set t to 2**56
int log2_t = 56;
BigInteger t = (new BigInteger("1")).shiftLeft(log2_t);
System.out.println("Squarings (total)= " + t);
// Now generate RSA parameters
int primelength = 1536;
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 FIVE = new BigInteger("5");
BigInteger p = new BigInteger("7");
BigInteger q = new BigInteger("11");
BigInteger n = new BigInteger("77");
BigInteger max_n = (new BigInteger("1").shiftLeft(2*primelength));
BigInteger min_n = (new BigInteger("1").shiftLeft(2*primelength-1));
while (n.compareTo(min_n)==-1 || n.compareTo(max_n)==1)
{
// Note that 5 has maximal order modulo 2^k (See Knuth)
prand = prand.add(ONE);
p = getNextPrime(FIVE.modPow(prand,twoPower));
System.out.println("p = "+p);
qrand = qrand.add(ONE);
q = getNextPrime(FIVE.modPow(qrand,twoPower));
System.out.println("q = "+q);
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("puzzleoutput.txt"));
pw.println("Crypto-Puzzle for CSAIL 2019 Time Capsule.");
pw.println("Created by Ronald L. Rivest. May 14, 2019."); pw.println();
pw.println("(Successor to LCS 35 Crypto-Puzzle.)"); 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.print(" = 2 ** "); pw.print(log2_t); pw.println(); 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^1536) is just below a prime factor of n.)");
pw.println(" ");
pw.close();
// Wait for input carriage return to pause before closing
System.in.read();
}
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