SECCON 2021 | Sign Wars - crypto-writeup-public

#seccon2021

from Crypto.Util.number import bytes_to_long, long_to_bytes
from Crypto.Util.Padding import pad
import random
from secret import msg1, msg2, flag

flag = pad(flag, 96)
flag1 = flag[:48]
flag2 = flag[48:]

# P-384 Curve
p = 39402006196394479212279040100143613805079739270465446667948293404245721771496870329047266088258938001861606973112319
a = -3
b = 27580193559959705877849011840389048093056905856361568521428707301988689241309860865136260764883745107765439761230575
curve = EllipticCurve(GF(p), [a, b])
order = 39402006196394479212279040100143613805079739270465446667946905279627659399113263569398956308152294913554433653942643
Z_n = GF(order)
gx = 26247035095799689268623156744566981891852923491109213387815615900925518854738050089022388053975719786650872476732087
gy = 8325710961489029985546751289520108179287853048861315594709205902480503199884419224438643760392947333078086511627871
G = curve(gx, gy)

for b in msg1:
    assert b >= 0x20 and b <= 0x7f
z1 = bytes_to_long(msg1)
assert z1 < 2^128

for b in msg2:
    assert b >= 0x20 and b <= 0x7f
z2 = bytes_to_long(msg2)
assert z2 < 2^384

# prequel trilogy
def sign_prequel():
    d = bytes_to_long(flag1)
    sigs = []
    for _ in range(80):
        # normal ECDSA. all bits of k are unknown.
        k1 = random.getrandbits(128)
        k2 = z1
        k3 = random.getrandbits(128)
        k = (k3 << 256) + (k2 << 128) + k1
        kG = k*G
        r, _ = kG.xy()
        r = Z_n(r)
        k = Z_n(k)
        s = (z1 + r*d) / k
        sigs.append((r,s))

    return sigs

# original trilogy
def sign_original():
    d = bytes_to_long(flag2)
    sigs = []
    for _ in range(3):
        # normal ECDSA
        k = random.getrandbits(384)
        kG = k*G
        r, _ = kG.xy()
        r = Z_n(r)
        k = Z_n(k)
        s = (z2 + r*d) / k
        sigs.append((r,s))

    return sigs


def sign():
    sigs1 = sign_prequel()
    print(sigs1)
    sigs2 = sign_original()
    print(sigs2)


if __name__ == "__main__":
    sign()

ECDSA だが $k_i = k_{i,1}*2^{256} + z *2^{128} + k_{i,3}$ となっている。2段階目はメルセンヌツイスターやるだけなので省略

式変形すると

$sk \equiv z + rd$

→ $k \equiv s^{-1}z + s^{-1}rd$

→ $(s^{-1} - 2^{128})z + s^{-1}rd - k_1*2^{256} - k_3 - tn = 0$

ということになる。このとき、 $N$ 個の式に対して未知変数は $3N + 2$ 個あることになる

これは少し重たいので $k_3 < 2^{128}$ から大きさのわかっている未知変数を直接求めないテクを利用して次のように変形する

$(s^{-1} - 2^{128})z + s^{-1}rd - k_1*2^{256} - tn = k_3 < 2^{128}$

これで未知変数を $2N + 2$ 個に減らせた。あとはInequality_Solving_with_CVPをやる

import ast


with open("./output.txt") as f:
    r, s = zip(*ast.literal_eval(f.readline()))
    r2, s2 = zip(*ast.literal_eval(f.readline()))


n = 39402006196394479212279040100143613805079739270465446667946905279627659399113263569398956308152294913554433653942643
rinv = [Integer(inverse_mod(r[i], n)) for i in range(len(r))]
sinv = [Integer(inverse_mod(s[i], n)) for i in range(len(s))]

N = 5
# (z, d, k_{1,1}, k_{1,2}, ..., t1, t2, ...)
M = matrix(ZZ, 2*N + 2, 2*N + 2)
M[0, 0] = 1
M[1, 1] = 1

for i in range(N):
    M[i+2,     0] = (sinv[i] - 2**128) % n
    M[i+2,     1] = (sinv[i]*r[i]) % n
    M[i+2,   i+2] = -2**256
    M[i+2, N+i+2] = -n

for i in range(N):
    M[N+i+2, i+2] = 1


lb = [     0, 0] + [     0 for _ in range(N)] + [     0 for _ in range(N)]
ub = [2**128, n] + [2**128 for _ in range(N)] + [2**128 for _ in range(N)]

load("./rkm.sage")
_, _ , res = solve(M.T, lb, ub)
print(res[0]) # z
print(res[1]) # d