2022-西湖论剑-wp-crypto

今年西湖论剑马上就要开始了，为了准备比赛，复现一下昨年的题目。

LockByLock

题目描述：

Lock Lock Lock…

题目：

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

class Lock:
    def __init__(self, p, q) -> None:
        while True:
            self.p = p
            self.q = q
            self.n = self.p * self.q
            self.e = random.randint(10**14, 10**15)
            
            if gcd(self.e, (self.p-1)*(self.q-1)) == 1:
                self.d = invert(self.e, (self.p-1)*(self.q-1))
                break
    
    def lock(self, message: int) -> int:
        assert 1 < message < self.n
        return powmod(message, self.e, self.n)
    
    def unlock(self, cipher: int) -> int:
        assert 1 < cipher < self.n
        return powmod(cipher, self.d, self.n)


def secureProcedure(A, B):
    global flag
    flag = bytes_to_long(flag)
    print('Alice: lock lock lock lock unlock')
    msg1 = A.lock(flag)
    print(f'Alice: locked msg1 = {msg1}')
    print('Alice: lock lock lock lock')
    
    print('Bob: lock unlock lock lock')
    msg2 = B.lock(msg1)
    print(f'Bob: locked msg2 = {msg2}')
    print('Bob: lock lock lock lock')
    
    print('Alice: unlock unlock unlock...')
    msg3 = A.unlock(msg2)
    print(f'Alice: unlocked msg3 = {msg3}')
    print('Alice: lock lock lock lock')
    
    print('Bob: unlock unlock unlock...')
    msg = B.unlock(msg3)
    
    assert msg == flag
    print('Bob: lock lock unlock')
    print('Bob: lock by lock, lock lock right, unlock unlock unlock...')
    print('Alice: right right, lock lock unlock')
    print('Bob: lock lock lock, flag lock lock lock.')
    print('Alice: lock unlock lock lock, unlock lock lock')
    print('Bob: lock lock!')
    
    
def proxyProcedure(A, B):
    print('Agent: lock lock, lock lock lock, unlock lock lock right')
    print('Alice: lock!')
    print('Bob: lock lock, unlock lock!')
    omsg = int(input())
    
    print('Alice: lock lock lock lock unlock')
    msg1 = A.lock(omsg)
    print(f'Alice: locked msg1 = {msg1}')
    print('Alice: lock lock lock lock')
    
    print('Bob: lock unlock lock lock')
    msg2 = B.lock(msg1)
    print(f'Bob: locked msg2 = {msg2}')
    print('Bob: lock lock lock lock')
    
    print('Alice: unlock unlock unlock...')
    msg3 = A.unlock(msg2)
    print(f'Alice: unlocked msg3 = {msg3}')
    print('Alice: lock lock lock lock')
    
    print('Bob: unlock unlock unlock...')
    msg = B.unlock(msg3)
    
    
    assert msg == omsg
    print('Bob: lock, lock, locked lock lock lock unlock')
    print('Bob: lock by lock, lock lock right, lock unlock unlock unlock...')
    print('Alice: right right, locked lock lock lock unlock')
    print('Bob: lock lock!')
    

def main():
    p = getPrime(1024)
    q = getPrime(1024)
    AliceLock = Lock(p, q)
    BobLock = Lock(p, q)
    
    secureProcedure(AliceLock, BobLock)
    
    try:
        proxyProcedure(AliceLock, BobLock)
        proxyProcedure(AliceLock, BobLock)
        print('Lock: lock lock lock, unlock lock lock lock, lock lock unlock lock unlock lock, lock.')
    except Exception:
        print('lock unlock, lock locked, unlocked lock')


if __name__ == '__main__':
    main()

题目比较长，但流程并不复杂。首先生成两个1024bit的素数p、q，然后以此为基础，生成两个Lock类AliceLock与BobLock，Lock类中的数据包含以下RSA密钥对，并提供加密和解密操作：

$$AliceLock:(n,e_1),(p,q,d_1)$$ $$BobLock:(n,e_2),(p,q,d_2)$$

也就是说，两者只有加密指数e和解密指数d有区别，而模数n是完全一样的。同时e的数量级是10^14-10^15之间。

至此，题目完成了数据的准备工作。但是需要注意的是，我们不知道其中任何数据，包括公钥中的模数n与加密指数e。

然后就进入题目加密环节，首先，靶机会传送给我们：

$$m^{e_1},\quad m^{e_1e_2},\quad m^{e_2} \quad \quad(mod\;n)$$

m是flag值。然后，我们拥有两次机会，可以给靶机输入a，然后获得：

$$a^{e_1},\quad a^{e_1e_2},\quad a^{e_2} \quad \quad(mod\;n)$$

要想办法以此解出flag值。

那么首先就要想办法还原模数n，这一点很简单，我们只需要利用这两次机会，分别传入2和4，就能获得：

$$2^{e_1},\quad 2^{e_1e_2},\quad 2^{e_2} \quad \quad(mod\;n)$$ $$4^{e_1},\quad 4^{e_1e_2},\quad 4^{e_2} \quad \quad(mod\;n)$$

然后我们就可以借助2和4的平方关系，求解下面几个式子的GCD，并去除小因子得到n：

$$(2^{e_1})^2-4^{e_1},\quad (2^{e_1e_2})^2-4^{e_1e_2},\quad (2^{e_2})^2-4^{e_2}$$

得到n过后就要想办法解出m，而e1、e2两个不同的加密指数很明显在提示共模，因此下一步就是要把e1、e2分别求出来。而突破点在于e1、e2的数量级在10^14-10^15之间，大约2^50左右，是可以用bsgs或Pollard’s kangaroo algorithm之类的方法求DLP的。而可供求解的组也不少，比如：

$$2,2^{e_1}$$ $$4,4^{e_1}$$ $$m^{e_1},m^{e_1e_2}$$ $$......$$

但是直觉上来说，肯定是求解以2为底的较好。但看别人wp和自己尝试确实都是求以4为底的更快一些，也许是因为阶的原因。

求出e1、e2后就是简单共模。

exp：

from Pwn4Sage.pwn import *
from Crypto.Util.number import *
from gmpy2 import *

r = remote("node4.anna.nssctf.cn",28184)

#part1 get msg about flag
r.recvuntil(b"Alice: locked msg1 = ")
m1 = int(r.recvline().strip().decode())
r.recvuntil(b"Bob: locked msg2 = ")
m12 = int(r.recvline().strip().decode())
r.recvuntil(b"Alice: unlocked msg3 = ")
m2 = int(r.recvline().strip().decode())

#part2 get n,send 2 and 4
r.sendline(b"2")
r.recvuntil(b"Alice: locked msg1 = ")
s1 = int(r.recvline().strip().decode())
r.recvuntil(b"Bob: locked msg2 = ")
s12 = int(r.recvline().strip().decode())
r.recvuntil(b"Alice: unlocked msg3 = ")
s2 = int(r.recvline().strip().decode())

r.sendline(b"4")
r.recvuntil(b"Alice: locked msg1 = ")
t1 = int(r.recvline().strip().decode())
r.recvuntil(b"Bob: locked msg2 = ")
t12 = int(r.recvline().strip().decode())
r.recvuntil(b"Alice: unlocked msg3 = ")
t2 = int(r.recvline().strip().decode())

def clear_small_factors(num):
    for i in range(2,10000):
        while(num % i == 0):
            num //= i
    return num
n = clear_small_factors(GCD(s1^2-t1,s2^2-t2))

#part3 DLP
F = Zmod(n)
e1 = discrete_log_lambda(F(t1),F(4),(10^14, 10^15))
e2 = discrete_log_lambda(F(t2),F(4),(10^14, 10^15))

d,x,y = gcdext(e1,e2)
flag = pow(m1,x,n)*pow(m2,y,n) % n
print(long_to_bytes(int(flag)))

#NSSCTF{9be90567-ffcd-400a-971f-b906f5d73706}

MyErrorLearn

题目描述：

Reach Learn With Error. Reach My Xenny Oracle.

题目：

from Crypto.Util.number import *
import random, os
from gmpy2 import *
flag = os.getenv('DASFLAG')

p = random.getrandbits(1024)

print('> mod =', p)
secret = random.randint(1, p-1)

def XennyOracle():
    r = getPrime(512)
    d = invert(secret+r, p) - getPrime(246)
    print('> r =', r)
    print('> d =', d)

def task():
    for _ in range(3):
        op = int(input())
        if op == 1:
            XennyOracle()
        elif op == 2:
            ss = int(input())

            if ss == secret:
                print('flag: ', flag)

try:
    task()
except Exception:
    print("Error. try again.")

很简洁的题目(接下来的几个题目都是这个风格，非常喜欢)。题目首先生成一个1024bit的随机数p，并且生成一个小于p的secret值，然后进入一个最多三次的交互，每次交互可以：

• 输入1，可以进入XennyOracle，获取一组数据
• 输入2，可以核验secret值，如果输入值等于secret则得到flag

那么也就是要输入两次1，用获取的两组数据解出secret，然后输入2获得flag。那么接下来就看看 XennyOracle究竟返回什么样的数据供使用。可以发现，他先生成512bit的素数r，然后按如下式子计算出d：

$$d = (secret+r)^{-1} -e \quad(mod\;p)$$

并返回给我们r和d的值，其中，e是一个246bit的素数。

由于我们有两组数据，所以我们可以列出如下式子：

$$(d_0 + e_0)(secret+r_0) = 1 \quad(mod\;p)$$ $$(d_1 + e_1)(secret+r_1) = 1 \quad(mod\;p)$$

而突破点就在于，两个e，也就是error，都是246bit的数量级，相较于p的1024bit来说都是小量。因此，如果联立两个方程消去secret后，就可以构造出一个可以二元copper的式子。具体来说消元过程如下。

首先把secret前的系数配相同：

$$(d_1 + e_1)(d_0 + e_0)(secret+r_0) = (d_1 + e_1) \quad(mod\;p)$$ $$(d_0 + e_0)(d_1 + e_1)(secret+r_1) = (d_0 + e_0) \quad(mod\;p)$$

然后简单作差就可以消去secret：

$$(r_0-r_1)(d_1 + e_1)(d_0 + e_0)-(d_1 + e_1)+(d_0 + e_0) = 0\quad(mod\;p)$$

这就是二元copper的式子了，求出e1、e2后代入任意一个式子就能求出secret，从而获得flag。

但是由于题目p的生成方式是getrandbits(1024)，所以p并不一定是个素数，因此求逆的操作不一定能成功，所以靶机返回”Error. try again.”也是常有的事，多交互几次就好。

exp：

from Pwn4Sage.pwn import *
from Crypto.Util.number import *
import itertools

#part1 get number
sh = remote("node4.anna.nssctf.cn",28597)
sh.recvuntil(b"> mod =")
p = int(sh.recvline().strip().decode())
r = []
d = []
for i in range(2):
    sh.sendline(b"1")
    sh.recvuntil(b"> r =")
    r.append(int(sh.recvline().strip().decode()))
    sh.recvuntil(b"> d =")
    d.append(int(sh.recvline().strip().decode()))

#part2 bivariate copper
def small_roots(f, bounds, m=1, d=None):
    if not d:
        d = f.degree()
    R = f.base_ring()
    N = R.cardinality()
    f /= f.coefficients().pop(0)
    f = f.change_ring(ZZ)
    G = Sequence([], f.parent())
    for i in range(m + 1):
        base = N ^ (m - i) * f ^ i
        for shifts in itertools.product(range(d), repeat=f.nvariables()):
            g = base * prod(map(power, f.variables(), shifts))
            G.append(g)
    B, monomials = G.coefficient_matrix()
    monomials = vector(monomials)
    factors = [monomial(*bounds) for monomial in monomials]
    for i, factor in enumerate(factors):
        B.rescale_col(i, factor)
    B = B.dense_matrix().LLL()
    B = B.change_ring(QQ)
    for i, factor in enumerate(factors):
        B.rescale_col(i, 1 / factor)
    H = Sequence([], f.parent().change_ring(QQ))
    for h in filter(None, B * monomials):
        H.append(h)
        I = H.ideal()
        if I.dimension() == -1:
            H.pop()
        elif I.dimension() == 0:
            roots = []
            for root in I.variety(ring=ZZ):
                root = tuple(R(root[var]) for var in f.variables())
                roots.append(root)
            return roots
    return []

PR.<e0,e1>=Zmod(p)[]
f = (r[0]-r[1])*(d[0]+e0)*(d[1]+e1) + d[0] + e0 - d[1] - e1
e0,e1 = small_roots(f,bounds=(2^246,2^246))[0]

#part3 get flag
secret = (inverse(int(d[0]+e0),p)-r[0]) % p
sh.sendline(b"2")
sh.sendline(str(secret).encode())
sh.recvline()
sh.recvline()
print(sh.recvline())

#NSSCTF{87cfab12-9e93-4e8d-948b-21e2b4433696}

MyErrorLearnTwice

题目描述：

Cross my XennyOracle again.

题目：

from Crypto.Util.number import *
import random, os
from gmpy2 import *
flag = os.getenv('DASFLAG')

p = random.getrandbits(1024)

print('> mod =', p)
secret = random.randint(1, p-1)

def XennyOracle():
    r = getPrime(512)
    d = invert(secret+r, p) - getPrime(328)
    print('> r =', r)
    print('> d =', d)

def task():
    for _ in range(16):
        op = int(input())
        if op == 1:
            XennyOracle()
        elif op == 2:
            ss = int(input())

            if ss == secret:
                print('flag: ', flag)

try:
    task()
except Exception:
    print("Error. try again.")

这个题目就是上一个题目的进阶，他与上一个题目的区别在于：

• error从246bit提升到了328bit
• 可以获得的数据从最多2组变成了最多15组

可以想见这个数量级直接二元copper肯定不行了，但是328bit相较于1024bit来说，e是小量的这一性质依然没有变。而小量+多组数据的形式很容易就想到用格来解决。我们记获得的数据为 $r_i,d_i (0 \le i \le 14)$ ，那么用类似HNP的构造方式，将1-14组数据与第0组数据，做上一题一样的消元，得到14个如下形式的模等式：

$$(r_0-r_i)(d_i + e_i)(d_0 + e_0)-(d_i + e_i)+(d_0 + e_0) = 0\quad(mod\;p)$$

其中ei、e0均是未知小量，为了更清楚地构造出格的结构，需要合并同类项得到对应系数：

$$(r_0-r_i)e_0e_i + (d_i(r_0-r_i)+1)e_0 + (d_0(r_0-r_i)-1)e_i + d_0d_i(r_0-r_i) + d_0-d_i = 0 \quad(mod\;p)$$

为了看上去方便，把其中所有系数分别记作：

$$A_i = r_0-r_i$$ $$B_i = d_i(r_0-r_i)+1$$ $$C_i = d_0(r_0-r_i)-1$$ $$D_i = d_0d_i(r_0-r_i) + d_0-d_i$$

那么整个式子就变成：

$$A_ie_0e_i + B_ie_0 + C_ie_i + D_i = 0 \quad(mod\;p)$$

写成等式形式：

$$A_ie_0e_i + B_ie_0 + C_ie_i + D_i +k_ip = 0$$

然后用这个式子去造格就可以了，造出来的形式是：

$$\left(\begin{matrix} 1 & &&&&&& &&&A_1 & \\ &1 &&&&&& &&& &A_2 \\ & &&&&&& &&& &&... \\ & &&...&&&& && &&&&A_n \\ & & &&&& && &&B_1&B_2&...&B_n \\ & & &&&...&&&& &C_1&&& \\ & & &&&&&& &&&C_2&& \\ & & &&&&&...&& &&&...& \\ & & &&&&&& 1&&&&&C_n \\ & & &&&&&& & 1&D_1&D_2&...&D_n \\ & & &&&&&& &&p&&& \\ & & &&&&&& &&&p&& \\ & & &&&&&& &&&&...& \\ & & &&&&&& &&&&&p \\ \end{matrix} \right)$$

这个格具有如下线性关系：

$$(e_0e_1,e_0e_2,...e_0e_n,e_0,e_1,...e_n,1,k_1,k_2,...k_n) \left(\begin{matrix} 1 & &&&&&& &&&A_1 & \\ &1 &&&&&& &&& &A_2 \\ & &&&&&& &&& &&... \\ & &&...&&&& && &&&&A_n \\ & & &&&& && &&B_1&B_2&...&B_n \\ & & &&&...&&&& &C_1&&& \\ & & &&&&&& &&&C_2&& \\ & & &&&&&...&& &&&...& \\ & & &&&&&& 1&&&&&C_n \\ & & &&&&&& & 1&D_1&D_2&...&D_n \\ & & &&&&&& &&p&&& \\ & & &&&&&& &&&p&& \\ & & &&&&&& &&&&...& \\ & & &&&&&& &&&&&p \\ \end{matrix} \right) = (e_0e_1,e_0e_2,...e_0e_n,e_0,e_1,...e_n,1,0,0,...,0)$$

然后就是配平系数，使规约出来的向量数量级相当，同时可以在最后n列乘上大系数T保证规约出0。LLL得到目标向量后就能得到所有ei，仍然是代入任意一个式子就可以算出secret，并发送给靶机得到flag。

p不是素数导致逆元可能不存在的问题依然存在，所以可能还是要多交互几次。

exp：

from Pwn4Sage.pwn import *
from Crypto.Util.number import *
import itertools

#part1 get number
sh = remote("node4.anna.nssctf.cn",28544)
sh.recvuntil(b"> mod =")
p = int(sh.recvline().strip().decode())
r = []
d = []
enum = 15
for i in range(enum):
    sh.sendline(b"1")
    sh.recvuntil(b"> r =")
    r.append(int(sh.recvline().strip().decode()))
    sh.recvuntil(b"> d =")
    d.append(int(sh.recvline().strip().decode()))
A = [r[0]-r[i] for i in range(1,enum)]
B = [d[i]*(r[0]-r[i])+1 for i in range(1,enum)]
C = [d[0]*(r[0]-r[i])-1 for i in range(1,enum)]
D = [d[0]*d[i]*(r[0]-r[i])+d[0]-d[i] for i in range(1,enum)]

#part2 use Lattice
T = 2^1000
L = Matrix(ZZ,3*enum-1,3*enum-1)
for i in range(enum-1):
    L[i,i] = 1
    L[i,-(enum-1)+i] = A[i]*T

    L[enum-1,-(enum-1)+i] = B[i]*T
    L[i+enum,-(enum-1)+i] = C[i]*T

    L[2*enum-1,-(enum-1)+i] = D[i]*T
    L[i+2*enum,-(enum-1)+i] = p*T
for i in range(enum):
    L[i+enum-1,i+enum-1] = 2^328
L[2*enum-1,2*enum-1] = 2^(328*2)

res = L.LLL()[0]
#e0 = int(res[14])//(2^328)
e0 = GCD(res[0],res[14])

#part3 get flag
secret = (inverse(int(d[0]+e0),p)-r[0]) % p
sh.sendline(b"2")
sh.sendline(str(secret).encode())
sh.recvline()
sh.recvline()
print(sh.recvline())

#NSSCTF{d15f053f-8bf0-4dc2-a299-017841518c7e}

MyCurveErrorLearn

题目描述：

Reach My XennyOracle base elliptic curve

题目：

from Crypto.Util.number import *
import os

flag = os.getenv('FLAG')

p = getPrime(1024)
a = getPrime(200)
b = getPrime(200)
E = EllipticCurve(GF(p), [a, b])
R = E.random_element()
P = E.random_element()

print('> mod =', p)
print('> a =', a)
print('> b =', b)
print(f'> R = ({R[0]}, {R[1]})', )

def XennyOracle(t):
    O = P + t*R
    return int(O[0]) - getPrime(163)


def task():
    for _ in range(30):
        op = int(input())
        if op == 1:
            XennyOracle(int(input()))
        elif op == 2:
            ss = int(input())

            if ss == P[0]:
                print('flag: ', flag)

try:
    task()
except Exception:
    print("Error. try again.")

仍然与前面的题目很像，只是背景换成了曲线。

题目首先会随机生成一条椭圆曲线，并发送给我们曲线的所有参数：

$$y^2 = x^3 + ax + b \quad(mod \;p)$$

然后从曲线上取两个随机点R、P，并给出我们R的坐标，至此数据准备工作就全部结束，进入交互部分。

在交互部分，我们有最多30次交互机会，每一次仍然有两个选择：

• 输入1，进入XennyOracle
• 输入2，可以核验P点的横坐标，如果输入值与P横坐标相等则得到flag

目的也很明确，用前面最多29组数据来求出P的横坐标，从而获取flag。那么接下来看看这题里的XennyOracle又做了什么。每次进入XennyOracle，我们可以输入一个值t，靶机会计算一个O点：

$$O = P + tR$$

但是靶机最终返回的是：

$$h = x(O) - e$$

其中x(O)代表取O的横坐标，e是一个163bit的小量。

做了上一个题目也有一些经验，毕竟椭圆曲线其实本质上也就是模p下的一个多项式，所以这题依然是小量+多组数据的形式，肯定是要用多项式造格来解。而很自然地会先想到发送0-28给靶机，得到：

$$h_t = x(P + tR) - e_t \quad(0 \le t \le 28)$$

我们把点tR记作Qt，由于t的值以及R点我们都有，所以Qt点的坐标我们也知道，那么上式可以写作：

$$h_t = x(P + Q_t) - e_t \quad(0 \le t \le 28)$$

那么接下来就是根据点加法的计算表达式来构造等式：

$$k = \frac{y_P-y_Q}{x_P-x_Q} \quad(mod\;p)$$ $$x_O = k^2 - x_P - x_Q \quad(mod\;p)$$

即：

$$x_O = (\frac{y_P-y_Q}{x_P-x_Q})^2 - x_P - x_Q \quad(mod\;p)$$

然后移项转化一下就能得到关于yP,xP,xO的多项式。

但是这样显然有冗余项，因为一个点在曲线上的横纵坐标是有椭圆曲线方程作支撑的，yP显然可以用xP表示出来。同时，这样构造多项式，不同的项会很多，难以构造一个简洁明了的格。

然后就想到椭圆曲线上点有如下性质：

$$tR = Q_t = (x_Q,y_Q)$$ $$-tR = Q_{-t} = (x_Q,-y_Q)$$

也就是说，两个乘数互为相反数的倍点，其横坐标相等而纵坐标相反，而这就为消去纵坐标提供了一种便利。我们可以考虑按如下形式发送t：

• 第一次发送0，得到的其实就是受干扰的P点横坐标
• 后面依次成对发送不同的t，-t，每次得到一对：

$$h_t = x(P + Q_t) - e_t$$ $$h_{-t} = x(P + Q_{-t}) - e_{-t}$$

对于得到的每一对ht、h(-t)，我们把error移到左边：

$$h_t + e_t = x(P + Q_t)$$ $$h_{-t} + e_{-t} = x(P + Q_{-t})$$

那么两式相加，由于有刚才提到的横坐标相等而纵坐标相反这一特点，所以对于等式右侧而言就是：

$$x(P + Q_t) + x(P + Q_{-t}) = (\frac{y_P-y_{Q_t}}{x_P-x_{Q_t}})^2 - x_P - x_{Q_t} + (\frac{y_P+y_{Q_t}}{x_P-x_{Q_t}})^2 - x_P - x_{Q_t} \quad(mod\;p)$$

即：

$$x(P + Q_t) + x(P + Q_{-t}) = (\frac{y_P-y_{Q_t}}{x_P-x_{Q_t}})^2 + (\frac{y_P+y_{Q_t}}{x_P-x_{Q_t}})^2 - 2x_P - 2x_{Q_t} \quad(mod\;p)$$

这样一来，化简后分子就只留有yP和yQ的二次形式，就可以用椭圆曲线的方程将他们完全转化掉，变成只关于横坐标的等式：

$$x(P + Q_t) + x(P + Q_{-t}) = 2(\frac{x_{Q_t}x_P^2 + (a+x_{Q_t}^2)x_P + ax_{Q_t} + 2b}{(x_P-x_{Q_t})^2}) \quad(mod\;p)$$

也就是：

$$h_t + e_t + h_{-t} + e_{-t} = 2(\frac{x_{Q_t}x_P^2 + (a+x_{Q_t}^2)x_P + ax_{Q_t} + 2b}{(x_P-x_{Q_t})^2}) \quad(mod\;p)$$

而对于xP，我们在第一次发送0时，也得到了一组关于他的等式：

$$x_P = h_0 + e_0$$

把这个代入上面的xP中就得到：

$$h_t + e_t + h_{-t} + e_{-t} = 2(\frac{x_{Q_t}(h_0 + e_0)^2 + (a+x_{Q_t}^2)(h_0 + e_0) + ax_{Q_t} + 2b}{((h_0 + e_0)-x_{Q_t})^2}) \quad(mod\;p)$$

这样未知量就只剩下所有e了，化简之后合并同类项，就得到关于所有e的等式，简化出来的形式是：

$$e_o^2e_i + A_ie_0^2 + A_{0,i}e_0e_i + B_ie_0 + B_{0,i}e_i + C_i + k_ip = 0$$

这也是题目论文里的构造(其实上面的题目也是有论文的，但是其实这些题目要自己构造出格，也并不算极其困难的事情，只是化简过程比较繁琐且易错)。其中各项系数为：

A = [h[i] - 2*xQ[i] for i in range(1,n)]
A0 = [2*(h[0]-xQ[i]) for i in range(1,n)]
B = [2*(h[i]*(h[0]-xQ[i])-2*h[0]*xQ[i]-a-xQ[i]^2) for i in range(1,n)]
B0 = [(h[0]-xQ[i])^2 for i in range(1,n)]
C = [h[i]*(h[0]-xQ[i])^2-2*((h[0]^2+a)*xQ[i]+(a+xQ[i]^2)*h[0]+2*b) for i in range(1,n)]

然后就可以构造一个如下形式的格(构造的大体思路可以说与上一个题目完全相同)：

$$\left(\begin{matrix} 1&& & &&&& && &&C_1&C_2&...&C_n \\ &1& & &&&& && &&B_1&B_2&...&B_n \\ & &&&&&&& &&&B_{0,1} && \\ & &&...&&&&& &&& &B_{0,2}& \\ & &&&&&&& &&& &&... \\ & &&&&...&&& &&& &&&B_{0,n} \\ & && &&&& && &&A_1&A_2&...&A_n \\ & &&&&&&...& &&&A_{0,1} && \\ & &&&&&&& &&& &A_{0,2}& \\ & &&&&&&& &...&& &&... \\ & &&&&&&& &&1& &&&A_{0,n} \\ & && &&&&&& &&p&&& \\ & && &&&&&& &&&p&& \\ & && &&&&&& &&&&...& \\ & && &&&&&& &&&&&p \\ \end{matrix} \right)$$

这个格具有如下线性关系：

$$(1,e_0,e_1,...e_n,e_0^2,e_0e_1,...e_0e_n,k_1,k_2,...k_n) \left(\begin{matrix} 1&& & &&&& && &&C_1&C_2&...&C_n \\ &1& & &&&& && &&B_1&B_2&...&B_n \\ & &&&&&&& &&&B_{0,1} && \\ & &&...&&&&& &&& &B_{0,2}& \\ & &&&&&&& &&& &&... \\ & &&&&...&&& &&& &&&B_{0,n} \\ & && &&&& && &&A_1&A_2&...&A_n \\ & &&&&&&...& &&&A_{0,1} && \\ & &&&&&&& &&& &A_{0,2}& \\ & &&&&&&& &...&& &&... \\ & &&&&&&& &&1& &&&A_{0,n} \\ & && &&&&&& &&p&&& \\ & && &&&&&& &&&p&& \\ & && &&&&&& &&&&...& \\ & && &&&&&& &&&&&p \\ \end{matrix} \right) = (1,e_0,e_1,...e_n,e_0^2,e_0e_1,...e_0e_n,e_0^2e_1,e_0^2e_2,...e_0^2e_n)$$

当然，这次要给前面2n+3列配对应系数，使目标向量中各项数量级相当。规约出目标向量后，用其中的e0加上h0就得到P的正确横坐标，发送给靶机就能得到flag了。

exp：

from Pwn4Sage.pwn import *
from Crypto.Util.number import *

#part1 get number
sh = remote("node4.anna.nssctf.cn",28005)
sh.recvuntil(b"> mod =")
p = int(sh.recvline().strip().decode())
sh.recvuntil(b"> a =")
a = int(sh.recvline().strip().decode())
sh.recvuntil(b"> b =")
b = int(sh.recvline().strip().decode())
sh.recvuntil(b"> R =")
R = eval(sh.recvline().strip().decode())
E = EllipticCurve(GF(p), [a, b])
R = E(R)

#part2 send t and -t to construct poly
h = []
xQ = [0]
#first get error_P
sh.sendline(b"1")
sh.sendline(b"0")
h.append(int(sh.recvline().strip().decode()))

n = 15
for t in range(1,n):
    sh.sendline(b"1")
    sh.sendline(str(t).encode())
    h1 = int(sh.recvline().strip().decode())
    sh.sendline(b"1")
    sh.sendline(str(-t).encode())
    h2 = int(sh.recvline().strip().decode())
    h.append(h1+h2)

    xQ.append(int((t*R)[0]))

A = [h[i] - 2*xQ[i] for i in range(1,n)]
A0 = [2*(h[0]-xQ[i]) for i in range(1,n)]
B = [2*(h[i]*(h[0]-xQ[i])-2*h[0]*xQ[i]-a-xQ[i]^2) for i in range(1,n)]
B0 = [(h[0]-xQ[i])^2 for i in range(1,n)]
C = [h[i]*(h[0]-xQ[i])^2-2*((h[0]^2+a)*xQ[i]+(a+xQ[i]^2)*h[0]+2*b) for i in range(1,n)]

#part3 use poly to get Lattice and LLL
delta = 2^163
n = n-1
L = Matrix(ZZ,3*n+3,3*n+3)

L[0,0] = delta^3
for i in range(n+1):
    L[i+1,i+1] = delta^2
for i in range(n+1):
    L[i+n+2,i+n+2] = delta
for i in range(n):
    L[i+2*n+3,i+2*n+3] = p

for i in range(n):
    L[0,i+2*n+3] = C[i]
    L[1,i+2*n+3] = B[i]
    L[2+i,i+2*n+3] = B0[i]
for i in range(n):
    L[n+2,i+2*n+3] = A[i]
    L[n+2+1+i,i+2*n+3] = A0[i]

res = L.LLL()[0]

#part4 get flag
e0 = int(GCD(res[1],res[n+2]) // delta)
print(isPrime(e0))
xP = h[0] + e0

sh.sendline(b"2")
sh.sendline(str(xP).encode())
print(sh.recvline())

#NSSCTF{676bdb2a-791d-466b-83e2-d54a2b3f64ab}

其实这题目格看着复杂，但其实主要难度在于繁琐的化简运算得到多项式，造格是化简正确后水到渠成的事情。同时，要想到发送t和-t来消去y，这一步也很关键。

想偷懒的话可以直接照着论文复现(包括上面的题目也是)，不过自己造一造格其实也挺有乐趣的：

https://www.math.auckland.ac.nz/~sgal018/BarakShaniPhD.pdf

MyOracleTwice

题目描述：

Contact XennyOracle again.

题目：

from Crypto.Util.number import *
import random, os
from gmpy2 import *
flag = os.getenv('DASFLAG')

mod = random.getrandbits(1024)

# print('> mod =', mod)

def XennyOracle():
    m = random.getrandbits(40)
    e = random.getrandbits(40)
    c = powmod(m, e, mod)
    print('> c =', c & 0xffffffff)
    msg = int(input('Input r:'))
    
    if m == msg:
        return True
    return False

def task():
    cnt = 0
    while True:
        if XennyOracle():
            cnt += 1
        
        if cnt == 100:
            print('flag: ', flag)
            
task()

我只是明白这一题的思路，但这一题的脚本说实话感觉会比较麻烦，凭我的功力一时半会儿写不出来，因此就简单说一下大概思路好了。

题目仍然是用getrandbits(1024)生成一个模数n，并且也不发送给我们，然后就进入了不限次数的交互中。每次交互会：

• 用getrandbits(40)生成m
• 用getrandbits(40)生成e
• 计算：

$$c = m^e \quad(mod\;n)$$

• 将c的低32位发送给我们
• 有一个核验机会，可以输入一个值，如果值等于m的话cnt就会加一，cnt达到100则获得flag

很明显的一点是，这个题目一直在用getrandbits()这个方法来生成伪随机数，而众所周知，getrandbits()用的是MT19937来生成随机数的，掌握足够的状态就可以往后预测随机数。所以这个题目就是想办法从给的信息中，去推出一个完整的624x32的state，然后就可以向后预测随机数了。

但问题就在于，模数n我们也不知道，我们唯一能获得的信息就是每次交互的c的低32位而已，那怎么才能获得随机数的bit信息呢？

答案就是：如果我们随机到的模数n是一个偶数(当然我们是没有办法知道他是不是偶数的，就碰那个二分之一的概率)，那么对于运算：

$$c = m^e \quad(mod\;n)$$

c不会改变m的奇偶性，也就是说，c的LSB就是m的LSB。这也就等价于：每次交互我们可以获得m的最后一个比特。

而MT19937的整个运算过程都是线性的，因此可以用矩阵方程来表示出初始state和后面任意比特的线性关系。具体来说，初始state是624x32个比特位，我们把它展开成为一个长为624x32，也就是19968的向量：

$$(x_1,x_2,...x_{19968})$$

而对于getrandbits()方法，他获取随机数的单位是32bit，如果获取的bit不是32的整数倍，那么他会获取32的整数倍个bit并截断。这也就是说，我们可以定位每一次交互中，m的最低比特在哪一个新state的哪一个位置。那么对于任意一个我们已知的m的最后一bit，记作mi，它都可以看作是初始state经过某个线性运算得到的结果，也就可以用矩阵方程表示：

$$(x_1,x_2,...x_{19968}) \left(\begin{matrix} t_1\\ t_2\\ ...\\ t_{19968}\\ \end{matrix} \right) = (m_i)$$

其中ti组成的向量是未知的线性表达式对应的向量。而一旦我们收集到19968个m的最低bit，我们就可以把上方的矩阵方程写成一个满秩的矩阵方程：

$$(x_1,x_2,...x_{19968}) \left(\begin{matrix} t_{1,1} & t_{1,2} & & t_{1,19968}\\ t_{2,1} & t_{1,2} & & t_{1,19968}\\ & & ... & \\ t_{19968,1} & t_{19968,2} & & t_{19968,19968}\\ \end{matrix} \right) = (m_1,m_2,...m_{19968})$$

把他抽象出来先写作：

$$XT = M$$

而我们现在只有M，我们的目标是求出X也就是初始state，这样就可以预测之后的所有随机数。为此我们需要想办法求得矩阵T，如果能求出T，我们就可以直接求解上面的矩阵方程得到X了。

因此现在的问题就在于如何求出T，这里需要采用一种选择明文攻击的方法(类似于黑盒测试)，具体来说，我们选择：

$$(1,0,...,0)$$

作为X向量也就是初始state，然后用MT19937去生成对应位置的M向量，就有：

$$(1,0,...,0) T = M_1$$

而之所以这样选择明文，是因为可以发现，这样得到的M1向量其实就是T的第一行。那么接下来，如法炮制继续选择：

$$(0,1,0,...,0)$$ $$(0,0,1,...,0)$$ $$......$$ $$(0,0,0,...,1)$$

这样就能依次得到T的所有行从而构建出完整的T矩阵，此时用我们在题目中获取的M向量去解矩阵方程就能得到初始state，然后就从初始state开始往后预测随机数，一直预测到我们当前产生m的这个state，然后预测成功100次就能拿到flag了。

但是可想而知这个脚本应该不是很好写，所以exp就暂时放弃，先懂个思路。

(其实是想偷懒，等以后偷个别的师傅的exp来用(′@ω@‵))

如果你对MT19937还有其他的疑问，有两篇非常详细的文章可以参考：

MT19937 - Cryptography-Wiki

浅析MT19937伪随机数生成算法-安全客 - 安全资讯平台 (anquanke.com)

总结

昨年的西湖论剑是我打的第一场比赛，当时python也不会写，文件末尾的16进制隐写也不了解，就和室友一起蹭进了学长的队伍。那天上午，我和室友努力了好一会儿把签到做了出来，在那之后我自己到处查资料，捣鼓了一天MP3隐写那个题目，最后也没弄出个名堂，比赛也稀里糊涂之间就结束了。

虽然打完之后，一段时间内也没有入坑ctf(差不多是又被室友拉着打了NKCTF之后，才真正决定跨入ctf的大门)，但是那场西湖论剑仍然是印象非常深刻、对我来说也很有纪念意义的一场比赛。而正好现在放寒假，我也了解了一些crypto知识并且掌握了一些技能，就复现了一下去年Xenny师傅出的几个题目。

入坑ctf差不多10个多月的时间里，学习密码，和室友、学长一起打比赛，研究题目，结识志同道合的师傅，这些都是非常美好的回忆，我想就算以后不打ctf的时候也会常常想起这段时光。新一届的西湖论剑马上就来了，希望这一次能有一个不错的发挥。