[LCG]P4 WriteUP

Problem: [LCG]P4

[[toc]]

思路

we have a relation like that:

\begin{cases} X_n \equiv a X_{n-1} + b \pmod m\\ X_{n-1} \equiv a X_{n-2} + b \pmod m \end{cases}

it can be:

\begin{pmatrix} a,b,1,k_1,k_2 \end{pmatrix} \begin{bmatrix} X_{n-1} & X_{n-2} & 1/m & 0 & 0\\ 1 & 1 & 0 & 1/m & 0 \\ -X_n & -X_{n-1} & 0 & 0 & 1 \\ m & 0 & 0 & 0 & 0\\ 0 & m & 0 & 0 & 0 \end{bmatrix} \begin{pmatrix} 0,0,a/m,b/m,1 \end{pmatrix}

EXP

m = 96343920769213509183566159649645883498232615147408833719260458991750774595569
X = [10252710164251491500439276567353270040858009893278574805365710282130751735178,45921408119394697679791444870712342819994277665465694974769614615154688489325,27580830484789044454303424960338587428190874764114011948712258959481449527087]

B = matrix(
    [
        [X[0], X[1], 1 / m, 0, 0],
        [1, 1, 0, 1 / m, 0],
        [-X[1], -X[2], 0, 0, 1],
        [m, 0, 0, 0, 0],
        [0, m, 0, 0, 0],
    ]
)
L = B.LLL()

for i in L:
    if i[0] == 0 and i[1] == 0:
        if i[-1] == 1:
            a, b = i[2] * m % m, i[3] * m % m
        elif i[-1] == -1:
            a, b = -i[2] * m % m, -i[3] * m % m

x = int(X[0])
while 1:
    x = (x - b) * pow(a, -1, m) % m
    try:
        mm = bytes.fromhex(hex(int(x))[2:])
        if b"NSSCTF" in mm:
            print(mm)
            break
    except:
        pass

总结

lattice!