SUCTF2025-crypto

SUCTF2025

题目很不错,但就出了两题,还有几题感兴趣的,有时间复现一下

密码做题步骤:发动强大的搜索引擎,先拿代码问GPT,得到代码的大致流程和一些关键信息(比如算法、用到的知识点),然后打开搜索引擎(bing、Google),开始搜索对应知识点,最最重要的是:在前面加上ctf,然后对知识点加上双引号(搜索结果包含),然后直接找wp有脚本就好啦!

SU—signin

题目

数据就不贴了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
from Crypto.Util.number import *
from secret import flag

bit_length = len(flag) * 8

p = 0x1a0111ea397fe69a4b1ba7b6434bacd764774b84f38512bf6730d2a0f6b0f6241eabfffeb153ffffb9feffffffffaaab
K = GF(p)
E = EllipticCurve(K, (0, 4))
o = 793479390729215512516507951283169066088130679960393952059283337873017453583023682367384822284289
n1, n2 = 859267, 52437899

while(1):
G1, G2 = E.random_element(), E.random_element()
if(G1.order() == o and G2.order() == o):
P1, P2 = (o//n1)*G1, (o//n2)*G2
break

cs = [(randrange(0, o) * P1 + randrange(0, o) * G2).xy() if i == "1" else (randrange(0, o) * G1 + randrange(0, o) * P2).xy() for i in bin(bytes_to_long(flag))[2:].zfill(bit_length)]
print(cs)

解题

通过搜索是BLS12-381曲线,知道了有良好的双线性配对,正好毕设了解过。

P1=pn2G1,P2=pn2G2flag的比特位为0时,我们有csi=aP1+bG2=apn2G1+bG2因此当我们用n2乘以上式之后,有csi=apG1+bn2G2=kiG2modp根据双线性配对的性质e(a,a)=1,e(ka,a)=1k=1所以只要我们遍历cs,然后利用双线性配对就可以判断这个比特为是否为0;反之,为1P_1=\frac{p}{n_2}*G_1,P_2=\frac{p}{n_2}*G_2 \\ 当flag的比特位为0时,我们有cs_i=a*P_1+b*G_2=a*\frac{p}{n_2}*G_1+b*G_2 \\ 因此当我们用n_2乘以上式之后,有cs_i=a*p*G1+b*n_2*G_2=k_i*G_2 \mod p \\ 根据双线性配对的性质e(a,a)=1,e(k*a,a)=1^k=1 \\ 所以只要我们遍历cs,然后利用双线性配对就可以判断这个比特为是否为0;反之,为1

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
from Crypto.Util.number import long_to_bytes
import ast

# BLS12-381 curve
p = 0x1a0111ea397fe69a4b1ba7b6434bacd764774b84f38512bf6730d2a0f6b0f6241eabfffeb153ffffb9feffffffffaaab
K = GF(p)
E = EllipticCurve(K, (0, 4))
o = 793479390729215512516507951283169066088130679960393952059283337873017453583023682367384822284289
n1, n2 = 859267, 52437899
cs = ast.literal_eval(open("chall.txt").read())
cs = [E(c) for c in cs]

is0=cs[0]
is0=is0*n2

flag=''
for i in cs:
tmp=is0.weil_pairing(i*n2,o)
if tmp==1:
flag+='0'
else:
flag+='1'
print(flag)
print(long_to_bytes(int(flag,2)))
"""
01010011010101010100001101010100010001100111101101010111011001010011000101100011011011110110110101100101010111110101111101010100001100000101111101011111010100110101010101000011010101000100011001011111010111110011001000110000001100100011010101111101
b'SUCTF{We1come__T0__SUCTF__2025}'
"""

SU_mathgame

题目

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
import socketserver
import signal
from Crypto.Util.number import *
from random import randint
import time
from sage.geometry.hyperbolic_space.hyperbolic_isometry import moebius_transform
from secret import flag

banner = br'''
_____ ______ ________ _________ ___ ___ ________ ________ _____ ______ _______
|\ _ \ _ \|\ __ \|\___ ___\\ \|\ \ |\ ____\|\ __ \|\ _ \ _ \|\ ___ \
\ \ \\\__\ \ \ \ \|\ \|___ \ \_\ \ \\\ \ \ \ \___|\ \ \|\ \ \ \\\__\ \ \ \ __/|
\ \ \\|__| \ \ \ __ \ \ \ \ \ \ __ \ \ \ \ __\ \ __ \ \ \\|__| \ \ \ \_|/__
\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \|\ \ \ \ \ \ \ \ \ \ \ \ \_|\ \
\ \__\ \ \__\ \__\ \__\ \ \__\ \ \__\ \__\ \ \_______\ \__\ \__\ \__\ \ \__\ \_______\
\|__| \|__|\|__|\|__| \|__| \|__|\|__| \|_______|\|__|\|__|\|__| \|__|\|_______|

'''
welcome = b"\nWelcome to my math game, let's start now!\n"


class Task(socketserver.BaseRequestHandler):
def _recvall(self):
BUFF_SIZE = 2048
data = b''
while True:
part = self.request.recv(BUFF_SIZE)
data += part
if len(part) < BUFF_SIZE:
break
return data.strip()

def send(self, msg, newline=True):
try:
if newline:
msg += b'\n'
self.request.sendall(msg)
except:
pass

def recv(self, prompt=b'SERVER <INPUT>: '):
self.send(prompt, newline=False)
return self._recvall()

def game1(self):
self.send(b"\nLet's play the game1!")
rounds = 1000
pseudo_prime = int(self.recv(prompt=b'[+] Plz Tell Me your number: '))
if isPrime(pseudo_prime):
self.send(b"\nNo! it's a prime, go away!")
self.request.close()
for i in range(rounds):
if pow(randint(2, pseudo_prime), pseudo_prime - 1, pseudo_prime) != 1:
self.send(b"\nYou failed in round " + str(i + 1).encode() + b', bye~~')
self.request.close()
self.send(b"\nCongratulations, you have won the game1!\n")
return True

def game2(self):
self.send(b"Let's play the game2!")
res = self.recv(prompt=b'[+] Plz give Me your a, b, c: ')
a,b,c = [int(x) for x in res.split(b',')]
try:
assert (isinstance(a, int) and isinstance(a, int) and isinstance(c, int))
assert a > 0
assert b > 0
assert c > 0
assert a / (b + c) + b / (a + c) + c / (a + b) == 4
assert int(a).bit_length() > 900 and int(a).bit_length() < 1000
assert int(b).bit_length() > 900 and int(b).bit_length() < 1000
assert int(c).bit_length() > 900 and int(c).bit_length() < 1000
self.send(b"\nCongratulations, you have won the game2!\n")
return True
except:
self.send(b"\nNo! Game over!")
self.request.close()

def final_game(self):
self.send(b"Let's play the game3!")
set_random_seed(int(time.time()))
C = ComplexField(999)
M = random_matrix(CC, 2, 2)
Trans = lambda z: moebius_transform(M, z)
out = []
for _ in range(3):
x = C.random_element()
out.append((x,Trans(x)))
out = str(out).encode()
self.send(out)
kx = C.random_element()
kx_str = str(kx).encode()
self.send(kx_str)
C2 = ComplexField(50)
ans = C(self.recv(prompt=b'[+] Plz Tell Me your answer: ').decode())
if C2(ans) == C2(Trans(kx)):
self.send(b"\nCongratulations, you have won the game3!")
self.send(flag)
self.request.close()
else:
self.send(b"\nNo! Game over!")
self.request.close()

def handle(self):
signal.alarm(300)
self.send(banner)
self.send(welcome)
step1 = self.game1()
if not step1:
self.request.close()
step2 = self.game2()
if not step2:
self.request.close()
self.final_game()


class ThreadedServer(socketserver.ThreadingMixIn, socketserver.TCPServer):
pass

class ForkedServer(socketserver.ForkingMixIn, socketserver.TCPServer):
pass

if __name__ == "__main__":
HOST, PORT = '0.0.0.0', 10001
print("HOST:POST " + HOST+":" + str(PORT))
server = ForkedServer((HOST, PORT), Task)
server.allow_reuse_address = True
server.serve_forever()

解题

题目被分为了三个挑战

GAME1

伪素数,随便找了个wp拿了一个数

https://ctftime.org/writeup/21898
340649031679478708871356501710247209854526956821188127472136012686397651

GAME2

通过搜索知道是一种’钓鱼题’,并且已经有了很详细分析

论文地址:https://ami.uni-eszterhazy.hu/uploads/papers/finalpdf/AMI_43_from29to41.pdf

首先看了这个视频讲解,有了大致的概念https://www.bilibili.com/video/BV1TA411175n

然后找了个脚本https://ctftime.org/writeup/9637,在根据论文和这篇https://zhuanlan.zhihu.com/p/33853851的讲解,调整参数m可以逐渐增长数字直到获得我们想要的数据

GAME3

通过搜索知道是一种Möbius变换,不懂,但搜到脚本一把梭https://github.com/Masrt200/sagetf/blob/master/Advanced%20Crypto.ipynb(搜索引擎搜索Möbius即可),然后由于精度问题,有点难通过验证(不知道是不是因为这个),所以直接爆破了

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

from Crypto.Util.number import *
from pwn import *
while True:
r=remote("1.95.46.185",10001)

#https://ctftime.org/writeup/21898 随便拿一个数
r.recvuntil(b'[+] Plz Tell Me your number: ')
r.sendline(b'340649031679478708871356501710247209854526956821188127472136012686397651')

#https://zhuanlan.zhihu.com/p/33853851
N=4
e=(4*(N^2)) + ((12*N)-3)
f=32*(N+3)
eq=EllipticCurve([0,e,0,f,0]) # Define the elliptic curve corresponding to the equation a/(b+c)+b/(a+c)+c/(a+b)=N
eq.rank()
eq.gens()
tmpP=eq(-100,260)
m=9
while True:
P=m*tmpP
x=P[0]
y=P[1]
a=(8*(N+3)-x+y)/(2*(N+3)*(4-x))
b=(8*(N+3)-x-y)/(2*(N+3)*(4-x))
c=(-4*(N+3)-(N+2)*x)/((N+3)*(4-x))
da=denominator(a)
db=denominator(b)
dc=denominator(c)
l=lcm(da,lcm(db,dc))
a,b,c=[int(a*l),int(b*l),int(c*l)]
try:
assert a > 0
assert b > 0
assert c > 0
assert a / (b + c) + b / (a + c) + c / (a + b) == 4
assert int(a).bit_length() > 900 and int(a).bit_length() < 1000
assert int(b).bit_length() > 900 and int(b).bit_length() < 1000
assert int(c).bit_length() > 900 and int(c).bit_length() < 1000
break
except:
pass
m=m+1

r.recvuntil(b'[+] Plz give Me your a, b, c: ')
r.sendline((f'{a},{b},{c}').encode())

#https://github.com/Masrt200/sagetf/blob/master/Advanced%20Crypto.ipynb
r.recvuntil(b"Let's play the game3!")
r.recvline()
C = ComplexField(999)
zw=r.recvline().strip().decode()
zw=eval(zw)
z4=r.recvline().strip().decode()
Z, W = [], []
for z,w in zw:
Z.append(C(z))
W.append(C(w))
z = C(z4)
A = (W[0] - W[1]) * (z - Z[1]) * (Z[0] - Z[2])
B = (W[0] - W[2]) * (Z[0] - Z[1]) * (z - Z[2])
fz = (A * W[2] - B * W[1])/(A - B)
r.sendline(str(fz).encode())
flag=r.recvall()
if b'suctf' in flag or b'SUCTF' in flag:
print(flag)
r.close()
break
r.close()

#b'[+] Plz Tell Me your answer: \nCongratulations, you have won the game3!\n\nSUCTF{Hope_Y0u_have_a_NICE_tr1p_in_SUCTF~}\n'

复现

以下复现参考鸡块师傅的wp:https://tangcuxiaojikuai.xyz/post/67c5a822.html

*SU_rsa

题目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
from Crypto.Util.number import *
from hashlib import sha256
flag = open("flag.txt").read()
p = getPrime(512)
q = getPrime(512)
e = getPrime(256)
n = p*q
d = inverse(e,(p-1)*(q-1))
d_m = ((d >> 512) << 512)
print("d_m = ",d_m)
print("n = ",n)
print("e = ",e)

assert flag[6:-1] == sha256(str(p).encode()).hexdigest()[:32]

解题

d高位,之前密挑有一个d高位+低位的,看来还没研究透。

我自己只能到求出k了,后面就不知道怎么格,太难了。(哭

主要点就是格的配平,然后格出来的结果第二行才是目标向量,而且也不是预期的

然后得到p%e的值,p低位求解,要用到多线程爆破

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
from Crypto.Util.number import *

d_m = 54846367460362174332079522877510670032871200032162046677317492493462931044216323394426650814743565762481796045534803612751698364585822047676578654787832771646295054609274740117061370718708622855577527177104905114099420613343527343145928755498638387667064228376160623881856439218281811203793522182599504560128
n = 102371500687797342407596664857291734254917985018214775746292433509077140372871717687125679767929573899320192533126974567980143105445007878861163511159294802350697707435107548927953839625147773016776671583898492755338444338394630801056367836711191009369960379855825277626760709076218114602209903833128735441623
e = 112238903025225752449505695131644979150784442753977451850362059850426421356123


k = e*d_m // n + 1
# s=p+q
# ed_l+ks+[ed_h-1-k(n+1)]=0
#(d_l,s,1)*L=(d_l,s,1)

L = Matrix(ZZ, [
[1, 0, e],
[0, 1, k],
[0, 0, e*d_m - 1 - k*(n+1)],
])

# 配平目标向量
# 513就行了(512也不行),至于为啥,我不清楚
L[:, -1:] *= 2^513

L = L.LLL()
# L[0]:(-k,e,0)
# L[1]:(d_l-t*k,s+t*e,0)
# 理解:e和k只有256bit,比我们想要的d_l(512bit)和s(512bit)都要短
# LLL之后肯定是前者这个较短的向量,所以从第二小的向量入手

res=L[1] # s+t*e
s=res[1]%e
PR.<x> = PolynomialRing(Zmod(e))
f = x^2 + n - s*x #p*p+p*q-p*s
res = f.roots()
pl = int(res[0][0]) # p%e

import multiprocessing
import tqdm
from hashlib import sha256

def copper_attack(i):
PR.<x> = PolynomialRing(Zmod(n))
f = e*(2^12*x + i) + pl
f = f.monic()
res = f.small_roots(X=2^244, beta=0.499, epsilon=0.02)
if(res != []):
t = int(res[0])
p = e*(2^12*t + i) + pl
q = n // p
assert p * q == n and isPrime(p) and isPrime(q)
print(sha256(str(p).encode()).hexdigest()[:32])
print(sha256(str(q).encode()).hexdigest()[:32])
return True

with multiprocessing.Pool(processes=16) as pool:
for _ in tqdm.tqdm(pool.imap(copper_attack, range(2^12)), total=int(2^12)):
if(_):
break
"""
1c56d344aba19600db3956abebc34425
c1864501fab1841178177d4f15af4ad8
"""

*SU_hash

题目

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
from Crypto.Util.number import *

flag = b'SUCTF{??????????????????????????????}'

class myhash:
def __init__(self,n):
self.g = 91289086035117540959154051117940771730039965839291520308840839624996039016929
self.n = n

def update(self,msg: bytes):
for i in range(len(msg)):
self.n = self.g * (2 * self.n + msg[i])
self.n = self.n & ((1 << 383) - 1)

def digest(self) -> bytes:
return ((self.n - 0xd1ef3ad53f187cc5488d19045) % (1 << 128)).to_bytes(16,"big")

def xor(x, y):
x = b'\x00'*(16-len(x)) + x
y = b'\x00'*(16-len(y)) + y
return long_to_bytes(bytes_to_long(bytes([a ^ b for a, b in zip(x, y)])))

def fn(msg, n0):
h = myhash(n0)
ret = bytes([0] * 16)
for b in msg:
h.update(bytes([b]))
ret = xor(ret,h.digest())
return ret

n0 = getRandomNBitInteger(382)
print("n0 = ",n0)
your_input = bytes.fromhex(input("give me your msg ->").strip())
if fn(your_input, n0) == b'justjusthashhash':
print(flag)
else:
print("try again?")

解题

(环境没了,自己搭的有问题,所以直接用程序跑了)
直接抄鸡块师傅的了,还是一知半解状态。

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
from Crypto.Util.number import *

class myhash:
def __init__(self,n):
self.g = 91289086035117540959154051117940771730039965839291520308840839624996039016929
self.n = n

def update(self,msg: bytes):
for i in range(len(msg)):
self.n = self.g * (2 * self.n + msg[i])
self.n = self.n & ((1 << 383) - 1)

def digest(self) -> bytes:
return int((self.n - 0xd1ef3ad53f187cc5488d19045) % (1 << 128)).to_bytes(16,"big")

def xor(x, y):
x = b'\x00'*(16-len(x)) + x
y = b'\x00'*(16-len(y)) + y
return long_to_bytes(bytes_to_long(bytes([a ^^ b for a, b in zip(x, y)])))

def fn(msg, n0):
h = myhash(n0)
ret = bytes([0] * 16)
for b in msg:
h.update(bytes([b]))
ret = xor(ret,h.digest())
return ret



n0 = getRandomNBitInteger(382) # 当作接收
# 消除n0的影响,作为初始状态
t = (bytes_to_long(fn(b"\x00"*128, n0))) % 2^128

# 用 初始状态 异或 最终状态 得到 fn(输入状态)
R = vector(GF(2), list(map(int, bin((bytes_to_long(b"justjusthashhash") ^^ t) % 2^128)[2:].zfill(128))))

# 因为myhash是线性变化所以可以直接利用矩阵求解
# + b"\x00"*128 也是为了消除n0的影响
L = []
for i in range(128):
temp = long_to_bytes(i, 1) + b"\x00"*128
L.append(list(map(int, bin(bytes_to_long(fn(temp, 0)))[2:].zfill(128))))
L = Matrix(GF(2), L)
res = L.solve_left(R)

msg = b"\x00"*128
for i, j in enumerate(res):
if(j == 1):
msg += (long_to_bytes(i, 1) + b"\x00"*128)
print(fn(msg,n0))
print(fn(msg, n0) == b"justjusthashhash")

SUCTF2025-crypto
http://example.com/2025/01/12/suctf2025/
作者
Naby
发布于
2025年1月12日
许可协议