nepctf部分

题1

import random
from Crypto.Util.number import getPrime, bytes_to_long


def generate_challenge():
    bits = 1024
    p = getPrime(bits)
    q = getPrime(bits)
    N = p * q

    hidden_p_bits = 502
    p_high = p >> hidden_p_bits

    a = random.randint(2, p - 1)
    c = random.randint(2, p - 1)

    flag = flag.ljust(64, b'\x00')
    seed = bytes_to_long(flag)
    assert seed < p

    def lcg(state):
        return a * ( state - c) % p

    states = [seed]
    for _ in range(5):
        states.append(lcg(states[-1]))

    k = 256
    outputs = [s >> k for s in states]

    print("===== The Coppersmith & LLL Forge =====")
    print(f"N = {N}")
    print(f"p_high = {p_high}")
    print(f"a = {a}")
    print(f"c = {c}")
    print(f"outputs = {outputs}")


if __name__ == "__main__":
    generate_challenge()

"""
N = 
p_high = 
a = 
c = 
outputs = 
"""

分析

恢复p

首先已知n和p_high,是一个常规的coppersmith分解n还原p，q，这里比较值得注意的是epsilon的选值:

$$X < \tfrac12\, N^{\beta^2/d - \varepsilon}$$

进而：

$$\varepsilon \approx \frac{\beta^2}{d} - \frac{\log_2 X}{\log_2 N}\approx 0.25 - \frac{502}{2048} \approx 0.005$$

而epsilon默认为epsilon = beta / 8 = 0.625是出不来的

恢复flag

下一步题目用p作为模做了5次lcg，各项参数已知，但是输出被截断

解决思路大致于隐藏数问题相同，列方程造格打

一个数据我们拆成H+L，L就是我们目标短项量
我们把每一个L对应的方程表示：

$$H_2 + L_2 \equiv a(H_1 + L_1) + b \pmod{m}$$

$$\therefore L_2 \equiv aL_1 + \left(aH_1 + b - H_2\right) \pmod{m}$$

$$\text{记} \ A_1 = a,\ B_1 \equiv \left(aH_1 + b - H_2\right) \pmod{m}$$

$$\because H_3 + L_3 \equiv a(H_2 + L_2) + b \pmod{m}$$

$$\therefore L_3 \equiv a^2L_1 + a(aH_1 + b - H_2) + aH_2 + b - H_3 \pmod{m}$$

$$\text{记} \ A_2 = a^2,\ B_2 \equiv \left(aB_1 + aH_2 + b - H_3\right) \pmod{m}$$

$$\text{到这里我们就可以发现系数规律：}$$

$$L_{i+1} = A_i L_1 + B_i \pmod{m}$$

$$A_i = a^i \pmod{m}$$

$$\ B_i = \left(aB_{i-1} + aH_2 + b - H_{i+1}\right) \pmod{m}$$

对应exp：

A = [1]
B = [0]

for i in range(1, len(h)-1):
	A.append(a*A[i-1] % m)
	B.append((a*B[i-1]+a*h[i]+b-h[i+1]) % m)

A = A[1:]
B = B[1:]

造格:

$$\begin{pmatrix} k_1 & k_2 & \dots & k_n & L_1 & 1 \end{pmatrix} \begin{pmatrix} m & 0 & \dots & 0 & 0 & 0 \\ 0 & m & \dots & 0 & 0 & 0 \\ \vdots & \vdots & \ddots & \vdots & \vdots & \vdots \\ 0 & 0 & \dots & m & 0 & 0 \\ A_1 & A_2 & \dots & A_n & 1 & 0 \\ B_1 & B_2 & \dots & B_n & 0 & K \end{pmatrix} = \begin{pmatrix} L_2 & L_3 & \dots & L_{n+1} & L_1 & K \end{pmatrix}$$

即可还原$L_i$
由此恢复完整的lcg输出，变成常规lcg题目

完整exp

from Crypto.Util.number import long_to_bytes

N = ...; p_high = ...; a = ...; c = ...; outputs = [...]

# Step 1: Coppersmith recover p
hidden = 502
PR.<x> = PolynomialRing(Zmod(N))
f = ((Integer(p_high) << hidden) + x).monic()
p = Integer((p_high << hidden) + ZZ(f.small_roots(X=2^hidden, beta=0.5, epsilon=0.008)[0]))

# Step 2: Truncated LCG -> lattice
a = Integer(a) % p
c = Integer(c) % p
b = (-a * c) % p
k = 256
Y = 2^k
H = [Integer(o) << k for o in outputs]
n = len(outputs)

A = [Integer(1)]
B = [Integer(0)]
for i in range(n - 1):
    A.append(a * A[-1] % p)
    B.append((a * B[-1] + a * H[i] + b - H[i+1]) % p)

t = n - 1
M = matrix(ZZ, t + 2, t + 2)
for i in range(t):
    M[i, i] = p
    M[t, i] = A[i+1]
    M[t+1, i] = B[i+1]
M[t, t] = 1
M[t+1, t+1] = Y

res = M.LLL()
for row in res:
    y0 = abs(Integer(row[t]))
    if y0 < Y:
        seed = H[0] + y0
        s = seed
        for i in range(1, n):
            s = a * (s - c) % p
        if (s >> k) == outputs[-1]:
            print(long_to_bytes(int(seed)).rstrip(b"\x00"))
            break