Time Capsule

by goulov and ice

Points: 122 (Dynamic, 120 solves)

Description:

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

Given: time_capsule_aa5d041f6d3bef8d9977d6bd0e2cfeab322c4a39.txz

Solution:

TLDR

Figure out this is LCS35 Time Capsule Crypto-Puzzle.
Try to factor n. Succeed.
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)