diceCTF 2021 | benaloh - crypto-writeup-public

from Crypto.Random.random import randrange
from Crypto.Util.number import getPrime, GCD

r = 17

def keygen():
    while True:
        p = getPrime(1024)
        a, b = divmod(p-1, r)
        if b == 0 and GCD(r, a) == 1:
            break
    while True:
        q = getPrime(1024)
        if GCD(r, q-1) == 1:
            break
    n = p*q
    phi = (p-1)*(q-1)//r
    y = 1
    while True:
        y = randrange(n)
        x = pow(y, phi, n)
        if x != 1:
            break
    log = {pow(x, i, n): i for i in range(r)}
    return (n, y), (n, phi, log)

def encrypt(data, pk):
    n, y = pk
    u = randrange(n)
    a = randrange(n)
    c = randrange(n)
    for m in data.hex():
        yield pow(y, int(m, 16), n) * pow(u, r, n) % n
        u = (a*u + c) % n

def decrypt(data, sk):
    n, phi, log = sk
    return bytes.fromhex(''.join(f'{log[pow(z, phi, n)]:x}' for z in data))

if __name__ == '__main__':
    from local import flag
    pk, sk = keygen()
    print(pk)
    for z in encrypt(flag, pk):
        print(z)

benaloh cryptosystem だがそちらが本質ではなく、平文 $m_i$ が $c_i = y^{m_i}u_i^r \mod n$

で $u_{i+1} = au_i + c \mod n$ と計算されているところが難しい

フラグはdice から始まるので $u_0^r, \dots, u_7^r$ はわかるが、 $a, u_i, c$ がわからないので難しい

ということで手がかりになるのは

$u_0^r \equiv u_0^r \equiv c_0y^{-m_0} \mod n$

$u_1^r \equiv (au_0 + c)^r \mod n$

$u_2^r \equiv (au_1 + c)^r \mod n$

$u_3^r \equiv (au_2 + c)^r \mod n$

…

という合同連立方程式のみ

共通根をもつ多変数多項式 $p_1(x), p_2(x), \dots, p_s(x)$ があるときの武器はグレブナー基底

グレブナー基底は、共通根を持つ多項式からなるイデアルを変形して得られる、等価なより性質の良いイデアル。グレブナー基底への変換にはBuchberger's algorithmなどがあるが、実装はsageにまかせておく

とにかく、今知っている多項式をグレブナー基底に放り込むことによって、次の形のイデアルに変換された

$\langle u_0^{r} + k_1, a + k_2, c + k_3u_0 \rangle$

（ここで $k_i$ は定数）

ここから、 $a = -k_2, u_0^{r} = -k_1, \frac{u_0}{c} = \frac{-1}{k_3}$ を得ることができる。これらの値からどうにかして $u_i^r$ を得ることができないだろうか

ここで、少し $u_2^r$ を展開してみる

$u_2^r \equiv (au_1 + c)^r \equiv (a(au_0 + c) + c)^r \equiv (a^2u_0 + ac + c)^r \equiv (a^2u_0 + c(a+ 1) \mod n$

では $u_3^r$ はどうか

$u_3^r \equiv (au_2 + c) ^r \equiv (a(a^2u_0 + ac + c) + c)^r \equiv (a^3u_0 + a^2c + ac + c)^r \equiv (a^3u_0 + c(a^2 + a + 1))^r \mod n$

すなわち一般に、 $u_i^r \equiv (a^iu_0 + (a^{i-1} + a^{i-2} + \cdots + 1)c)^r \mod n$

今、 $u_0^r$ は既知なので

$u_i^r \equiv u_0^r(a^i + (a^{i-1} + a^{i-2} + \cdots + 1)\frac{c}{u_0})^r \mod n$

と変形できる。なんとこの式の右辺はすべての値を知っているから、 $u_i^r$ を求めることができそう

import time

with open('out.txt') as f:
    n, y = eval(f.readline())
    F = Zmod(n)
    z = list(map(F, f.readlines()))

vs = []
for i, m in enumerate(b"dice".hex()):
    # u_i^r = c_i * y^{-m_i}
    ur = inverse_mod(pow(y, int(m, 16), n), n) * z[i] % n
    vs.append(ur)

r = 17
PR.<a, c, u0> = PolynomialRing(F)
p = u0
ps = []
for i, v in enumerate(vs):
    ps.append(p^r - v)
    p = a*p + c

# groebner basis
I = Ideal(ps)
print("[+] finding groebner basis...")
t1 = time.time()
B = I.groebner_basis()
t2 = time.time()
print("[+] done", t2 - t1)

u0_r = -B[0].constant_coefficient() # u_0^r
a = -B[1].constant_coefficient()    # a
c_u0 = -B[2][u0] / B[2][c] % n      # \frac{c}{u_0}

# u^r_i
ui_r = [u0_r]
asum = 0
for i in range(1, len(z)):
    asum += a^(i-1)
    ui_r.append(u0_r * (a^i + asum * c_u0)^r % n)


# m_i
mhex = []
for i in range(len(z)):
    # exaustive search m_i
    for x in range(16):
        if z[i] == pow(y, x, n) * ui_r[i] % n:
            mhex.append(x)
            break
    else:
        raise Exception("m_{} not found".format(i))


flag = 0
for h in mhex:
    flag = flag * 16 + h
print(bytes.fromhex(hex(flag)[2:]))

グレブナー基底の計算には大体2~3分