昨天的一场比赛，看了一眼就外出了，今天补上。学到了不少东西。CUSO神力！！

Guillotine

题目：

import random

flag = 'NSSCTF{**************************}'
p, n, m = 257, 36, 50
e = [choice(range(-3,4)) for i in range(m)]
secret = random.randrange(1,2^n)

random.seed(int(1337))
A = [[[random.randrange(p) for i in range(2)] for j in range(n)] for i in range(m)]
B = []

for time in range(m):
    b = (sum(A[time][j][(secret >> j) & 1] for j in range(n))+e[time])%p
    B.append(b)

print("give you B:",B)

alarm(10)
print("The time for defiance is over. Provide the encryption key, and you shall be granted the mercy of a swift end. Refuse, and your death will be prolonged.")
assert int(input(">")) == secret
print(f"Do you really think I would let you go? {flag}")

$A,B$已知，$e_{t}\in(-3,3)$，且有一共50组这样的式子:

$B_{t}=\sum_{j=0}^{n-1} A_{t}[j][secret_{bit}]+e_{t}\pmod{p}$

第一直觉是LWE，尝试了优化的primary attack，但是失败了（然后就出门了）。后面比赛后得知有CUSO这个东西，直接梭哈。设$secret=(x_{0},x_{1},\dots,x_{n})$有式子：

${B}_{t}=\sum_{j=0}^{n-1} \left( A_{t}[j][0] \cdot (1 - {x}[j]) + A_{t}[j][1] \cdot {x}[j] \right) + e_{t}\pmod{p}$

from pwn import *
import cuso
import random
import os

context.log_level = 'debug'
os.environ['DYLD_LIBRARY_PATH'] = "/Users/nightmare/flatter/build/lib"
p = 257
n = 36
m = 50
random.seed(int(1337))
A = [[[random.randrange(p) for i in range(2)] for j in range(n)] for i in range(m)]
vars = var(','.join([f'x{i}' for i in range(n)]))
es = var(','.join([f'e{i}' for i in range(m)]))

bounds = {eval(f"x{i}"): (-1, 2) for i in range(n)} 
bounds.update({eval(f"e{i}"): (-4, 5) for i in range(m)})
relations = []

io = remote('node6.anna.nssctf.cn', '29938')
B = eval(io.recvline().split(b': ')[1])

for time in range(m):
    equation = sum(A[time][j][0] * (1 - vars[j]) + A[time][j][1] * vars[j] for j in range(n)) + es[time] - B[time]
    relations.append(equation)

roots = cuso.find_small_roots(relations, bounds, modulus=p)[0]
res = ''.join([str(roots[eval(f'x{_}')]) for _ in range(n)])[::-1]
secret = int(res, 2)
print(secret)
io.sendlineafter(b'>' ,str(secret).encode())
flag = io.recvline()
print(flag)
io.interactive()

LeetSpe4k

题目：

from functools import reduce
from random import choice
from secret import flag

le4t = lambda x: "".join(choice(next((j for j in ['a@4A', 'b8B', 'cC', 'dD', 'e3E', 'fF', 'g9G', 'hH', 'iI', 'jJ', 'kK', 'l1L', 'mM', 'nN', 'o0O', 'pP', 'qQ', 'rR', 's$5S', 't7T', 'uU', 'vV', 'wW', 'xX', 'yY', 'z2Z'] if i in j), i)) for i in x.decode())
h4sH = lambda x: reduce(lambda acc, i: ((acc * (2**255+95)) % 2**256) + i, x, 0)

print(le4t(flag), h4sH(flag))
#nSsCtf{H@pPy_A7h_4nNiv3R$arY_ns$C7F_@nD_l3t$_d0_7h3_LllE3t$pEAk!} 9114319649335272435156391225321827082199770146054215376559826851511551461403

题目很短，也不难发现这是一道关于fnv的题目，就自然而然有式子：

$hash(flag)=\sum_{i=1}^{n}c_{i}g^{n-i}\pmod{p}$

直接造格没法求解且leet字符并没用上。开始想到的是对leet字符的ascii码做离散化使得他落在小范围内能够直接规约出结果，但是发现这并不是一件容易的事情。在求助@tangcuxiaojikuai之后，得知，可以把每个$c_{i}$写成bit向量乘上leet集的形式，比如把a替换成@可以写成：$(0,1,0,0)*(a,@,4,A)^T$。根据这个形式可以对fnv的格进行优化，然后就可以出了。但是发现cuso好像更加暴力便捷，于是选择了用cuso。

import cuso
import os

os.environ['DYLD_LIBRARY_PATH'] = "/Users/nightmare/flatter/build/lib"

table = ['a@4A', 'b8B', 'cC', 'dD', 'e3E', 'fF', 'g9G', 'hH', 'iI', 'jJ', 'kK', 'l1L', 'mM', 'nN', 'o0O', 'pP', 'qQ', 'rR', 's$5S', 't7T', 'uU', 'vV', 'wW', 'xX', 'yY', 'z2Z']

h4sH = lambda x: reduce(lambda acc, i: ((acc * (2**255+95)) % 2**256) + i, x, 0)
flag = '{H@pPy_A7h_4nNiv3R$arY_ns$C7F_@nD_l3t$_d0_7h3_LllE3t$pEAk!}'

g = 2^255 + 95
p = 2^256
flag_example = 'NSSCTF' + ''.join([char if char in {'{', '}', '_', '!'} else '\x00' for char in flag])
flag_example = flag_example.encode()

hash_value = 9114319649335272435156391225321827082199770146054215376559826851511551461403
hash_value = hash_value - h4sH(flag_example)

leet_index = []
vars = []
cur_len = -1
dict = {}
for leet_char in flag:
    if leet_char in ['{', '}', '_', '!']: continue
    cur_len += 1
    for table_char in table:
        if leet_char in table_char:
            vars.append(var(','.join([f'x_{cur_len}_{tab_len}' for tab_len in range(len(table_char))])))
            leet_index.append(table.index(table_char))

idx = -1
equation = []
bit_equation = []
bound = {}
for i in range(len(flag_example)):
    if flag_example[i]: continue
    idx += 1
    s = sum(vars[idx][j] * ord(table[leet_index[idx]][j]) for j in range(len(table[leet_index[idx]])))
    equation.append(s * (g ^ (len(flag_example)- i - 1)))
    bit_equation.append(sum(vars[idx][j] for j in range(len(table[leet_index[idx]]))) - 1)
    bound.update({eval(f"x_{idx}_{j}"): (-1, 2) for j in range(len(table[leet_index[idx]]))})
equation = sum(equation) - hash_value

relations = [equation] + bit_equation
res = cuso.find_small_roots(relations, bounds=bound, modulus=p)[0]

flag = ''
idx = -1
for i in range(len(flag_example)):
    if flag_example[i]:
        flag += chr(flag_example[i])
        continue
    idx += 1
    bit_dic = [f'x_{idx}_{j}' for j in range(len(table[leet_index[idx]]))]
    for j in range(len(bit_dic)):
        if res[eval(bit_dic[j])] == 1:
            flag += table[leet_index[idx]][j]
            break
print(flag)

HiddenOracle

题目：

from treasure import FLAG, p, a, b  
  
E = EllipticCurve(GF(p), [a,b])  
A = [randint(0,p) for _ in range(64)]  
B = sorted([randint(0,p) for _ in range(64)])  
oracle = lambda x: sum([a*pow(int(x),b,p) for a,b in zip(A,B)])*E.lift_x(0x1337)  
  
for _ in range(128):  
    print("[+]", oracle(input("[?] ")).xy())  
if int(input("[*]")) == A[0]: print(FLAG)

一共有128组，其中$G$为$E$上横坐标为0x1337的点：

$leak_{i}=\left( \sum_{j}a_{j}\cdot (x_{i}^{b_{j}} \mod p) \right)*G$

可以知道$leak$的点肯定都是在曲线上的，所以可以先恢复一下系数。恢复完系数之后，可以发现该曲线的order=p，那就可以直接打smart attack求出$\sum_{j}a_{j}\cdot (x_{i}^{b_{j}} \mod p)$。难点在于如何根据128个式子求出$a_{0}$。在@adwa的帮助下，找到了Ben-Or/Tiwari这个算法，此处相当于只有一个元，照着搓搓就好了。

from pwn import *

def SmartAttack(P,Q,p):
    E = P.curve()
    Eqp = EllipticCurve(Qp(p, 2), [ ZZ(t) + randint(0,p)*p for t in E.a_invariants() ])

    P_Qps = Eqp.lift_x(ZZ(P.xy()[0]), all=True)
    for P_Qp in P_Qps:
        if GF(p)(P_Qp.xy()[1]) == P.xy()[1]:
            break

    Q_Qps = Eqp.lift_x(ZZ(Q.xy()[0]), all=True)
    for Q_Qp in Q_Qps:
        if GF(p)(Q_Qp.xy()[1]) == Q.xy()[1]:
            break

    p_times_P = p*P_Qp
    p_times_Q = p*Q_Qp

    x_P,y_P = p_times_P.xy()
    x_Q,y_Q = p_times_Q.xy()

    phi_P = -(x_P/y_P)
    phi_Q = -(x_Q/y_Q)
    k = phi_Q/phi_P
    return ZZ(k)

point = [(161327874338378710119045173360110020172, 146211053105565414607092824897476611769),
(18640344881989485589826421817204171679, 93612267272283301509698942398210487992),
(157134026509852901241125107586310827797, 47069415459314099567908898235034040542),
(113155526393230548108441293824806664192, 97811312431923646161921683294127113172),
(175820630411500611266721556942898858534, 215536195888802052297970999177605243285)]

PR.<a, b> = PolynomialRing(ZZ)
F = []
for i in range(5):
    x, y = point[i]
    f = x^3 + a * x + b - y^2
    F.append(f)

res = Ideal(F).groebner_basis()
p = int(res[2])
a, b = p - res[0].constant_coefficient(), p - res[1].constant_coefficient()

E = EllipticCurve(GF(p), [a,b])
G = E.lift_x(0x1337)

context.log_level = 'debug'
# io = remote('')
io = process(['python', '/Users/nightmare/myCode/NSSCTF4th/example.py'])

t = 64
F = GF(p)
g = F.multiplicative_generator()
v = []
for i in range(2*t):
    io.sendlineafter(b'[?] ', str(g^i).encode())
    leak = E(eval(io.recvline().split(b']')[1]))
    v.append(SmartAttack(G, leak, p))

V = matrix([v[i:i+t] for i in range(t)])
assert rank(V) == t

s = -vector(v[t:2*t])
L = V.solve_right(s)

PR.<z> = PolynomialRing(F)
Lambda = z^t + sum(F(L[i]) * z^i for i in range(t))
R = Lambda.roots(multiplicities=False)
B = [m.log(g) for m in R]

V = matrix([[m^i for m in R] for i in range(t)])
b = vector(v[:t])

a = V.solve_right(b)
a0 = a[B.index(min(B))]
io.sendlineafter(b"[*]", str(a0).encode())
io.close()

N1gh7ma12e的小站

NSS 4th

Guillotine

LeetSpe4k

HiddenOracle