Crypto

Time Capsule

Crypto - 120 solves

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

#!/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)

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

Solution

If we can calculate l, we can retrieve the flag. Since t is large, calculating l directly as we see it in the given code will be very hard. However, we can use the property from modular arithmetic:

c \equiv d \pmod{\phi(n)} \implies a^c \equiv a^d \pmod n

which allows us to calculate l efficiently if we can factorise n. It turns out that n is easily factorised and therefore we can easily compute l:

from functools import reduce
# from factordb.factordb import FactorDB
from Crypto.Util.number import long_to_bytes

flag, n, t, z = (30263951492003430418944035844723976843761515320480688994488846431636782360488888188067655841720110193942081554547272176290791213962513701884837856823209432209367951673301622535940395295826053396595886942990258678430777333636450042181585837395671842878310404080487115827773100028876775230121509570227303374672524063165714509957850966189605469484201028704363052317830254920108664916139026741331552127849056897534960886647382429202269846392809641322613341548025760209280611758326300214885296175538901366986310471066687700879304860668964595202268317011117634615297226602309205086105573924029744405559823548638486054634428, 16801166465109052984956796702219479136700692152603640001472470493600002617002298302681832215942994746974878002533318970006820414971818787350153626339308150944829424332670924459749331062287393811934457789103209090873472485865328414154574392274611574654819495894137917800304580119452390318440601827273834522783696472257727329819952363099498446006266115011271978143149347765073211516486037823196033938908784720042927986421555211961923200006343296692217770693318701970436618066568854673260978968978974409802211538011638213976732286150311971354861300195440286582255769421094876667270445809991401456443444265323573485901383, 6039738711082505929, 13991757597132156574040593242062545731003627107933800388678432418251474177745394167528325524552592875014173967690166427876430087295180152485599151947856471802414472083299904768768434074446565880773029215057131908495627123103779932128807797869164409662146821626628200600678966223382354752280901657213357146668056525234446747959642220954294230018094612469738051942026463767172625588865125393400027831917763819584423585903587577154729283694206436985549513217882666427997109549686825235958909428605247221998366006018410026392446064720747424287400728961283471932279824049509228058334419865822774654587977497006575152095818)

# f = FactorDB(n)
# f.connect()
# fn = f.get_factor_list()
fn = [15013, 583343756982313, 585503197547927, 609245815680559, 612567235432583, 634947980859229, 635224892351513, 639438000563939, 654170414254271, 654269804672441, 667954470985657, 706144068530309, 721443717105973, 737993471695639, 744872496387077, 746232585529679, 795581973851653, 815694637597057, 817224718609627, 841183196554507, 864339847436159, 873021823131881, 884236929660113, 899583643974479, 922745965897867, 942872831732189, 951697329369323, 971274523714349, 1017566110290559, 1018452110902339, 1025985735184171, 1027313536626551, 1059774237802229, 1067609726096989, 1070689247726159, 1079289330417443, 1098516592571807, 1107673252158281, 1108654254305327, 1110918654474373, 1111516996694389, 1112193819715441]
phi = reduce(lambda a, v: (v-1) * a, fn, 1)
l = pow(2, pow(2, t, phi), n)
m = flag ^ l ^ z
print(long_to_bytes(m).decode())

> python ./solve.py
CCTF{_______________________________________________Happy_Birthday_LCS______________________________________________}

roXen

Crypto - 22 solves

Relationship with a cryptographer!

The Girlfriend: All you ever care about is crypto! I am sick of it! It's me or crypto!

The Cryptographer boyfriend: You meant to say it's you XOR cryptography.

The Girlfriend: I am leaving you.

#!/usr/bin/env python

from Crypto.Util.number import *
from secret import exp, flag, nbit

assert exp & (exp + 1) == 0

def adlit(x):
    l = len(bin(x)[2:])
    return (2 ** l - 1) ^ x

def genadlit(nbit):
    while True:
        p = getPrime(nbit)
        q = adlit(p) + 31337
        if isPrime(q):
            return p, q

p, q = genadlit(nbit)
e, n = exp, p * q

c = pow(bytes_to_long(flag), e, n)

print 'n =', hex(n)
print 'c =', hex(c)

n = 0x3ff77ad8783e006b6a2c9857f2f13a9d896297558e7c986c491e30c1a920512a0bad9f07c5569cf998fc35a3071de9d8b0f5ada4f8767b828e35044abce5dcf88f80d1c0a0b682605cce776a184e1bcb8118790fff92dc519d24f998a9c04faf43c434bef6c0fa39a3db7452dc07ccfced9271799f37d91d56b5f21c51651d6a9a41ee5a8af17a2f945fac2b1a0ea98bc70ef0f3e37371c9c7b6f90d3d811212fc80e0abcd5bbefe0c6edb3ca6845ded90677ccd8ff4de2c747b37265fc1250ba9aa89b4fd2bdfb4b4b72a7ff5b5ee67e81fd25027b6cb49db610ec60a05016e125ce0848f2c32bff33eed415a6d227262b338b0d1f3803d83977341c0d3638fL
c = 0x2672cade2272f3024fd2d1984ea1b8e54809977e7a8c70a07e2560f39e6fcce0e292426e28df51492dec67d000d640f3e5b4c6c447845e70d1432a3c816a33da6a276b0baabd0111279c9f267a90333625425b1d73f1cdc254ded2ad54955914824fc99e65b3dea3e365cfb1dce6e025986b2485b6c13ca0ee73c2433cf0ca0265afe42cbf647b5c721a6e51514220bab8fcb9cff570a6922bceb12e9d61115357afe1705bda3c3f0b647ba37711c560b75841135198cc076d0a52c74f9802760c1f881887cc3e50b7e0ff36f0d9fa1bfc66dff717f032c066b555e315cb07e3df13774eaa70b18ea1bb3ea0fd1227d4bac84be2660552d3885c79815baef661L

Solution

We start by analysing the adlit function. All it does is flip the bits of its input, so algebraically, it is equivalent to: $adlit(x) = 2^l - 1 - x$ , where $l$ is the bit length of $x$ . We can see that this is used to generate the RSA primes; p is generated using getPrime, while q is generated from p using the adlit function. Therefore, we can construct a quadratic equation in p which we can easily solve:

\begin{aligned} q = 2^l - 1 - p + 31337 \implies n = pq &= p(2^l + 31336 - p) \cr &= 2^lp - 31336p - p^2 \end{aligned}

so we get $p^2 + (31336-2^l)p + n = 0$

We can guess/bruteforce $l$ based on the number of bits in $n$ . The point is that we now know the value of p and can therefore find q and $\phi(n)$ .

The next part of the problem is finding the public exponent e and decrypting the ciphertext properly. We notice that e must satisfy the condition e & (e+1) == 0, which is equivalent to saying that e is one less than a power of 2. We have no guarantee that $\gcd(e, \phi(n)) = 1$ (we can try it and we won't find the flag, so we know this most likely is not the case).

So we assume that $e$ and $\phi(n)$ are not coprime. Let $g = \gcd(e, \phi(n))$ . Then we can let

d \equiv (\frac{e}{g})^{-1} \pmod{\phi(n)}

(note that $\frac{e}{g}$ is an integer). $d$ should exist if $\gcd(\frac{e}{g}, \phi(n)) = 1$ . From this, we get

d\times\frac{e}{g} \equiv 1 \pmod{\phi(n)}

which implies

d\times\frac{e}{g} - 1 = k\phi(n) \\ \implies d = \frac{g}{e} (1 + k\phi(n))

Then we perform the calculation:

\begin{aligned} c^d &\equiv (m^e)^d \pmod n \cr &\equiv m^{ed} \pmod n \cr &\equiv m^{e\frac{g}{e}(1+k\phi(n))} \pmod n \cr &\equiv m^gm^{gk\phi(n)} \pmod n \cr &\equiv m^g(m^{gk})^{\phi(n)} \pmod n \cr &\equiv m^g \pmod n \end{aligned}

The last line follows from Euler's theorem

To find $m$ , we simply take the $g$ th root of $c^d \mod n$ .

Implementation:

n = 0x3ff77ad8783e006b6a2c9857f2f13a9d896297558e7c986c491e30c1a920512a0bad9f07c5569cf998fc35a3071de9d8b0f5ada4f8767b828e35044abce5dcf88f80d1c0a0b682605cce776a184e1bcb8118790fff92dc519d24f998a9c04faf43c434bef6c0fa39a3db7452dc07ccfced9271799f37d91d56b5f21c51651d6a9a41ee5a8af17a2f945fac2b1a0ea98bc70ef0f3e37371c9c7b6f90d3d811212fc80e0abcd5bbefe0c6edb3ca6845ded90677ccd8ff4de2c747b37265fc1250ba9aa89b4fd2bdfb4b4b72a7ff5b5ee67e81fd25027b6cb49db610ec60a05016e125ce0848f2c32bff33eed415a6d227262b338b0d1f3803d83977341c0d3638f
c = 4853661856538137406464034645906094152913630881745619406489837142176663842103161345726810796014324314815721708473241794990602572186090153630178109119000213575671689095484555801915325918814943882491883912939695163112247489821713563958885663470619257776668644302133854563122818923079903345131503071641985122522971974296790978299728014731290028116679328055229119298349730647468258800098306200875957662303051682669135862889528217767209821797678213735216907093405968738909692976414606843097568371074804700587363228896629583675336567001789346679322477777578268489982160639014959437742274169277165123841304006603130339784289

from gmpy2 import iroot, invert
from Crypto.Util.number import *

def quadratic(a, b, c):
    try:
        (d, t) = iroot(b*b - (4*a*c),2)
        if not t:
            return 0
        return ((-b-d)//(2*a), (-b+d)//(2*a))
    except:
        return 0


for l in range(10,2050):
    p_try = quadratic(1, -(2**l + 31336), n)
    if p_try:
        print('nbit=',l)
        p = p_try[1]
        break

q = n//p
assert(isPrime(int(q)))
assert(isPrime(int(p)))
assert(n == p*q)
print('p=',int(p))
print('q=',int(q))
for e in [int('1'*l, 2) for l in range(1, 50000)]:
    phi = (p-1)*(q-1)
    g = GCD(e, phi)
    if g == 1: continue
    print('trying with e bits:', e.bit_length(), 'gcd=', g)
    d = inverse(e//g, phi)
    m = pow(c, d, n)
    m, t = iroot(m, g)
    if not t: continue
    flag = long_to_bytes(m)
    if b'CCTF' in flag:
        print(flag)
        exit(0)

It turns out e was 3729 bits long!

The flag is: CCTF{it5_3a5y_l1k3_5uNd4y_MOrn1N9}