nss4th

发表于 更新于

周末闲着打了打，大部分时间卡着RSA那里了导致后面的LeetSpe4k没看，不然肯定可以再做一题的/(ㄒoㄒ)/~~

Guillotine

题目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
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}")

这种典型的格一眼就是可以用 cuso 一把梭的，但是注意代码

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

直接丢 cuso 肯定不行，不过对于 [A,B][i] 这种二者挑一个的话可以看作 (1 - x) A + x B 这样子就可以改作 cuso 能用的式子了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
from sage.all import var
import random
from ast import literal_eval
from pwn import *
from cuso import find_small_roots

r = remote('node9.anna.nssctf.cn', 22723)
p, n, m = 257, 36, 50
es = var(','.join(f'e_{i}' for i in range(m)))
ss = var(','.join(f's_{i}' for i in range(n)))
bounds = {}

for i in es:
    bounds[i] = (-4, 5)
for i in ss:
    bounds[i] = (-1, 2)
    
random.seed(int(1337))
A = [[[random.randrange(p) for i in range(2)] for j in range(n)] for i in range(m)]

B = literal_eval(r.recvline().strip().decode().split('B: ')[-1])

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

s = ['?'] * n
roots = find_small_roots(relations=F, bounds=bounds, modulus=p)[0]
for i in roots:
    ii = str(i)
    if 's_' in ii:
        s[int(ii.split('_')[-1])] = str(roots[i])


secret = int(''.join(s).zfill(36)[::-1], 2)
print(secret)
r.recvline()
r.sendlineafter(b'>', str(secret).encode())
r.interactive()

HiddenOracle

题目

1
2
3
4
5
6
7
8
9
10
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)

第一步先随便输点东西恢复ECC的参数，然后发现它的阶是等于模数的，所以解ECDLP是可行的

然后就是一个稀疏多项式插值的问题，我们可以用 Ben-Or/Tiwari 算法就可以解决了。

但是不知道为啥拿到的 A 的顺序和实际的不符，可能哪里写的有的问题，丢给 GPT 更乱了。那就不管了，反正 GPT 的代码也还可以跑而且 1/64 的概率也是一个样的挂一段时间就出来了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
from Crypto.Util.number import *
from sage.all import *
from pwn import remote, process
from tqdm import trange

''' step 1'''
def solvep(x,y):
    from functools import reduce

    A=[]
    for i in range(len(x)-2):
        A.append(abs((x[i+1]-x[i])*(pow(y[i+2],2)-pow(y[i+1],2)-pow(x[i+2],3)+pow(x[i+1],3))-(x[i+2]-x[i+1])*(pow(y[i+1],2)-pow(y[i],2)-pow(x[i+1],3)+pow(x[i],3))))
    return reduce(GCD, A)

def solvea(x,y,p):
    return ((pow(y[1],2)-pow(y[0],2)-pow(x[1],3)+pow(x[0],3))*inverse(x[1]-x[0],p))%p

def solveb(x,y,p,a):
    return (pow(y[0],2)-pow(x[0],3)-a*x[0])%p


R = [(171819077447104349729775318230128610329, 100881689251479188167408877430920651395), (146159606192758583249716113758919783753, 80533281247513973659122060089873270989), (59017974640689970995344196273079355184, 104746038157191809171185097730819308641), (197595545243296583966922301250921927421, 124928953110104935664793476365310710267), (73968574145300091693338909355207503860, 186652589263761044876849068334695198879), (235827423492689864475083287633450448774, 172913282150535116698543986314403198219), (108003866338161147025654122299627959057, 106135106599969220245633457159754254343), (147930291615697867998498043226133690759, 166883835501879812581658678603301948629)]
X = [i[0] for i in R]
Y = [i[1] for i in R]
p = solvep(X, Y) // 2
assert isPrime(p)
a = solvea(X, Y, p)
b = solveb(X,Y,p,a)

E = EllipticCurve(GF(p), [a, b])
for i in R:
    print(E(i))

print(a, b, p)
'''
a = 190000065892557574829635621682189530240 
b = 5554245539026928962619432281074770856 
p = 239475380061526138915008749403622049527
'''


''' step 2'''


a = 190000065892557574829635621682189530240 
b = 5554245539026928962619432281074770856 
p = 239475380061526138915008749403622049527

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

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)

# r = process(['python', 'chall.py'])
# print(int(r.recvline()))
while 1:
    r = remote('node8.anna.nssctf.cn', 26520)
    out = []
    for i in trange(128):
        r.sendlineafter(b'[?] ', str(2**i))
        Q = E(eval(r.recvline().split(b'] ')[-1]))
        out.append(SmartAttack(P, Q, p))

    t = 64
    if len(out) != 2 * t:
        print(f"[!] 错误: 你需要在 'out' 列表中提供 {2*t} 个值。")
        print(f"[!] 当前列表有 {len(out)} 个值。")
        exit()

    # 定义有限域
    Fp = GF(p)
    # 选择与你查询时相同的基数 g
    g = Fp(2)


    # 将输入列表转换为有限域中的向量
    try:
        v = vector(Fp, [int(val) for val in out])
        print(f"[+] 成功加载 {len(v)} 个 oracle 输出值。")
    except (ValueError, TypeError) as e:
        print(f"[!] 错误: 无法将 'out' 列表中的值转换为整数。请检查你的输入。")
        print(f"[!] 原始错误: {e}")
        exit()


    # --- 步骤 2: 求解定位多项式 ---
    print("[+] 正在构建汉克尔矩阵并求解线性方程组...")
    M = Matrix(Fp, t, t, lambda i, j: v[i+j])

    if M.is_singular():
        print("[!] 矩阵 M 不可逆，可能的原因是你的输入数据有误，或者需要更换基数 g。")
        exit()

    b = -vector(Fp, [v[i+t] for i in range(t)])
    lambda_coeffs = M.solve_right(b)
    print("[+] 定位多项式系数求解成功！")

    Rz = Fp['z']
    z = Rz.gen()
    Lambda = z**t + sum(lambda_coeffs[i] * z**i for i in range(t))

    # --- 步骤 3: 恢复指数 B_i ---
    print("[+] 正在求解定位多项式的根...")
    roots_m = Lambda.roots(multiplicities=False)

    print("[+] 正在通过离散对数恢复指数 B_i...")
    exponents_B = [log(m, g) for m in roots_m]

    # --- 步骤 4: 恢复系数 A_i ---
    print("[+] 正在构建范德蒙德矩阵以求解系数 A_i...")
    V = Matrix(Fp, t, t, lambda j, i: g**(j * exponents_B[i]))

    if V.is_singular():
        print("[!] 范德蒙德矩阵 V 不可逆，这通常不应该发生。")
        exit()

    v_sub = v[:t]
    coeffs_A = V.solve_right(v_sub)
    print("[+] 所有系数 A_i 恢复成功！")

    # --- 步骤 5: 找到 A[0] ---
    term_map = {int(B): A for B, A in zip(exponents_B, coeffs_A)}
    A = [i[1] for i in term_map.items()]
    t = str(choice(A)).encode()
    print(t)
    r.sendlineafter(b"[*]", t)
    try:
        flag = r.recvline()
        if flag:
            print(flag)
            break
    except:
        r.close()
        pass

LeetSpe4k

题目

1
2
3
4
5
6
7
8
9
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

这种一眼肯定也是 cuso 可以大力出奇迹的玩意。

方法一

第一种思路很简单，就是直接把每个 ascii 设做变量，然后带进 h4sH 里面。然后对于约束条件的话，就看假如 le4t 里面如果对应的是 H，那么这个变量就是 Hh 的二者其中一个，可以写作等式 (H-x)(h-x) 毕竟这个等式恒唯一。但是测试发现至少要有 22 个已知的字符(不算 _），算上 NSSCTF{ 和 !} 也差 11 个。爆破的话要大概 61 h，不过算了算比赛时间开多线程也是可用的，就贴一个理论秒出的随机寻找代码了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
from sage.all import *
from cuso import find_small_roots   
from functools import reduce

from random import choice

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())


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']
c1 = 'NSSCTF{H@pPy_A7h_Anniv3R$arY_ns$C7F_@nD_l3t$_d0_7h3_LllE3t$pEAk!}'
c2 = 9114319649335272435156391225321827082199770146054215376559826851511551461403

start = 20
end = -2
n = []
for i in c1[start:end]:
    if i not in '_!':
        for j in table:
            if i in j:
                n.append(j)
        
h4sH = lambda x: reduce(lambda acc, i: (acc * (2**255 + 95)) + i, x, 0)

xs = var([f'x_{i}' for i in range(len(n))])

while 1:
    c1 = 'NSSCTF{' + le4t(b'Happy_4th_ann') + 'iv3R$arY_ns$C7F_@nD_l3t$_d0_7h3_LllE3t$pEAk!}'
    T = [*map(ord, c1[:start])]
    jj = 0
    for i in c1[start:end]:
        if i not in '_!':
            T.append(xs[jj])
            jj += 1
        else: T.append(ord(i))
        
    T += [*map(ord, c1[end:])]
    f = h4sH(T) - c2
    bounds={}
    for i in range(len(n)):
        bounds[xs[i]] = (min(map(ord, n[i])) - 1, 122)

    F = [f]
    for i in range(len(n)):
        F += [prod(xs[i] - ord(n[i][j]) for j in range(len(n[i])))]
    try:
        print(find_small_roots(F, bounds, [2**256] + [None] * (len(F) - 1)))
        break
    except: pass

方法二

这样子不能直接出的原因是要规约的元素太大了，我们要想办法减少规约值的大小才可以。我们可以发现，对于每一个元素我们都已经限定了它的明文空间了。就比如密文第九个字符是 @，那么其明文就是 'a@4A' 其中一个。我们可以定义四个变量把这个地方写作 x1 * a + x2 * @ + x3 * 4 + x4 * A 这样子虽然多了几个变量但是规约的大小也大大变小了。

那么对于这个 FNV 我们可以改成很多的 0、1 变量和 table 的值的乘积和再进行规约就可以不用做爆破规约出想要的答案了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
from sage.all import *
from cuso import find_small_roots   
from functools import reduce

from random import choice

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)) + i, x, 0)


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']
c1 = 'NSSCTF{H@pPy_A7h_4nNiv3R$arY_ns$C7F_@nD_l3t$_d0_7h3_LllE3t$pEAk!}'
c2 = 9114319649335272435156391225321827082199770146054215376559826851511551461403

start = 7
end = -2
n = []
for i in c1[start:end]:
    if i not in '_!':
        for j in table:
            if i in j:
                n.extend(j)

xs = PolynomialRing(Zmod(2**256), names=[f'x_{i}' for i in range(len(n))], implementation="generic").gens()
T = [*map(ord, c1[:start])]
jj = 0
F = []
for i in c1[start:end]:
    if i not in '_!':
        for j in table:
            if i in j:
                T.append(sum(xs[jj + k] * ord(j[k]) for k in range(len(j))))
                F.append(sum(xs[jj + k] for k in range(len(j))) - 1)
                jj += len(j)
    else: T.append(ord(i))
T += [*map(ord, c1[end:])]
f = h4sH(T) - c2
F += [f]
bounds={}
for i in range(len(n)):
    bounds[xs[i]] = (-1, 2)
roots = find_small_roots(F, bounds)[0]
# [{x_133: 0, x_132: 1, x_131: 0, x_130: 0, x_129: 1, x_128: 0, x_127: 0, x_126: 0, x_125: 1, x_124: 0, x_123: 1, x_122: 0, x_121: 0, x_120: 1, x_119: 0, x_118: 1, x_117: 0, x_116: 0, x_115: 1, x_114: 0, x_113: 0, x_112: 0, x_111: 0, x_110: 1, x_109: 1, x_108: 0, x_107: 0, x_106: 1, x_105: 0, x_104: 0, x_103: 1, x_102: 0, x_101: 0, x_100: 0, x_99: 1, x_98: 0, x_97: 0, x_96: 1, x_95: 0, x_94: 1, x_93: 0, x_92: 1, x_91: 0, x_90: 0, x_89: 0, x_88: 1, x_87: 1, x_86: 0, x_85: 0, x_84: 0, x_83: 1, x_82: 0, x_81: 0, x_80: 0, x_79: 1, x_78: 0, x_77: 0, x_76: 1, x_75: 0, x_74: 1, x_73: 0, x_72: 1, x_71: 0, x_70: 0, x_69: 0, x_68: 0, x_67: 1, x_66: 1, x_65: 0, x_64: 0, x_63: 0, x_62: 1, x_61: 1, x_60: 0, x_59: 1, x_58: 0, x_57: 0, x_56: 0, x_55: 0, x_54: 0, x_53: 0, x_52: 1, x_51: 0, x_50: 1, x_49: 0, x_48: 1, x_47: 1, x_46: 0, x_45: 0, x_44: 1, x_43: 0, x_42: 0, x_41: 0, x_40: 0, x_39: 1, x_38: 0, x_37: 0, x_36: 1, x_35: 1, x_34: 0, x_33: 0, x_32: 0, x_31: 1, x_30: 1, x_29: 0, x_28: 0, x_27: 1, x_26: 0, x_25: 1, x_24: 1, x_23: 0, x_22: 0, x_21: 0, x_20: 0, x_19: 1, x_18: 1, x_17: 0, x_16: 0, x_15: 0, x_14: 1, x_13: 0, x_12: 0, x_11: 1, x_10: 0, x_9: 0, x_8: 1, x_7: 1, x_6: 0, x_5: 0, x_4: 0, x_3: 1, x_2: 0, x_1: 0, x_0: 1}]
flag = ''
for t in T:
    if type(t) == int:
        flag += chr(t)
        continue
    flag += chr(int(t.subs({xi: roots[xi] for xi in roots})))
print(flag)

*IqqT

题目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
from Crypto.Util.number import * 
from secret import flag

while 1:
    p = getStrongPrime(512)
    q = getStrongPrime(512)
    if (GCD(p-1,q-1)) == 2:
        break

Dbits = 440
N = p*q
phi = (p - 1) * (q-1)
d1 = getPrime(Dbits)
d2 = getPrime(Dbits)
e1 = pow(d1, -1,phi)
e2 = pow(d2, -1,phi)
m = bytes_to_long(flag)
c = pow(m,e1,N)
c = pow(c,e2,N)

print(f"n = {N}")
print(f"e1 = {e1}")
print(f"e2 = {e2}")
print(f"c = {c}")

# n = 153098639535230461427067981471925418840838598338005180035334795636906122233147195601425250354397215037964687813767036136951747775082105669481477681815877751367786247871862319200300034505895599830252899234816623479894529037827470533297869568936005422622937802442126007732338221711447957108942595934348420152967
# e1 = 26675174225063019792412591801113799130868333007861486357720578798352030914999710926292644671603600643369845213171396954004158372043593223603274138224817810197939227716991483870437629436082594926630937775718564690554680519001757082557490487364436474044434348412437933432480883175650430050712391958500932343901
# e2 = 43950877784211432364704383093702059665468498126670135130662770287054349774316943441695986309047768423965591753129960761705976613430837039441242214744782506036708881166308335886272786409715558332802625980679432726451306523481798238346507261619084743433957076290727858148266709423500224748925763767341340730807
# c = 93877717323267388927595086106164695425439307573037159369718380924127343418544815509333679743420188507149532789861080535086578879105173477672709484480809535461054572173818555600022970592546859742598747214025487041690467952494343056536435494716815059600034890617984024099540213482984895312025775728869974483561

看着就头大，润