# Writeup: Crypto 2019 - Time Capsule

## Information

*category*: crypto*points*: 122

## Description

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

## Writeup

The challenge gives us two files.

`time-capsule.py`

:

1 | #!/usr/bin/python |

`time-capsule.txt`

:

1 | (30263951492003430418944035844723976843761515320480688994488846431636782360488888188067655841720110193942081554547272176290791213962513701884837856823209432209367951673301622535940395295826053396595886942990258678430777333636450042181585837395671842878310404080487115827773100028876775230121509570227303374672524063165714509957850966189605469484201028704363052317830254920108664916139026741331552127849056897534960886647382429202269846392809641322613341548025760209280611758326300214885296175538901366986310471066687700879304860668964595202268317011117634615297226602309205086105573924029744405559823548638486054634428L, 16801166465109052984956796702219479136700692152603640001472470493600002617002298302681832215942994746974878002533318970006820414971818787350153626339308150944829424332670924459749331062287393811934457789103209090873472485865328414154574392274611574654819495894137917800304580119452390318440601827273834522783696472257727329819952363099498446006266115011271978143149347765073211516486037823196033938908784720042927986421555211961923200006343296692217770693318701970436618066568854673260978968978974409802211538011638213976732286150311971354861300195440286582255769421094876667270445809991401456443444265323573485901383L, 6039738711082505929, 13991757597132156574040593242062545731003627107933800388678432418251474177745394167528325524552592875014173967690166427876430087295180152485599151947856471802414472083299904768768434074446565880773029215057131908495627123103779932128807797869164409662146821626628200600678966223382354752280901657213357146668056525234446747959642220954294230018094612469738051942026463767172625588865125393400027831917763819584423585903587577154729283694206436985549513217882666427997109549686825235958909428605247221998366006018410026392446064720747424287400728961283471932279824049509228058334419865822774654587977497006575152095818L) |

So we have:

1 | c --> ciphertext |

We can easily guess that the flag is `m`

.

To find the value of `m`

we can do `m = c xor l xor z = (l xor z xor m) xor l xor z = m`

.

The tricky part in this script is that `l`

is defined as :

`l = pow(2, pow(2, t), n)`

–> `l = 2^(2^t) mod n`

.

`2^t`

takes a very long time to compute because the value of `t`

is very large (6039738711082505929). This is very similar/identical to the Rivest Puzzle which was solved in april 2019 after `20`

years. However we can check in the original paper of the puzzle that Rivest said `There is no known way to perform this computation more quickly without knowing the factorization of n`

.

We can easily see that we can find the factors of `n`

using yafu or factordb. How we can compute quickly `l`

now ? We can use this property of number theory :

`a^k mod n = a^(k mod phi(n)) mod n`

This is very useful because we know that normal exponentiations with big integers are very slow to compute, but modular exponentiations are very fast.

`exploit.py`

:

1 | #!/usr/bin/python3 |

## Flag

1 | CCTF{_______________________________________________Happy_Birthday_LCS______________________________________________} |