# My example of Time-lock-puzzles-and-timed-release-Crypt (cpp)

Time Capsule Crypto-Puzzle

My MSVC example: Time-lock-puzzles-and-timed-release-Crypto.rar (MSVC)
Description:
lcs35-puzzle-description.txt
Timelock puzzles and timedrelease Crypto (PDF)

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.)

#### Добавить комментарий

• • • 