Crypto 2019 - Time Capsule

Rivest puzzle.

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 :

#!/usr/bin/python

from Crypto.Util.number import *
from secret import flag, n, t, z


def encrypt_time_capsule(msg, n, t, z):
	m = bytes_to_long(msg)
	l = pow(2, pow(2, t), n)
	c = l ^ z ^ m
	return (c, n, t, z) 

print encrypt_time_capsule(flag, n, t, z)

time-capsule.txt :

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

So we have:

c --> ciphertext
z --> variable
t --> part of the exponent
n --> modulo

We can easily guess that the flag is $m$. To find the value of $m$ we can do $m = c \oplus l \oplus z = (l \oplus z \oplus m) \oplus l \oplus z = m$.

The tricky part in this script is that $l$ is defined as :

$$ l = 2^{2^t} \pmod 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 knowin 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, derived from the Euler’s theorem, which states that if $a \in Z_n^{*}$, then:

$$ a^k \pmod n = a^{k \pmod{\varphi(n)}} \pmod n $$

We have that $a$ is 2, and $n$ ends with 3, so $a$ is relative prime to $n$ and we can use this property.

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 :

#!/usr/bin/python3

from Crypto.Util.number import *
from factordb.factordb import FactorDB

c = 30263951492003430418944035844723976843761515320480688994488846431636782360488888188067655841720110193942081554547272176290791213962513701884837856823209432209367951673301622535940395295826053396595886942990258678430777333636450042181585837395671842878310404080487115827773100028876775230121509570227303374672524063165714509957850966189605469484201028704363052317830254920108664916139026741331552127849056897534960886647382429202269846392809641322613341548025760209280611758326300214885296175538901366986310471066687700879304860668964595202268317011117634615297226602309205086105573924029744405559823548638486054634428
n = 16801166465109052984956796702219479136700692152603640001472470493600002617002298302681832215942994746974878002533318970006820414971818787350153626339308150944829424332670924459749331062287393811934457789103209090873472485865328414154574392274611574654819495894137917800304580119452390318440601827273834522783696472257727329819952363099498446006266115011271978143149347765073211516486037823196033938908784720042927986421555211961923200006343296692217770693318701970436618066568854673260978968978974409802211538011638213976732286150311971354861300195440286582255769421094876667270445809991401456443444265323573485901383
t = 6039738711082505929
z = 13991757597132156574040593242062545731003627107933800388678432418251474177745394167528325524552592875014173967690166427876430087295180152485599151947856471802414472083299904768768434074446565880773029215057131908495627123103779932128807797869164409662146821626628200600678966223382354752280901657213357146668056525234446747959642220954294230018094612469738051942026463767172625588865125393400027831917763819584423585903587577154729283694206436985549513217882666427997109549686825235958909428605247221998366006018410026392446064720747424287400728961283471932279824049509228058334419865822774654587977497006575152095818

f = FactorDB(n)
f.connect()
factors = f.get_factor_list()

phi = 1
for i in factors:
    phi *= i-1

# c = l ^ z ^ m
# m = c ^ l ^ z
l = pow(2, pow(2, t, phi), n)
m = c ^ z ^ l
msg = long_to_bytes(m)
print(msg)

Flag

CCTF{_______________________________________________Happy_Birthday_LCS______________________________________________}