# Time Capsule

by icemonster and majo

Points: 122 (Dynamic, 120 solves)

Description:

You neither need 35 years nor even 20 years to solve this problem!

# Solution:

## TLDR

1. Figure out this is LCS35 Time Capsule Crypto-Puzzle.

2. Try to factor n. Succeed.

3. Apply Euler’s theorem and solve the puzzle to get the flag.

## Description

This challenge is LCS35 Time Capsule Crypto-Puzzle by Rivest (https://people.csail.mit.edu/rivest/lcs35-puzzle-description.txt).

Interestingly, the original challenge was recently solved (https://www.csail.mit.edu/news/programmers-solve-mits-20-year-old-cryptographic-puzzle).

This challenge requires, given $$n,t$$, to compute: $w = 2^{2^{t}}\ mod\ n$

Solving this problem should require squaring sequentially $$t$$ times. And $$t$$ could be chosen to set how long the challenge should take to be solved.

## Solving

In the original reference (linked above) there is an interesting quote by Rivest:

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.

Of course this CTF challenge won’t take decades of computations to solve, so we (try to make a breakthrough in the art of factoring and) try to factor $$n$$. And we succeed! Given the factorization we can compute $$\phi(n)$$ and then we can apply Euler theorem to reduce the computation from years to seconds: $2^{2^t} = 2^{2^t\ mod\ \phi(n)}\ mod\ n$

CCTF{_______________________________________________Happy_Birthday_LCS______________________________________________}


# Resources:

The solution code can be found in sol.py (variables in givenvars.py)