Time Capsule  CryptoCTF 2019
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!
Given: time_capsule_aa5d041f6d3bef8d9977d6bd0e2cfeab322c4a39.txz
Solution:
TLDR

Figure out this is LCS35 Time Capsule CryptoPuzzle.

Try to factor n. Succeed.

Apply Euler’s theorem and solve the puzzle to get the flag.
Description
This challenge is LCS35 Time Capsule CryptoPuzzle by Rivest (https://people.csail.mit.edu/rivest/lcs35puzzledescription.txt).
Interestingly, the original challenge was recently solved (https://www.csail.mit.edu/news/programmerssolvemits20yearoldcryptographicpuzzle).
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 2048bit 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)