GeekGame 2024 - 不经意的逆转

Published: at 05:41 AM

第一次做到以不经意传输（Oblivious transfer）为背景的题目，记录一下. 本题基于 RSA，类似的题目还有

题目代码

from Crypto.Util.number import bytes_to_long, getPrime
from secrets import randbelow
from hashlib import shake_128

flag1 = b"fake{flag-1}"
flag2 = b"fake{flag-2}"

def gen():
    e = 65537
    nbits = 1024
    p = getPrime(nbits)
    while p % e == 1:
        p = getPrime(nbits)
    q = getPrime(nbits)
    while q % e == 1:
        q = getPrime(nbits)
    n = p * q
    phi = (p - 1) * (q - 1)
    d = pow(e, -1, phi)
    return n, e, d, p, q

level = int(input("Please select the level[1/2]: "))
assert level in [1, 2]

n, e, d, p, q = gen()

if level == 1:
    f = bytes_to_long(flag1 + shake_128(flag1).digest(128-len(flag1)))
else:
    f = bytes_to_long(flag2 + shake_128(flag2).digest(128-len(flag2)))

x0 = randbelow(n)
x1 = randbelow(n)

print(f"{n = }")
print(f"{e = }")
print(f"{x0 = }")
print(f"{x1 = }")
print("Which message do you want to know?")

v = int(input("v = "))

if level == 1:
    v0 = (pow(v-x0, d, n) + pow(p+q, d, n) + f) % n
    v1 = (pow(v-x1, d, n) + pow(p-q, d, n) + f) % n
else:
    v0 = (pow(v-x0, d, n) + pow(p+q, d, n) + f) % n
    v1 = (pow(v-x1, d, n) + pow(p-q, d, n) + pow(f, -1, n)) % n

print()
print(f"{v0 = }")
print(f"{v1 = }")

Flag 1

{v0≡(v−x0)d+(p+q)d+f(modn)v1≡(v−x1)d+(p−q)d+f(modn)\begin{cases} v_0&\equiv{(v-x_0)}^d + {(p+q)}^d+f&\pmod{n}\\ v_1&\equiv{(v-x_1)}^d + {(p-q)}^d+f&\pmod{n} \end{cases}

两式都有 ff，考虑作差

v0−v1=(v−x0)d−(v−x1)d+(p+q)d−(p−q)d(modn)v_0-v_1 ={(v-x_0)}^d-{(v-x_1)}^d+{(p+q)}^d-{(p-q)}^d\pmod{n}

由二项式定理

(p+q)d−(p−q)d=2∑k odd(dk)pd−kqk=K⋅q{(p+q)}^d-{(p-q)}^d = 2 \sum_{k \text{ odd}} \binom{d}{k} p^{d-k} q^k = K\cdot q

把模数换到 qq 下有

v0−v1=(v−x0)d−(v−x1)d(modq)v_0-v_1 ={(v-x_0)}^d-{(v-x_1)}^d\pmod{q}

此时考虑 vv 的取值，让右侧尽量简单，尝试

(v−x0)d=−(v−x1)d{(v-x_0)}^d =-{(v-x_1)}^d

由于 dd 为奇数，那么 v−x0=−(v−x1)v-x_0=-(v-x_1)，即 v=x0+x12v=\frac{x_0+x_1}{2}.

此时有

v0−v1=2(v−x0)d(modq)(v0−v1)e=2e(v−x0)(modq)(v0−v1)e=2e(v−x0)+K′⋅qK′⋅q=(v0−v1)e−2e(v−x0)\begin{align} v_0-v_1&= 2{(v-x_0)}^d\pmod{q}\\ {(v_0-v_1)}^e&= 2^e(v-x_0)\pmod{q}\\ {(v_0-v_1)}^e&= 2^e(v-x_0)+K'\cdot q\\ K'\cdot q&={(v_0-v_1)}^e-2^e(v-x_0) \end{align}

计算 GCD(K′⋅q,n)\text{GCD}(K'\cdot q, n) 即分解 nn. 接下来不难求得 ff.

Flag 2

{v0≡(v−x0)d+(p+q)d+f(modn)v1≡(v−x1)d+(p−q)d+f−1(modn)\begin{cases} v_0&\equiv{(v-x_0)}^d + {(p+q)}^d+f&\pmod{n}\\ v_1&\equiv{(v-x_1)}^d + {(p-q)}^d+f^{-1}&\pmod{n} \end{cases}

仍取 v=x0+x12v=\frac{x_0+x_1}{2}，有

v0+v1≡(v−x0)d+(v−x1)d+(p+q)d+(p−q)d+f+f−1(modn)v0+v1≡(v−x0)d+(−1)d(v−x0)d+(p+q)d+(p−q)d+f+f−1(modn)v0+v1≡(p+q)d+(p−q)d+f+f−1(modn)\begin{align} v_0+v_1&\equiv {(v-x_0)}^d+{(v-x_1)}^d+{(p+q)}^d+{(p-q)}^d+f+f^{-1}&\pmod{n}\\ v_0+v_1&\equiv {(v-x_0)}^d+(-1)^d{(v-x_0)}^d+{(p+q)}^d+{(p-q)}^d+f+f^{-1}&\pmod{n}\\ v_0+v_1&\equiv {(p+q)}^d+{(p-q)}^d+f+f^{-1}&\pmod{n}\\ \end{align}

由二项式定理

(p+q)d+(p−q)d=K⋅p{(p+q)}^d+{(p-q)}^d = K\cdot p

把模数换到 pp 下有

v0+v1≡f+f−1(modp)f2−(v0+v1)f+1≡0(modp)\begin{align} v_0+v_1&\equiv f+f^{-1}&\pmod{p}\\ f^2-(v_0+v_1)f+1&\equiv 0&\pmod{p}\\ \end{align}

这里 ff 是 1024-bit 的，相对于 pp 不够小. 可以多取几组数据构成方程组

{f2−g0⋅f+1≡0(modp0)f2−g1⋅f+1≡0(modp1)⋯f2−g2⋅f+1≡0(modp5)\begin{cases} f^2-g_0\cdot f+1&\equiv 0&\pmod{p_0}\\ f^2-g_1\cdot f+1&\equiv 0&\pmod{p_1}\\ &\cdots\\ f^2-g_2\cdot f+1&\equiv 0&\pmod{p_5}\\ \end{cases}

应用多项式的中国剩余定理得到

f2−g⋅f+1≡0(modp0p1⋯p5)(1)f^2-g\cdot f+1\equiv 0\pmod{p_0p_1\cdots p_5}\tag 1

注意这里的模数实际上我们是不知道的，不过 CopperSmith 算法的扩展 允许我们在模数未知的情况下求小根，也就是对 (2)(2) 式应用 CopperSmith

f2−g⋅f+1≡0(modn0n1⋯n5)(2)f^2-g\cdot f+1\equiv 0\pmod{n_0n_1\cdots n_5}\tag 2

能够求出 (1)(1) 式的小根，注意这里令 β=16\beta=\frac{1}{6}.

这种解「模单变量多项式方程组」的问题被称为 SMUPE-problem，N1CTF 2022-babyecc 也是类似的姿势～

Previous Post
差分分析学习（一）
Next Post
Hello, world!