ASIS CTF 2020 | Dead Drop 1 - crypto-writeup-public

参考： https://www.sousse.love/post/deaddrop-asisctf2020/

#!/usr/bin/python

from Crypto.Util.number import *
import random
from flag import flag

p = 22883778425835100065427559392880895775739

flag_b = bin(bytes_to_long(flag))[2:]
l = len(flag_b)

enc = []
for _ in range(l):
    a = [random.randint(1, p - 1) for _ in range(l)]
    a_s = 1
    for i in range(l):
        a_s = a_s * a[i] ** int(flag_b[i]) % p
    enc.append([a, a_s])

f = open('flag.enc', 'w')
f.write(str(p) + '\n' + str(enc))
f.close()

$s_k = \prod_{i=0}^{n-1} a^{f_i}_{ki} \pmod p$

こういう $s_k$ が $n$ 個与えられる

discrete_logがとれたならこれは次のような式に変形可能

$\log_x(s_k) = \sum_{i=0}^{n-1} f_i \log_x(a_{ki}) \pmod{\phi(p)}$

$n$ 個変数があって $n$ 個式があるので、これなら解くことができる。

ところで、こんな見た目をしていながら $p$ は合成数

$A = \sum a_i \pmod{\phi(p)}$

で $p$ の約数であるような $q$ について

$A = \sum a_i \pmod{\phi(q)}$ も同様に成り立つ

ということで $p$ の素因数でdiscrete logを試してみると次のようになった。これは359個式があるうち、式の要素の全てがdiscrete log可能であるものの個数を数えたもの

19: 0/359
113: 16/359
2657: 313/359
6823: 340/359
587934254364063975369377416367: N/A

これを見ると、 $q = 6823$ を使えば、340 / 359 bit は復元できそうに見える。フラグが ASIS{...と始まるであろうことを考えれば、先頭の19bitを推測して 340変数の連立方程式をたてられそうに見える。

剰余連立方程式を行列で解く

from sage.all import *
import sys

enc = eval(open("flag.enc").read().strip().replace("L", "").split("\n")[1])

p = 22883778425835100065427559392880895775739
q = 6823

F = GF(q)
g = F.multiplicative_generator()

M = []
V = []

n = 340
known_bits = [1,0,0,0,0,0,1,0,1,0,1,0,0,1,1,0,1,0,0]

for en in enc:
    xs, xproduct = en

    try:
        logxs = []
        for x in xs[-n:]:
            logx = F(x).log(g)
            logxs.append(logx)

        xsum = F(xproduct).log(g)
        for i, k in enumerate(known_bits):
            xsum -= F(xs[i]).log(g) * k

        M.append(logxs)
        V.append(xsum)
    except ValueError:
        pass

M = matrix(Zmod(q-1), M)
V = vector(Zmod(q-1), V)

R = M.solve_right(V)
ans = 0
for b in known_bits + list(R):
    ans = ans * 2 + int(b)
print(bytes.fromhex(hex(ans)[2:]))

https://gist.github.com/enedil/a4ea63dbfef39a6a07af8c3afb030dc9