Theoretical solver of the LCS35 Time Capsule Crypto-Puzzle

timecapsule.py

#!/usr/bin/env python3

"""
Theoretical solver of the LCS35 Time Capsule Crypto-Puzzle

See: https://people.csail.mit.edu/rivest/lcs35-puzzle-description.txt

Example usage:

    % time ./timecapsule.py -t 100000
    230195281883451811244330425685617[...]214563011854122010792677489171995
    A single step takes about 10.3 nanoseconds
    It would take 24 years and 261 days to complete
    ./timecapsule.py -t 100000  1,00s user 0,00s system 99% cpu 1,009 total

    % time ./timecapsule.py -t 100000 -g
    230195281883451811244330425685617[...]214563011854122010792677489171995
    A single step takes about 1.2 nanoseconds
    It would take 2 years and 323 days to complete
    ./timecapsule.py -t 100000 -g  0,14s user 0,01s system 99% cpu 0,145 total

"""

import sys
import time
import argparse

try:
    import gmpy2
except ImportError:
    gmpy2 = None


T = 79_685_186_856_218
N = int(
    "".join(
        """
    631446608307288889379935712613129233236329881833084137558899
    077270195712892488554730844605575320651361834662884894808866
    350036848039658817136198766052189726781016228055747539383830
    826175971321892666861177695452639157012069093997368008972127
    446466642331918780683055206795125307008202024124623398241073
    775370512734449416950118097524189066796385875485631980550727
    370990439711973361466670154390536015254337398252457931357531
    765364633198906465140213398526580034199190398219284471021246
    488745938885358207031808428902320971090703239693491996277899
    532332018406452247646396635593736700936921275809208629319872
    7008292431243681
    """.split()
    )
)


def solve(x=2, t=T, n=N, chunk=2**10, gmp=False):
    e = 2 ** chunk
    if gmp:
        x = gmpy2.mpz(x)
        e = gmpy2.mpz(e)
        n = gmpy2.mpz(n)

    q, r = divmod(t, chunk)
    for _ in range(q):
        x = pow(x, e, n)
    return pow(x, 2**r, n)


def main(t, n, gmp):
    start = time.time()
    print(solve(t=t, n=n, gmp=gmp))
    delta = time.time() - start
    step = delta / t
    step_ns = step * 1024 * 1024
    days = int(step * T / 3600 / 24)
    years, days = divmod(days, 365)
    print(
        f"A single step takes about {step_ns:.1f} nanoseconds\n"
        f"It would take {years} years and {days} days to complete",
        file=sys.stderr,
    )


if __name__ == "__main__":
    parser = argparse.ArgumentParser()
    parser.add_argument("-n", type=int, default=N)
    parser.add_argument("-t", type=int, default=T)
    parser.add_argument("-g", "--gmp", action="store_true")
    args = parser.parse_args()
    if args.gmp and gmpy2 is None:
        parser.error(
            "gmpy2 is not installed. Install it using: `pip install gmpy2`"
        )
    main(args.t, args.n, args.gmp)