近期比赛复现Vol.3

西湖论剑2024

Or1cle

题目没有提供附件，提供了nc，先链接靶机，显示如下信息：

   _  __                                       __________        ___________ 
  | |/_/__ ___  ___  __ __    __              /\____;;___\      |          |
 _>  </ -_) _ \/ _ \/ // /   /o \________    | /  haruki /      |  flag    |
/_/|_|\__/_//_/_//_/\_, /    \_/       | |   .', ----. /|       |———————————
                   /___/                     ||     ||||        |
                                             \'.____.'||        |
                                              '--------'

1. get_signature
2. get_flag
3. gift
4. exit

直接提供了一个交互程序，可以通过一些操作得到包含源代码的信息，首先在get_flag时如果输入的不合适会进行报错，返回一段代码：

    self.P = self.d*secp256k1.G

    def signature(self,msg):
        h = int(hashlib.sha256(msg).hexdigest(),16)
        k = h^self.d
        r = (k*secp256k1.G).x
        s = inverse(k,secp256k1.q) * (h + r*self.d) % secp256k1.q
        return '%064x%064x' % (r, s)

    def verify(self,z, signature):
        r, s = int(signature[:64], 16), int(signature[64:], 16)
        z = int(hashlib.sha256(z).hexdigest(), 16)
        s_inv = pow(s, secp256k1.q - 2, secp256k1.q)
        u1 = (z * s_inv) % secp256k1.q
        u2 = (r * s_inv) % secp256k1.q
        point = u1 * secp256k1.G + u2 * self.P
        return point.x == r

banner = """
   _  __   

提供了签名和验证的代码。后续测试发现在get_signature时如果连续签名五次也会进行报错，得到另一段代码：

a = getPrime(256)
private_key = random.getrandbits(256) ^ a
xenny = Xenny(private_key)
client_socket.send(banner.encode())
co = 5
while True:
    client_socket.send(Menu.encode())
    choice = client_socket.recv(1024).decode().strip()
    if choice == '1' :
        if co == 0:
            raise CountError("No more!!!!")
        client_socket.send("give me something sign: ".encode())
        s = client_socket.recv(1024)[:-1]
        if b"xenny" in s:
            client_socket.send("What makes you think you can pose as Xenny?\n".encode())
            break
        sign = xenny.signature(s)
        client_socket.send(f"{sign}\n".encode())
        co -= 1
    elif choice == '2':
        client_socket.send("sign: ".encode())

大概已经能知道这个题目的逻辑了，就是验证一个签名，满足后就可以返回flag，当我们随便发送一个满足要求的签名对进行验签时会得到一句话：

Only xenny can get flag

而我尝试使用xenny进行签名时，也会返回一句：

What makes you think you can pose as Xenny?

所以这个题目要求的就是我们需要伪造一个xenny的签名使其通过验证。

这题还提供了一个3选项，这个选项测试之后发现是一个伪随机数验证，研究了一下发现似乎没什么用。

观察这里的验证代码：

def verify(self,z, signature):
    r, s = int(signature[:64], 16), int(signature[64:], 16)
    z = int(hashlib.sha256(z).hexdigest(), 16)
    s_inv = pow(s, secp256k1.q - 2, secp256k1.q)
    u1 = (z * s_inv) % secp256k1.q
    u2 = (r * s_inv) % secp256k1.q
    point = u1 * secp256k1.G + u2 * self.P
    return point.x == r

发现这里求解逆元用的是s_inv = pow(s, secp256k1.q - 2, secp256k1.q)，最后验证的是点的x坐标和r值是否相等。所以理论上我们都设为0，使得最后验证的时候为0 == 0就可以了，发送验签就发送128个0就可以了。验签通过。

我们在数学的角度上来看这个问题，试着用一个比较合理的做法进行求解：

观察签名函数：

def signature(self,msg):
    h = int(hashlib.sha256(msg).hexdigest(),16)
    k = h^self.d
    r = (k*secp256k1.G).x
    s = inverse(k,secp256k1.q) * (h + r*self.d) % secp256k1.q
    return '%064x%064x' % (r, s)

发现：

$$k=h\oplus d$$ $$s_i(h_i\oplus d)\equiv h_i+r_id\pmod q$$

在secp256k1中的参数是公开确定的，返回的值包含了$(r,s)$对，所以上面的同余式只有$d$一个未知量。根据题目的思路，我们可以获得五组不同的数据构成等式。

但是，式子其中的异或运算仔细想想是不容易直接解出来的，异或的本质上相当于将一个未知数变成了它未知bit位个未知数，解不了。进而去尝试用格来求解：

先来记住一个公式：

$$a\oplus b=a+b-2(a\ \&\ b)$$

这个式子将异或运算转化成了加减法和按位与运算，又有：

$$a\ \&\ b=\sum^n_{i=0}2^ia_ib_i$$

所以，可以将看似复杂的异或运算进行简化：

$$a\oplus b=a+b-2(\sum^n_{i=0}2^ia_ib_i)$$

转换成题目中的式子，我们先使用一组数据：

$$s_0(h_0+d-2(\sum^n_{j=0}2^jh_{0,j}d_j))\equiv h_0+r_0d\pmod q$$

将上式中的$d$也可以转化成按位表示的形式，这样这个方程的未知数只剩每个bit位了：

$$s_0(h_0+(\sum^n_{i=0}2^id_i)-2(\sum^n_{j=0}2^jh_{0,j}d_j))-h_0-r_0(\sum^n_{i=0}2^id_i)\equiv 0\pmod q$$

写出方便造格的形式：

$$h_0(s_0-1)+(\sum^n_{i=0}2^id_i)(s_0-r_0)-2^{0+1}s_0h_{0,0}d_0-...-2^{255+1}s_0h_{0,255}d_{255}+t_iq=0$$

合并一下同类项：

$$h_0(s_0-1)+((s_0-r_0)2^0-2^{0+1}s_0h_{0,0})d_0+...+((s_0-r_0)2^{255}-2^{255+1}s_0h_{0,255})d_{255}+t_iq=0$$

我们的格基就是这种形式：

$$\begin{bmatrix} 1&&&&&(s_0-r_0)2^0-2^{0+1}s_0h_{0,0}&(s_0-r_0)2^0-2^{0+1}s_1h_{1,0}&...&(s_0-r_0)2^0-2^{0+1}s_4h_{4,0}\\ &1&&&&(s_0-r_0)2^1-2^{1+1}s_0h_{0,1}&(s_0-r_0)2^1-2^{1+1}s_1h_{1,1}&...&(s_0-r_0)2^1-2^{1+1}s_4h_{4,1}\\ &&...&&&...&...&...&...\\ &&&1&&(s_0-r_0)2^{255}-2^{255+1}s_0h_{0,255}&(s_0-r_0)2^{255}-2^{255+1}s_1h_{0,255}&...&(s_0-r_0)2^{255}-2^{255+1}s_4h_{4,255}\\ &&&&1&h_0(s_0-1)&h_1(s_1-1)&...&h_4(s_4-1)\\ &&&&&q&&...&\\ &&&&&&q&...&\\ &&&&&&&...&\\ &&&&&&&...&q\\ \end{bmatrix}$$

满足关系：

$$\begin{pmatrix} d_0&d_1&...&d_{255}&1&t_0&t_1&t_2&t_3&t_4 \end{pmatrix} L =\begin{pmatrix} d_0&d_1&...&d_{255}&1&0&0&0&0&0 \end{pmatrix}$$

进行格基规约，找规约后矩阵满足上面等式右侧形式的，就相当于求得了这个私钥$d$，之后我们就可以利用他的签名方式自己制作一个xenny的签名，验签通过。贴一个大佬的脚本：

from Pwn4Sage.pwn import *
from tqdm import *
from Crypto.Util.number import *
from fastecdsa.curve import secp256k1 as CURVE
from hashlib import sha256

#context.log_level = 'debug'

sh = remote("1.14.108.193",32252)

R = []
S = []
z = [int(sha256(i).hexdigest(),16) for i in [b"0",b"1",b"2",b"3",b"4"]]
if(1):
    for i in range(5):
        sh.sendline(b"1")

        sh.recvuntil(b"give me something sign:")
        msg = str(i).encode()
        sh.sendline(msg)
        rs = sh.recvline().strip().decode()
        r,s = int(rs[:len(rs)//2],16),int(rs[len(rs)//2:],16)
        R.append(r)
        S.append(s) 
print(R)
print(S) 
sigs = []
for i in range(5):
    sigs.append((z[i],R[i],S[i]))


#part2 get d
def recover_d(sigs):
    P = PolynomialRing(Zmod(CURVE.q), "d", 256)
    ds = P.gens()
    dd = sum([2 ** i * di for i, di in enumerate(ds)])
    polys = []
    for z, r, s in sigs:
        d_and_z = sum([2 ** i * ((z & (1 << i)) >> i) * di for i, di in enumerate(ds)])
        # fact: (a xor b) = a + b - 2 * (a and b)
        k = dd + z - 2 * d_and_z
        polys.append((s * k) - (z + r * dd))
    M, v = Sequence(polys).coefficient_matrix()
    print(v.T)
    M = M.T.dense_matrix()
    a, b = M.dimensions()
    B = block_matrix(
        ZZ, [[matrix.identity(b) * CURVE.q, matrix.zero(b, a)], [M, matrix.identity(a)]]
    )
    B[:, :b] *= 2 ^ 64
    print("LLL", B.dimensions())
    for row in B.LLL():
        if row[:b] == 0 and row[-1] == 1 and all(0 <= x <= 1 for x in row[b:-1]):
            dbits = row[b:-1]
            d = int("".join(map(str, dbits[::-1])), 2)
            return d

d = recover_d(sigs)
print(d)
#part3 get flag
h = int(sha256(b"xenny").hexdigest(),16)
k = h^^d
r = (k*CURVE.G).x
s = inverse(k,CURVE.q) * (h + r*d) % CURVE.q
signature = hex(r)[2:].zfill(64)+hex(s)[2:].zfill(64)

sh.sendline(b"2")
sh.recvuntil(b"sign: ")
sh.sendline(signature.encode())
sh.recvline()
print(sh.recvline())

L3HCTF 2024

随便打了一下，misc那边还做了几个题，就不写了，还是只看看密码吧！

babySPN

import random
import time
from secret import flag
from hashlib import sha256
from Crypto.Util.number import *

def bin_to_list(r, bit_len):
    list = [r >> d & 1 for d in range(bit_len)][::-1]
    return list

def list_to_int(list):
    return int("".join(str(i) for i in list), 2)

Pbox=[1, 5, 9, 13, 2, 6, 10, 14, 3, 7, 11, 15, 4, 8, 12, 16]
Sbox=[14, 13, 11, 0, 2, 1, 4, 15, 7, 10, 8, 5, 9, 12, 3, 6]

def round_func(X,r,K):
    kstart=4*r - 4
    XX = [0] * 16
    for i in range(16):
        XX[i] = X[i] ^ K[kstart+i]
    for i in range(4):
        value = list_to_int(XX[4*i:4*i+4])
        s_value = Sbox[value]
        s_list = bin_to_list(s_value, 4)
        XX[4*i],XX[4*i+1],XX[4*i+2],XX[4*i+3] = s_list[0],s_list[1],s_list[2],s_list[3]

    Y=[0] * 16
    for i in range(16):
        Y[Pbox[i]-1]=XX[i]
    return Y

def enc(X,K):
    Y = round_func(X,1,K)
    Y = round_func(Y,2,K)
    Y = round_func(Y,3,K)
    Y = round_func(Y,4,K)

    kstart=4*5 - 4
    for i in range(16):
        Y[i] ^= K[kstart+i]
    return Y

K = [0, 1, 1, 0, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0]

assert len(K) == 32
for i in K:
    assert i == 0 or i == 1

hash_value = sha256(long_to_bytes(list_to_int(K))).hexdigest()
assert flag[7:-1] == hash_value

XX = [0]*16
for i in range(4):
    XX[i*4] = 1
    print(enc(XX,K))
    XX[i*4] = 0

# [0, 1, 1, 0, 1, 1, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0]
# [1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 1, 0, 1, 0, 1, 1]
# [0, 1, 1, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1]
# [1, 1, 1, 1, 1, 0, 0, 1, 0, 1, 0, 0, 0, 1, 1, 0]

看着非常复杂，但是注意观察：

K = [0, 1, 1, 0, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0]

assert len(K) == 32
for i in K:
    assert i == 0 or i == 1

hash_value = sha256(long_to_bytes(list_to_int(K))).hexdigest()
assert flag[7:-1] == hash_value

这相当于直接把flag告诉我们了，直接输出就能得到flag：

from Crypto.Util.number import *
from hashlib import *

def list_to_int(list):
    return int("".join(str(i) for i in list), 2)

K = [0, 1, 1, 0, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0]

hash_value = sha256(long_to_bytes(list_to_int(K))).hexdigest()
print('L3HCTF{' + hash_value + '}')

can_you_guess_me

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

q = getPrime(128)

n = 5
T = 2**48
E = 2**32

t = [randint(1,T) for i in range(n)]
e = [randint(1,E) for i in range(n)]
a = [(t[i] * flag - e[i]) % q for i in range(n)]

print('q =', q)
print('a =', a)

flag = "L3HSEC{" + hex(flag)[2:] + "}"

print('flag =', flag)

# q = 313199526393254794805899275326380083313
# a = [258948702106389340127909287396807150259, 130878573261697415793888397911168583971, 287085364108707601156242002650192970665, 172240654236516299340495055728541554805, 206056586779420225992168537876290239524]

题目给了五组$a_i$，需要我们恢复flag，根据代码可以发现flag内部的hex应该是在域$q$里的，相对比较小。

$$a_i\equiv t_is-e_i\pmod q$$

由于题目代码我们知道$t,e$是比较小的，可以想法造格去求，找一下对应关系：

$$a_it_j\equiv t_jt_is-e_it_j\pmod q$$ $$a_jt_i\equiv t_jt_is-e_jt_i\pmod q$$

既然这里我们是要求解这些小值，想个办法把位置的flag$s$消掉，这样两式作差：

$$a_it_j-a_jt_i\equiv e_jt_i-e_it_j\pmod q$$

展开成为等式，将右边可以设为$x_i$：

$$a_it_j-a_jt_i-k_nq=x_n$$

通过五组数据排列组合，我们可以得到$4+3+2+1=10$个这样的方程，造格：

$$M=\begin{bmatrix} 2^{32}&&&&&-a_1&-a_2&-a_3&-a_4&&&&&&\\ &2^{32}&&&&a_0&&&&-a_2&-a_3&-a_4&&&\\ &&2^{32}&&&&a_0&&&a_1&&&-a_3&-a_4&\\ &&&2^{32}&&&&a_0&&&a_1&&a_2&&-a_4\\ &&&&2^{32}&&&&a_0&&&a_1&&a_2&a_3\\ &&&&&q\\ &&&&&&q\\ &&&&&&&q\\ &&&&&&&&q&&&&&&\\ &&&&&&&&&q&&&&&\\ &&&&&&&&&&q&&&&\\ &&&&&&&&&&&q&&&\\ &&&&&&&&&&&&q&&\\ &&&&&&&&&&&&&q&\\ &&&&&&&&&&&&&&q\\ \end{bmatrix}$$ $$v=\begin{bmatrix} t_0&t_1&t_2&t_3&t_4&k_0&...&k_9 \end{bmatrix}$$

有：

$$vM=\begin{bmatrix} 2^{32}t_0&2^{32}t_1&2^{32}t_2&2^{32}t_3&2^{32}t_4 & x_0&...&x_9 \end{bmatrix}$$

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

q = 313199526393254794805899275326380083313
a = [
    258948702106389340127909287396807150259,
    130878573261697415793888397911168583971,
    287085364108707601156242002650192970665,
    172240654236516299340495055728541554805,
    206056586779420225992168537876290239524,
]
M = Matrix(ZZ, 15, 15)
for i in range(5):
    M[i, i] = 2 ^ 32
for i in range(10):
    M[i + 5, i + 5] = q
for i in range(4):
    M[0, i + 5] = -a[i + 1]
    M[i + 1, i + 5] = a[0]
for i in range(3):
    M[1, i + 9] = -a[i + 2]
    M[i + 2, i + 9] = a[1]
for i in range(2):
    M[2, i + 12] = -a[i + 3]
    M[i + 3, i + 12] = a[2]
for i in range(1):
    M[3, i + 14] = -a[i + 4]
    M[i + 4, i + 14] = a[3]
res = M.LLL()

得到的规约基中，查看每行的前五个元素，如果这个数能整除$2^{32}$而且除后在$2^{48}$以内，那么就说明这个是正确的$t$。得到$t$之后，就可以进一步求解$e$：

$$a_it_j-a_jt_i\equiv e_jt_i-e_it_j\pmod q$$

在这个式子中，我们现在已经得到了所有的$t$，左边是已知的，设为$m$，可以进一步把这个式子放在模$t_i$中，得到：

$$-m\equiv e_it_j\pmod {t_i}$$

接下来求解逆元就可以得到$e_i$，根据式子逆回去就可以得到flag：

$$a_i\equiv t_is-e_i\pmod q$$

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

a = [
    258948702106389340127909287396807150259,
    130878573261697415793888397911168583971,
    287085364108707601156242002650192970665,
    172240654236516299340495055728541554805,
    206056586779420225992168537876290239524,
]
q = 313199526393254794805899275326380083313
res1 = [
    302629699205295889186816,
    34258694174788154294272,
    769413139329500181430272,
    758297091828795756773376,
    623555694340443278934016,
    147333855057140118568110,
    -202558222663678621328172,
    -45435975667911134188158,
    -112313314799199080915418,
    -397515460206855156581094,
    -374316900522869789955471,
    -316289419197217617437916,
    392031168144698477023056,
    131814534905250913679766,
    -187803770679128076856665,
]
T = []
for i in range(5):
    assert res1[i] % 2 * 32 == 0
    T.append(res1[i] // 2**32)

print(gmpy2.gcd(T[3], T[1]))
tmp = ((-(T[3] * a[1] - T[1] * a[3])) % q) % T[1]
e1 = tmp * gmpy2.invert(T[3], T[1]) % T[1]
flag = ((a[1] + e1) * gmpy2.invert(T[1], q)) % q
flag = "L3HSEC{" + hex(flag)[2:] + "}"
print(flag)

Badrlwe

from Crypto.Util.number import *
from random import *
import random
import numpy as np
from secret import flag, sk

assert len(flag[7:-1]) <= 64
data = [ord(i) for i in list(flag[7:-1])]

for i in range(len(sk)):
    assert data[i] == sk[i] 

q = 1219077173
R.<x> = PolynomialRing(Zmod(q), 'x')
N = 1024

f = x^N - 1

a = [0] * N
for i in range(N):
    a[i] = randint(0, q)

s = sk

e = [0] * N
for i in range(N):
    val = np.random.normal(loc=0.0, scale=2.1, size=None)
    e[i] = int(val)

a = R(a)
s = R(s)
e = R(e)
b = (a*s + e)%f

print(a)
print(b)
print(q)

# 1219077173
# 216047404*x^1023 + 1008199117*x^1022 + 39562072*x^1021 + 189992355*x^1020 + 1087671639*x^1019 + 541371337*x^1018 + 1146044200*x^1017 + 212969175*x^1016 + 1114159572*x^1015 + 1112032860*x^1014 + 1204883609*x^1013 + 1181544913*x^1012 + 851496082*x^1011 + 222877006*x^1010 + 163176236*x^1009 + 268697504*x^1008 + 613151090*x^1007 + 1185245256*x^1006 + 215725010*x^1005 + 789898500*x^1004 + 1156619111*x^1003 + 610859911*x^1002 + 959814483*x^1001 + 684353251*x^1000 + 290850651*x^999 + 675880502*x^998 + 836239751*x^997 + 487296407*x^996 + 778816128*x^995 + 1013639221*x^994 + 189137575*x^993 + 172217836*x^992 + 572872008*x^991 + 865759581*x^990 + 399805736*x^989 + 394587004*x^988 + 633085719*x^987 + 15142893*x^986 + 461176831*x^985 + 1078060208*x^984 + 787396508*x^983 + 877420202*x^982 + 1121486845*x^981 + 146921816*x^980 + 670134387*x^979 + 574407635*x^978 + 1148395437*x^977 + 748514947*x^976 + 970442995*x^975 + 280085063*x^974 + 420670822*x^973 + 20159574*x^972 + 219680665*x^971 + 401202858*x^970 + 328444623*x^969 + 623312316*x^968 + 917712264*x^967 + 588061576*x^966 + 625482841*x^965 + 220929234*x^964 + 778461001*x^963 + 498203565*x^962 + 1055981771*x^961 + 70562147*x^960 + 931081750*x^959 + 93569863*x^958 + 314876311*x^957 + 932364613*x^956 + 1132016772*x^955 + 371703330*x^954 + 189301560*x^953 + 739232608*x^952 + 916695967*x^951 + 399818344*x^950 + 558604923*x^949 + 1092603913*x^948 + 987195616*x^947 + 665679589*x^946 + 1142632478*x^945 + 198797278*x^944 + 110832477*x^943 + 775688737*x^942 + 275416086*x^941 + 435656120*x^940 + 754150483*x^939 + 1024583186*x^938 + 972075461*x^937 + 1071060217*x^936 + 710789980*x^935 + 691361770*x^934 + 1097024307*x^933 + 862356288*x^932 + 354500195*x^931 + 158151296*x^930 + 733475281*x^929 + 215008492*x^928 + 151139272*x^927 + 1000425669*x^926 + 590964357*x^925 + 373950911*x^924 + 43038800*x^923 + 338044906*x^922 + 293954870*x^921 + 393479*x^920 + 555095359*x^919 + 418829106*x^918 + 95391760*x^917 + 897658305*x^916 + 1040609125*x^915 + 239948276*x^914 + 1190720461*x^913 + 160498737*x^912 + 394967890*x^911 + 104302686*x^910 + 48021969*x^909 + 761000569*x^908 + 356140410*x^907 + 225246587*x^906 + 79172445*x^905 + 975365689*x^904 + 1077396491*x^903 + 728717352*x^902 + 964273647*x^901 + 258781036*x^900 + 746930481*x^899 + 793742220*x^898 + 542128050*x^897 + 562413014*x^896 + 701216258*x^895 + 928704966*x^894 + 98656502*x^893 + 1016152774*x^892 + 140544845*x^891 + 226416702*x^890 + 309310359*x^889 + 519065123*x^888 + 346740110*x^887 + 116615122*x^886 + 990804519*x^885 + 208648062*x^884 + 605381435*x^883 + 821163414*x^882 + 864698754*x^881 + 424773230*x^880 + 1184139330*x^879 + 437390254*x^878 + 41435781*x^877 + 824197241*x^876 + 1181823353*x^875 + 354135255*x^874 + 921600154*x^873 + 972782404*x^872 + 304175744*x^871 + 976950586*x^870 + 561195955*x^869 + 840601911*x^868 + 848362310*x^867 + 698380233*x^866 + 703722831*x^865 + 527081934*x^864 + 996708932*x^863 + 926257884*x^862 + 113808466*x^861 + 111022399*x^860 + 336240881*x^859 + 281602555*x^858 + 456022351*x^857 + 303940681*x^856 + 1152960332*x^855 + 762827305*x^854 + 1097893502*x^853 + 1159492861*x^852 + 791288185*x^851 + 552596428*x^850 + 1160303133*x^849 + 855459983*x^848 + 870046128*x^847 + 412042730*x^846 + 527317697*x^845 + 118258027*x^844 + 1156090191*x^843 + 1184418516*x^842 + 736914609*x^841 + 1042440949*x^840 + 1118336201*x^839 + 692314475*x^838 + 888141647*x^837 + 611975215*x^836 + 112482309*x^835 + 774541929*x^834 + 877613260*x^833 + 218484596*x^832 + 744043072*x^831 + 1149426359*x^830 + 1086732941*x^829 + 218727414*x^828 + 111004493*x^827 + 48035668*x^826 + 1129753198*x^825 + 410088959*x^824 + 1186919074*x^823 + 291266088*x^822 + 622780685*x^821 + 908030149*x^820 + 152548456*x^819 + 970996704*x^818 + 643233117*x^817 + 97648457*x^816 + 167039372*x^815 + 451159004*x^814 + 21522258*x^813 + 446568222*x^812 + 97236135*x^811 + 601480363*x^810 + 896523050*x^809 + 635312918*x^808 + 771155729*x^807 + 727217487*x^806 + 1103325662*x^805 + 1145702253*x^804 + 111451279*x^803 + 709647761*x^802 + 155865734*x^801 + 788861657*x^800 + 25328658*x^799 + 387592047*x^798 + 631380316*x^797 + 195654331*x^796 + 379901017*x^795 + 110746571*x^794 + 821639667*x^793 + 1196705497*x^792 + 926725497*x^791 + 752090468*x^790 + 565928514*x^789 + 107924077*x^788 + 1035444397*x^787 + 389590222*x^786 + 746022468*x^785 + 1152494936*x^784 + 1047183126*x^783 + 935173423*x^782 + 237022259*x^781 + 68211471*x^780 + 682392084*x^779 + 900610142*x^778 + 659697118*x^777 + 381789469*x^776 + 895479393*x^775 + 342674862*x^774 + 1034152415*x^773 + 736863278*x^772 + 233824501*x^771 + 511543257*x^770 + 43539547*x^769 + 871109943*x^768 + 234226499*x^767 + 958639125*x^766 + 913885377*x^765 + 757234386*x^764 + 330354514*x^763 + 693659124*x^762 + 46757147*x^761 + 24910108*x^760 + 263754046*x^759 + 1007999117*x^758 + 569158879*x^757 + 781185896*x^756 + 328234792*x^755 + 1166796778*x^754 + 1023882729*x^753 + 1126014838*x^752 + 412948341*x^751 + 745762031*x^750 + 184601330*x^749 + 1195686854*x^748 + 226180761*x^747 + 813440273*x^746 + 198496604*x^745 + 646284299*x^744 + 775658802*x^743 + 1051631440*x^742 + 382010443*x^741 + 884529292*x^740 + 1171509241*x^739 + 148470016*x^738 + 545551560*x^737 + 895321797*x^736 + 990533556*x^735 + 1006826878*x^734 + 444425261*x^733 + 538658289*x^732 + 1201448839*x^731 + 813543244*x^730 + 866138640*x^729 + 992484781*x^728 + 797592952*x^727 + 5350520*x^726 + 1088776239*x^725 + 1011384293*x^724 + 202279961*x^723 + 580990742*x^722 + 608736084*x^721 + 592191483*x^720 + 603821965*x^719 + 686032966*x^718 + 309449994*x^717 + 997796743*x^716 + 323694959*x^715 + 404631321*x^714 + 684041814*x^713 + 954922509*x^712 + 17334061*x^711 + 1038027065*x^710 + 189030167*x^709 + 238786122*x^708 + 854157242*x^707 + 857322405*x^706 + 847505723*x^705 + 531600098*x^704 + 413144959*x^703 + 150862275*x^702 + 176120020*x^701 + 147651128*x^700 + 20961937*x^699 + 924892688*x^698 + 207889399*x^697 + 506289209*x^696 + 201657090*x^695 + 866897606*x^694 + 282950189*x^693 + 484625027*x^692 + 720969770*x^691 + 557487808*x^690 + 664292309*x^689 + 667236796*x^688 + 505039446*x^687 + 636507041*x^686 + 717904854*x^685 + 742491214*x^684 + 235380401*x^683 + 885103138*x^682 + 227708439*x^681 + 195450351*x^680 + 914408549*x^679 + 890140153*x^678 + 959662247*x^677 + 655663410*x^676 + 682768547*x^675 + 1063757282*x^674 + 776284911*x^673 + 1114588219*x^672 + 689022198*x^671 + 1160585767*x^670 + 784564493*x^669 + 599804982*x^668 + 954265199*x^667 + 1160092910*x^666 + 1178991310*x^665 + 610146522*x^664 + 589028938*x^663 + 972903553*x^662 + 933544074*x^661 + 910101746*x^660 + 1199479046*x^659 + 129564572*x^658 + 16630574*x^657 + 604268174*x^656 + 905616984*x^655 + 229755095*x^654 + 543777663*x^653 + 880642044*x^652 + 750742780*x^651 + 801027824*x^650 + 59869899*x^649 + 178293151*x^648 + 413473523*x^647 + 790966353*x^646 + 36947608*x^645 + 215402931*x^644 + 198271237*x^643 + 394503398*x^642 + 933396244*x^641 + 764498758*x^640 + 960831635*x^639 + 710558646*x^638 + 160491214*x^637 + 161213508*x^636 + 932611994*x^635 + 226519192*x^634 + 554464756*x^633 + 82595536*x^632 + 1144714763*x^631 + 361090580*x^630 + 747809061*x^629 + 114293244*x^628 + 253349999*x^627 + 1051279816*x^626 + 1079507344*x^625 + 864605458*x^624 + 1100098300*x^623 + 323233106*x^622 + 1070769430*x^621 + 1048471132*x^620 + 23281664*x^619 + 1099148878*x^618 + 812556000*x^617 + 452606567*x^616 + 892217880*x^615 + 741556204*x^614 + 37168552*x^613 + 286980867*x^612 + 1125383508*x^611 + 782814488*x^610 + 1214851511*x^609 + 270577673*x^608 + 364433480*x^607 + 825553809*x^606 + 589475297*x^605 + 293114041*x^604 + 1115978872*x^603 + 21831218*x^602 + 856821602*x^601 + 213782489*x^600 + 287159884*x^599 + 1015101950*x^598 + 494211644*x^597 + 38143731*x^596 + 882805771*x^595 + 721674528*x^594 + 120092153*x^593 + 636819567*x^592 + 365557574*x^591 + 619653423*x^590 + 1207892829*x^589 + 971282528*x^588 + 379459809*x^587 + 507124241*x^586 + 1050378769*x^585 + 113715629*x^584 + 841835564*x^583 + 1055649818*x^582 + 904319486*x^581 + 83232231*x^580 + 282044435*x^579 + 11563226*x^578 + 283283452*x^577 + 515932154*x^576 + 415242679*x^575 + 686396058*x^574 + 414011723*x^573 + 22692318*x^572 + 593039855*x^571 + 42054428*x^570 + 242713788*x^569 + 756543053*x^568 + 297264974*x^567 + 656668981*x^566 + 103185189*x^565 + 279211827*x^564 + 66472175*x^563 + 221289056*x^562 + 418547255*x^561 + 587378319*x^560 + 781217899*x^559 + 828907515*x^558 + 1026785730*x^557 + 936576598*x^556 + 914519864*x^555 + 458326840*x^554 + 846364356*x^553 + 1048948157*x^552 + 276890468*x^551 + 211463242*x^550 + 611009955*x^549 + 41350370*x^548 + 1120260432*x^547 + 1217213406*x^546 + 1096884636*x^545 + 107298827*x^544 + 556646889*x^543 + 514714957*x^542 + 592531623*x^541 + 1185635127*x^540 + 866796164*x^539 + 1199009440*x^538 + 760543377*x^537 + 135043128*x^536 + 1184521976*x^535 + 53368352*x^534 + 614063947*x^533 + 117184488*x^532 + 1090625549*x^531 + 928160285*x^530 + 1065640157*x^529 + 307397590*x^528 + 383318068*x^527 + 890835908*x^526 + 416986540*x^525 + 222852700*x^524 + 965323537*x^523 + 151764017*x^522 + 193722745*x^521 + 439803983*x^520 + 942882901*x^519 + 56286764*x^518 + 824204572*x^517 + 478793274*x^516 + 183238303*x^515 + 922253103*x^514 + 5444136*x^513 + 402856270*x^512 + 508652113*x^511 + 898341402*x^510 + 56743140*x^509 + 179078829*x^508 + 360574641*x^507 + 691533190*x^506 + 982373838*x^505 + 719429684*x^504 + 962339948*x^503 + 1097706834*x^502 + 682588935*x^501 + 1193566532*x^500 + 1140505780*x^499 + 1167874911*x^498 + 669408623*x^497 + 15348570*x^496 + 896129486*x^495 + 100671957*x^494 + 1015786650*x^493 + 605094306*x^492 + 704959137*x^491 + 503877361*x^490 + 546763047*x^489 + 281625173*x^488 + 874599768*x^487 + 187483443*x^486 + 791213383*x^485 + 670376251*x^484 + 484751013*x^483 + 519454749*x^482 + 898655062*x^481 + 1088862155*x^480 + 843442957*x^479 + 429341712*x^478 + 869408179*x^477 + 921648096*x^476 + 526019939*x^475 + 856290375*x^474 + 531710459*x^473 + 1135323038*x^472 + 222776023*x^471 + 223826994*x^470 + 782612384*x^469 + 208579370*x^468 + 809908930*x^467 + 802818642*x^466 + 1182584545*x^465 + 245518705*x^464 + 114792460*x^463 + 646248449*x^462 + 63969962*x^461 + 761908644*x^460 + 523665668*x^459 + 1131060959*x^458 + 507746193*x^457 + 215968166*x^456 + 186113215*x^455 + 1117740378*x^454 + 649175082*x^453 + 396834257*x^452 + 274002774*x^451 + 626055138*x^450 + 924423066*x^449 + 81357715*x^448 + 1042994674*x^447 + 380053163*x^446 + 687766657*x^445 + 414805559*x^444 + 1118153385*x^443 + 1196507975*x^442 + 223759358*x^441 + 808836890*x^440 + 558230978*x^439 + 470920831*x^438 + 313868031*x^437 + 696317665*x^436 + 38725962*x^435 + 722983488*x^434 + 982704221*x^433 + 931470025*x^432 + 658261117*x^431 + 1043739465*x^430 + 422603501*x^429 + 879856656*x^428 + 977082068*x^427 + 593021461*x^426 + 955543544*x^425 + 194004912*x^424 + 1057355064*x^423 + 1153279801*x^422 + 1104874965*x^421 + 1157109085*x^420 + 54358054*x^419 + 802241073*x^418 + 489376522*x^417 + 250441773*x^416 + 740903923*x^415 + 81493461*x^414 + 966046559*x^413 + 295086523*x^412 + 1192114766*x^411 + 1186654005*x^410 + 768853461*x^409 + 302013033*x^408 + 1127093874*x^407 + 401944628*x^406 + 463364841*x^405 + 277324527*x^404 + 357826211*x^403 + 302642912*x^402 + 785232813*x^401 + 1155455395*x^400 + 240939622*x^399 + 1090741169*x^398 + 941697407*x^397 + 1108935255*x^396 + 63027943*x^395 + 415750779*x^394 + 36046273*x^393 + 172429619*x^392 + 563533800*x^391 + 961503349*x^390 + 356454474*x^389 + 586712431*x^388 + 572728001*x^387 + 670855384*x^386 + 268877633*x^385 + 51139525*x^384 + 806328542*x^383 + 790061093*x^382 + 140256246*x^381 + 430118720*x^380 + 924612224*x^379 + 923573107*x^378 + 1124645882*x^377 + 1044890409*x^376 + 509180566*x^375 + 371227114*x^374 + 161843486*x^373 + 296514161*x^372 + 454272518*x^371 + 755779732*x^370 + 295567281*x^369 + 1063635155*x^368 + 46603670*x^367 + 112353112*x^366 + 571920305*x^365 + 484055586*x^364 + 148075787*x^363 + 700140701*x^362 + 922814151*x^361 + 198283677*x^360 + 806078101*x^359 + 1218701262*x^358 + 679274064*x^357 + 408382456*x^356 + 284971608*x^355 + 1072737570*x^354 + 999420946*x^353 + 704897365*x^352 + 1147239838*x^351 + 1148707218*x^350 + 119677974*x^349 + 139766009*x^348 + 289899118*x^347 + 3099746*x^346 + 478334394*x^345 + 671867092*x^344 + 1123276962*x^343 + 1053910974*x^342 + 776016929*x^341 + 408840884*x^340 + 702734268*x^339 + 101137143*x^338 + 157330682*x^337 + 608473559*x^336 + 355406102*x^335 + 1189624142*x^334 + 87874850*x^333 + 1097033743*x^332 + 984835279*x^331 + 133446104*x^330 + 990221835*x^329 + 34152703*x^328 + 902602955*x^327 + 564227604*x^326 + 378045277*x^325 + 330935315*x^324 + 300442927*x^323 + 504016276*x^322 + 592727454*x^321 + 1075766200*x^320 + 718996149*x^319 + 823573424*x^318 + 834215705*x^317 + 430497892*x^316 + 879722938*x^315 + 968236501*x^314 + 262764692*x^313 + 37503817*x^312 + 607855810*x^311 + 1173289902*x^310 + 906609932*x^309 + 11948749*x^308 + 948969610*x^307 + 1130417155*x^306 + 892108695*x^305 + 1040897188*x^304 + 174698274*x^303 + 85414336*x^302 + 758730292*x^301 + 615781943*x^300 + 1215130735*x^299 + 1168693743*x^298 + 1070287857*x^297 + 501559848*x^296 + 485147924*x^295 + 1218893131*x^294 + 923876087*x^293 + 565056561*x^292 + 282754375*x^291 + 794028720*x^290 + 288419549*x^289 + 688387454*x^288 + 40339086*x^287 + 659115548*x^286 + 614342861*x^285 + 391568544*x^284 + 464738754*x^283 + 28669498*x^282 + 1115640335*x^281 + 870635325*x^280 + 126237247*x^279 + 1111165998*x^278 + 205027579*x^277 + 911218811*x^276 + 208748481*x^275 + 725176545*x^274 + 765151044*x^273 + 939495648*x^272 + 550038893*x^271 + 905707993*x^270 + 267107699*x^269 + 477779883*x^268 + 251985659*x^267 + 754082836*x^266 + 159569451*x^265 + 781616103*x^264 + 1098961576*x^263 + 1139687026*x^262 + 473401848*x^261 + 623689501*x^260 + 1012676202*x^259 + 76777202*x^258 + 170602576*x^257 + 266093330*x^256 + 732274753*x^255 + 193219366*x^254 + 610602682*x^253 + 749761392*x^252 + 536911921*x^251 + 1052883954*x^250 + 1139729422*x^249 + 617278363*x^248 + 603450863*x^247 + 877968049*x^246 + 1078543204*x^245 + 441578327*x^244 + 821469144*x^243 + 1083268726*x^242 + 592074734*x^241 + 431251183*x^240 + 1151073027*x^239 + 596034003*x^238 + 507176703*x^237 + 638155464*x^236 + 820097610*x^235 + 69713965*x^234 + 111089281*x^233 + 403306683*x^232 + 417322569*x^231 + 510992488*x^230 + 406068742*x^229 + 487323397*x^228 + 1105866147*x^227 + 126043214*x^226 + 565379393*x^225 + 774566507*x^224 + 94477834*x^223 + 301787901*x^222 + 891557978*x^221 + 246179873*x^220 + 76065360*x^219 + 632831219*x^218 + 967852970*x^217 + 982932236*x^216 + 457056482*x^215 + 611696056*x^214 + 187879254*x^213 + 919970751*x^212 + 726626422*x^211 + 744906999*x^210 + 514152204*x^209 + 400846913*x^208 + 1057213516*x^207 + 458393393*x^206 + 39867352*x^205 + 482474421*x^204 + 1017159775*x^203 + 1127386440*x^202 + 186890818*x^201 + 297371952*x^200 + 827010510*x^199 + 457757189*x^198 + 120047360*x^197 + 403406161*x^196 + 561776540*x^195 + 269984973*x^194 + 1105865523*x^193 + 356682370*x^192 + 521018201*x^191 + 714326305*x^190 + 230112489*x^189 + 468954949*x^188 + 428412182*x^187 + 418097923*x^186 + 648421330*x^185 + 119412602*x^184 + 1029175202*x^183 + 961854350*x^182 + 359274957*x^181 + 918516748*x^180 + 393392054*x^179 + 998769881*x^178 + 713880369*x^177 + 23918875*x^176 + 19140072*x^175 + 296443203*x^174 + 1036511543*x^173 + 208417465*x^172 + 856221174*x^171 + 724608949*x^170 + 1148614286*x^169 + 605394185*x^168 + 1037184954*x^167 + 1149508482*x^166 + 748219008*x^165 + 762595570*x^164 + 240812860*x^163 + 221590855*x^162 + 921277317*x^161 + 666749995*x^160 + 270085731*x^159 + 719780654*x^158 + 1023109552*x^157 + 948736441*x^156 + 942460534*x^155 + 1190076672*x^154 + 298412436*x^153 + 146236637*x^152 + 136974417*x^151 + 247369427*x^150 + 1164600849*x^149 + 80725190*x^148 + 563971590*x^147 + 838975230*x^146 + 605884308*x^145 + 695738052*x^144 + 457993644*x^143 + 608089160*x^142 + 279768415*x^141 + 167776427*x^140 + 99830319*x^139 + 724761513*x^138 + 838344856*x^137 + 349705095*x^136 + 700591961*x^135 + 495192008*x^134 + 166834844*x^133 + 829383641*x^132 + 689577635*x^131 + 1063098370*x^130 + 1217658142*x^129 + 210005674*x^128 + 709445493*x^127 + 890260692*x^126 + 11818873*x^125 + 356866298*x^124 + 657354178*x^123 + 1083325742*x^122 + 256937537*x^121 + 832141251*x^120 + 738779202*x^119 + 531375449*x^118 + 570407521*x^117 + 253499493*x^116 + 936295735*x^115 + 840539077*x^114 + 1108243632*x^113 + 518037787*x^112 + 512681158*x^111 + 659791034*x^110 + 615039004*x^109 + 6475754*x^108 + 112655504*x^107 + 135513268*x^106 + 814830817*x^105 + 312451349*x^104 + 459204360*x^103 + 536270797*x^102 + 487599107*x^101 + 995873996*x^100 + 947176358*x^99 + 161110841*x^98 + 1215850742*x^97 + 828031021*x^96 + 393857015*x^95 + 483165571*x^94 + 1169422374*x^93 + 185485308*x^92 + 1113820447*x^91 + 1217012548*x^90 + 591690262*x^89 + 230984245*x^88 + 1183186281*x^87 + 984746087*x^86 + 321334226*x^85 + 356396152*x^84 + 812358214*x^83 + 652862462*x^82 + 1159946831*x^81 + 1185692555*x^80 + 1101691161*x^79 + 1162783803*x^78 + 592033894*x^77 + 545367197*x^76 + 441688164*x^75 + 169491076*x^74 + 181297517*x^73 + 590332818*x^72 + 814337101*x^71 + 1148316386*x^70 + 700258144*x^69 + 719201877*x^68 + 1160695934*x^67 + 1186868159*x^66 + 508542038*x^65 + 1113702100*x^64 + 921032142*x^63 + 758636144*x^62 + 890540800*x^61 + 136808203*x^60 + 74886413*x^59 + 156077420*x^58 + 925473910*x^57 + 111404286*x^56 + 355116767*x^55 + 468038980*x^54 + 89708844*x^53 + 878616521*x^52 + 1154657871*x^51 + 677831135*x^50 + 903468800*x^49 + 890557208*x^48 + 1035114476*x^47 + 198189399*x^46 + 864375452*x^45 + 1164916963*x^44 + 929627324*x^43 + 418711325*x^42 + 97430691*x^41 + 1172413774*x^40 + 760600756*x^39 + 943281805*x^38 + 53033182*x^37 + 123566782*x^36 + 665472336*x^35 + 521103310*x^34 + 892876972*x^33 + 169828417*x^32 + 315862403*x^31 + 973295601*x^30 + 1036868940*x^29 + 469235131*x^28 + 1097609240*x^27 + 446027303*x^26 + 356219098*x^25 + 480790123*x^24 + 94742566*x^23 + 691728720*x^22 + 922852954*x^21 + 21648854*x^20 + 903452116*x^19 + 1043050543*x^18 + 867501915*x^17 + 402312961*x^16 + 772349320*x^15 + 806410607*x^14 + 573402289*x^13 + 103888540*x^12 + 147927873*x^11 + 1005161156*x^10 + 988774771*x^9 + 682875980*x^8 + 54946232*x^7 + 717143945*x^6 + 323577100*x^5 + 803064428*x^4 + 598462622*x^3 + 1110253556*x^2 + 764371182*x + 634648371
# 735531500*x^1023 + 684755229*x^1022 + 978579144*x^1021 + 560225565*x^1020 + 758090578*x^1019 + 367477932*x^1018 + 326779415*x^1017 + 26800946*x^1016 + 199017905*x^1015 + 1156874439*x^1014 + 673969262*x^1013 + 617169647*x^1012 + 462256026*x^1011 + 303059784*x^1010 + 663728970*x^1009 + 376865711*x^1008 + 830705685*x^1007 + 573964358*x^1006 + 1210202059*x^1005 + 269197755*x^1004 + 586236496*x^1003 + 621987820*x^1002 + 485567868*x^1001 + 305700227*x^1000 + 1052698462*x^999 + 86861550*x^998 + 44767901*x^997 + 410897986*x^996 + 212344404*x^995 + 336381747*x^994 + 398182335*x^993 + 660275371*x^992 + 52728322*x^991 + 1193103469*x^990 + 684295535*x^989 + 1029981794*x^988 + 1051866415*x^987 + 418681909*x^986 + 976794520*x^985 + 1180496804*x^984 + 438513041*x^983 + 822843942*x^982 + 1119264881*x^981 + 790873853*x^980 + 1146506838*x^979 + 27016797*x^978 + 1149126201*x^977 + 967895459*x^976 + 1201841165*x^975 + 264216641*x^974 + 751855165*x^973 + 277480010*x^972 + 955969328*x^971 + 784721168*x^970 + 696371212*x^969 + 401164998*x^968 + 654719011*x^967 + 785183205*x^966 + 79070435*x^965 + 1140562925*x^964 + 1025154340*x^963 + 1044315421*x^962 + 392734282*x^961 + 234286141*x^960 + 962551866*x^959 + 133742245*x^958 + 998056106*x^957 + 781318236*x^956 + 23528574*x^955 + 1214036424*x^954 + 296666931*x^953 + 1211729921*x^952 + 561550286*x^951 + 634392845*x^950 + 422332555*x^949 + 765556851*x^948 + 1151849524*x^947 + 305981530*x^946 + 246290056*x^945 + 24304550*x^944 + 477073522*x^943 + 416104453*x^942 + 898162013*x^941 + 611609496*x^940 + 445765799*x^939 + 430180169*x^938 + 1151421310*x^937 + 439515367*x^936 + 795257572*x^935 + 578106992*x^934 + 929259980*x^933 + 550407102*x^932 + 1219047347*x^931 + 15972593*x^930 + 515513177*x^929 + 679675449*x^928 + 914537835*x^927 + 156230965*x^926 + 385558312*x^925 + 1036365654*x^924 + 1098274877*x^923 + 348628203*x^922 + 1093802915*x^921 + 1162728002*x^920 + 200502246*x^919 + 551049082*x^918 + 969116717*x^917 + 1127382445*x^916 + 968172543*x^915 + 346881523*x^914 + 41744706*x^913 + 335042561*x^912 + 593895276*x^911 + 15888292*x^910 + 324866127*x^909 + 937351605*x^908 + 347255852*x^907 + 1120419679*x^906 + 249832197*x^905 + 896923860*x^904 + 129801128*x^903 + 207849052*x^902 + 386825059*x^901 + 823406098*x^900 + 977635408*x^899 + 108813100*x^898 + 561865827*x^897 + 718000532*x^896 + 48090035*x^895 + 832337939*x^894 + 1084389292*x^893 + 793335438*x^892 + 1095245016*x^891 + 1080787282*x^890 + 122666287*x^889 + 937313249*x^888 + 62818846*x^887 + 1170462486*x^886 + 182439366*x^885 + 792906343*x^884 + 1205386767*x^883 + 310389549*x^882 + 603676058*x^881 + 671251954*x^880 + 640345010*x^879 + 1087374504*x^878 + 119769446*x^877 + 135989573*x^876 + 880703983*x^875 + 613578242*x^874 + 1207874966*x^873 + 972002390*x^872 + 644470053*x^871 + 335762119*x^870 + 1079917808*x^869 + 1023711373*x^868 + 861485470*x^867 + 230979333*x^866 + 683284149*x^865 + 645804102*x^864 + 577971621*x^863 + 33779989*x^862 + 915467237*x^861 + 834966216*x^860 + 445758874*x^859 + 685228217*x^858 + 979609284*x^857 + 842509205*x^856 + 221373358*x^855 + 150166201*x^854 + 927937340*x^853 + 995054125*x^852 + 704623324*x^851 + 1112892592*x^850 + 782816865*x^849 + 878518510*x^848 + 391872241*x^847 + 30062686*x^846 + 108900016*x^845 + 1034780269*x^844 + 1190084541*x^843 + 441686497*x^842 + 117953957*x^841 + 840802549*x^840 + 903238790*x^839 + 551715093*x^838 + 539420097*x^837 + 1007110444*x^836 + 673864283*x^835 + 756402005*x^834 + 197892310*x^833 + 981720851*x^832 + 798897509*x^831 + 1127242378*x^830 + 666754217*x^829 + 685248618*x^828 + 327773092*x^827 + 390697118*x^826 + 912223373*x^825 + 482947333*x^824 + 1110169857*x^823 + 780612147*x^822 + 194698743*x^821 + 716386043*x^820 + 424946693*x^819 + 22701975*x^818 + 293011366*x^817 + 947695756*x^816 + 1188483932*x^815 + 1002073886*x^814 + 1078210750*x^813 + 1127684166*x^812 + 719332394*x^811 + 1072532713*x^810 + 550629553*x^809 + 188195613*x^808 + 614412704*x^807 + 649960359*x^806 + 1010011298*x^805 + 824975518*x^804 + 311757403*x^803 + 93674481*x^802 + 380323800*x^801 + 1086623904*x^800 + 240170088*x^799 + 956396081*x^798 + 939969890*x^797 + 131843464*x^796 + 1045744996*x^795 + 424359277*x^794 + 550616456*x^793 + 1061637035*x^792 + 444548551*x^791 + 677546521*x^790 + 149605032*x^789 + 829567560*x^788 + 516053142*x^787 + 1191529914*x^786 + 294270928*x^785 + 142024389*x^784 + 584911191*x^783 + 307856659*x^782 + 81514660*x^781 + 543784156*x^780 + 108008163*x^779 + 13154295*x^778 + 155266054*x^777 + 663702892*x^776 + 782494602*x^775 + 747547833*x^774 + 242456376*x^773 + 669844220*x^772 + 552894098*x^771 + 1036366706*x^770 + 1074841665*x^769 + 720745418*x^768 + 1137936670*x^767 + 840875363*x^766 + 476498840*x^765 + 1088669461*x^764 + 1249649*x^763 + 882277578*x^762 + 37842126*x^761 + 398977801*x^760 + 328296234*x^759 + 536342859*x^758 + 608139240*x^757 + 897424944*x^756 + 76562916*x^755 + 428081420*x^754 + 627420927*x^753 + 265131678*x^752 + 1034443577*x^751 + 177902661*x^750 + 490977141*x^749 + 1084536775*x^748 + 1189221123*x^747 + 854191429*x^746 + 952038058*x^745 + 891288300*x^744 + 929356576*x^743 + 223874272*x^742 + 220297702*x^741 + 1099283305*x^740 + 1008574448*x^739 + 619949004*x^738 + 747199791*x^737 + 760703880*x^736 + 7682727*x^735 + 88566484*x^734 + 733742620*x^733 + 381443925*x^732 + 799269923*x^731 + 233342676*x^730 + 1205696983*x^729 + 765306727*x^728 + 29342855*x^727 + 287728251*x^726 + 214358216*x^725 + 355991367*x^724 + 344973841*x^723 + 436344093*x^722 + 547944829*x^721 + 1041405031*x^720 + 368771692*x^719 + 37426577*x^718 + 502936636*x^717 + 732825913*x^716 + 518778589*x^715 + 561797784*x^714 + 773068766*x^713 + 75615306*x^712 + 668933267*x^711 + 628975723*x^710 + 1140697439*x^709 + 108807342*x^708 + 283945737*x^707 + 701674528*x^706 + 1120373548*x^705 + 421627231*x^704 + 260846853*x^703 + 292537012*x^702 + 583513440*x^701 + 609720259*x^700 + 831373721*x^699 + 1126099385*x^698 + 431095431*x^697 + 296863241*x^696 + 371013827*x^695 + 549980853*x^694 + 550174635*x^693 + 620963563*x^692 + 952040422*x^691 + 1150044500*x^690 + 893175261*x^689 + 1139857784*x^688 + 972717568*x^687 + 735672517*x^686 + 1177501026*x^685 + 765934764*x^684 + 710762091*x^683 + 871268519*x^682 + 969318271*x^681 + 286261161*x^680 + 65128931*x^679 + 1100922672*x^678 + 47619662*x^677 + 981578224*x^676 + 67232154*x^675 + 1928142*x^674 + 817643007*x^673 + 675713298*x^672 + 185236805*x^671 + 331446457*x^670 + 129023118*x^669 + 431426370*x^668 + 1154277684*x^667 + 723182950*x^666 + 1144823093*x^665 + 822001162*x^664 + 356099532*x^663 + 705989193*x^662 + 878712048*x^661 + 1095044481*x^660 + 332193401*x^659 + 613329359*x^658 + 673744151*x^657 + 808080280*x^656 + 225562949*x^655 + 185686220*x^654 + 742469973*x^653 + 986152315*x^652 + 13611550*x^651 + 535747170*x^650 + 233786507*x^649 + 27955348*x^648 + 1004446959*x^647 + 1071164149*x^646 + 265258708*x^645 + 63221383*x^644 + 682228580*x^643 + 867131152*x^642 + 997600620*x^641 + 993922001*x^640 + 693252545*x^639 + 865655581*x^638 + 518295141*x^637 + 902072633*x^636 + 704953646*x^635 + 587251157*x^634 + 99168972*x^633 + 1105480730*x^632 + 1040404159*x^631 + 436113220*x^630 + 152714904*x^629 + 697469981*x^628 + 1185372838*x^627 + 216027999*x^626 + 616083931*x^625 + 399419685*x^624 + 23193568*x^623 + 1174129641*x^622 + 75724376*x^621 + 570399858*x^620 + 754947446*x^619 + 1037864447*x^618 + 794730343*x^617 + 60369472*x^616 + 750769016*x^615 + 61444481*x^614 + 333194445*x^613 + 1109236037*x^612 + 513379869*x^611 + 706807998*x^610 + 999669914*x^609 + 1198194959*x^608 + 336044172*x^607 + 402719207*x^606 + 1050007981*x^605 + 429464593*x^604 + 679293134*x^603 + 734513317*x^602 + 838385265*x^601 + 990800608*x^600 + 1162093896*x^599 + 173467508*x^598 + 123947890*x^597 + 325712596*x^596 + 1049522320*x^595 + 1072653958*x^594 + 565759817*x^593 + 549918485*x^592 + 574268523*x^591 + 1052593520*x^590 + 474323970*x^589 + 262787725*x^588 + 1091470590*x^587 + 782664905*x^586 + 1201833996*x^585 + 808712564*x^584 + 619522329*x^583 + 233329446*x^582 + 730502283*x^581 + 1017501853*x^580 + 306080194*x^579 + 283641594*x^578 + 195324593*x^577 + 1116741123*x^576 + 289439631*x^575 + 206064600*x^574 + 280021778*x^573 + 425409216*x^572 + 1107952582*x^571 + 131800177*x^570 + 106903346*x^569 + 72306234*x^568 + 934072451*x^567 + 242740893*x^566 + 106611451*x^565 + 429378634*x^564 + 127624569*x^563 + 587315789*x^562 + 932709753*x^561 + 523886142*x^560 + 110330665*x^559 + 963244036*x^558 + 227339325*x^557 + 185882207*x^556 + 987833442*x^555 + 981380006*x^554 + 1140813804*x^553 + 538704418*x^552 + 842520362*x^551 + 597627400*x^550 + 165232274*x^549 + 900076209*x^548 + 311342603*x^547 + 477271753*x^546 + 1072907066*x^545 + 1066126181*x^544 + 791702251*x^543 + 623246063*x^542 + 1082681410*x^541 + 759396967*x^540 + 878108937*x^539 + 724607060*x^538 + 79223685*x^537 + 307312027*x^536 + 234246571*x^535 + 330319932*x^534 + 274254378*x^533 + 1082820468*x^532 + 68920838*x^531 + 1195376541*x^530 + 170971307*x^529 + 399525324*x^528 + 238798853*x^527 + 664426862*x^526 + 269949285*x^525 + 698202786*x^524 + 88964561*x^523 + 635539315*x^522 + 1016514687*x^521 + 122364467*x^520 + 1095096646*x^519 + 513834099*x^518 + 672478524*x^517 + 47526709*x^516 + 48782616*x^515 + 166225959*x^514 + 810099682*x^513 + 168540411*x^512 + 30055377*x^511 + 817325819*x^510 + 202717189*x^509 + 739906349*x^508 + 186072589*x^507 + 451966755*x^506 + 684027658*x^505 + 251331059*x^504 + 591972494*x^503 + 289197098*x^502 + 829928406*x^501 + 160528626*x^500 + 90951219*x^499 + 496118642*x^498 + 117818178*x^497 + 215417436*x^496 + 937904122*x^495 + 962080493*x^494 + 423647737*x^493 + 1094089608*x^492 + 97559711*x^491 + 412409151*x^490 + 1039695658*x^489 + 461079746*x^488 + 564664118*x^487 + 2231630*x^486 + 667569567*x^485 + 471400483*x^484 + 691739455*x^483 + 146641223*x^482 + 445509678*x^481 + 788647561*x^480 + 100316571*x^479 + 927803124*x^478 + 225739054*x^477 + 339283562*x^476 + 741552554*x^475 + 674303545*x^474 + 610706793*x^473 + 1045437706*x^472 + 758427998*x^471 + 518677374*x^470 + 1020530386*x^469 + 81672436*x^468 + 684553666*x^467 + 36416557*x^466 + 1083076029*x^465 + 63903696*x^464 + 655765095*x^463 + 464055997*x^462 + 874368360*x^461 + 909538282*x^460 + 1084815716*x^459 + 971305398*x^458 + 504958756*x^457 + 941782746*x^456 + 410981017*x^455 + 44463213*x^454 + 57796260*x^453 + 633624768*x^452 + 902476625*x^451 + 1190884714*x^450 + 30960289*x^449 + 698111360*x^448 + 507015564*x^447 + 595305556*x^446 + 1170147546*x^445 + 595449153*x^444 + 1132050715*x^443 + 566093951*x^442 + 1125890381*x^441 + 864044563*x^440 + 608408253*x^439 + 128031905*x^438 + 951152598*x^437 + 41054884*x^436 + 1012755213*x^435 + 1091670374*x^434 + 481898210*x^433 + 1007980179*x^432 + 43301236*x^431 + 6478999*x^430 + 1175215424*x^429 + 597862715*x^428 + 441537430*x^427 + 339705054*x^426 + 289227345*x^425 + 795113772*x^424 + 404870950*x^423 + 997272819*x^422 + 634256255*x^421 + 453060086*x^420 + 821493547*x^419 + 842289852*x^418 + 223251279*x^417 + 929721613*x^416 + 63980045*x^415 + 298369623*x^414 + 1026287144*x^413 + 979092254*x^412 + 1182904024*x^411 + 298048453*x^410 + 653297794*x^409 + 365769179*x^408 + 45373617*x^407 + 7228243*x^406 + 1086374067*x^405 + 389455721*x^404 + 992518297*x^403 + 433929335*x^402 + 1149626197*x^401 + 90006250*x^400 + 1011632630*x^399 + 940906615*x^398 + 564772117*x^397 + 692974220*x^396 + 561321375*x^395 + 1095715303*x^394 + 1006114558*x^393 + 95516055*x^392 + 640816811*x^391 + 869737844*x^390 + 248741996*x^389 + 101754352*x^388 + 253268107*x^387 + 593472036*x^386 + 627778298*x^385 + 801877646*x^384 + 286581226*x^383 + 645931883*x^382 + 373119745*x^381 + 461109006*x^380 + 594214135*x^379 + 751634451*x^378 + 706229440*x^377 + 247985412*x^376 + 993987710*x^375 + 618989435*x^374 + 600506682*x^373 + 179955505*x^372 + 956234357*x^371 + 1049030902*x^370 + 727597507*x^369 + 1196607714*x^368 + 610634244*x^367 + 619865634*x^366 + 849131167*x^365 + 1094185730*x^364 + 685353152*x^363 + 299082549*x^362 + 1076769237*x^361 + 792938001*x^360 + 885082721*x^359 + 1198739364*x^358 + 273154602*x^357 + 597517874*x^356 + 351418158*x^355 + 621945565*x^354 + 949756104*x^353 + 1020290901*x^352 + 315372660*x^351 + 291246927*x^350 + 1016861207*x^349 + 171467993*x^348 + 1074074496*x^347 + 660775696*x^346 + 562891589*x^345 + 258618000*x^344 + 521058831*x^343 + 152819838*x^342 + 1141330990*x^341 + 383408903*x^340 + 677850803*x^339 + 165908062*x^338 + 66975904*x^337 + 510786934*x^336 + 32306220*x^335 + 708115806*x^334 + 474352780*x^333 + 963188335*x^332 + 151844162*x^331 + 907339624*x^330 + 456166118*x^329 + 111742252*x^328 + 318018829*x^327 + 624012970*x^326 + 255354390*x^325 + 1218329311*x^324 + 375000855*x^323 + 54956044*x^322 + 13543809*x^321 + 671163260*x^320 + 226676913*x^319 + 1193470867*x^318 + 477161216*x^317 + 519506783*x^316 + 748987057*x^315 + 768531367*x^314 + 327816599*x^313 + 59056092*x^312 + 520958252*x^311 + 243337260*x^310 + 608632530*x^309 + 65258636*x^308 + 1012579720*x^307 + 400176357*x^306 + 104583966*x^305 + 1114827176*x^304 + 70705682*x^303 + 5320656*x^302 + 1207465008*x^301 + 1211372826*x^300 + 886104873*x^299 + 747144635*x^298 + 227753814*x^297 + 427912588*x^296 + 425232985*x^295 + 135219277*x^294 + 541439233*x^293 + 82586191*x^292 + 1024575564*x^291 + 408418547*x^290 + 1076407665*x^289 + 184646604*x^288 + 894569780*x^287 + 730742386*x^286 + 473643018*x^285 + 561906151*x^284 + 582231889*x^283 + 928617667*x^282 + 460594931*x^281 + 946340582*x^280 + 881007408*x^279 + 655553538*x^278 + 107738502*x^277 + 958107338*x^276 + 874269820*x^275 + 689734430*x^274 + 1025286771*x^273 + 809509338*x^272 + 126580761*x^271 + 425724981*x^270 + 91398446*x^269 + 915486182*x^268 + 750598785*x^267 + 331692120*x^266 + 266239686*x^265 + 41813860*x^264 + 1003196915*x^263 + 1006275694*x^262 + 958171508*x^261 + 387655573*x^260 + 529686749*x^259 + 2533683*x^258 + 851532040*x^257 + 515865631*x^256 + 331149910*x^255 + 1058283457*x^254 + 478391568*x^253 + 1020601120*x^252 + 193954604*x^251 + 125558467*x^250 + 916367669*x^249 + 965664721*x^248 + 737411958*x^247 + 145954639*x^246 + 787702411*x^245 + 256023548*x^244 + 831752864*x^243 + 637799028*x^242 + 202325459*x^241 + 189858829*x^240 + 221236168*x^239 + 276967229*x^238 + 732958371*x^237 + 31622618*x^236 + 558911372*x^235 + 257580689*x^234 + 490167674*x^233 + 1164269554*x^232 + 765931664*x^231 + 89716985*x^230 + 639008878*x^229 + 716033538*x^228 + 186948569*x^227 + 870251868*x^226 + 383121640*x^225 + 604362204*x^224 + 405526662*x^223 + 127371887*x^222 + 543669202*x^221 + 823112915*x^220 + 523517382*x^219 + 791437322*x^218 + 1069279817*x^217 + 960628355*x^216 + 1012582276*x^215 + 1200088601*x^214 + 927011022*x^213 + 830570829*x^212 + 700668365*x^211 + 1205573850*x^210 + 276778781*x^209 + 786305215*x^208 + 928215922*x^207 + 154393796*x^206 + 169298902*x^205 + 177646296*x^204 + 173339370*x^203 + 287217637*x^202 + 1077403939*x^201 + 1004965535*x^200 + 677352462*x^199 + 545192340*x^198 + 464170452*x^197 + 381853900*x^196 + 205643848*x^195 + 973330672*x^194 + 1148733662*x^193 + 458436519*x^192 + 68604889*x^191 + 193530886*x^190 + 141661386*x^189 + 1117183144*x^188 + 153035244*x^187 + 830892599*x^186 + 795500906*x^185 + 67041425*x^184 + 617209634*x^183 + 180547177*x^182 + 1183445159*x^181 + 303603618*x^180 + 842724764*x^179 + 784982658*x^178 + 1199356684*x^177 + 321497016*x^176 + 513738925*x^175 + 465949450*x^174 + 981246204*x^173 + 814398377*x^172 + 950247970*x^171 + 720838080*x^170 + 399493165*x^169 + 735365971*x^168 + 109745845*x^167 + 897998838*x^166 + 547497972*x^165 + 174675208*x^164 + 716115074*x^163 + 237209800*x^162 + 186394653*x^161 + 876995839*x^160 + 1187252196*x^159 + 819282320*x^158 + 44596523*x^157 + 679033559*x^156 + 736746236*x^155 + 1184916922*x^154 + 451294643*x^153 + 443590366*x^152 + 304384335*x^151 + 1064695584*x^150 + 602535518*x^149 + 684486124*x^148 + 863476315*x^147 + 496170722*x^146 + 737062216*x^145 + 285799611*x^144 + 1085153158*x^143 + 247783563*x^142 + 1208043659*x^141 + 208776666*x^140 + 117730360*x^139 + 279620264*x^138 + 273045622*x^137 + 893971194*x^136 + 240743423*x^135 + 1143029271*x^134 + 326725356*x^133 + 294174585*x^132 + 672819095*x^131 + 138843366*x^130 + 1176670148*x^129 + 573825049*x^128 + 835249905*x^127 + 778468469*x^126 + 300257393*x^125 + 409352854*x^124 + 953527813*x^123 + 653640743*x^122 + 1210615840*x^121 + 596684403*x^120 + 46012813*x^119 + 510765516*x^118 + 1213476223*x^117 + 1132779740*x^116 + 769195645*x^115 + 963749389*x^114 + 843804183*x^113 + 109759209*x^112 + 493130294*x^111 + 1122857844*x^110 + 1130618881*x^109 + 648465049*x^108 + 364595574*x^107 + 410134064*x^106 + 597836905*x^105 + 831243271*x^104 + 226275998*x^103 + 686704033*x^102 + 662011231*x^101 + 112226051*x^100 + 623946037*x^99 + 469742204*x^98 + 369854172*x^97 + 731154062*x^96 + 352916654*x^95 + 45991298*x^94 + 614913911*x^93 + 632337602*x^92 + 327529986*x^91 + 111251878*x^90 + 657089210*x^89 + 499853920*x^88 + 966818975*x^87 + 454584975*x^86 + 116582431*x^85 + 619242494*x^84 + 455382561*x^83 + 246350547*x^82 + 495191129*x^81 + 900852972*x^80 + 264825752*x^79 + 426813960*x^78 + 478124215*x^77 + 1080567657*x^76 + 858353771*x^75 + 215115660*x^74 + 963682245*x^73 + 964445096*x^72 + 73603206*x^71 + 734630202*x^70 + 199652522*x^69 + 520021635*x^68 + 763256200*x^67 + 861482624*x^66 + 890485659*x^65 + 523362913*x^64 + 785087110*x^63 + 381314881*x^62 + 843850504*x^61 + 61951613*x^60 + 119100925*x^59 + 531827488*x^58 + 199818669*x^57 + 592207491*x^56 + 354682041*x^55 + 1015447358*x^54 + 328324806*x^53 + 24880841*x^52 + 516663598*x^51 + 716706066*x^50 + 1042483154*x^49 + 331433641*x^48 + 929901382*x^47 + 502140671*x^46 + 48123362*x^45 + 1112586174*x^44 + 14618102*x^43 + 764832169*x^42 + 446768463*x^41 + 920421919*x^40 + 491851586*x^39 + 24718814*x^38 + 83091454*x^37 + 155770396*x^36 + 12824441*x^35 + 954371888*x^34 + 318592841*x^33 + 788251579*x^32 + 246435934*x^31 + 387083299*x^30 + 395226231*x^29 + 646811732*x^28 + 1131418388*x^27 + 1135116504*x^26 + 986902782*x^25 + 323457413*x^24 + 521885110*x^23 + 234655676*x^22 + 965166497*x^21 + 755967054*x^20 + 574743395*x^19 + 1175664410*x^18 + 117322371*x^17 + 794664856*x^16 + 570463*x^15 + 1148572518*x^14 + 439320220*x^13 + 815953366*x^12 + 389050726*x^11 + 1167287391*x^10 + 397052468*x^9 + 275572458*x^8 + 548665509*x^7 + 1202175986*x^6 + 518662014*x^5 + 1084425257*x^4 + 7854568*x^3 + 274607457*x^2 + 162444786*x + 410560230

比赛时没怎么看这道题，后续来复现一下。

这题属于RLWE，环和方程为：

$$R=\frac{Z_q[x]}{x^{1024}-1}$$ $$b=as+e$$

$s$向量为ASCII，比较小，可以作为LLL求解的短向量。

这个题如果直接套RLWE模板，发现格的维度过于大，解不出来。发现$s$向量只有$64$个低位不为$0$，其他位全为$0$，可以利用这个特点去解。

可以把多项式按照$s$的特点来切分：

$$(b_0|b_1)\equiv (s_0|0)\begin{bmatrix} A_0&A_1\\ A_2&A_3\\ \end{bmatrix} +(e_0|e_1) \pmod q$$

这里的$A$是RLWE的卷积矩阵：

$$\left( \begin{matrix} a_0 &a_1 &a_2 &\cdots &a_{n-1}\\ a_{n-1}&a_0 &a_1 &\cdots &a_{n-2}\\ a_{n-2}&a_{n-1}&a_0 &\cdots &a_{n-3}\\ \vdots &\vdots &\vdots&\ddots &\vdots\\ a_1 &a_2 &a_3 &\cdots &a_0\\ \end{matrix} \right)$$

可以发现，由于零向量的引入，可以消除$A_2,A_3$：

$$(b_0|b_1)\equiv s_0\begin{bmatrix} A_0&A_1\\ \end{bmatrix} +(e_0|e_1) \pmod q$$

相当于最终我们只需求出$s_0$，可以省去一些多余部分$A_1$，对应消去其他项，进一步化简式子：

$$b_0\equiv s_0A_0 +e_0 \pmod q$$

接下来就是构造RLWE的格直接解就可以了，上一个改的模板：

a = 216047404*x^1023 + 1008199117*x^1022 + 39562072*x^1021 + 189992355*x^1020 + 1087671639*x^1019 + 541371337*x^1018 + 1146044200*x^1017 + 212969175*x^1016 + 1114159572*x^1015 + 1112032860*x^1014 + 1204883609*x^1013 + 1181544913*x^1012 + 851496082*x^1011 + 222877006*x^1010 + 163176236*x^1009 + 268697504*x^1008 + 613151090*x^1007 + 1185245256*x^1006 + 215725010*x^1005 + 789898500*x^1004 + 1156619111*x^1003 + 610859911*x^1002 + 959814483*x^1001 + 684353251*x^1000 + 290850651*x^999 + 675880502*x^998 + 836239751*x^997 + 487296407*x^996 + 778816128*x^995 + 1013639221*x^994 + 189137575*x^993 + 172217836*x^992 + 572872008*x^991 + 865759581*x^990 + 399805736*x^989 + 394587004*x^988 + 633085719*x^987 + 15142893*x^986 + 461176831*x^985 + 1078060208*x^984 + 787396508*x^983 + 877420202*x^982 + 1121486845*x^981 + 146921816*x^980 + 670134387*x^979 + 574407635*x^978 + 1148395437*x^977 + 748514947*x^976 + 970442995*x^975 + 280085063*x^974 + 420670822*x^973 + 20159574*x^972 + 219680665*x^971 + 401202858*x^970 + 328444623*x^969 + 623312316*x^968 + 917712264*x^967 + 588061576*x^966 + 625482841*x^965 + 220929234*x^964 + 778461001*x^963 + 498203565*x^962 + 1055981771*x^961 + 70562147*x^960 + 931081750*x^959 + 93569863*x^958 + 314876311*x^957 + 932364613*x^956 + 1132016772*x^955 + 371703330*x^954 + 189301560*x^953 + 739232608*x^952 + 916695967*x^951 + 399818344*x^950 + 558604923*x^949 + 1092603913*x^948 + 987195616*x^947 + 665679589*x^946 + 1142632478*x^945 + 198797278*x^944 + 110832477*x^943 + 775688737*x^942 + 275416086*x^941 + 435656120*x^940 + 754150483*x^939 + 1024583186*x^938 + 972075461*x^937 + 1071060217*x^936 + 710789980*x^935 + 691361770*x^934 + 1097024307*x^933 + 862356288*x^932 + 354500195*x^931 + 158151296*x^930 + 733475281*x^929 + 215008492*x^928 + 151139272*x^927 + 1000425669*x^926 + 590964357*x^925 + 373950911*x^924 + 43038800*x^923 + 338044906*x^922 + 293954870*x^921 + 393479*x^920 + 555095359*x^919 + 418829106*x^918 + 95391760*x^917 + 897658305*x^916 + 1040609125*x^915 + 239948276*x^914 + 1190720461*x^913 + 160498737*x^912 + 394967890*x^911 + 104302686*x^910 + 48021969*x^909 + 761000569*x^908 + 356140410*x^907 + 225246587*x^906 + 79172445*x^905 + 975365689*x^904 + 1077396491*x^903 + 728717352*x^902 + 964273647*x^901 + 258781036*x^900 + 746930481*x^899 + 793742220*x^898 + 542128050*x^897 + 562413014*x^896 + 701216258*x^895 + 928704966*x^894 + 98656502*x^893 + 1016152774*x^892 + 140544845*x^891 + 226416702*x^890 + 309310359*x^889 + 519065123*x^888 + 346740110*x^887 + 116615122*x^886 + 990804519*x^885 + 208648062*x^884 + 605381435*x^883 + 821163414*x^882 + 864698754*x^881 + 424773230*x^880 + 1184139330*x^879 + 437390254*x^878 + 41435781*x^877 + 824197241*x^876 + 1181823353*x^875 + 354135255*x^874 + 921600154*x^873 + 972782404*x^872 + 304175744*x^871 + 976950586*x^870 + 561195955*x^869 + 840601911*x^868 + 848362310*x^867 + 698380233*x^866 + 703722831*x^865 + 527081934*x^864 + 996708932*x^863 + 926257884*x^862 + 113808466*x^861 + 111022399*x^860 + 336240881*x^859 + 281602555*x^858 + 456022351*x^857 + 303940681*x^856 + 1152960332*x^855 + 762827305*x^854 + 1097893502*x^853 + 1159492861*x^852 + 791288185*x^851 + 552596428*x^850 + 1160303133*x^849 + 855459983*x^848 + 870046128*x^847 + 412042730*x^846 + 527317697*x^845 + 118258027*x^844 + 1156090191*x^843 + 1184418516*x^842 + 736914609*x^841 + 1042440949*x^840 + 1118336201*x^839 + 692314475*x^838 + 888141647*x^837 + 611975215*x^836 + 112482309*x^835 + 774541929*x^834 + 877613260*x^833 + 218484596*x^832 + 744043072*x^831 + 1149426359*x^830 + 1086732941*x^829 + 218727414*x^828 + 111004493*x^827 + 48035668*x^826 + 1129753198*x^825 + 410088959*x^824 + 1186919074*x^823 + 291266088*x^822 + 622780685*x^821 + 908030149*x^820 + 152548456*x^819 + 970996704*x^818 + 643233117*x^817 + 97648457*x^816 + 167039372*x^815 + 451159004*x^814 + 21522258*x^813 + 446568222*x^812 + 97236135*x^811 + 601480363*x^810 + 896523050*x^809 + 635312918*x^808 + 771155729*x^807 + 727217487*x^806 + 1103325662*x^805 + 1145702253*x^804 + 111451279*x^803 + 709647761*x^802 + 155865734*x^801 + 788861657*x^800 + 25328658*x^799 + 387592047*x^798 + 631380316*x^797 + 195654331*x^796 + 379901017*x^795 + 110746571*x^794 + 821639667*x^793 + 1196705497*x^792 + 926725497*x^791 + 752090468*x^790 + 565928514*x^789 + 107924077*x^788 + 1035444397*x^787 + 389590222*x^786 + 746022468*x^785 + 1152494936*x^784 + 1047183126*x^783 + 935173423*x^782 + 237022259*x^781 + 68211471*x^780 + 682392084*x^779 + 900610142*x^778 + 659697118*x^777 + 381789469*x^776 + 895479393*x^775 + 342674862*x^774 + 1034152415*x^773 + 736863278*x^772 + 233824501*x^771 + 511543257*x^770 + 43539547*x^769 + 871109943*x^768 + 234226499*x^767 + 958639125*x^766 + 913885377*x^765 + 757234386*x^764 + 330354514*x^763 + 693659124*x^762 + 46757147*x^761 + 24910108*x^760 + 263754046*x^759 + 1007999117*x^758 + 569158879*x^757 + 781185896*x^756 + 328234792*x^755 + 1166796778*x^754 + 1023882729*x^753 + 1126014838*x^752 + 412948341*x^751 + 745762031*x^750 + 184601330*x^749 + 1195686854*x^748 + 226180761*x^747 + 813440273*x^746 + 198496604*x^745 + 646284299*x^744 + 775658802*x^743 + 1051631440*x^742 + 382010443*x^741 + 884529292*x^740 + 1171509241*x^739 + 148470016*x^738 + 545551560*x^737 + 895321797*x^736 + 990533556*x^735 + 1006826878*x^734 + 444425261*x^733 + 538658289*x^732 + 1201448839*x^731 + 813543244*x^730 + 866138640*x^729 + 992484781*x^728 + 797592952*x^727 + 5350520*x^726 + 1088776239*x^725 + 1011384293*x^724 + 202279961*x^723 + 580990742*x^722 + 608736084*x^721 + 592191483*x^720 + 603821965*x^719 + 686032966*x^718 + 309449994*x^717 + 997796743*x^716 + 323694959*x^715 + 404631321*x^714 + 684041814*x^713 + 954922509*x^712 + 17334061*x^711 + 1038027065*x^710 + 189030167*x^709 + 238786122*x^708 + 854157242*x^707 + 857322405*x^706 + 847505723*x^705 + 531600098*x^704 + 413144959*x^703 + 150862275*x^702 + 176120020*x^701 + 147651128*x^700 + 20961937*x^699 + 924892688*x^698 + 207889399*x^697 + 506289209*x^696 + 201657090*x^695 + 866897606*x^694 + 282950189*x^693 + 484625027*x^692 + 720969770*x^691 + 557487808*x^690 + 664292309*x^689 + 667236796*x^688 + 505039446*x^687 + 636507041*x^686 + 717904854*x^685 + 742491214*x^684 + 235380401*x^683 + 885103138*x^682 + 227708439*x^681 + 195450351*x^680 + 914408549*x^679 + 890140153*x^678 + 959662247*x^677 + 655663410*x^676 + 682768547*x^675 + 1063757282*x^674 + 776284911*x^673 + 1114588219*x^672 + 689022198*x^671 + 1160585767*x^670 + 784564493*x^669 + 599804982*x^668 + 954265199*x^667 + 1160092910*x^666 + 1178991310*x^665 + 610146522*x^664 + 589028938*x^663 + 972903553*x^662 + 933544074*x^661 + 910101746*x^660 + 1199479046*x^659 + 129564572*x^658 + 16630574*x^657 + 604268174*x^656 + 905616984*x^655 + 229755095*x^654 + 543777663*x^653 + 880642044*x^652 + 750742780*x^651 + 801027824*x^650 + 59869899*x^649 + 178293151*x^648 + 413473523*x^647 + 790966353*x^646 + 36947608*x^645 + 215402931*x^644 + 198271237*x^643 + 394503398*x^642 + 933396244*x^641 + 764498758*x^640 + 960831635*x^639 + 710558646*x^638 + 160491214*x^637 + 161213508*x^636 + 932611994*x^635 + 226519192*x^634 + 554464756*x^633 + 82595536*x^632 + 1144714763*x^631 + 361090580*x^630 + 747809061*x^629 + 114293244*x^628 + 253349999*x^627 + 1051279816*x^626 + 1079507344*x^625 + 864605458*x^624 + 1100098300*x^623 + 323233106*x^622 + 1070769430*x^621 + 1048471132*x^620 + 23281664*x^619 + 1099148878*x^618 + 812556000*x^617 + 452606567*x^616 + 892217880*x^615 + 741556204*x^614 + 37168552*x^613 + 286980867*x^612 + 1125383508*x^611 + 782814488*x^610 + 1214851511*x^609 + 270577673*x^608 + 364433480*x^607 + 825553809*x^606 + 589475297*x^605 + 293114041*x^604 + 1115978872*x^603 + 21831218*x^602 + 856821602*x^601 + 213782489*x^600 + 287159884*x^599 + 1015101950*x^598 + 494211644*x^597 + 38143731*x^596 + 882805771*x^595 + 721674528*x^594 + 120092153*x^593 + 636819567*x^592 + 365557574*x^591 + 619653423*x^590 + 1207892829*x^589 + 971282528*x^588 + 379459809*x^587 + 507124241*x^586 + 1050378769*x^585 + 113715629*x^584 + 841835564*x^583 + 1055649818*x^582 + 904319486*x^581 + 83232231*x^580 + 282044435*x^579 + 11563226*x^578 + 283283452*x^577 + 515932154*x^576 + 415242679*x^575 + 686396058*x^574 + 414011723*x^573 + 22692318*x^572 + 593039855*x^571 + 42054428*x^570 + 242713788*x^569 + 756543053*x^568 + 297264974*x^567 + 656668981*x^566 + 103185189*x^565 + 279211827*x^564 + 66472175*x^563 + 221289056*x^562 + 418547255*x^561 + 587378319*x^560 + 781217899*x^559 + 828907515*x^558 + 1026785730*x^557 + 936576598*x^556 + 914519864*x^555 + 458326840*x^554 + 846364356*x^553 + 1048948157*x^552 + 276890468*x^551 + 211463242*x^550 + 611009955*x^549 + 41350370*x^548 + 1120260432*x^547 + 1217213406*x^546 + 1096884636*x^545 + 107298827*x^544 + 556646889*x^543 + 514714957*x^542 + 592531623*x^541 + 1185635127*x^540 + 866796164*x^539 + 1199009440*x^538 + 760543377*x^537 + 135043128*x^536 + 1184521976*x^535 + 53368352*x^534 + 614063947*x^533 + 117184488*x^532 + 1090625549*x^531 + 928160285*x^530 + 1065640157*x^529 + 307397590*x^528 + 383318068*x^527 + 890835908*x^526 + 416986540*x^525 + 222852700*x^524 + 965323537*x^523 + 151764017*x^522 + 193722745*x^521 + 439803983*x^520 + 942882901*x^519 + 56286764*x^518 + 824204572*x^517 + 478793274*x^516 + 183238303*x^515 + 922253103*x^514 + 5444136*x^513 + 402856270*x^512 + 508652113*x^511 + 898341402*x^510 + 56743140*x^509 + 179078829*x^508 + 360574641*x^507 + 691533190*x^506 + 982373838*x^505 + 719429684*x^504 + 962339948*x^503 + 1097706834*x^502 + 682588935*x^501 + 1193566532*x^500 + 1140505780*x^499 + 1167874911*x^498 + 669408623*x^497 + 15348570*x^496 + 896129486*x^495 + 100671957*x^494 + 1015786650*x^493 + 605094306*x^492 + 704959137*x^491 + 503877361*x^490 + 546763047*x^489 + 281625173*x^488 + 874599768*x^487 + 187483443*x^486 + 791213383*x^485 + 670376251*x^484 + 484751013*x^483 + 519454749*x^482 + 898655062*x^481 + 1088862155*x^480 + 843442957*x^479 + 429341712*x^478 + 869408179*x^477 + 921648096*x^476 + 526019939*x^475 + 856290375*x^474 + 531710459*x^473 + 1135323038*x^472 + 222776023*x^471 + 223826994*x^470 + 782612384*x^469 + 208579370*x^468 + 809908930*x^467 + 802818642*x^466 + 1182584545*x^465 + 245518705*x^464 + 114792460*x^463 + 646248449*x^462 + 63969962*x^461 + 761908644*x^460 + 523665668*x^459 + 1131060959*x^458 + 507746193*x^457 + 215968166*x^456 + 186113215*x^455 + 1117740378*x^454 + 649175082*x^453 + 396834257*x^452 + 274002774*x^451 + 626055138*x^450 + 924423066*x^449 + 81357715*x^448 + 1042994674*x^447 + 380053163*x^446 + 687766657*x^445 + 414805559*x^444 + 1118153385*x^443 + 1196507975*x^442 + 223759358*x^441 + 808836890*x^440 + 558230978*x^439 + 470920831*x^438 + 313868031*x^437 + 696317665*x^436 + 38725962*x^435 + 722983488*x^434 + 982704221*x^433 + 931470025*x^432 + 658261117*x^431 + 1043739465*x^430 + 422603501*x^429 + 879856656*x^428 + 977082068*x^427 + 593021461*x^426 + 955543544*x^425 + 194004912*x^424 + 1057355064*x^423 + 1153279801*x^422 + 1104874965*x^421 + 1157109085*x^420 + 54358054*x^419 + 802241073*x^418 + 489376522*x^417 + 250441773*x^416 + 740903923*x^415 + 81493461*x^414 + 966046559*x^413 + 295086523*x^412 + 1192114766*x^411 + 1186654005*x^410 + 768853461*x^409 + 302013033*x^408 + 1127093874*x^407 + 401944628*x^406 + 463364841*x^405 + 277324527*x^404 + 357826211*x^403 + 302642912*x^402 + 785232813*x^401 + 1155455395*x^400 + 240939622*x^399 + 1090741169*x^398 + 941697407*x^397 + 1108935255*x^396 + 63027943*x^395 + 415750779*x^394 + 36046273*x^393 + 172429619*x^392 + 563533800*x^391 + 961503349*x^390 + 356454474*x^389 + 586712431*x^388 + 572728001*x^387 + 670855384*x^386 + 268877633*x^385 + 51139525*x^384 + 806328542*x^383 + 790061093*x^382 + 140256246*x^381 + 430118720*x^380 + 924612224*x^379 + 923573107*x^378 + 1124645882*x^377 + 1044890409*x^376 + 509180566*x^375 + 371227114*x^374 + 161843486*x^373 + 296514161*x^372 + 454272518*x^371 + 755779732*x^370 + 295567281*x^369 + 1063635155*x^368 + 46603670*x^367 + 112353112*x^366 + 571920305*x^365 + 484055586*x^364 + 148075787*x^363 + 700140701*x^362 + 922814151*x^361 + 198283677*x^360 + 806078101*x^359 + 1218701262*x^358 + 679274064*x^357 + 408382456*x^356 + 284971608*x^355 + 1072737570*x^354 + 999420946*x^353 + 704897365*x^352 + 1147239838*x^351 + 1148707218*x^350 + 119677974*x^349 + 139766009*x^348 + 289899118*x^347 + 3099746*x^346 + 478334394*x^345 + 671867092*x^344 + 1123276962*x^343 + 1053910974*x^342 + 776016929*x^341 + 408840884*x^340 + 702734268*x^339 + 101137143*x^338 + 157330682*x^337 + 608473559*x^336 + 355406102*x^335 + 1189624142*x^334 + 87874850*x^333 + 1097033743*x^332 + 984835279*x^331 + 133446104*x^330 + 990221835*x^329 + 34152703*x^328 + 902602955*x^327 + 564227604*x^326 + 378045277*x^325 + 330935315*x^324 + 300442927*x^323 + 504016276*x^322 + 592727454*x^321 + 1075766200*x^320 + 718996149*x^319 + 823573424*x^318 + 834215705*x^317 + 430497892*x^316 + 879722938*x^315 + 968236501*x^314 + 262764692*x^313 + 37503817*x^312 + 607855810*x^311 + 1173289902*x^310 + 906609932*x^309 + 11948749*x^308 + 948969610*x^307 + 1130417155*x^306 + 892108695*x^305 + 1040897188*x^304 + 174698274*x^303 + 85414336*x^302 + 758730292*x^301 + 615781943*x^300 + 1215130735*x^299 + 1168693743*x^298 + 1070287857*x^297 + 501559848*x^296 + 485147924*x^295 + 1218893131*x^294 + 923876087*x^293 + 565056561*x^292 + 282754375*x^291 + 794028720*x^290 + 288419549*x^289 + 688387454*x^288 + 40339086*x^287 + 659115548*x^286 + 614342861*x^285 + 391568544*x^284 + 464738754*x^283 + 28669498*x^282 + 1115640335*x^281 + 870635325*x^280 + 126237247*x^279 + 1111165998*x^278 + 205027579*x^277 + 911218811*x^276 + 208748481*x^275 + 725176545*x^274 + 765151044*x^273 + 939495648*x^272 + 550038893*x^271 + 905707993*x^270 + 267107699*x^269 + 477779883*x^268 + 251985659*x^267 + 754082836*x^266 + 159569451*x^265 + 781616103*x^264 + 1098961576*x^263 + 1139687026*x^262 + 473401848*x^261 + 623689501*x^260 + 1012676202*x^259 + 76777202*x^258 + 170602576*x^257 + 266093330*x^256 + 732274753*x^255 + 193219366*x^254 + 610602682*x^253 + 749761392*x^252 + 536911921*x^251 + 1052883954*x^250 + 1139729422*x^249 + 617278363*x^248 + 603450863*x^247 + 877968049*x^246 + 1078543204*x^245 + 441578327*x^244 + 821469144*x^243 + 1083268726*x^242 + 592074734*x^241 + 431251183*x^240 + 1151073027*x^239 + 596034003*x^238 + 507176703*x^237 + 638155464*x^236 + 820097610*x^235 + 69713965*x^234 + 111089281*x^233 + 403306683*x^232 + 417322569*x^231 + 510992488*x^230 + 406068742*x^229 + 487323397*x^228 + 1105866147*x^227 + 126043214*x^226 + 565379393*x^225 + 774566507*x^224 + 94477834*x^223 + 301787901*x^222 + 891557978*x^221 + 246179873*x^220 + 76065360*x^219 + 632831219*x^218 + 967852970*x^217 + 982932236*x^216 + 457056482*x^215 + 611696056*x^214 + 187879254*x^213 + 919970751*x^212 + 726626422*x^211 + 744906999*x^210 + 514152204*x^209 + 400846913*x^208 + 1057213516*x^207 + 458393393*x^206 + 39867352*x^205 + 482474421*x^204 + 1017159775*x^203 + 1127386440*x^202 + 186890818*x^201 + 297371952*x^200 + 827010510*x^199 + 457757189*x^198 + 120047360*x^197 + 403406161*x^196 + 561776540*x^195 + 269984973*x^194 + 1105865523*x^193 + 356682370*x^192 + 521018201*x^191 + 714326305*x^190 + 230112489*x^189 + 468954949*x^188 + 428412182*x^187 + 418097923*x^186 + 648421330*x^185 + 119412602*x^184 + 1029175202*x^183 + 961854350*x^182 + 359274957*x^181 + 918516748*x^180 + 393392054*x^179 + 998769881*x^178 + 713880369*x^177 + 23918875*x^176 + 19140072*x^175 + 296443203*x^174 + 1036511543*x^173 + 208417465*x^172 + 856221174*x^171 + 724608949*x^170 + 1148614286*x^169 + 605394185*x^168 + 1037184954*x^167 + 1149508482*x^166 + 748219008*x^165 + 762595570*x^164 + 240812860*x^163 + 221590855*x^162 + 921277317*x^161 + 666749995*x^160 + 270085731*x^159 + 719780654*x^158 + 1023109552*x^157 + 948736441*x^156 + 942460534*x^155 + 1190076672*x^154 + 298412436*x^153 + 146236637*x^152 + 136974417*x^151 + 247369427*x^150 + 1164600849*x^149 + 80725190*x^148 + 563971590*x^147 + 838975230*x^146 + 605884308*x^145 + 695738052*x^144 + 457993644*x^143 + 608089160*x^142 + 279768415*x^141 + 167776427*x^140 + 99830319*x^139 + 724761513*x^138 + 838344856*x^137 + 349705095*x^136 + 700591961*x^135 + 495192008*x^134 + 166834844*x^133 + 829383641*x^132 + 689577635*x^131 + 1063098370*x^130 + 1217658142*x^129 + 210005674*x^128 + 709445493*x^127 + 890260692*x^126 + 11818873*x^125 + 356866298*x^124 + 657354178*x^123 + 1083325742*x^122 + 256937537*x^121 + 832141251*x^120 + 738779202*x^119 + 531375449*x^118 + 570407521*x^117 + 253499493*x^116 + 936295735*x^115 + 840539077*x^114 + 1108243632*x^113 + 518037787*x^112 + 512681158*x^111 + 659791034*x^110 + 615039004*x^109 + 6475754*x^108 + 112655504*x^107 + 135513268*x^106 + 814830817*x^105 + 312451349*x^104 + 459204360*x^103 + 536270797*x^102 + 487599107*x^101 + 995873996*x^100 + 947176358*x^99 + 161110841*x^98 + 1215850742*x^97 + 828031021*x^96 + 393857015*x^95 + 483165571*x^94 + 1169422374*x^93 + 185485308*x^92 + 1113820447*x^91 + 1217012548*x^90 + 591690262*x^89 + 230984245*x^88 + 1183186281*x^87 + 984746087*x^86 + 321334226*x^85 + 356396152*x^84 + 812358214*x^83 + 652862462*x^82 + 1159946831*x^81 + 1185692555*x^80 + 1101691161*x^79 + 1162783803*x^78 + 592033894*x^77 + 545367197*x^76 + 441688164*x^75 + 169491076*x^74 + 181297517*x^73 + 590332818*x^72 + 814337101*x^71 + 1148316386*x^70 + 700258144*x^69 + 719201877*x^68 + 1160695934*x^67 + 1186868159*x^66 + 508542038*x^65 + 1113702100*x^64 + 921032142*x^63 + 758636144*x^62 + 890540800*x^61 + 136808203*x^60 + 74886413*x^59 + 156077420*x^58 + 925473910*x^57 + 111404286*x^56 + 355116767*x^55 + 468038980*x^54 + 89708844*x^53 + 878616521*x^52 + 1154657871*x^51 + 677831135*x^50 + 903468800*x^49 + 890557208*x^48 + 1035114476*x^47 + 198189399*x^46 + 864375452*x^45 + 1164916963*x^44 + 929627324*x^43 + 418711325*x^42 + 97430691*x^41 + 1172413774*x^40 + 760600756*x^39 + 943281805*x^38 + 53033182*x^37 + 123566782*x^36 + 665472336*x^35 + 521103310*x^34 + 892876972*x^33 + 169828417*x^32 + 315862403*x^31 + 973295601*x^30 + 1036868940*x^29 + 469235131*x^28 + 1097609240*x^27 + 446027303*x^26 + 356219098*x^25 + 480790123*x^24 + 94742566*x^23 + 691728720*x^22 + 922852954*x^21 + 21648854*x^20 + 903452116*x^19 + 1043050543*x^18 + 867501915*x^17 + 402312961*x^16 + 772349320*x^15 + 806410607*x^14 + 573402289*x^13 + 103888540*x^12 + 147927873*x^11 + 1005161156*x^10 + 988774771*x^9 + 682875980*x^8 + 54946232*x^7 + 717143945*x^6 + 323577100*x^5 + 803064428*x^4 + 598462622*x^3 + 1110253556*x^2 + 764371182*x + 634648371
b = 735531500*x^1023 + 684755229*x^1022 + 978579144*x^1021 + 560225565*x^1020 + 758090578*x^1019 + 367477932*x^1018 + 326779415*x^1017 + 26800946*x^1016 + 199017905*x^1015 + 1156874439*x^1014 + 673969262*x^1013 + 617169647*x^1012 + 462256026*x^1011 + 303059784*x^1010 + 663728970*x^1009 + 376865711*x^1008 + 830705685*x^1007 + 573964358*x^1006 + 1210202059*x^1005 + 269197755*x^1004 + 586236496*x^1003 + 621987820*x^1002 + 485567868*x^1001 + 305700227*x^1000 + 1052698462*x^999 + 86861550*x^998 + 44767901*x^997 + 410897986*x^996 + 212344404*x^995 + 336381747*x^994 + 398182335*x^993 + 660275371*x^992 + 52728322*x^991 + 1193103469*x^990 + 684295535*x^989 + 1029981794*x^988 + 1051866415*x^987 + 418681909*x^986 + 976794520*x^985 + 1180496804*x^984 + 438513041*x^983 + 822843942*x^982 + 1119264881*x^981 + 790873853*x^980 + 1146506838*x^979 + 27016797*x^978 + 1149126201*x^977 + 967895459*x^976 + 1201841165*x^975 + 264216641*x^974 + 751855165*x^973 + 277480010*x^972 + 955969328*x^971 + 784721168*x^970 + 696371212*x^969 + 401164998*x^968 + 654719011*x^967 + 785183205*x^966 + 79070435*x^965 + 1140562925*x^964 + 1025154340*x^963 + 1044315421*x^962 + 392734282*x^961 + 234286141*x^960 + 962551866*x^959 + 133742245*x^958 + 998056106*x^957 + 781318236*x^956 + 23528574*x^955 + 1214036424*x^954 + 296666931*x^953 + 1211729921*x^952 + 561550286*x^951 + 634392845*x^950 + 422332555*x^949 + 765556851*x^948 + 1151849524*x^947 + 305981530*x^946 + 246290056*x^945 + 24304550*x^944 + 477073522*x^943 + 416104453*x^942 + 898162013*x^941 + 611609496*x^940 + 445765799*x^939 + 430180169*x^938 + 1151421310*x^937 + 439515367*x^936 + 795257572*x^935 + 578106992*x^934 + 929259980*x^933 + 550407102*x^932 + 1219047347*x^931 + 15972593*x^930 + 515513177*x^929 + 679675449*x^928 + 914537835*x^927 + 156230965*x^926 + 385558312*x^925 + 1036365654*x^924 + 1098274877*x^923 + 348628203*x^922 + 1093802915*x^921 + 1162728002*x^920 + 200502246*x^919 + 551049082*x^918 + 969116717*x^917 + 1127382445*x^916 + 968172543*x^915 + 346881523*x^914 + 41744706*x^913 + 335042561*x^912 + 593895276*x^911 + 15888292*x^910 + 324866127*x^909 + 937351605*x^908 + 347255852*x^907 + 1120419679*x^906 + 249832197*x^905 + 896923860*x^904 + 129801128*x^903 + 207849052*x^902 + 386825059*x^901 + 823406098*x^900 + 977635408*x^899 + 108813100*x^898 + 561865827*x^897 + 718000532*x^896 + 48090035*x^895 + 832337939*x^894 + 1084389292*x^893 + 793335438*x^892 + 1095245016*x^891 + 1080787282*x^890 + 122666287*x^889 + 937313249*x^888 + 62818846*x^887 + 1170462486*x^886 + 182439366*x^885 + 792906343*x^884 + 1205386767*x^883 + 310389549*x^882 + 603676058*x^881 + 671251954*x^880 + 640345010*x^879 + 1087374504*x^878 + 119769446*x^877 + 135989573*x^876 + 880703983*x^875 + 613578242*x^874 + 1207874966*x^873 + 972002390*x^872 + 644470053*x^871 + 335762119*x^870 + 1079917808*x^869 + 1023711373*x^868 + 861485470*x^867 + 230979333*x^866 + 683284149*x^865 + 645804102*x^864 + 577971621*x^863 + 33779989*x^862 + 915467237*x^861 + 834966216*x^860 + 445758874*x^859 + 685228217*x^858 + 979609284*x^857 + 842509205*x^856 + 221373358*x^855 + 150166201*x^854 + 927937340*x^853 + 995054125*x^852 + 704623324*x^851 + 1112892592*x^850 + 782816865*x^849 + 878518510*x^848 + 391872241*x^847 + 30062686*x^846 + 108900016*x^845 + 1034780269*x^844 + 1190084541*x^843 + 441686497*x^842 + 117953957*x^841 + 840802549*x^840 + 903238790*x^839 + 551715093*x^838 + 539420097*x^837 + 1007110444*x^836 + 673864283*x^835 + 756402005*x^834 + 197892310*x^833 + 981720851*x^832 + 798897509*x^831 + 1127242378*x^830 + 666754217*x^829 + 685248618*x^828 + 327773092*x^827 + 390697118*x^826 + 912223373*x^825 + 482947333*x^824 + 1110169857*x^823 + 780612147*x^822 + 194698743*x^821 + 716386043*x^820 + 424946693*x^819 + 22701975*x^818 + 293011366*x^817 + 947695756*x^816 + 1188483932*x^815 + 1002073886*x^814 + 1078210750*x^813 + 1127684166*x^812 + 719332394*x^811 + 1072532713*x^810 + 550629553*x^809 + 188195613*x^808 + 614412704*x^807 + 649960359*x^806 + 1010011298*x^805 + 824975518*x^804 + 311757403*x^803 + 93674481*x^802 + 380323800*x^801 + 1086623904*x^800 + 240170088*x^799 + 956396081*x^798 + 939969890*x^797 + 131843464*x^796 + 1045744996*x^795 + 424359277*x^794 + 550616456*x^793 + 1061637035*x^792 + 444548551*x^791 + 677546521*x^790 + 149605032*x^789 + 829567560*x^788 + 516053142*x^787 + 1191529914*x^786 + 294270928*x^785 + 142024389*x^784 + 584911191*x^783 + 307856659*x^782 + 81514660*x^781 + 543784156*x^780 + 108008163*x^779 + 13154295*x^778 + 155266054*x^777 + 663702892*x^776 + 782494602*x^775 + 747547833*x^774 + 242456376*x^773 + 669844220*x^772 + 552894098*x^771 + 1036366706*x^770 + 1074841665*x^769 + 720745418*x^768 + 1137936670*x^767 + 840875363*x^766 + 476498840*x^765 + 1088669461*x^764 + 1249649*x^763 + 882277578*x^762 + 37842126*x^761 + 398977801*x^760 + 328296234*x^759 + 536342859*x^758 + 608139240*x^757 + 897424944*x^756 + 76562916*x^755 + 428081420*x^754 + 627420927*x^753 + 265131678*x^752 + 1034443577*x^751 + 177902661*x^750 + 490977141*x^749 + 1084536775*x^748 + 1189221123*x^747 + 854191429*x^746 + 952038058*x^745 + 891288300*x^744 + 929356576*x^743 + 223874272*x^742 + 220297702*x^741 + 1099283305*x^740 + 1008574448*x^739 + 619949004*x^738 + 747199791*x^737 + 760703880*x^736 + 7682727*x^735 + 88566484*x^734 + 733742620*x^733 + 381443925*x^732 + 799269923*x^731 + 233342676*x^730 + 1205696983*x^729 + 765306727*x^728 + 29342855*x^727 + 287728251*x^726 + 214358216*x^725 + 355991367*x^724 + 344973841*x^723 + 436344093*x^722 + 547944829*x^721 + 1041405031*x^720 + 368771692*x^719 + 37426577*x^718 + 502936636*x^717 + 732825913*x^716 + 518778589*x^715 + 561797784*x^714 + 773068766*x^713 + 75615306*x^712 + 668933267*x^711 + 628975723*x^710 + 1140697439*x^709 + 108807342*x^708 + 283945737*x^707 + 701674528*x^706 + 1120373548*x^705 + 421627231*x^704 + 260846853*x^703 + 292537012*x^702 + 583513440*x^701 + 609720259*x^700 + 831373721*x^699 + 1126099385*x^698 + 431095431*x^697 + 296863241*x^696 + 371013827*x^695 + 549980853*x^694 + 550174635*x^693 + 620963563*x^692 + 952040422*x^691 + 1150044500*x^690 + 893175261*x^689 + 1139857784*x^688 + 972717568*x^687 + 735672517*x^686 + 1177501026*x^685 + 765934764*x^684 + 710762091*x^683 + 871268519*x^682 + 969318271*x^681 + 286261161*x^680 + 65128931*x^679 + 1100922672*x^678 + 47619662*x^677 + 981578224*x^676 + 67232154*x^675 + 1928142*x^674 + 817643007*x^673 + 675713298*x^672 + 185236805*x^671 + 331446457*x^670 + 129023118*x^669 + 431426370*x^668 + 1154277684*x^667 + 723182950*x^666 + 1144823093*x^665 + 822001162*x^664 + 356099532*x^663 + 705989193*x^662 + 878712048*x^661 + 1095044481*x^660 + 332193401*x^659 + 613329359*x^658 + 673744151*x^657 + 808080280*x^656 + 225562949*x^655 + 185686220*x^654 + 742469973*x^653 + 986152315*x^652 + 13611550*x^651 + 535747170*x^650 + 233786507*x^649 + 27955348*x^648 + 1004446959*x^647 + 1071164149*x^646 + 265258708*x^645 + 63221383*x^644 + 682228580*x^643 + 867131152*x^642 + 997600620*x^641 + 993922001*x^640 + 693252545*x^639 + 865655581*x^638 + 518295141*x^637 + 902072633*x^636 + 704953646*x^635 + 587251157*x^634 + 99168972*x^633 + 1105480730*x^632 + 1040404159*x^631 + 436113220*x^630 + 152714904*x^629 + 697469981*x^628 + 1185372838*x^627 + 216027999*x^626 + 616083931*x^625 + 399419685*x^624 + 23193568*x^623 + 1174129641*x^622 + 75724376*x^621 + 570399858*x^620 + 754947446*x^619 + 1037864447*x^618 + 794730343*x^617 + 60369472*x^616 + 750769016*x^615 + 61444481*x^614 + 333194445*x^613 + 1109236037*x^612 + 513379869*x^611 + 706807998*x^610 + 999669914*x^609 + 1198194959*x^608 + 336044172*x^607 + 402719207*x^606 + 1050007981*x^605 + 429464593*x^604 + 679293134*x^603 + 734513317*x^602 + 838385265*x^601 + 990800608*x^600 + 1162093896*x^599 + 173467508*x^598 + 123947890*x^597 + 325712596*x^596 + 1049522320*x^595 + 1072653958*x^594 + 565759817*x^593 + 549918485*x^592 + 574268523*x^591 + 1052593520*x^590 + 474323970*x^589 + 262787725*x^588 + 1091470590*x^587 + 782664905*x^586 + 1201833996*x^585 + 808712564*x^584 + 619522329*x^583 + 233329446*x^582 + 730502283*x^581 + 1017501853*x^580 + 306080194*x^579 + 283641594*x^578 + 195324593*x^577 + 1116741123*x^576 + 289439631*x^575 + 206064600*x^574 + 280021778*x^573 + 425409216*x^572 + 1107952582*x^571 + 131800177*x^570 + 106903346*x^569 + 72306234*x^568 + 934072451*x^567 + 242740893*x^566 + 106611451*x^565 + 429378634*x^564 + 127624569*x^563 + 587315789*x^562 + 932709753*x^561 + 523886142*x^560 + 110330665*x^559 + 963244036*x^558 + 227339325*x^557 + 185882207*x^556 + 987833442*x^555 + 981380006*x^554 + 1140813804*x^553 + 538704418*x^552 + 842520362*x^551 + 597627400*x^550 + 165232274*x^549 + 900076209*x^548 + 311342603*x^547 + 477271753*x^546 + 1072907066*x^545 + 1066126181*x^544 + 791702251*x^543 + 623246063*x^542 + 1082681410*x^541 + 759396967*x^540 + 878108937*x^539 + 724607060*x^538 + 79223685*x^537 + 307312027*x^536 + 234246571*x^535 + 330319932*x^534 + 274254378*x^533 + 1082820468*x^532 + 68920838*x^531 + 1195376541*x^530 + 170971307*x^529 + 399525324*x^528 + 238798853*x^527 + 664426862*x^526 + 269949285*x^525 + 698202786*x^524 + 88964561*x^523 + 635539315*x^522 + 1016514687*x^521 + 122364467*x^520 + 1095096646*x^519 + 513834099*x^518 + 672478524*x^517 + 47526709*x^516 + 48782616*x^515 + 166225959*x^514 + 810099682*x^513 + 168540411*x^512 + 30055377*x^511 + 817325819*x^510 + 202717189*x^509 + 739906349*x^508 + 186072589*x^507 + 451966755*x^506 + 684027658*x^505 + 251331059*x^504 + 591972494*x^503 + 289197098*x^502 + 829928406*x^501 + 160528626*x^500 + 90951219*x^499 + 496118642*x^498 + 117818178*x^497 + 215417436*x^496 + 937904122*x^495 + 962080493*x^494 + 423647737*x^493 + 1094089608*x^492 + 97559711*x^491 + 412409151*x^490 + 1039695658*x^489 + 461079746*x^488 + 564664118*x^487 + 2231630*x^486 + 667569567*x^485 + 471400483*x^484 + 691739455*x^483 + 146641223*x^482 + 445509678*x^481 + 788647561*x^480 + 100316571*x^479 + 927803124*x^478 + 225739054*x^477 + 339283562*x^476 + 741552554*x^475 + 674303545*x^474 + 610706793*x^473 + 1045437706*x^472 + 758427998*x^471 + 518677374*x^470 + 1020530386*x^469 + 81672436*x^468 + 684553666*x^467 + 36416557*x^466 + 1083076029*x^465 + 63903696*x^464 + 655765095*x^463 + 464055997*x^462 + 874368360*x^461 + 909538282*x^460 + 1084815716*x^459 + 971305398*x^458 + 504958756*x^457 + 941782746*x^456 + 410981017*x^455 + 44463213*x^454 + 57796260*x^453 + 633624768*x^452 + 902476625*x^451 + 1190884714*x^450 + 30960289*x^449 + 698111360*x^448 + 507015564*x^447 + 595305556*x^446 + 1170147546*x^445 + 595449153*x^444 + 1132050715*x^443 + 566093951*x^442 + 1125890381*x^441 + 864044563*x^440 + 608408253*x^439 + 128031905*x^438 + 951152598*x^437 + 41054884*x^436 + 1012755213*x^435 + 1091670374*x^434 + 481898210*x^433 + 1007980179*x^432 + 43301236*x^431 + 6478999*x^430 + 1175215424*x^429 + 597862715*x^428 + 441537430*x^427 + 339705054*x^426 + 289227345*x^425 + 795113772*x^424 + 404870950*x^423 + 997272819*x^422 + 634256255*x^421 + 453060086*x^420 + 821493547*x^419 + 842289852*x^418 + 223251279*x^417 + 929721613*x^416 + 63980045*x^415 + 298369623*x^414 + 1026287144*x^413 + 979092254*x^412 + 1182904024*x^411 + 298048453*x^410 + 653297794*x^409 + 365769179*x^408 + 45373617*x^407 + 7228243*x^406 + 1086374067*x^405 + 389455721*x^404 + 992518297*x^403 + 433929335*x^402 + 1149626197*x^401 + 90006250*x^400 + 1011632630*x^399 + 940906615*x^398 + 564772117*x^397 + 692974220*x^396 + 561321375*x^395 + 1095715303*x^394 + 1006114558*x^393 + 95516055*x^392 + 640816811*x^391 + 869737844*x^390 + 248741996*x^389 + 101754352*x^388 + 253268107*x^387 + 593472036*x^386 + 627778298*x^385 + 801877646*x^384 + 286581226*x^383 + 645931883*x^382 + 373119745*x^381 + 461109006*x^380 + 594214135*x^379 + 751634451*x^378 + 706229440*x^377 + 247985412*x^376 + 993987710*x^375 + 618989435*x^374 + 600506682*x^373 + 179955505*x^372 + 956234357*x^371 + 1049030902*x^370 + 727597507*x^369 + 1196607714*x^368 + 610634244*x^367 + 619865634*x^366 + 849131167*x^365 + 1094185730*x^364 + 685353152*x^363 + 299082549*x^362 + 1076769237*x^361 + 792938001*x^360 + 885082721*x^359 + 1198739364*x^358 + 273154602*x^357 + 597517874*x^356 + 351418158*x^355 + 621945565*x^354 + 949756104*x^353 + 1020290901*x^352 + 315372660*x^351 + 291246927*x^350 + 1016861207*x^349 + 171467993*x^348 + 1074074496*x^347 + 660775696*x^346 + 562891589*x^345 + 258618000*x^344 + 521058831*x^343 + 152819838*x^342 + 1141330990*x^341 + 383408903*x^340 + 677850803*x^339 + 165908062*x^338 + 66975904*x^337 + 510786934*x^336 + 32306220*x^335 + 708115806*x^334 + 474352780*x^333 + 963188335*x^332 + 151844162*x^331 + 907339624*x^330 + 456166118*x^329 + 111742252*x^328 + 318018829*x^327 + 624012970*x^326 + 255354390*x^325 + 1218329311*x^324 + 375000855*x^323 + 54956044*x^322 + 13543809*x^321 + 671163260*x^320 + 226676913*x^319 + 1193470867*x^318 + 477161216*x^317 + 519506783*x^316 + 748987057*x^315 + 768531367*x^314 + 327816599*x^313 + 59056092*x^312 + 520958252*x^311 + 243337260*x^310 + 608632530*x^309 + 65258636*x^308 + 1012579720*x^307 + 400176357*x^306 + 104583966*x^305 + 1114827176*x^304 + 70705682*x^303 + 5320656*x^302 + 1207465008*x^301 + 1211372826*x^300 + 886104873*x^299 + 747144635*x^298 + 227753814*x^297 + 427912588*x^296 + 425232985*x^295 + 135219277*x^294 + 541439233*x^293 + 82586191*x^292 + 1024575564*x^291 + 408418547*x^290 + 1076407665*x^289 + 184646604*x^288 + 894569780*x^287 + 730742386*x^286 + 473643018*x^285 + 561906151*x^284 + 582231889*x^283 + 928617667*x^282 + 460594931*x^281 + 946340582*x^280 + 881007408*x^279 + 655553538*x^278 + 107738502*x^277 + 958107338*x^276 + 874269820*x^275 + 689734430*x^274 + 1025286771*x^273 + 809509338*x^272 + 126580761*x^271 + 425724981*x^270 + 91398446*x^269 + 915486182*x^268 + 750598785*x^267 + 331692120*x^266 + 266239686*x^265 + 41813860*x^264 + 1003196915*x^263 + 1006275694*x^262 + 958171508*x^261 + 387655573*x^260 + 529686749*x^259 + 2533683*x^258 + 851532040*x^257 + 515865631*x^256 + 331149910*x^255 + 1058283457*x^254 + 478391568*x^253 + 1020601120*x^252 + 193954604*x^251 + 125558467*x^250 + 916367669*x^249 + 965664721*x^248 + 737411958*x^247 + 145954639*x^246 + 787702411*x^245 + 256023548*x^244 + 831752864*x^243 + 637799028*x^242 + 202325459*x^241 + 189858829*x^240 + 221236168*x^239 + 276967229*x^238 + 732958371*x^237 + 31622618*x^236 + 558911372*x^235 + 257580689*x^234 + 490167674*x^233 + 1164269554*x^232 + 765931664*x^231 + 89716985*x^230 + 639008878*x^229 + 716033538*x^228 + 186948569*x^227 + 870251868*x^226 + 383121640*x^225 + 604362204*x^224 + 405526662*x^223 + 127371887*x^222 + 543669202*x^221 + 823112915*x^220 + 523517382*x^219 + 791437322*x^218 + 1069279817*x^217 + 960628355*x^216 + 1012582276*x^215 + 1200088601*x^214 + 927011022*x^213 + 830570829*x^212 + 700668365*x^211 + 1205573850*x^210 + 276778781*x^209 + 786305215*x^208 + 928215922*x^207 + 154393796*x^206 + 169298902*x^205 + 177646296*x^204 + 173339370*x^203 + 287217637*x^202 + 1077403939*x^201 + 1004965535*x^200 + 677352462*x^199 + 545192340*x^198 + 464170452*x^197 + 381853900*x^196 + 205643848*x^195 + 973330672*x^194 + 1148733662*x^193 + 458436519*x^192 + 68604889*x^191 + 193530886*x^190 + 141661386*x^189 + 1117183144*x^188 + 153035244*x^187 + 830892599*x^186 + 795500906*x^185 + 67041425*x^184 + 617209634*x^183 + 180547177*x^182 + 1183445159*x^181 + 303603618*x^180 + 842724764*x^179 + 784982658*x^178 + 1199356684*x^177 + 321497016*x^176 + 513738925*x^175 + 465949450*x^174 + 981246204*x^173 + 814398377*x^172 + 950247970*x^171 + 720838080*x^170 + 399493165*x^169 + 735365971*x^168 + 109745845*x^167 + 897998838*x^166 + 547497972*x^165 + 174675208*x^164 + 716115074*x^163 + 237209800*x^162 + 186394653*x^161 + 876995839*x^160 + 1187252196*x^159 + 819282320*x^158 + 44596523*x^157 + 679033559*x^156 + 736746236*x^155 + 1184916922*x^154 + 451294643*x^153 + 443590366*x^152 + 304384335*x^151 + 1064695584*x^150 + 602535518*x^149 + 684486124*x^148 + 863476315*x^147 + 496170722*x^146 + 737062216*x^145 + 285799611*x^144 + 1085153158*x^143 + 247783563*x^142 + 1208043659*x^141 + 208776666*x^140 + 117730360*x^139 + 279620264*x^138 + 273045622*x^137 + 893971194*x^136 + 240743423*x^135 + 1143029271*x^134 + 326725356*x^133 + 294174585*x^132 + 672819095*x^131 + 138843366*x^130 + 1176670148*x^129 + 573825049*x^128 + 835249905*x^127 + 778468469*x^126 + 300257393*x^125 + 409352854*x^124 + 953527813*x^123 + 653640743*x^122 + 1210615840*x^121 + 596684403*x^120 + 46012813*x^119 + 510765516*x^118 + 1213476223*x^117 + 1132779740*x^116 + 769195645*x^115 + 963749389*x^114 + 843804183*x^113 + 109759209*x^112 + 493130294*x^111 + 1122857844*x^110 + 1130618881*x^109 + 648465049*x^108 + 364595574*x^107 + 410134064*x^106 + 597836905*x^105 + 831243271*x^104 + 226275998*x^103 + 686704033*x^102 + 662011231*x^101 + 112226051*x^100 + 623946037*x^99 + 469742204*x^98 + 369854172*x^97 + 731154062*x^96 + 352916654*x^95 + 45991298*x^94 + 614913911*x^93 + 632337602*x^92 + 327529986*x^91 + 111251878*x^90 + 657089210*x^89 + 499853920*x^88 + 966818975*x^87 + 454584975*x^86 + 116582431*x^85 + 619242494*x^84 + 455382561*x^83 + 246350547*x^82 + 495191129*x^81 + 900852972*x^80 + 264825752*x^79 + 426813960*x^78 + 478124215*x^77 + 1080567657*x^76 + 858353771*x^75 + 215115660*x^74 + 963682245*x^73 + 964445096*x^72 + 73603206*x^71 + 734630202*x^70 + 199652522*x^69 + 520021635*x^68 + 763256200*x^67 + 861482624*x^66 + 890485659*x^65 + 523362913*x^64 + 785087110*x^63 + 381314881*x^62 + 843850504*x^61 + 61951613*x^60 + 119100925*x^59 + 531827488*x^58 + 199818669*x^57 + 592207491*x^56 + 354682041*x^55 + 1015447358*x^54 + 328324806*x^53 + 24880841*x^52 + 516663598*x^51 + 716706066*x^50 + 1042483154*x^49 + 331433641*x^48 + 929901382*x^47 + 502140671*x^46 + 48123362*x^45 + 1112586174*x^44 + 14618102*x^43 + 764832169*x^42 + 446768463*x^41 + 920421919*x^40 + 491851586*x^39 + 24718814*x^38 + 83091454*x^37 + 155770396*x^36 + 12824441*x^35 + 954371888*x^34 + 318592841*x^33 + 788251579*x^32 + 246435934*x^31 + 387083299*x^30 + 395226231*x^29 + 646811732*x^28 + 1131418388*x^27 + 1135116504*x^26 + 986902782*x^25 + 323457413*x^24 + 521885110*x^23 + 234655676*x^22 + 965166497*x^21 + 755967054*x^20 + 574743395*x^19 + 1175664410*x^18 + 117322371*x^17 + 794664856*x^16 + 570463*x^15 + 1148572518*x^14 + 439320220*x^13 + 815953366*x^12 + 389050726*x^11 + 1167287391*x^10 + 397052468*x^9 + 275572458*x^8 + 548665509*x^7 + 1202175986*x^6 + 518662014*x^5 + 1084425257*x^4 + 7854568*x^3 + 274607457*x^2 + 162444786*x + 410560230
n = 1024
p = 1219077173
R.<x> = PolynomialRing(Zmod(p), 'x')
f = x^n - 1
a = R(a)
b = R(b)
va = vector(ZZ, list(a))
vb = vector(ZZ, list(b))

nn=64
#part 1 construct matrix of poly_mul
A = matrix(ZZ, nn, nn)
for i in range(nn):
  for j in range(nn):
    A[j, i] = va[(i - j) % n]

#part 2 construct Lattice of RLWE
M = matrix(ZZ, nn*2+1, nn*2+1)
for i in range(nn):
  for j in range(nn):
    M[i+64, j] = A[i, j]
  M[i, i] = p
  M[i+nn, i+nn] = 1
  M[-1, i] = b[i]
M[-1, -1] = 1

#part 3 LLL to get s and get flag
res = M.LLL()[0]
s = res[nn:2*nn]
print(''.join(chr(abs(i)) for i in s))

VNCTF 2024

练车去了没打，赛后看看题吧。

SignAhead

试试伪造token和md5签名！

from hashlib import md5
from secret import flag
from secrets import token_bytes


ROUNDS = 100

successful_forge = 0

for i in range(ROUNDS):
    print(f'Round {i}')

    key = token_bytes(32)

    msg = token_bytes(64)

    sign = md5(key + msg).hexdigest()

    print('msg:', msg.hex())
    print('sign:', sign)

    print('FORGE ME!!!!')
    
    newmsg = bytes.fromhex(input('msg: '))
    newsign = input('sign: ').strip()

    assert msg != newmsg

    if md5(key + newmsg).hexdigest() == newsign:
        print('GREAT JOB')
        successful_forge += 1
    else:
        print('you failed!')

if successful_forge == ROUNDS:
    print('Here is your reward:', flag)
else:
    print('try harder next time !')

这里是哈希长度拓展攻击，相关内容在：哈希函数 | Chemtrails (ch3mtr4ils.cn)

照着脚本改改即可：

# 参考：https://github.com/bkfish/Script-DES-Crypto/blob/master/MD5/python3/md5.py

import hashlib
import math
from typing import Any, Dict, List
from Crypto.Util.number import *
from pwn import *

rotate_amounts = [7, 12, 17, 22, 7, 12, 17, 22, 7, 12, 17, 22, 7, 12, 17, 22,
                  5, 9, 14, 20, 5, 9, 14, 20, 5, 9, 14, 20, 5, 9, 14, 20,
                  4, 11, 16, 23, 4, 11, 16, 23, 4, 11, 16, 23, 4, 11, 16, 23,
                  6, 10, 15, 21, 6, 10, 15, 21, 6, 10, 15, 21, 6, 10, 15, 21]

constants = [int(abs(math.sin(i + 1)) * 2 ** 32) & 0xFFFFFFFF for i in range(64)]

functions = 16 * [lambda b, c, d: (b & c) | (~b & d)] + \
            16 * [lambda b, c, d: (d & b) | (~d & c)] + \
            16 * [lambda b, c, d: b ^ c ^ d] + \
            16 * [lambda b, c, d: c ^ (b | ~d)]

index_functions = 16 * [lambda i: i] + \
                  16 * [lambda i: (5 * i + 1) % 16] + \
                  16 * [lambda i: (3 * i + 5) % 16] + \
                  16 * [lambda i: (7 * i) % 16]


def get_init_values(A: int = 0x67452301, B: int = 0xefcdab89, C: int = 0x98badcfe, D: int = 0x10325476) -> List[int]:
    return [A, B, C, D]


def left_rotate(x, amount):
    x &= 0xFFFFFFFF
    return ((x << amount) | (x >> (32 - amount))) & 0xFFFFFFFF


def padding_message(msg: bytes) -> bytes:
    """
    在MD5算法中，首先需要对输入信息进行填充，使其位长对512求余的结果等于448，并且填充必须进行，即使其位长对512求余的结果等于448。
    因此，信息的位长（Bits Length）将被扩展至N*512+448，N为一个非负整数，N可以是零。
    填充的方法如下：
        1) 在信息的后面填充一个1和无数个0，直到满足上面的条件时才停止用0对信息的填充。
        2) 在这个结果后面附加一个以64位二进制表示的填充前信息长度（单位为Bit），如果二进制表示的填充前信息长度超过64位，则取低64位。
    经过这两步的处理，信息的位长=N*512+448+64=(N+1）*512，即长度恰好是512的整数倍。这样做的原因是为满足后面处理中对信息长度的要求。
    """
    orig_len_in_bits = (8 * len(msg)) & 0xffffffffffffffff
    msg += bytes([0x80])
    while len(msg) % 64 != 56:
        msg += bytes([0x00])
    msg += orig_len_in_bits.to_bytes(8, byteorder = 'little')
    return msg


def md5(message: bytes, A: int = 0x67452301, B: int = 0xefcdab89, C: int = 0x98badcfe, D: int = 0x10325476) -> int:
    message = padding_message(message)
    hash_pieces = get_init_values(A, B, C, D)[:]
    for chunk_ofst in range(0, len(message), 64):
        a, b, c, d = hash_pieces
        chunk = message[chunk_ofst:chunk_ofst + 64]
        for i in range(64):
            f = functions[i](b, c, d)
            g = index_functions[i](i)
            to_rotate = a + f + constants[i] + int.from_bytes(chunk[4 * g:4 * g + 4], byteorder = 'little')
            new_b = (b + left_rotate(to_rotate, rotate_amounts[i])) & 0xFFFFFFFF
            a, b, c, d = d, new_b, b, c
        for i, val in enumerate([a, b, c, d]):
            hash_pieces[i] += val
            hash_pieces[i] &= 0xFFFFFFFF
    
    return sum(x << (32 * i) for i, x in enumerate(hash_pieces))


def md5_to_hex(digest: int) -> str:
    raw = digest.to_bytes(16, byteorder = 'little')
    return '{:032x}'.format(int.from_bytes(raw, byteorder = 'big'))


def get_md5(message: bytes, A: int = 0x67452301, B: int = 0xefcdab89, C: int = 0x98badcfe, D: int = 0x10325476) -> str:
    return md5_to_hex(md5(message, A, B, C, D))


def md5_attack(message: bytes, A: int = 0x67452301, B: int = 0xefcdab89, C: int = 0x98badcfe,
               D: int = 0x10325476) -> int:
    hash_pieces = get_init_values(A, B, C, D)[:]
    for chunk_ofst in range(0, len(message), 64):
        a, b, c, d = hash_pieces
        chunk = message[chunk_ofst:chunk_ofst + 64]
        for i in range(64):
            f = functions[i](b, c, d)
            g = index_functions[i](i)
            to_rotate = a + f + constants[i] + int.from_bytes(chunk[4 * g:4 * g + 4], byteorder = 'little')
            new_b = (b + left_rotate(to_rotate, rotate_amounts[i])) & 0xFFFFFFFF
            a, b, c, d = d, new_b, b, c
        for i, val in enumerate([a, b, c, d]):
            hash_pieces[i] += val
            hash_pieces[i] &= 0xFFFFFFFF
    
    return sum(x << (32 * i) for i, x in enumerate(hash_pieces))


def get_init_values_from_hash_str(real_hash: str) -> List[int]:
    """
    
    Args:
        real_hash: 真实的hash结算结果

    Returns: 哈希初始化值[A, B, C, D]

    """
    str_list: List[str] = [real_hash[i * 8:(i + 1) * 8] for i in range(4)]
    # 先按照小端字节序将十六进制字符串转换成整数，然后按照大端字节序重新读取这个数字
    return [int.from_bytes(int('0x' + s, 16).to_bytes(4, byteorder = 'little'), byteorder = 'big') for s in str_list]


def get_md5_attack_materials(origin_msg: bytes, key_len: int, real_hash: str, append_data: bytes) -> Dict[str, Any]:
    """
    
    Args:
        origin_msg: 原始的消息字节流
        key_len: 原始密钥（盐）的长度
        real_hash: 计算出的真实的hash值
        append_data: 需要添加的攻击数据

    Returns: 发起攻击需要的物料信息
        {
            'attack_fake_msg': bytes([...]),
            'attack_hash_value': str(a1b2c3d4...)
        }

    """
    init_values = get_init_values_from_hash_str(real_hash)
    # print(['{:08x}'.format(x) for x in init_values])
    # 只知道key的长度，不知道key的具体内容时，任意填充key的内容
    fake_key: bytes = bytes([0xff for _ in range(key_len)])
    # 计算出加了append_data后的真实填充数据
    finally_padded_attack_data = padding_message(padding_message(fake_key + origin_msg) + append_data)
    # 攻击者提前计算添加了攻击数据的哈希
    attack_hash_value = md5_to_hex(md5_attack(finally_padded_attack_data[len(padding_message(fake_key + origin_msg)):],
                                              A = init_values[0],
                                              B = init_values[1],
                                              C = init_values[2],
                                              D = init_values[3]))
    fake_padding_data = padding_message(fake_key + origin_msg)[len(fake_key + origin_msg):]
    attack_fake_msg = origin_msg + fake_padding_data + append_data
    return {'attack_fake_msg': attack_fake_msg, 'attack_hash_value': attack_hash_value}


if __name__ == '__main__':
    sh = remote(...)
    for Rounds in range(100):
        print(Rounds)
    
        sh.recvuntil(b"Round")
        sh.recvuntil(b"msg:")
        # 服务端根据正常的数据预先计算出来的哈希值
        msg = long_to_bytes(int(sh.recvline().strip().decode(),16))
        attack_data: bytes = b"SPARKLE"
        sh.recvuntil(b"sign:")
        h = sh.recvline().strip().decode()
        md5_value = h
        
        # 预备发起攻击，先计算构造碰撞相关的参数
        attack_materials = get_md5_attack_materials(msg, 32, md5_value, attack_data)
        newmsg = attack_materials['attack_fake_msg']
        h = attack_materials['attack_hash_value']
        sh.sendline(newmsg.hex().encode())
        sh.sendline(h.encode())

    sh.recvline()
    sh.recvline()
    print(sh.recvline())

basiccry

import random 
from Crypto.Util.number import *
flag = b'********************************'
m = bytes_to_long(flag)

rr = matrix(ZZ,[random_vector(ZZ,256,0,2) for _ in range(256)])
mm = matrix(GF(2),[list(bin(m)[2:].rjust(256,'0'))]*256)
cc = mm+rr
ii = vector(ZZ,input("Undoubtedly, this is a backdoor left for you: ").split(","))
dd = rr*ii

print(cc)
print(dd)

题目定义了一个$rr$是随机的$256$维的$0$或$1$矩阵，$mm$是$256$个$256$长度的flag向量组成的矩阵，也是$0$或$1$，有公式：

$$cc=mm+rr$$ $$dd=rr\cdot ii$$

这里的$ii$是我们传给靶机的，我们可以自定义这个向量，所以这个题目中我们已知$dd,ii,cc$。

很明显，我们如果知道$rr$根据模二加法就能进一步得到flag，这里可以想到用背包密码中的超递增向量反向求解$rr$，定义一个超递增向量$ii$，根据$dd$的第一个数据就可以还原$rr$的第一个行向量，反向就能求解$mm[0]$，由于这矩阵的所有行向量都是flag，所以随便求出一个就能转化成flag了，比较简单，先获取数据：

from pwn import *


def gen_list(length):
    pack = [1]
    for i in range(length-1):
        temp = sum(pack) + 1
        pack.append(temp)
    return pack

length = 256
pack = gen_list(length)
print(pack)

sh = remote("manqiu.top",20224)
sh.recvuntil(b"Undoubtedly, this is a backdoor left for you: ")
sh.sendline(str(pack)[1:-1].encode())
print(sh.recvline())
for i in range(length-1):
    sh.recvline()
print(sh.recvline())

接下来直接利用超递增向量的特性和模二加法的特点就可以还原：

from Crypto.Util.number import *

bp= [1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288, 1048576, 2097152, 4194304, 8388608, 16777216, 33554432, 67108864, 134217728, 268435456, 536870912, 1073741824, 2147483648, 4294967296, 8589934592, 17179869184, 34359738368, 68719476736, 137438953472, 274877906944, 549755813888, 1099511627776, 2199023255552, 4398046511104, 8796093022208, 17592186044416, 35184372088832, 70368744177664, 140737488355328, 281474976710656, 562949953421312, 1125899906842624, 2251799813685248, 4503599627370496, 9007199254740992, 18014398509481984, 36028797018963968, 72057594037927936, 144115188075855872, 288230376151711744, 576460752303423488, 1152921504606846976, 2305843009213693952, 4611686018427387904, 9223372036854775808, 18446744073709551616, 36893488147419103232, 73786976294838206464, 147573952589676412928, 295147905179352825856, 590295810358705651712, 1180591620717411303424, 2361183241434822606848, 4722366482869645213696, 9444732965739290427392, 18889465931478580854784, 37778931862957161709568, 75557863725914323419136, 151115727451828646838272, 302231454903657293676544, 604462909807314587353088, 1208925819614629174706176, 2417851639229258349412352, 4835703278458516698824704, 9671406556917033397649408, 19342813113834066795298816, 38685626227668133590597632, 77371252455336267181195264, 154742504910672534362390528, 309485009821345068724781056, 618970019642690137449562112, 1237940039285380274899124224, 2475880078570760549798248448, 4951760157141521099596496896, 9903520314283042199192993792, 19807040628566084398385987584, 39614081257132168796771975168, 79228162514264337593543950336, 158456325028528675187087900672, 316912650057057350374175801344, 633825300114114700748351602688, 1267650600228229401496703205376, 2535301200456458802993406410752, 5070602400912917605986812821504, 10141204801825835211973625643008, 20282409603651670423947251286016, 40564819207303340847894502572032, 81129638414606681695789005144064, 162259276829213363391578010288128, 324518553658426726783156020576256, 649037107316853453566312041152512, 1298074214633706907132624082305024, 2596148429267413814265248164610048, 5192296858534827628530496329220096, 10384593717069655257060992658440192, 20769187434139310514121985316880384, 41538374868278621028243970633760768, 83076749736557242056487941267521536, 166153499473114484112975882535043072, 332306998946228968225951765070086144, 664613997892457936451903530140172288, 1329227995784915872903807060280344576, 2658455991569831745807614120560689152, 5316911983139663491615228241121378304, 10633823966279326983230456482242756608, 21267647932558653966460912964485513216, 42535295865117307932921825928971026432, 85070591730234615865843651857942052864, 170141183460469231731687303715884105728, 340282366920938463463374607431768211456, 680564733841876926926749214863536422912, 1361129467683753853853498429727072845824, 2722258935367507707706996859454145691648, 5444517870735015415413993718908291383296, 10889035741470030830827987437816582766592, 21778071482940061661655974875633165533184, 43556142965880123323311949751266331066368, 87112285931760246646623899502532662132736, 174224571863520493293247799005065324265472, 348449143727040986586495598010130648530944, 696898287454081973172991196020261297061888, 1393796574908163946345982392040522594123776, 2787593149816327892691964784081045188247552, 5575186299632655785383929568162090376495104, 11150372599265311570767859136324180752990208, 22300745198530623141535718272648361505980416, 44601490397061246283071436545296723011960832, 89202980794122492566142873090593446023921664, 178405961588244985132285746181186892047843328, 356811923176489970264571492362373784095686656, 713623846352979940529142984724747568191373312, 1427247692705959881058285969449495136382746624, 2854495385411919762116571938898990272765493248, 5708990770823839524233143877797980545530986496, 11417981541647679048466287755595961091061972992, 22835963083295358096932575511191922182123945984, 45671926166590716193865151022383844364247891968, 91343852333181432387730302044767688728495783936, 182687704666362864775460604089535377456991567872, 365375409332725729550921208179070754913983135744, 730750818665451459101842416358141509827966271488, 1461501637330902918203684832716283019655932542976, 2923003274661805836407369665432566039311865085952, 5846006549323611672814739330865132078623730171904, 11692013098647223345629478661730264157247460343808, 23384026197294446691258957323460528314494920687616, 46768052394588893382517914646921056628989841375232, 93536104789177786765035829293842113257979682750464, 187072209578355573530071658587684226515959365500928, 374144419156711147060143317175368453031918731001856, 748288838313422294120286634350736906063837462003712, 1496577676626844588240573268701473812127674924007424, 2993155353253689176481146537402947624255349848014848, 5986310706507378352962293074805895248510699696029696, 11972621413014756705924586149611790497021399392059392, 23945242826029513411849172299223580994042798784118784, 47890485652059026823698344598447161988085597568237568, 95780971304118053647396689196894323976171195136475136, 191561942608236107294793378393788647952342390272950272, 383123885216472214589586756787577295904684780545900544, 766247770432944429179173513575154591809369561091801088, 1532495540865888858358347027150309183618739122183602176, 3064991081731777716716694054300618367237478244367204352, 6129982163463555433433388108601236734474956488734408704, 12259964326927110866866776217202473468949912977468817408, 24519928653854221733733552434404946937899825954937634816, 49039857307708443467467104868809893875799651909875269632, 98079714615416886934934209737619787751599303819750539264, 196159429230833773869868419475239575503198607639501078528, 392318858461667547739736838950479151006397215279002157056, 784637716923335095479473677900958302012794430558004314112, 1569275433846670190958947355801916604025588861116008628224, 3138550867693340381917894711603833208051177722232017256448, 6277101735386680763835789423207666416102355444464034512896, 12554203470773361527671578846415332832204710888928069025792, 25108406941546723055343157692830665664409421777856138051584, 50216813883093446110686315385661331328818843555712276103168, 100433627766186892221372630771322662657637687111424552206336, 200867255532373784442745261542645325315275374222849104412672, 401734511064747568885490523085290650630550748445698208825344, 803469022129495137770981046170581301261101496891396417650688, 1606938044258990275541962092341162602522202993782792835301376, 3213876088517980551083924184682325205044405987565585670602752, 6427752177035961102167848369364650410088811975131171341205504, 12855504354071922204335696738729300820177623950262342682411008, 25711008708143844408671393477458601640355247900524685364822016, 51422017416287688817342786954917203280710495801049370729644032, 102844034832575377634685573909834406561420991602098741459288064, 205688069665150755269371147819668813122841983204197482918576128, 411376139330301510538742295639337626245683966408394965837152256, 822752278660603021077484591278675252491367932816789931674304512, 1645504557321206042154969182557350504982735865633579863348609024, 3291009114642412084309938365114701009965471731267159726697218048, 6582018229284824168619876730229402019930943462534319453394436096, 13164036458569648337239753460458804039861886925068638906788872192, 26328072917139296674479506920917608079723773850137277813577744384, 52656145834278593348959013841835216159447547700274555627155488768, 105312291668557186697918027683670432318895095400549111254310977536, 210624583337114373395836055367340864637790190801098222508621955072, 421249166674228746791672110734681729275580381602196445017243910144, 842498333348457493583344221469363458551160763204392890034487820288, 1684996666696914987166688442938726917102321526408785780068975640576, 3369993333393829974333376885877453834204643052817571560137951281152, 6739986666787659948666753771754907668409286105635143120275902562304, 13479973333575319897333507543509815336818572211270286240551805124608, 26959946667150639794667015087019630673637144422540572481103610249216, 53919893334301279589334030174039261347274288845081144962207220498432, 107839786668602559178668060348078522694548577690162289924414440996864, 215679573337205118357336120696157045389097155380324579848828881993728, 431359146674410236714672241392314090778194310760649159697657763987456, 862718293348820473429344482784628181556388621521298319395315527974912, 1725436586697640946858688965569256363112777243042596638790631055949824, 3450873173395281893717377931138512726225554486085193277581262111899648, 6901746346790563787434755862277025452451108972170386555162524223799296, 13803492693581127574869511724554050904902217944340773110325048447598592, 27606985387162255149739023449108101809804435888681546220650096895197184, 55213970774324510299478046898216203619608871777363092441300193790394368, 110427941548649020598956093796432407239217743554726184882600387580788736, 220855883097298041197912187592864814478435487109452369765200775161577472, 441711766194596082395824375185729628956870974218904739530401550323154944, 883423532389192164791648750371459257913741948437809479060803100646309888, 1766847064778384329583297500742918515827483896875618958121606201292619776, 3533694129556768659166595001485837031654967793751237916243212402585239552, 7067388259113537318333190002971674063309935587502475832486424805170479104, 14134776518227074636666380005943348126619871175004951664972849610340958208, 28269553036454149273332760011886696253239742350009903329945699220681916416, 56539106072908298546665520023773392506479484700019806659891398441363832832, 113078212145816597093331040047546785012958969400039613319782796882727665664, 226156424291633194186662080095093570025917938800079226639565593765455331328, 452312848583266388373324160190187140051835877600158453279131187530910662656, 904625697166532776746648320380374280103671755200316906558262375061821325312, 1809251394333065553493296640760748560207343510400633813116524750123642650624, 3618502788666131106986593281521497120414687020801267626233049500247285301248, 7237005577332262213973186563042994240829374041602535252466099000494570602496, 14474011154664524427946373126085988481658748083205070504932198000989141204992, 28948022309329048855892746252171976963317496166410141009864396001978282409984, 57896044618658097711785492504343953926634992332820282019728792003956564819968]
plus1=[1,0,0,0,1,1,0,1,0,0,1,0,1,0,0,0,1,1,1,1,0,0,0,0,1,0,1,1,1,1,1,0,0,0,1,1,1,1,0,1,1,1,0,1,1,1,0,1,1,1,1,0,1,1,1,1,1,0,0,0,1,0,0,0,0,1,1,0,1,1,1,1,1,0,1,0,1,0,0,0,0,0,1,1,0,1,1,1,0,1,0,0,1,0,1,0,1,1,0,1,0,0,1,0,1,0,0,1,1,1,1,1,0,0,1,1,0,0,0,1,1,1,1,1,1,0,0,0,0,0,0,1,1,1,0,1,0,1,0,1,0,1,0,0,1,0,1,1,0,1,1,1,1,1,1,0,0,0,0,1,0,1,0,1,1,1,1,0,1,0,1,0,0,0,1,0,0,1,1,1,0,0,0,0,0,0,0,1,1,1,0,1,1,1,1,0,0,0,0,1,0,1,0,1,1,1,1,1,0,1,0,0,1,1,1,0,0,0,0,0,1,0,0,1,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,1,1,1,0,0,0,1,1,0,1,0,0,1,1,0,1]
sum1 = 5546453186440519691496595155009849783987915124560425731803798586517151901403


T = []
for i in range(len(bp)-1, -1, -1):
    if sum1>=bp[i]:
        sum1-=bp[i]
        T.append(1)
    else:
        T.append(0)
T=T[::-1]
m=''
for i in range(len(plus1)):
    if plus1[i]!=T[i]:
        m+='1'
    else:
        m+='0'
mm=int(m,2)
print(long_to_bytes(mm))

也可以直接用sage求一下向量差直接得到：

from Crypto.Util.number import *

bp= [1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288, 1048576, 2097152, 4194304, 8388608, 16777216, 33554432, 67108864, 134217728, 268435456, 536870912, 1073741824, 2147483648, 4294967296, 8589934592, 17179869184, 34359738368, 68719476736, 137438953472, 274877906944, 549755813888, 1099511627776, 2199023255552, 4398046511104, 8796093022208, 17592186044416, 35184372088832, 70368744177664, 140737488355328, 281474976710656, 562949953421312, 1125899906842624, 2251799813685248, 4503599627370496, 9007199254740992, 18014398509481984, 36028797018963968, 72057594037927936, 144115188075855872, 288230376151711744, 576460752303423488, 1152921504606846976, 2305843009213693952, 4611686018427387904, 9223372036854775808, 18446744073709551616, 36893488147419103232, 73786976294838206464, 147573952589676412928, 295147905179352825856, 590295810358705651712, 1180591620717411303424, 2361183241434822606848, 4722366482869645213696, 9444732965739290427392, 18889465931478580854784, 37778931862957161709568, 75557863725914323419136, 151115727451828646838272, 302231454903657293676544, 604462909807314587353088, 1208925819614629174706176, 2417851639229258349412352, 4835703278458516698824704, 9671406556917033397649408, 19342813113834066795298816, 38685626227668133590597632, 77371252455336267181195264, 154742504910672534362390528, 309485009821345068724781056, 618970019642690137449562112, 1237940039285380274899124224, 2475880078570760549798248448, 4951760157141521099596496896, 9903520314283042199192993792, 19807040628566084398385987584, 39614081257132168796771975168, 79228162514264337593543950336, 158456325028528675187087900672, 316912650057057350374175801344, 633825300114114700748351602688, 1267650600228229401496703205376, 2535301200456458802993406410752, 5070602400912917605986812821504, 10141204801825835211973625643008, 20282409603651670423947251286016, 40564819207303340847894502572032, 81129638414606681695789005144064, 162259276829213363391578010288128, 324518553658426726783156020576256, 649037107316853453566312041152512, 1298074214633706907132624082305024, 2596148429267413814265248164610048, 5192296858534827628530496329220096, 10384593717069655257060992658440192, 20769187434139310514121985316880384, 41538374868278621028243970633760768, 83076749736557242056487941267521536, 166153499473114484112975882535043072, 332306998946228968225951765070086144, 664613997892457936451903530140172288, 1329227995784915872903807060280344576, 2658455991569831745807614120560689152, 5316911983139663491615228241121378304, 10633823966279326983230456482242756608, 21267647932558653966460912964485513216, 42535295865117307932921825928971026432, 85070591730234615865843651857942052864, 170141183460469231731687303715884105728, 340282366920938463463374607431768211456, 680564733841876926926749214863536422912, 1361129467683753853853498429727072845824, 2722258935367507707706996859454145691648, 5444517870735015415413993718908291383296, 10889035741470030830827987437816582766592, 21778071482940061661655974875633165533184, 43556142965880123323311949751266331066368, 87112285931760246646623899502532662132736, 174224571863520493293247799005065324265472, 348449143727040986586495598010130648530944, 696898287454081973172991196020261297061888, 1393796574908163946345982392040522594123776, 2787593149816327892691964784081045188247552, 5575186299632655785383929568162090376495104, 11150372599265311570767859136324180752990208, 22300745198530623141535718272648361505980416, 44601490397061246283071436545296723011960832, 89202980794122492566142873090593446023921664, 178405961588244985132285746181186892047843328, 356811923176489970264571492362373784095686656, 713623846352979940529142984724747568191373312, 1427247692705959881058285969449495136382746624, 2854495385411919762116571938898990272765493248, 5708990770823839524233143877797980545530986496, 11417981541647679048466287755595961091061972992, 22835963083295358096932575511191922182123945984, 45671926166590716193865151022383844364247891968, 91343852333181432387730302044767688728495783936, 182687704666362864775460604089535377456991567872, 365375409332725729550921208179070754913983135744, 730750818665451459101842416358141509827966271488, 1461501637330902918203684832716283019655932542976, 2923003274661805836407369665432566039311865085952, 5846006549323611672814739330865132078623730171904, 11692013098647223345629478661730264157247460343808, 23384026197294446691258957323460528314494920687616, 46768052394588893382517914646921056628989841375232, 93536104789177786765035829293842113257979682750464, 187072209578355573530071658587684226515959365500928, 374144419156711147060143317175368453031918731001856, 748288838313422294120286634350736906063837462003712, 1496577676626844588240573268701473812127674924007424, 2993155353253689176481146537402947624255349848014848, 5986310706507378352962293074805895248510699696029696, 11972621413014756705924586149611790497021399392059392, 23945242826029513411849172299223580994042798784118784, 47890485652059026823698344598447161988085597568237568, 95780971304118053647396689196894323976171195136475136, 191561942608236107294793378393788647952342390272950272, 383123885216472214589586756787577295904684780545900544, 766247770432944429179173513575154591809369561091801088, 1532495540865888858358347027150309183618739122183602176, 3064991081731777716716694054300618367237478244367204352, 6129982163463555433433388108601236734474956488734408704, 12259964326927110866866776217202473468949912977468817408, 24519928653854221733733552434404946937899825954937634816, 49039857307708443467467104868809893875799651909875269632, 98079714615416886934934209737619787751599303819750539264, 196159429230833773869868419475239575503198607639501078528, 392318858461667547739736838950479151006397215279002157056, 784637716923335095479473677900958302012794430558004314112, 1569275433846670190958947355801916604025588861116008628224, 3138550867693340381917894711603833208051177722232017256448, 6277101735386680763835789423207666416102355444464034512896, 12554203470773361527671578846415332832204710888928069025792, 25108406941546723055343157692830665664409421777856138051584, 50216813883093446110686315385661331328818843555712276103168, 100433627766186892221372630771322662657637687111424552206336, 200867255532373784442745261542645325315275374222849104412672, 401734511064747568885490523085290650630550748445698208825344, 803469022129495137770981046170581301261101496891396417650688, 1606938044258990275541962092341162602522202993782792835301376, 3213876088517980551083924184682325205044405987565585670602752, 6427752177035961102167848369364650410088811975131171341205504, 12855504354071922204335696738729300820177623950262342682411008, 25711008708143844408671393477458601640355247900524685364822016, 51422017416287688817342786954917203280710495801049370729644032, 102844034832575377634685573909834406561420991602098741459288064, 205688069665150755269371147819668813122841983204197482918576128, 411376139330301510538742295639337626245683966408394965837152256, 822752278660603021077484591278675252491367932816789931674304512, 1645504557321206042154969182557350504982735865633579863348609024, 3291009114642412084309938365114701009965471731267159726697218048, 6582018229284824168619876730229402019930943462534319453394436096, 13164036458569648337239753460458804039861886925068638906788872192, 26328072917139296674479506920917608079723773850137277813577744384, 52656145834278593348959013841835216159447547700274555627155488768, 105312291668557186697918027683670432318895095400549111254310977536, 210624583337114373395836055367340864637790190801098222508621955072, 421249166674228746791672110734681729275580381602196445017243910144, 842498333348457493583344221469363458551160763204392890034487820288, 1684996666696914987166688442938726917102321526408785780068975640576, 3369993333393829974333376885877453834204643052817571560137951281152, 6739986666787659948666753771754907668409286105635143120275902562304, 13479973333575319897333507543509815336818572211270286240551805124608, 26959946667150639794667015087019630673637144422540572481103610249216, 53919893334301279589334030174039261347274288845081144962207220498432, 107839786668602559178668060348078522694548577690162289924414440996864, 215679573337205118357336120696157045389097155380324579848828881993728, 431359146674410236714672241392314090778194310760649159697657763987456, 862718293348820473429344482784628181556388621521298319395315527974912, 1725436586697640946858688965569256363112777243042596638790631055949824, 3450873173395281893717377931138512726225554486085193277581262111899648, 6901746346790563787434755862277025452451108972170386555162524223799296, 13803492693581127574869511724554050904902217944340773110325048447598592, 27606985387162255149739023449108101809804435888681546220650096895197184, 55213970774324510299478046898216203619608871777363092441300193790394368, 110427941548649020598956093796432407239217743554726184882600387580788736, 220855883097298041197912187592864814478435487109452369765200775161577472, 441711766194596082395824375185729628956870974218904739530401550323154944, 883423532389192164791648750371459257913741948437809479060803100646309888, 1766847064778384329583297500742918515827483896875618958121606201292619776, 3533694129556768659166595001485837031654967793751237916243212402585239552, 7067388259113537318333190002971674063309935587502475832486424805170479104, 14134776518227074636666380005943348126619871175004951664972849610340958208, 28269553036454149273332760011886696253239742350009903329945699220681916416, 56539106072908298546665520023773392506479484700019806659891398441363832832, 113078212145816597093331040047546785012958969400039613319782796882727665664, 226156424291633194186662080095093570025917938800079226639565593765455331328, 452312848583266388373324160190187140051835877600158453279131187530910662656, 904625697166532776746648320380374280103671755200316906558262375061821325312, 1809251394333065553493296640760748560207343510400633813116524750123642650624, 3618502788666131106986593281521497120414687020801267626233049500247285301248, 7237005577332262213973186563042994240829374041602535252466099000494570602496, 14474011154664524427946373126085988481658748083205070504932198000989141204992, 28948022309329048855892746252171976963317496166410141009864396001978282409984, 57896044618658097711785492504343953926634992332820282019728792003956564819968]
plus1=[1,0,0,0,1,1,0,1,0,0,1,0,1,0,0,0,1,1,1,1,0,0,0,0,1,0,1,1,1,1,1,0,0,0,1,1,1,1,0,1,1,1,0,1,1,1,0,1,1,1,1,0,1,1,1,1,1,0,0,0,1,0,0,0,0,1,1,0,1,1,1,1,1,0,1,0,1,0,0,0,0,0,1,1,0,1,1,1,0,1,0,0,1,0,1,0,1,1,0,1,0,0,1,0,1,0,0,1,1,1,1,1,0,0,1,1,0,0,0,1,1,1,1,1,1,0,0,0,0,0,0,1,1,1,0,1,0,1,0,1,0,1,0,0,1,0,1,1,0,1,1,1,1,1,1,0,0,0,0,1,0,1,0,1,1,1,1,0,1,0,1,0,0,0,1,0,0,1,1,1,0,0,0,0,0,0,0,1,1,1,0,1,1,1,1,0,0,0,0,1,0,1,0,1,1,1,1,1,0,1,0,0,1,1,1,0,0,0,0,0,1,0,0,1,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,1,1,1,0,0,0,1,1,0,1,0,0,1,1,0,1]
sum1 = 5546453186440519691496595155009849783987915124560425731803798586517151901403

T = []
for i in range(length):
    if(sum1 < bp[length-i-1]):
        T.append(0)
    else:
        sum1 -= bp[length-i-1]
        T.append(1)
T = vector(GF(2),T[::-1])
plus1 = vector(GF(2),plus1)
m = list(plus1-T)
for i in range(len(m)):
    m[i] = str(m[i])
print(long_to_bytes(int("".join(m),2)))

N1CTF 2024

Junior RSA

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

m = bytes_to_long(flag)

def gen(bits):
    while True:
        a = getPrime(bits)
        b = getPrime(bits)
        c = getPrime(bits)
        p = (a << (2*bits)) + (b << bits) + c
        q = (c << (2*bits)) + (a << bits) + b
        if isPrime(p) and isPrime(q):
            break
    n = p * q
    e = 65537 * a * b * c
    return n, e

n, e = gen(256)
enc = pow(m, e, n)
print(f'n = {n}')
print(f'e = {e}')
print(f'enc = {enc}')

"""
n = 1224562468550864572988516321107388462006452125881847529675226398144888628055678744854491489016309262856785169494723943649344959507818155642772331582922466943539371681776924160647697558836379614689120727659593775446187326222964118917872973684996317614900715927751822277949264379149585370840318817143291878609357893969588131470982041272505875501444442064552286330626234504767040724907034678080283717062342383737341651784574675215207283219694413200065153603535550259
e = 47356701171507751941853094934330097161634963503549196148254287987823089762869775349307331223083118848869825102126184149696632299476124764277876323238594318983922914255635452587035212905468593961720866809724369270149104325019013500377581
enc = 307839781648837102719329833689146078918113606357673952357833605392673923316706392387378621203382529480917019155723632239435123748698548640308486267420983085309284306889248702165586731118889200017606360233948688879034822132551452439147516062116990766999765714755923073387252339782026780490661436777023426366620269445376047876173655782230659201893151372247389482285331969025687842851498151565880029377050013378302485301558801016888957357366922840214729734193614497
""

粗略看了一下代码发现需要分解$n$：

$$n=(2^{512}a+2^{256}b+c)(2^{512}c+2^{256}a+b)$$ $$e=65537abc$$

这里的$a,b,c$都是$256$位的素数，根据多项式乘积的位数分布，我们可以通过$n$的高$256$位和低$256$位直接得到$ac$积的高$256$位和$bc$乘积的低$256$位。对于$e$来说可以拆：

$$e=65537(2^{256}(ac)_h+(ac)_l)b$$ $$e=65537(2^{256}(bc)_h+(bc)_l)a$$

可以想办法先求出$b$，将第一个式子变一下：

$$\frac e{65537}=2^{256}(ac)_hb+(ac)_lb$$

发现当我们除以已知的$2^{256}(ac)_h$时，去掉余数，也就是第二项，我们就可以直接得到$b$，但是由于被除数和带余除法的余数相同位数不确定是否还能继续除，所以可能会有偏差，可以往前爆破一下验证得到$b$。

利用同样的方法展开第二个式子：

$$\frac e{65537}=2^{256}(bc)_ha+(bc)_la$$

这里可以很容易发现，等式放在模$2^{256}$下，直接就能得到：

$$\frac e{65537}\equiv (bc)_la\pmod {2^{256}}$$

求一下逆元，就能得到$a$：

$$\frac e{65537}(bc)_l^{-1}\equiv a\pmod {2^{256}}$$

$a,b$都得到了，就能得到$c$，可以进行因式分解求解RSA：

from Crypto.Util.number import *
import gmpy2

n = 1224562468550864572988516321107388462006452125881847529675226398144888628055678744854491489016309262856785169494723943649344959507818155642772331582922466943539371681776924160647697558836379614689120727659593775446187326222964118917872973684996317614900715927751822277949264379149585370840318817143291878609357893969588131470982041272505875501444442064552286330626234504767040724907034678080283717062342383737341651784574675215207283219694413200065153603535550259
e = 47356701171507751941853094934330097161634963503549196148254287987823089762869775349307331223083118848869825102126184149696632299476124764277876323238594318983922914255635452587035212905468593961720866809724369270149104325019013500377581
enc = 307839781648837102719329833689146078918113606357673952357833605392673923316706392387378621203382529480917019155723632239435123748698548640308486267420983085309284306889248702165586731118889200017606360233948688879034822132551452439147516062116990766999765714755923073387252339782026780490661436777023426366620269445376047876173655782230659201893151372247389482285331969025687842851498151565880029377050013378302485301558801016888957357366922840214729734193614497

bits = 256
ach = n >> (1024 + bits)
bcl = n % 2**bits

for i in range(10):
    if e % (b := (e // 65537 // (ach * 2**bits) + i)) == 0:
        print(b)
        break

a = (e // 65537) * gmpy2.invert(bcl, 2**bits) % 2**bits
c = e // a // b // 65537
p = (a << (2 * bits)) + (b << bits) + c
q = (c << (2 * bits)) + (a << bits) + b

phi = (p - 1) * (q - 1)
d = gmpy2.invert(e, phi)
m = pow(enc, d, n)
print(long_to_bytes(m))

NSSCTF ROUND19

Decision

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

class MRG:
    def __init__(self,para_len,p):
        self.init(para_len,p)

    def next(self):
        self.s = self.s[1: ] + [(sum([i * j for (i, j) in zip(self.a, self.s)]) + self.b) % self.p]
        return self.s[-1]

    def init(self,para_len,p):
        self.p = p
        self.b = randint(1, self.p)
        self.a = [randint(1, self.p) for i in range(para_len)]
        self.s = [ord(choice(string.printable)) for i in range(para_len)]
    
    def get_params(self):
        return [self.a,self.b,self.s[0]]


flag = bytes_to_long(flag)
flag_bin = bin(flag)[2:]

Round = 2024
A_len = 10
p = getPrime(256)

output = []
for i in flag_bin:
    if(i == "0"):
        temp = MRG(A_len,p)
        for j in range(Round):
            temp.next()
        output.append(temp.get_params())
    else:
        a = [randint(1,p) for i in range(A_len)]
        b = randint(1,p)
        s = randint(1,p)
        output.append([a,b,s])

with open("output.txt","w") as f:
    f.write(str(p))
    f.write(str(output))

题目是一个MRG（多重递归生成器），没咋见过直接研究研究生成算法得了：

def next(self):
    self.s = self.s[1: ] + [(sum([i * j for (i, j) in zip(self.a, self.s)]) + self.b) % self.p]
    return self.s[-1]

参数$a,b,s$都是随机数，其中$s$是随机从ASCII可见字符中的ASCII转码得到的，比较小，递推公式有：

$$s_{i+10}=\sum^{9}_{j=0}a_js_{i+j}+b\pmod p$$

新的状态就是一个前十个状态向量乘加上一个随机$b$得到的。

再来看看题目的加密：

for i in flag_bin:
    if(i == "0"):
        temp = MRG(A_len,p)
        for j in range(Round):
            temp.next()
        output.append(temp.get_params())
    else:
        a = [randint(1,p) for i in range(A_len)]
        b = randint(1,p)
        s = randint(1,p)
        output.append([a,b,s])

这里根据flag的每个二进制位判断，如果为$0$的话生成MRG2024轮后的参数，如果为$1$的话则是全随机的随机数。

我们需要判断每一组样本是MRG还是纯随机样本，类似于DLWE。还是注意到$s$是随机从ASCII可见字符中的ASCII转码得到的比较小的值，想到用格，可以先用矩阵表示一下：

$$\left( \begin{matrix} s_1\\ s_2\\ s_3\\ \vdots\\ s_9\\ s_{10}\\ 1\\ \end{matrix} \right) = \left( \begin{matrix} &1&&&&&\\ &&1&&&&\\ &&&1&&&\\ &&&&\ddots&&\\ &&&&&1&\\ a_0&a_1&a_2&a_3&\cdots&a_9&b\\ &&&&&&1\\ \end{matrix} \right) \left( \begin{matrix} s_0\\ s_1\\ s_2\\ \vdots\\ s_8\\ s_9\\ 1\\ \end{matrix} \right) \pmod p$$

这里每次迭代使用的$a,b$都是相同的，所以可以直接拿来继续表示所有的2024轮递推：

$$\left( \begin{matrix} s_{0+2024}\\ s_{1+2024}\\ s_{2+2024}\\ \vdots\\ s_{8+2024}\\ s_{9+2024}\\ 1\\ \end{matrix} \right) = \left( \begin{matrix} &1&&&&&\\ &&1&&&&\\ &&&1&&&\\ &&&&\ddots&&\\ &&&&&1&\\ a_0&a_1&a_2&a_3&\cdots&a_9&b\\ &&&&&&1\\ \end{matrix} \right) ^{2024} \left( \begin{matrix} s_0\\ s_1\\ s_2\\ \vdots\\ s_8\\ s_9\\ 1\\ \end{matrix} \right) \pmod p$$

假设现在我们有一组MRG样本，构造这个递推矩阵：

$$L = \left( \begin{matrix} &1&&&&&\\ &&1&&&&\\ &&&1&&&\\ &&&&\ddots&&\\ &&&&&1&\\ a_0&a_1&a_2&a_3&\cdots&a_9&b\\ &&&&&&1\\ \end{matrix} \right) ^{2024}$$

简化一下等式：

$$S_{2024}=LS_0$$

要想规约后表示成一个短向量形式，进行一下转置：

$$S^T_0L^T=S^T_{2024}$$ $$(s_0,s_1,...,s_9,1)L^T = (s_{2024},s_{2025},...,s_{2033},1) \pmod p$$

但是，题目只给了2024轮迭代后的第一个量（$s_{2024}$），干脆直接去掉剩下的未知部分，得到：

$$(s_0,s_1,...,s_9,1)L_1^T = (s_{2024}) \pmod p$$

造格：

$$M = \left( \begin{matrix} E &O& L_1^T \\ O &1& -s_{2024} \\ O &0& p \end{matrix} \right)$$ $$(s_0,s_1,...,s_9,1,1,k) M = (s_0,s_1,...,s_9,1,1,0)$$

注意配一下系数：

from tqdm import *

p = 
output = 

m = ""
for j in trange(len(output)):
    temp = output[j]
    a = temp[0]
    a.append(1)
    b = temp[1]
    s2024 = temp[2]
    Ge = Matrix(Zmod(p),11,11)
    for i in range(9):
        Ge[i,i+1] = 1
        Ge[-2,i] = a[i]
    Ge[-2,-2] = a[-2]
    Ge[-2,-1] = b
    Ge[-1,-1] = 1
    L = Ge^2024
    L1 = vector(ZZ,L.transpose()[:,0].list())
    M = Matrix(ZZ,13,13)
    for i in range(11):
        M[i,i] = 1
        M[i,-1] = L1[i]
    M[-2,-2] = 1
    M[-2,-1] = -s2024
    M[-1,-1] = p
    Q = diagonal_matrix([1]*12 + [2^1000])
    MM = M * Q
    MM = MM.LLL()
    MM = MM / Q
    MM = M.LLL()
    s0 = MM[0][0]
    if abs(s0) < 128:
        m += "0"
    else:
        m += "1"
        
flag = bytes.fromhex(hex(int(m,2))[2:])
print(flag)
# NSSCTF{D3c1s1on_MRG_I5n'7_diFFiCulT_R1GHT?}

Aliyun CTF 2024

打的稀烂，出了一道misc感觉还有点价值，拿来聊一聊。

帕鲁的情绪管理

没有附件，连接靶机，首先解一个sha256的POW，解出来之后提示：

Do you want to training? (y/n) y
sentiment: neutral, text: @JetBlue 1951 BOS to ORD
sentiment: neutral, text: @JetBlue do bags still fly for free anymore?
sentiment: neutral, text: @AmericanAir would like to talk to someone, please follow.
sentiment: neutral, text: @AmericanAir I've tried...its @USAirways anyway
sentiment: neutral, text: @united Bought a round trip to Chicago two days ago...today the same flight is half that! Is there any way for me to get that discount??
sentiment: neutral, text: @JetBlue Says #Lufthansa Incentive Offer To Have No Impact On Share Count - Nasdaq http://t.co/VU7XSWJKiY
sentiment: neutral, text: @AmericanAir i want to change my flight for next week, they will still charge me. Waiting for fligt status
....

会提示进行了一个training过程，然后发送了四十条文本，像是推文，且还自动匹配了一个对应的情绪，然后有：

Now, Do you want to start challenge? (y/n)

我们选择确定，然后会进入一个15轮的challenge：

Round  1/15, text: @SouthwestAir  Just sent DM. Thanks for your attentiveness to this matter.
Please input the answer:

这个验证是很快的，大概不到一秒不回答就超时了，看来是根据推文来回答当前的情绪，自己分析是肯定要超时的，首先想到的就是根据题目给出的training数据获得大量数据看看是否能查找得到当前的情绪。

简单拉了几组数据发现并不简单，数据量非常多，感觉大概在几万组，给出一个整合后的脚本，第一个大模块用来不断链接靶机读取数据，然后存到一个记事本中，由于不清楚数据量到底有多少，以及大概获得多少组数据就可以进行challenge了，所以就干脆慢慢去试，收集到一万组出头的数据后测了十几次终于有一次运气比较好过了：

import itertools
import hashlib
from pwn import *


def parse_tweet_data(tweet_string):
    parts = tweet_string.split(b", text: ")
    sentiment = parts[0][11:].strip()
    text = parts[1].strip()
    return {"sentiment": sentiment, "text": text}


# database prepared
tweet_db = []
with open("output1.txt", "r") as f:
    f = f.readlines()
    for i in range(0, len(f), 2):
        tweet_db.append(
            {"sentiment": f[i + 1].strip()[2:-1], "text": f[i].strip()[2:-1].encode()}
        )
t_len = len(tweet_db)

# read data round
if 0:
    for __ in range(50):

        # get new text
        tweet_db = []
        if __ != 0:
            with open("output1.txt", "r") as f:
                f = f.readlines()
                for i in range(0, len(f), 2):
                    tweet_db.append(
                        {
                            "sentiment": f[i + 1].strip()[2:-1],
                            "text": f[i].strip()[2:-1].encode(),
                        }
                    )
            print(len(tweet_db) - t_len)
        print("Reading data,Round", __ + 1)

        # POW
        r = remote("misc0.aliyunctf.com", 9999)
        k = (r.recvuntil(b'" + "????").encode()) =', drop=1)[-28:]).decode()
        res = r.recvline().strip().decode()
        for item in itertools.product(string.ascii_letters + string.digits, repeat=4):
            str1 = k + "".join(item)
            m = hashlib.sha256(str1.encode()).hexdigest()
            if m == res:
                break
        key1 = "".join(item).encode()
        r.sendline(key1)
        print("POW done!")

        # get new text for next round
        r.recvuntil(b"training? (y/n)", drop=1)
        r.sendline(b"y")
        for _ in range(40):
            try:
                res_tweet = parse_tweet_data(r.recvline())
                add_text = res_tweet["text"]
                choice = True
                for tweet in tweet_db:
                    if tweet["text"] == add_text:
                        choice = False
                        break
                if choice:
                    with open("output1.txt", "a") as f:
                        f.write(str(res_tweet["text"]) + "\n")
                        f.write(str(res_tweet["sentiment"]) + "\n")
            except:
                print(r.recvline().decode())
        t_len = len(tweet_db)
        r.close()

# solve challenge
if 1:
    r = remote("misc0.aliyunctf.com", 9999)
    k = (r.recvuntil(b'" + "????").encode()) =', drop=1)[-28:]).decode()
    res = r.recvline().strip().decode()
    for item in itertools.product(string.ascii_letters + string.digits, repeat=4):
        str1 = k + "".join(item)
        m = hashlib.sha256(str1.encode()).hexdigest()
        if m == res:
            break
    key1 = "".join(item).encode()
    r.sendline(key1)
    print("POW done!")
    r.recvuntil(b"training? (y/n)", drop=1)
    r.sendline(b"n")
    r.recvuntil(b"challenge? (y/n)", drop=1)
    r.sendline(b"y")
    for _ in range(15):
        tline = r.recvline()
        round, target_tweet = tline.split(b", text: ")
        print(round, target_tweet)
        for tweet in tweet_db:
            if tweet["text"] == target_tweet.strip():
                emotion = tweet["sentiment"]
                print("find it!", emotion)
                break
        r.sendline(emotion.encode())
    r.interactive()

[x] Opening connection to misc0.aliyunctf.com on port 9999
[x] Opening connection to misc0.aliyunctf.com on port 9999: Trying 47.99.106.207
[+] Opening connection to misc0.aliyunctf.com on port 9999: Done
POW done!
b' Round  1/15' b'@SouthwestAir its all good. flight eventually took off, and landed safely. oh, and I got the free cup o wine. thx\n'
find it! positive
b'Please input the answer: Round  2/15' b'@USAirways New marketing song? https://t.co/F2LFULCbQ7 let us know what you think? http://t.co/WbhbljJkS7\n'
find it! neutral
b'Please input the answer: Round  3/15' b"@united I'm counting on you, please don't let me down! #delayed #again #needtocatchmynextflight #alreadyrebookedonce\n"
find it! negative
b'Please input the answer: Round  4/15' b'@AmericanAir thank you!\n'
find it! positive
b'Please input the answer: Round  5/15' b'@united we are sitting on the runway for 2 hours! It is ridiculous!!\n'
find it! negative
b'Please input the answer: Round  6/15' b'@SouthwestAir and now no wifi??? Come on.\n'
find it! negative
b'Please input the answer: Round  7/15' b'@united Left item n the seatback on UA1260. Is there any way to call DCA to ask if they have the item? Already submitted lost & found report\n'
find it! neutral
b'Please input the answer: Round  8/15' b'@SouthwestAir I receive bad customer service and ended up spending several hundred dollars to accommodate my family during each cxl flight\n'
find it! negative
b'Please input the answer: Round  9/15' b'@united Listen, learn & do this: Remove your PQD requirement. It is insulting. ^HA\n'
find it! negative
b'Please input the answer: Round 10/15' b'@united Is a snowboard boot bag included in the standard checked baggage next to the snowboard bag?\n'
find it! neutral
b'Please input the answer: Round 11/15' b"@SouthwestAir DAL is due for sleet Sun. eve-didn't see it listed for cities that can re-book?  Fly to DCA at 8:10\n"
find it! neutral
b'Please input the answer: Round 12/15' b'@SouthwestAir its all good. flight eventually took off, and landed safely. oh, and I got the free cup o wine. thx\n'
find it! positive
b'Please input the answer: Round 13/15' b'@united Now about two dozen back in line to see a single CSR for reFlight Booking Problems final leg. (Kiosks on fritz.)\n'
find it! negative
b'Please input the answer: Round 14/15' b'@VirginAmerica awesome. I flew yall Sat morning. Any way we can correct my bill ?\n'
find it! positive
b'Please input the answer: Round 15/15' b"@SouthwestAir we're here at MCO. Thanks.\n"
find it! positive
[*] Switching to interactive mode
Please input the answer: Congratulations! You have passed the challenge!
Here is the flag: aliyunctf{N0_0N3_knOW_5ent1M3Nt_An41Y2E_7H4n_Y0u}
Bye!
[*] Got EOF while reading in interactive

字

非常烧脑的一个脑洞题目：

汉字，又称中文字、华⽂字、华语字、唐话字、唐人字、中国字，为记录汉语而发明的语素文字，受到汉字文化圈广泛使用，为世界唯一仍广泛使用并⾼度发展的语素文字，也是独有的指示会意⽂字体系。最初，由中国上古时代的黄河文明华夏族所发明创制，其字体历经长久改进及演变。目前确切出现的历史尚有讨论空间，最早可追溯至陶文，成熟于约公元前1300年商朝的甲骨⽂、籀文、金⽂，再到春秋战国与秦朝的籀⽂、⼩篆，发展⾄汉朝发生⾪变产⽣隶书并于后世派⽣出草书、楷书、行书，在唐代稳定为今日所用的⼿写字体标准——正楷。

汉字是迄今为止连续使用时间最长的主要⽂字，也是唯⼀使用至今的原生⽂字。相较而⾔，古埃及、巴⽐伦、古印度文字都早已消亡。中国历代皆以汉字为主要官⽅文字，现时在中华人民共和国为实务上的官方文字。汉字在古代已发展至⾼度完备的水准，不单中国使⽤，在很长时期内还充当东亚地区唯一的国际通用⽂字，在20世纪前都是朝鲜半岛、越南、琉球和⽇本等国家的书面规范⽂字。除了汉语之外，古代东亚诸国均有自行创制汉字。

现代汉语汉字⼤体分为传统汉字与简化字两⼤标准，前者主要用于台湾以及香港、澳门，后者则由中国大陆制定并使⽤，且为新加坡、马来西亚等华侨众多的国家采用。⾮汉语体系中，日本将部分汉字自行作简后，成为现在的⽇本新字体，大韩民国也制定了官⽅的朝鲜汉字使⽤规范，⽽史上曾使用过汉字的朝鲜民主主义人民共和国、越南、蒙古等国，汉字现今已不再具有官方规范地位。

此外，汉语也是多数国际组织（例如联合国、上海合作组织等）的⼯作语⾔，加上这些国际组织均采用简体字为⼯作语⾔，以及中国崛起等原因，所以现今多数国家的外国⼈如果学习汉字，均以简体字为主。少数情况下才会学习繁体字（如研究中国历史、研究古代汉语、派驻港澳台地区等）。

## “汉字”语源

“汉字”⼀词最早出自元朝《⾦史》卷九本纪第九，“章宗一”：“十⼋年，封⾦源郡王。始习本朝语言小字，及汉字经书，以进⼠完颜匡、司经徐孝美等侍读”。《⾦史》也出现多次，如：“女真初⽆⽂字，及破辽，获契丹、汉人，始通契丹、汉字，于是诸子皆学之”、“长子布辉，识⼥真、契丹、汉字，善骑射”，将汉族文字、女真族文字、契丹族文字之间互相区别。

在清朝前期，政府官⽅文字是满文，当时已用“汉字”一词称呼中国汉族的传统文字。另外，日本人也称呼为“漢字”，以别于由汉字派生的假名。在李⽒朝鲜，“漢字”则与训民正音（谚文）相区别。在越南，“漢字”则与由汉字派生的喃字相区别。在琉球国，“漢字”则与琉球国字头相区别。

## 汉字的历史 - 繁化与简化

汉字非为一时、⼀地、一⼈所造，是古⼈共同使用流传后的结果，受到多数⼈使用的字形则可流传⾄今，不受流通的字形则收藏在⾦⽯古典，或消失在历史洪流之中。因此，有的字会为了书写简便，省笔或速写渐渐成为另⼀个笔画少的字体，称为“汉字简化”；但是亦有为了使汉字能清晰识别或加强表音、表意，而将字形增加笔画或部件，使得该字能精准表达或是不易更动，称为“汉字繁化”。

“汉字繁化”的⾸要目的是加强汉字的识别度，避免混淆。如国字数字的大小写中，因“一、⼆、三”等数字笔画少，在书写后容易遭到篡改⽽影响金额、数量等利益，除若⼲数字是借⽤笔画较多的他字来代表数字，如以“壹”代“一”、“贰”代“二”、“伍”代“五”、“陆”代“六”、“玖”代“九”等外，另外则采增加笔画或部件⽽造出的汉字数字，如“一”有“弌”、“二”有“弍”、“三”有“弎、叄、叁(亦为参之代字后变体)”、“四”有“䦉”等，在原来的汉字上再加上其他笔画部件，⽽音义并未改变，是汉字繁化情形。“上”和“下”也是由古⽂“丄”（或“𠄞”）和“丅”（或“𠄟”）增笔繁化⽽成。

有些繁化现象，则为加强字理。例如为加强汉字标音功能⽽增加识音的声符。例如“⿒”字，古字作“𠚕”，是⼝中有⽛齿的象形。可能因不易识别字⾳而增加声符“止”作为标⾳，“𠚕”与“齒”的音和义是一样的。又如“⾾”字形是象⼆个散发动手打⽃之⼈，可能因不易识别字音而增加声符“⽃”、“豆”作为标⾳，繁化为“鬦”、“𩰒”，而“⾾”与“鬦”、“𩰒”的⾳和义是⼀样的。如此字义并⽆改变，繁化是为了能增加该字的标音功能。⼜例如替汉字增加义符，像“華”的古字并无上方的“艹”，本身是花朵的象形，后来增添义符“艹”表⽰类属。又如“舂”、“舊”等字所含有的“臼”字，甲骨⽂只作“⼐”，像凹陷下去的形状，然而这形状也很容易被理解作地⾯凹陷下去；因此⾦文就在“凵”内加像米粒、⾕粒的⼩点，增强它的象形成分，使“⾅”义明显。

另外，亦有汉字造字的繁化现象。汉字作为古人识别万事万物的工具，然⽽人事物众多，汉字却有限，若将万事万物都造⼀字表⽰，则汉字数量过于庞⼤，如古时以马作为生活交通⼯具，为不同类型的马造出许多汉字，如“骧(xiāng、ㄒㄧㄤ)：后右蹄白色的马”、“馵(zhù、ㄓㄨˋ)：后左脚白⾊的马”、“𩨊(qián、ㄑㄧㄢˊ)：四蹄全白的马”等字，⼤量增加马部专属的汉字，虽能特定、精准地专指某种马匹的意思，至今却鲜少使⽤。因此，一般仍是以⼀个汉字具备多项意义来运⽤，再由⼀个汉字沿伸出多个汉字，称为“汉字繁化”。而相同字义的汉字繁化，为汉字同源词中的“累增字”，繁化后产⽣不同意义者为汉字同源词中的“后起字”及“孳乳字”。

此处与“简体字”（“相同字义而笔画减省”的汉字）相对，故仅论述“相同字义而笔画增繁”的汉字，即“累增字”，指原字虽已造，然而该字借给他⽤后对于表达原事物的意义渐渐不清，故再增加表意部件来表达原字意义，如“止”本意为脚趾，后世多借⽤此字表示“停留”义，于是加“⾜”繁化为“趾”以示本义；“然”本意为燃烧，后多将其⽤作虚词，原义加“⽕”繁化为“燃”；“它”本意为蛇，但逐渐⽤作代词，本义则加“虫”部繁化为“蛇”。

汉字结构复杂，异体字⾮常多。自古以来已经有许多的俗字，其中有一些是为了书写简便，较之正字笔画减少的简俗字，但俗字多半是人民私下使⽤，正式的文书仍然是⽤繁体字。

近代，处于强势地位的西方⽂明开始进入东亚，整个汉字⽂化圈的各个国家中纷纷掀起了学习西方的思潮。当中有⼈坚持汉字的传统，亦有⿎吹放弃使用汉字。这些⿎吹放弃汉字运动的立论“汉字落后论”，内容为：跟西方拼⾳文字相比，汉字是繁琐笨拙的。尤其在近代个人电脑还没有普遍化以前，因为汉字不能透过打字机书写，⽽必须使⽤巨型的排版房的铅字，也就是说汉字已成为教育及信息化上的瓶颈。但是近代个人电脑普遍化以后，汉字能透过个人电脑输⼊，此种论述已经不具说服性。许多使⽤汉字国家以政治推行的⽅式，进⾏了不同程度的汉字简化，甚至还有完全拼音化的尝试。⽇本的使用假名方案以及汉语多种拼音⽅案的出现都是基于这种考量。

对于“汉字简化”，执⾏的對象有民间及官方⼆种。在民间百姓写字只为纪录或交流，不需要严格遵守笔画规范，因为汉字笔画多，在书写时会有连笔、省笔以求快速书写是古今皆有的现象，如将“⾙”、“見”、“且”、“直”等有框中二横、三横的笔画直接以一直笔代替，这是民间汉字简化的情形，加上普遍在社会中流通，成为民间“⼿头字”、“俗字”；而官方的“汉字简化”则是由政府以公权力进行并颁布实施。

1935年8⽉21日，中华民国国民政府教育部颁布《第一批简体字表》，1936年2月被通令“暂缓推行”。

中华人民共和国政府1956年1月28日发布《汉字简化方案》，1964年5⽉审定通过《简化字总表》，客观上配合了不久之后的文化大革命“破四旧”政策。1986年经少量修订后重新发表，⼀直在中国⼤陆地区使⽤⾄今。1977年，曾公布《第⼆批汉字简化⽅案（草案）》，发布“⼆简字”，试用一段时间（约八年）后因为字形过于简陋且混乱而停用，并于1986年正式宣布废除。新加坡和马来西亚政府分别发布了同中国大陆《简化字总表》相同的简化字表。

日本政府在二战结束后也进行了汉字简化。1946年日本内阁公布了《当用汉字表》，收字1850个，其中对部分汉字进行了简化，有些简化后的汉字与中国大陆简化后的汉字一致，有些则有一定差异，部分为日本自创。

发现题目中有一些字长得不大一样，网上搜索了一下发现是康熙部首，当时第一时间想到把这些康熙部首单独拿出来看看是不是有什么加密，去维基上查了一下对应关系，转化了几次没试出来。

看了官方wp，并不是直接全拿出来进行了什么什么加密，而是文章中相同的字有的被替换成了康熙部首，有的并没有替换，需要提取出所有带有对应康熙部首的字，然后根据是否替换来得到一串01序列密文。

这里的映射关系来自：unicode.org/Public/13.0.0/ucd/EquivalentUnifiedIdeograph.txt

unicode = open('unicode.txt', 'r').readlines()
hanzi = []
kangxi = []
for line in unicode:
    line = line.split()
    hanzi.append(chr(int(line[2], 16)))
    kangxi.append(chr(int(line[0], 16)))

得到序列之后将密文所有的字全部过一遍，得到筛选后的01序列：

enc = open('enc.txt', 'r', encoding='utf-8').read()

binary = []
for ch in enc:
    if ch in hanzi:
        binary.append('0')
    elif ch in kangxi:
        binary.append('1')
binary = ''.join(binary)

#00100000000010010000010011110110100010011000101101000001010011010011000101000101110001101111010011001101100010000100000000100000101101011110010000110110010010110101111001000011011001010111101000100011011000111001011101000101010111010001010101110100010101010110100100011001101100100011011000100001000000001000111111100000000000000000

这串序列末尾有非常多的0，然后后面还接着七个连续的1，如果我们把这七个1看做终止符的话，剩下的308位刚好能被7整除，猜测是7位一个对应，这里是用了GB2312字符集加密，直接decode用对应的字符集解密即可：

unicode = open('unicode.txt', 'r').readlines()
hanzi = []
kangxi = []
for line in unicode:
    line = line.split()
    hanzi.append(chr(int(line[2], 16)))
    kangxi.append(chr(int(line[0], 16)))

enc = open('enc.txt', 'r', encoding='utf-8').read()

binary = []
for ch in enc:
    if ch in hanzi:
        binary.append('0')
    elif ch in kangxi:
        binary.append('1')
binary = ''.join(binary)[:315-7] 

gb = []
for i in range(0, len(binary), 7):
    gb.append(f'{int(binary[i:i+7], 2) + 0xA0:02X}')
gb = ''.join(gb)

msg = bytes.fromhex(gb).decode('GB2312')
print(msg)