SUSCTF2025

SUSCTF2025-Crypto题目出题手记

0. Introduction

参与了SUSCTF 2025 密码学的出题部分,一共提供了 10 道赛题,其中 2 比 1 还需要靠注意力,10 有点太板子了(虽然我给它标了个Medium plus),9 有点太难了(Hard)。因此就没有放出来。最后放出来了1,3,4,5,6,7,8 七个题目。附上wp。

个人感觉这次 Crypto 赛题难度梯度还是控制的比较好的,不知道各位做题的师傅感受如何。

3

1.All U Need(Easy+,7 Solves, 237pts)

本题为动态附件,出题时准备了 800 份附件上传,每个人分配到的附件均不相同(数值和flag均不相同),但解法完全一致。

先看一下题目:

1
2
3
n=2904843071883500000000000000000077968341153552000000000000000001247490892311370000000000000000017202971801726400000000000000000172108837172285000000000000000001625541474334760000000000000000022269441527985100000000000000000263000084922760000000000000000002706746341050890000000000000000030157440708292800000000000000000298606737869309000000000000000003536628718954680000000000000000042190167488059500000000000000000472189179701384000000000000000004851880611409810000000000000000052976520884965400000000000000000540948274124889000000000000000005740148052406340000000000000000067192069373124700000000000000000630695683831718000000000000000006467633676752550000000000000000069480034984422600000000000000000711683946987899000000000000000007942729256445680000000000000000086817065194546500000000000000000852602856481182000000000000000009107741861772970000000000000000089852724145392800000000000000000933256474844053000000000000000010572355877086640000000000000000103275505433200100000000000000001044738076898846000000000000000010421343850951330000000000000000102470042454072200000000000000001040667738462861000000000000000010148501663850480000000000000000096417726625576500000000000000000918355490056316000000000000000008945969161845650000000000000000087359916557803400000000000000000889875962976993000000000000000009093271343745480000000000000000077814906978822100000000000000000731752316877060000000000000000007302126810147890000000000000000065610961673166200000000000000000640719012346937000000000000000006398350386236640000000000000000052875877317330700000000000000000513460599936704000000000000000005316229183128150000000000000000045069207864115400000000000000000503278034378491000000000000000004468137061001900000000000000000038847754943070300000000000000000373326405240394000000000000000003115125870491090000000000000000029165170477508400000000000000000261001793289055000000000000000002116489534021480000000000000000016024210804564100000000000000000124886521529344000000000000000000599416582023330000000000000000006456062538926000000000000000000030266403420083
e=...
c=...

题目只给出了 $n,e,c$ 没有给出其他消息,因此,只有考虑分解 $n$,才能实现RSA的解密。但尝试 $p-1$ 和 $p+1$ 分解法,$n$ 均无法被分解,说明使用的素数并非弱素数。

不过我们会”注意到”(呃,这个还是能看出来的),$n$ 里面有很多连续的 $0$,并且似乎每一段 $0$ 的长度都是差不多的(忽略零星出现的 $0$)。虽然题目没有给出 $n$ 是如何生成的,但我们可以大致看出(其实最初的一个版本是给了的,但感觉那样有点题目有点太简单了就没给,何况Crypto有3,4两个送分题)。

1.1 出题人预期解

既然我们提到, 里面有很多连续的 $0$,并且似乎每一段 $0$ 的长度都是差不多的,即 $n$ 具备明显的近似长度的分组结构。那么我们可以猜测 $p,q$ 中也存在很多 $0$,并且具有类似的等长分组结构。因此可以简单测试,暴力枚举分组长度。最后会发现当分组长度为 $32$ 时,能够取得比较好的效果,也就是每一组最高位全是 $0$,且长度近似。

1
2
3
4
5
6
7
8
9
10
11
sn=str(n)
def splitSn(sx,lpart):
sxi=sx[::-1]
# print(sxi)
L=[]
for i in range((len(sxi)+lpart-1)//lpart):
sii=sxi[lpart*i:lpart*i+lpart][::-1]
L.append(sii)
return L
Nx=splitSn(sn,32)
['00000000000000000030266403420083', '00000000000000000064560625389260', '00000000000000000059941658202333', '00000000000000000124886521529344', '00000000000000000160242108045641', '00000000000000000211648953402148', '00000000000000000261001793289055', '00000000000000000291651704775084', '00000000000000000311512587049109', '00000000000000000373326405240394', '00000000000000000388477549430703', '00000000000000000446813706100190', '00000000000000000503278034378491', '00000000000000000450692078641154', '00000000000000000531622918312815', '00000000000000000513460599936704', '00000000000000000528758773173307', '00000000000000000639835038623664', '00000000000000000640719012346937', '00000000000000000656109616731662', '00000000000000000730212681014789', '00000000000000000731752316877060', '00000000000000000778149069788221', '00000000000000000909327134374548', '00000000000000000889875962976993', '00000000000000000873599165578034', '00000000000000000894596916184565', '00000000000000000918355490056316', '00000000000000000964177266255765', '00000000000000001014850166385048', '00000000000000001040667738462861', '00000000000000001024700424540722', '00000000000000001042134385095133', '00000000000000001044738076898846', '00000000000000001032755054332001', '00000000000000001057235587708664', '00000000000000000933256474844053', '00000000000000000898527241453928', '00000000000000000910774186177297', '00000000000000000852602856481182', '00000000000000000868170651945465', '00000000000000000794272925644568', '00000000000000000711683946987899', '00000000000000000694800349844226', '00000000000000000646763367675255', '00000000000000000630695683831718', '00000000000000000671920693731247', '00000000000000000574014805240634', '00000000000000000540948274124889', '00000000000000000529765208849654', '00000000000000000485188061140981', '00000000000000000472189179701384', '00000000000000000421901674880595', '00000000000000000353662871895468', '00000000000000000298606737869309', '00000000000000000301574407082928', '00000000000000000270674634105089', '00000000000000000263000084922760', '00000000000000000222694415279851', '00000000000000000162554147433476', '00000000000000000172108837172285', '00000000000000000172029718017264', '00000000000000000124749089231137', '00000000000000000077968341153552', '29048430718835']

在找到 $n$ 的分组特征后,如果我们把 $p,q$ 也当作分组来看,可以看出 $n$ 的每一组都与 $p,q$ 有所关联。而 ”分组特征“ 可以建模成 ”多项式“,即我们将上面的分组结果构建整数多项式环 $\mathbb Z[x]$ 上的多项式 $N(x)$,那么一定存在两个多项式 $P(x),Q(x)$,使得 $N(x)=P(x)Q(x)$。那么此时可以构建多项式 $N(x)$,并分解 $N(x)$ 获取 $P(x)$ 和 $Q(x)$:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
sn=...
def splitSn(sx,lpart):
sxi=sx[::-1]
# print(sxi)
L=[]
for i in range((len(sxi)+lpart-1)//lpart):
sii=sxi[lpart*i:lpart*i+lpart][::-1]
L.append(sii)
return L
Nx=splitSn(sn,32)
print(Nx)
PRZ.<x>=PolynomialRing(ZZ)
Nx=PRZ([int(i) for i in Nx])
print(Nx)
factor(Nx)
#(4481389*x^32 + 6231239*x^31 + 9536595*x^30 + 9893789*x^29 + 2772725*x^28 + 2492017*x^27 + 2927275*x^26 + 4208633*x^25 + 2151961*x^24 + 7077115*x^23 + 2502337*x^22 + 6088579*x^21 + 9642093*x^20 + 9684731*x^19 + 7570433*x^18 + 5896329*x^17 + 2604387*x^16 + 4527057*x^15 + 8256741*x^14 + 4046673*x^13 + 8652691*x^12 + 2068847*x^11 + 3127087*x^10 + 5730787*x^9 + 2209191*x^8 + 9632779*x^7 + 6784831*x^6 + 3236041*x^5 + 7387021*x^4 + 9402933*x^3 + 2789721*x^2 + 9335063*x + 5379161) * (6482015*x^32 + 8385203*x^31 + 2383755*x^30 + 2918291*x^29 + 6751721*x^28 + 6619483*x^27 + 9306321*x^26 + 2058413*x^25 + 4774301*x^24 + 9471745*x^23 + 4161897*x^22 + 6666341*x^21 + 4192927*x^20 + 6803031*x^19 + 5416021*x^18 + 7161085*x^17 + 6899053*x^16 + 2293161*x^15 + 6330377*x^14 + 4436843*x^13 + 3204999*x^12 + 9084149*x^11 + 8030719*x^10 + 8549087*x^9 + 6203487*x^8 + 4097235*x^7 + 5606397*x^6 + 9386583*x^5 + 7768569*x^4 + 4685243*x^3 + 4342257*x^2 + 2237511*x + 5626603)

获取 $P(x)$ 和 $Q(x)$ 之后,将 $x=10^{32}$ 带入(因为是 $32$ 位一组)就可以得到 $p,q$ 了,最终直接执行 RSA 解密就OK。

1
2
3
4
5
6
7
8
9
10
11
12
Px=(4481389*x^32 + 6231239*x^31 + 9536595*x^30 + 9893789*x^29 + 2772725*x^28 + 2492017*x^27 + 2927275*x^26 + 4208633*x^25 + 2151961*x^24 + 7077115*x^23 + 2502337*x^22 + 6088579*x^21 + 9642093*x^20 + 9684731*x^19 + 7570433*x^18 + 5896329*x^17 + 2604387*x^16 + 4527057*x^15 + 8256741*x^14 + 4046673*x^13 + 8652691*x^12 + 2068847*x^11 + 3127087*x^10 + 5730787*x^9 + 2209191*x^8 + 9632779*x^7 + 6784831*x^6 + 3236041*x^5 + 7387021*x^4 + 9402933*x^3 + 2789721*x^2 + 9335063*x + 5379161)
Qx=(6482015*x^32 + 8385203*x^31 + 2383755*x^30 + 2918291*x^29 + 6751721*x^28 + 6619483*x^27 + 9306321*x^26 + 2058413*x^25 + 4774301*x^24 + 9471745*x^23 + 4161897*x^22 + 6666341*x^21 + 4192927*x^20 + 6803031*x^19 + 5416021*x^18 + 7161085*x^17 + 6899053*x^16 + 2293161*x^15 + 6330377*x^14 + 4436843*x^13 + 3204999*x^12 + 9084149*x^11 + 8030719*x^10 + 8549087*x^9 + 6203487*x^8 + 4097235*x^7 + 5606397*x^6 + 9386583*x^5 + 7768569*x^4 + 4685243*x^3 + 4342257*x^2 + 2237511*x + 5626603)
p,q=Px(10**32),Qx(10**32)
n=Nx(10**32)
assert n%p==0
e=...
c=...
from Crypto.Util.number import *
phi=(p-1)*(q-1)
d=inverse(e,phi)
print(long_to_bytes(pow(c,d,n)))

最后解出来,得到类似于:Attention is all you need 的语句。

3.CrySignin(Easy, 39 Solves, 125pts)

本题为动态附件,出题时准备了 800 份附件上传,每个人分配到的附件均不相同(数值和flag均不相同),但解法完全一致。

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
from Crypto.Util.number import *
from random import *
from secret import flag
from uuid import UUID
p=1329596764371107264260948790524463667078201288962092988229220331099216972202747986235496117149730240332402358728798174199576808159410988077039863933883707283021432596510812652195899704038126374630854432891580277457310166342238907250055728526757955693768208634626765002269557414142205735568171344541059676587026552819564587252379527557854007769644766922798602628730499830452043996042865583066303024746135216694290599886977846557408057361447210602309239731866416103
q=664798382185553632130474395262231833539100644481046494114610165549608486101373993117748058574865120166201179364399087099788404079705494038519931966941853641510716298255406326097949852019063187315427216445790138728655083171119453625027864263378977846884104317313382501134778707071102867784085672270529838293513276409782293626189763778927003884822383461399301314365249915226021998021432791533151512373067608347145299943488923278704028680723605301154619865933208051
g=25
a=randint(3,q-3)
for i in range(64):
print(f'g**(a**{i})=',pow(g,pow(a,i,q),p))
f=[randint(3,2**64) for i in range(64)]
f[-1]=1

fa=0
for i in range(64):
fa+=f[i]*pow(a,i,q)%q
fa%=q
w=None
while(1):
w=(a+randint(1,q-3))%q
fw=0
for i in range(64):
fw+=f[i]*pow(w,i,q)%q
fw%=q
if(fw):
break

print('f(x)=',f)
print('w=',w)
print('g**(f(a)/(a-w))=',pow(g,fa*inverse(a-w,q)%q,p))

ANS=pow(g,inverse(a-w,q),p)
assert flag==UUID(int=ANS%(2**128))

3.1 出题人预期解

题目两个素数 $p,q$,其中 $p=2q+1$ 为强素数。还给出了 g,g**a,g**(a**2),g**(a**3),...,g**(a**63),w 的数字,多项式 f(x) 的表达式,以及 h=g**(f(a)/(a-w))},目标值是求出g**(1/w)。需要注意的是:凡是指数都要模 $q$,而 $g$ 的幂次计算结果都是模 $p$。其中 每个人的附件中,$g,p,q$ 固定,但 $w,h$ 为不定值。并且每份附件中,$a$ 均不同,且我们不知道 $a$ 的值。(太离谱了,博客中公式放特别复杂的幂次会炸掉)

这个题中, $p$ 的一个原根是 $5$,也就是 $5^{i}$ 可以遍历 $1\sim p-1$ 中的所有值。而 $p-1=2q$,因此模 $p$ 乘法群上,有一个阶数为 $q$ 的子群,其生成元为 $5^2=25$,恰好是 $g$ 的值。

当然,为了求目标值,我们可以先构建这样两个多项式:

$$
F(x)=f(x)~\mathrm {div} ~(x-w)
$$

和:

$$
d=f(x)\mod (x-w)
$$

其中:$F(x)$ 为 62 次多项式,$d$ 为常数(因为被除式为63次,除式为1次)。我们设 $F(x)=F_0+F_1x+F_2x^2+…+F_{62}x^{62}$。其中 $F_0,F_1,F_2,…,F_{62}$ 可以直接获得。因此,我们可以计算 $g^{F(a)}$值如下:

$$
g^{F(a)}=\prod_{i=0}^{62} g^{F_ia^{i}}=\prod_{i=0}^{62} \left(g^{a^{i}}\right)^{F_i}
$$

这里需要把 g**(a**i) 看成一个整体,因为这个是我们所知道的,但我们是不知道 $a$ 的,因此不能把 $a$ 落单出来。

这样搞下来,我们就可以得到
$$
h/g^{F(a)}=g^{\frac{f(a)}{a-w}-F(a)}=g^{\frac{d}{(a-w)}}
$$

因此,最后目标就是:
$$
\left(h/g^{F(a)}\right)^{1/d}
$$

EXP:

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 sage.all import *

from Crypto.Util.number import *
from uuid import *
p=1329596764371107264260948790524463667078201288962092988229220331099216972202747986235496117149730240332402358728798174199576808159410988077039863933883707283021432596510812652195899704038126374630854432891580277457310166342238907250055728526757955693768208634626765002269557414142205735568171344541059676587026552819564587252379527557854007769644766922798602628730499830452043996042865583066303024746135216694290599886977846557408057361447210602309239731866416103
q=664798382185553632130474395262231833539100644481046494114610165549608486101373993117748058574865120166201179364399087099788404079705494038519931966941853641510716298255406326097949852019063187315427216445790138728655083171119453625027864263378977846884104317313382501134778707071102867784085672270529838293513276409782293626189763778927003884822383461399301314365249915226021998021432791533151512373067608347145299943488923278704028680723605301154619865933208051
g=25
gapow=[]
D=open('Crypto03.py','r').readlines()[36:]
for i in range(64):
line=D[i]
line=line.split('=')
gai=int(line[1])
gapow.append(int(gai))
PR=PolynomialRing(Zmod(q),name='X')
X=PR.gen(0)
line=D[64]
line=line.split('=')
f=PR(eval(line[1]))
line=D[65]
line=line.split('=')
w=int(line[1])
line=D[66]
line=line.split('=')
h=int(line[1])

fdivxw=list(f//(X-w))
fmodxw=f%(X-w)

G=1
for i in range(63):
G*=pow(int(gapow[i]),int(fdivxw[i]),p)
G%=p
u=h*inverse(G,p)
AAA=(pow(u,inverse(int(fmodxw),q),p))
print(UUID(int=AAA%(2**128)))
#susctf{0bf4a7d7-59f8-35ab-6866-687b470f7f36}

3.9 一些情况

本来这个题想作为交互题搞的,但出题人考虑到校赛不能太难(因为Crypto 06和去年hard难度基本一致,Crypto 07,08其实个人觉得难于去年的hard题),还是需要出点送分题,因此做成了附件,想送点分出去。不过看这个exp确实是交互版本魔改的。这个题貌似直接丢给AI应该也能出。但就是这样一个丢给AI就能出的送分题,使用动态附件产生了意想不到的效果,变成了送命题(笑)。

以及,虽然这个题似乎可以用AI直接秒,但是还是想问一下各位选手,看完这个题有多少人回看AI的输出结果的?如果回看一下的话,AI应该是用到了”多项式运算“,那既然多项式都可以运算了,为啥不尝试尝试多项式分解呢?试一下多项式分解,Crypto 01不就也出了吗?

2

4.Broadcast1(Easy,19 Solves, 135pts)

又是一个送分题。拿到题会发现每次 $A,s$ 都一样,然后 $e$ 是标准差 $1$ 的离散高斯分布产生的(这意味着 $e$ 的每个分量的很可能不超过 $4$)。题目给了 $548\times2=1096$ 次交互机会,多次交互,看哪个出现的最多和最中间就行了(对应的误差是 0)。得到没有误差的 $\vec b$ 之后,就可以直接解方程 $A\vec s=\vec b$ 获得秘密向量 $\vec s$ 了。

这个题主要是为了让各位新手师傅熟悉 LWE 这一抗量子密码,和第三题一样也没有什么难度,作为密码第 2 个签到题。

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
import random as random2
import os
from sage.all import *
from sage.stats.distributions.discrete_gaussian_integer import DiscreteGaussianDistributionIntegerSampler as DGDIS
n=128
p=31337
D=DGDIS(sigma=1) #Generate the discrete gaussian distribution with sigma = 1

flag=os.getenv('GZCTF_FLAG')+''.join([random2.choice('0123456789ABCDEGHJK')for _ in range(n)]) #漏了个F,写wp才发现:D
seedA=''.join([random2.choice('0123456789ABCDEFGHJK') for _ in range(24)])
print('Public Seed:'+seedA)
rng=random2.Random()
rng.seed(seedA.encode())
while(1):
A=matrix(Zmod(p),[[rng.randint(0,99) for _ in range(n)]for __ in range(n)])
if(A.rank()==n):
break

rng.seed(os.urandom(48))

s=vector(Zmod(p),[rng.randrange(200,p-200,200)+ord(flag[i]) for i in range(n)])

for i in range(548*2):
op=int(input('Give me your choice>'))
if(op==1):
e=vector(Zmod(p),[D() for _ in range(n)])
print(list(A*s+e))
else:
break

4.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
29
30
31
32
33
34
35
36
from sage.all import *
from pwn import *
from tqdm import *
import random
n=128
q=31337
sh=process(['python3','task.py'])
sh.recvuntil(b':')
seedA=sh.recvline(keepends=False).strip()
rng=random.Random()
rng.seed(seedA)
while(1):
A=matrix(Zmod(q),[[rng.randint(0,99) for _ in range(n)]for __ in range(n)])
if(A.rank()==n):
break

Recv=[]
for i in tqdm(range(600)):
sh.recvuntil(b'>')
sh.sendline(b'1')
res=eval(sh.recvline(keepends=False))
Recv.append(res)

y=[]
for i in range(n):
D=dict()
for j in range(600):
D[Recv[j][i]]=1+D.get(Recv[j][i],0)
ansi,anst=None,0
for u,v in D.items():
if(v>anst):
ansi,anst=u,v
y.append(ansi)
y=vector(Zmod(q),y)
s=A.solve_right(y)
print(bytes(s.change_ring(Zmod(200))))

4.2 297号选手的解题脚本,不需要sagemath也可以解

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
import socket
import time
import random as random2
import numpy as np

def modinv(a, p):
g, x, _ = extended_gcd(a, p)
return x % p if g == 1 else None

def extended_gcd(a, b):
if a == 0:
return b, 0, 1
g, y, x = extended_gcd(b % a, a)
return g, x - (b // a) * y, y

def matrix_mod_inverse(matrix, p):
n = matrix.shape[0]
aug = np.hstack((matrix, np.eye(n, dtype=int)))
for i in range(n):
# 寻找主元行
pivot_row = -1
for j in range(i, n):
if aug[j, i] != 0:
pivot_row = j
break
if pivot_row == -1:
return None
# 交换主元行与当前行
aug[[i, pivot_row]] = aug[[pivot_row, i]]
# 计算当前主元的逆元并归一化当前行
inv = modinv(aug[i, i], p)
if inv is None:
return None
aug[i] = (aug[i] * inv) % p
# 消去其他行的当前列元素
for j in range(n):
if j != i and aug[j, i] != 0:
aug[j] = (aug[j] - aug[j, i] * aug[i]) % p
# 返回逆矩阵(扩展矩阵的右半部分)
return aug[:, n:]

def get_flag_char(s_i):
# 遍历可能的k值,计算t_i和对应的字符ASCII码
for k in range((s_i - 126 + 199) // 200, (s_i - 32) // 200 + 1):
t_i = 200 * k
ord_char = s_i - t_i
# 检查字符ASCII码范围和t_i范围是否合法
if 32 <= ord_char <= 126 and 200 <= t_i <= 31137:
return chr(ord_char)
# 无法匹配时返回占位符
return "?"

def main():
# 配置参数:目标IP、端口、矩阵维度、模数、请求y的数量
HOST, PORT, n, p, NUM_Y = "106.14.191.23", 57766, 128, 31337, 200

with socket.socket(socket.AF_INET, socket.SOCK_STREAM) as s:
s.connect((HOST, PORT))
# 接收并解析公开种子
seedA = s.recv(1024).decode().split("Public Seed:")[1].strip()
# 初始化随机数生成器
rng = random2.Random()
rng.seed(seedA.encode())

# 生成满秩的随机矩阵A
A = None
while True:
A = np.array([[rng.randint(0, 99) for _ in range(n)] for _ in range(n)], dtype=int) % p
if np.linalg.matrix_rank(A) == n:
break

# 发送请求获取NUM_Y个y向量
y_list = []
for _ in range(NUM_Y):
try:
s.sendall(b"1\n")
time.sleep(0.1)
# 接收并解析y向量(注意:eval存在安全风险,实际使用可替换为更安全的解析方式)
y = eval(s.recv(4096).decode().strip())
if len(y) == n:
y_list.append([yi % p for yi in y])
except:
continue

# 发送请求获取c向量(y向量的均值)
s.sendall(b"2\n")
# 计算y向量的均值并取整、模p
c = np.round(np.mean(np.array(y_list, dtype=int), axis=0)).astype(int) % p

# 计算矩阵A的模p逆矩阵
A_inv = matrix_mod_inverse(A, p)
if A_inv is None:
return

# 计算s向量并解析为flag
s_list = (np.dot(A_inv, c) % p).astype(int).tolist()
flag = "".join(map(get_flag_char, s_list))
print(flag)
# 提取并打印包含{}的flag核心部分
if "{" in flag and "}" in flag:
print(flag[flag.index("{"):flag.index("}") + 1])

if __name__ == "__main__":
main()

5.ezStream(Easy+,6 Solves, 262pts)

这个题主要考察一些数论知识,当然,你可能也需要一些注意力。

题目代码:

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

p=int(input('Please give me a 32~50 bit prime modulus>'))

if(not isPrime(p) or p.bit_length()<=32 or p.bit_length()>=50):
print('Invalid parameter!')
exit(0)

RODICT=dict()
USED=set()

def RandomOracle(x):
global USED,RODICT
if(RODICT.get(x,None) is not None):
return RODICT[x]
while(1):
r=bytes_to_long(urandom(48))%p
if(r not in USED):
USED|={r}
RODICT[x]=r
return r

state=[randint(1,p-1) for _ in range(randint(256,512))]
visited=False
for i in range(200):
op=int(input('Give me your option>'))
if(op==1):
msg=input("Input your message array(Decimal Format)>")
#input example: 1 2 3 4 5 6 7 8 9 10 100 999 10000
msg=msg.split()
msg=msg[:512]
ciph=[]
for ch in msg:
cur=state.pop(0)
ciph.append(cur+RandomOracle(int(ch)))
state.append(pow(cur,2*(getrandbits(2)+1)+1,p))
print(ciph)

elif(op==2):
if(visited):
print('Only one chance!')
continue
else:
visited=True
ret=[]
flag=getenv('GZCTF_FLAG')
for ch in flag:
chi=ord(ch)
cur=state.pop(0)
ret.append(RandomOracle(chi)+cur)
state.append(pow(cur,2*(getrandbits(2)+1)+1,p))
print('Cipher of flag=',ret)

else:
break

5.1 出题人预期解

这个题目大意是:你需要输入一个素数 $p$ 作为模数,然后输入任意消息,消息会被经过一个随机预言机 $RO$,然后提取流密码状态中的值 $s$,加密获得 $RO(x)+s$。最后将 $s^3$ 或 $s^5$ 或 $s^7$ 或 $s^9$ 放入流密码 state 的末尾继续用。

这个题出题人测试时,丢AI,AI会告诉你选择一个较小的数字,或者较大的数字,或者提出加密时没有对 $p$ 取模。说明 AI 并非万能的:D。

这个题的正解是:找一个 $2\times 3^x\times 5^y\times 7^z+1$ 类型的素数,并且 $3$ 的指数尽可能大(其实 $2\times3^x+1$ 的素数也可以)。这样经过多次迭代之后,整个序列中就只剩下 $1$ 和 $-1$ 两个值了。然后枚举并尝试获取所有可见字符的 RO 。最后获取FLAG即可 :)。

exp比较简单,但先给出如何寻找可能可以的素数吧,代码如下。其实这种素数还是挺多的。。。这个代码输出的最后一个值为 $2\times 3^{30}+1$ ,刚好是 49 比特,用这个也不是不行:P

1
2
3
4
5
6
7
from Crypto.Util.number import *
for i in range(10,40):
for j in range(8):
for k in range(8):
r=2*3**i*5**j*7**k+1
if(isPrime(r) and r.bit_length() in range(33,50)):
print(r.bit_length(),i,j,k,r)

最终EXP:

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 Crypto.Util.number import *
from sage.all import *
from pwn import *
from tqdm import *
sh=remote('106.14.191.23',53054)

sh.recvuntil(b'>')
sh.sendline(str(2*3**30+1).encode())

for i in tqdm(range(100)):
sh.recvuntil(b'>')
sh.sendline(b'1')
sh.recvuntil(b'>')
sh.sendline(b'1 '*512)
D=dict()
for i in range(32,128,5):
sh.recvuntil(b'>')
sh.sendline(b'1')
sh.recvuntil(b'>')
sh.sendline((f'{i} '*100+f'{i+1} '*100+f'{i+2} '*100+f'{i+3} '*100+f'{i+4} '*100).encode())
A=eval(sh.recvline())
for j in set(A[:100]):
D[j]=i
for j in set(A[100:200]):
D[j]=i+1
for j in set(A[200:300]):
D[j]=i+2
for j in set(A[300:400]):
D[j]=i+3
for j in set(A[400:500]):
D[j]=i+4
sh.recvuntil(b'>')
sh.sendline(b'2')
sh.recvuntil(b'=')
C=eval(sh.recvline())
F=[]
for i in C:
F.append(D[i])
print(bytes(F))
#b'susctf{gcd_P_MInus_on3_aNd_EXPOnENt14I_M4K35_THi5_sTr34M_Clph3R_lnSEcURE_0aBCl59dZbAee76f}'

5.2 来自381号选手wp的解法

这个解法我审wp时竟然一开始没看懂,但后面仔细看了看,大概了解了意思,但和预期解相比,肯定是预期解更简单的。

虽然这个解法AI生成的痕迹挺明显的,但还是决定放出来。顺便说明:AI解题也许能给你一个答案,但其实并非最优解。并且AI给你的反馈,肯定还是你给它的消息,而给它什么消息,那还是靠你自己的经验积累了。。。

与远程服务器建立连接,使用指定大质数 P 作为模数 收集加密数据流(通过发送全 0 数组获取)。

基于收集的数据流计算关键参数 L(偏移量)和 H(0)(初始哈希值)(需借助 SageMath 计 算)。

构建字符与可能哈希值的映射关系(H(m)候选空间) 利用回溯算法结合 flag 前缀 susctf{,从加密的 flag 数据中破解出原始 flag

不是,哥们,你都发现 $3,5,7,9$ 了,为啥不往指数那边想呢?以及你计算 h_candidates 那个字典,你真的懂那一行是啥意思吗?

其他几个选手好像代码更复杂,但似乎结果类似

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
from pwn import *
from Crypto.Util.number import *
HOST = "106.14.191.23"
PORT = 55011
P = getPrime(33)
FLAG_PREFIX = "susctf("

def send_option(r, option):
r.sendlineafter(b'Give me your option>', str(option).encode())

def encrypt(r, msg_list):
send_option(r, 1)
msg_str = "".join(map(str, msg_list))
r.sendlineafter(b"Input your message array(Decimal Format)>", msg_str.encode())
r.recvuntil(b'[')
ciph_str = r.recvuntil(b']', drop=True).decode()
return [int(x) for x in ciph_str.split(',')] if ciph_str else []

def get_flag_cipher(r):
send_option(r, 2)
r.recvuntil(b'Cipher of flag: [')
ciph_str = r.recvuntil(b']', drop=True).decode()
return [int(x) for x in ciph_str.split(',')]

def solve():
r = remote(HOST, PORT, timeout=10)
r.sendlineafter(b'Please give me a 325 bit prim modulus', str(P).encode())

# 收集加密数据流
ciph_stream = []
for _ in range(8): # 1024//128=8
ciph_stream.extend(encrypt(r, [8]*128))

# 输入计算得到的L和H(实际使用时需替换为计算结果)
found_L = int(input("输入L值:"))
found_H0 = int(input("输入H(0)值:"))

# 构建H(m)候选空间
initial_state = [c - found_H0 for c in ciph_stream]
offset = len(ciph_stream)
chars = list(range(256))
ciph_probe = []
D = [3, 5, 7, 9]
for i in range(0, 256, 16):
ciph_probe.extend(encrypt(r, chars[i:i+16]))

h_candidates = {
m:{ciph_probe[i]-pow(initial_state[offset+i-found_L],d,P)for d in D}
for i,m in enumerate(chars)
}

# 破解flag
flag_cipher = get_flag_cipher(r)
solution = []
offset += 256

def backtrack(pos, current_flag, h_dict):
if solution or pos == len(flag_cipher):
if pos == len(flag_cipher):
solution.append(current_flag)
return
base_s = initial_state[offset + pos - found_L]
# 优先匹配前缀
chars_to_try = [ord(FLAG_PREFIX[pos])] if pos < len(FLAG_PREFIX) else range(256)
for m in chars_to_try:
for d in D:
s_pred = pow(base_s, d, P)
h_pred = flag_cipher[pos] - s_pred
# 检查候选合法性和冲突
if h_pred not in h_candidates.get(m, []):
continue
if any(v == h_pred and k != m for k, v in h_dict.items()):
continue
backtrack(pos + 1, current_flag + chr(m), {**h_dict, m: h_pred})

backtrack(0, "", {0: found_H0})
print("Flag:", solution[0] if solution else "未找到")
r.close()

if __name__ == "__main__":
solve()

5.9 一些疑问

我实在不知道为什么几个解题的都用的方法2。。明明预期解更简单的。。并且预期解同样不需要使用Sagemath。。

6.nfsr3(Medium, 1 Solves, 500pts)

去年有nfsr1,nfsr2,今年来个nfsr3。

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
from Crypto.Util.number import *
from random import *
from os import urandom,getenv


token=''.join([choice('ABCDEFGHJK0123456789')for _ in range(90)])

class LFSR:
def __init__(self,n,p,seed):
self.n=n
self.p=p
self.mask=[1]+[randint(0,p-1) for _ in range(n-1)]
self.state=seed[:n]
while(len(self.state)<n):
self.state.append(len(self.state))
def getstate(self):
ret=sum([u*v%self.p for u,v in zip(self.state,self.mask)])%self.p
self.state.append(ret)
self.state.pop(0)
return ret

p=getPrime(208)
h=32328345448461253988278351927
lfsr1=LFSR(45,p,[randrange(200,p-200,200)+ord(i) for i in token[:45]])
lfsr2=LFSR(45,h,[randrange(200,h-200,200)+ord(i) for i in token[45:]])
print(f'p={p}')
print(f'mask={lfsr1.mask}')
MONEY = 97
isHint=False
cHint=800
for i in range(500):
MENU=f"""
++++++MENU+++++++++
+1.Guess $ 1+
+2.BuyHint $350+
+3.SubmitTkn $2000+
+0.Exit +
++++++NFSR+3+++++++
DOLLAR:{str(MONEY).zfill(4)}
CHANCE:{str(500-i).zfill(4)}
"""
print(MENU)
op=int(input('Choice>'))
if(op==1):
MONEY-=1
x=int(input('Your Guess>'))
u=lfsr1.getstate()^((lfsr2.getstate()))
if(u==x):
print(f'AC, Your answer:{x} Right answer:{u}')
MONEY+=7
elif(abs(u-x)<=h):
print(f'PC, Your answer:{x} Right answer:{u}')
MONEY+=2
else:
print(f'WA, Your answer:{x} Right answer:{u}')
if(MONEY==0):
exit(0)
elif(op==2):
if(MONEY<350):
print(f'Sorry, The hint cost $350, You only have ${MONEY}')
continue
else:
MONEY-=350
print(f'lfsr2.mask={lfsr2.mask}')
print(f'lfsr2.state={lfsr2.state}')
isHint=True
elif(op==3):
if(MONEY<2000):
print(f'Sorry, token submission cost $2000, You only have ${MONEY}')
else:
MONEY-=2000
token1=input('NOW! GIVE ME MY TOKEN!>').strip()
if(token1.upper()==token):
FLAG=getenv('GZCTF_FLAG')
print(f'Congraduations! here is your flag!!!:{FLAG}')
else:
print('Sorry, but I think you could have your flag...')
else:
exit(0)

6.1 出题人预期解

一个猜数字的题,需要金币达到 2000,方可提交token,获得flag。

这个题的一个迷惑之处在于:我似乎给了你一个 op=2 的选项,花 350 金币可以买到 lfsr2 的状态。但其实这个选项对于解题并没有太大的帮助。因为 lfsr2 的值完全可以解出来。而如果解出了 lfsr1 的大致值而不去解 lfsr2,就会导致你要浪费 350 次去获取 lfsr2 的值,最后只剩下几十次机会,完全不够将金币刷到 2000获取 flag。

因此正确的做法是:由于一个大数 $a$ 异或一个小数 $b$,相当于这个大数 $a$ 加上或减去了另一个小数 $c$。因为我们有异或不等式($0\le b\lt a$):
$$
a-b\le a\oplus b\le a+b
$$
由于 $p$ 是 208 位素数,$h$ 是 95 位,而 lfsr1^lfsr2 的结果相当于 知道了每次 lfsr1 的高位,但不知道 lfsr1 的低位。因此这也算是一个 HNP 问题(如果你意识到异或小数字等价于加上或减去一个小数字的话)。

因此,我们可以将每个数拆分为高位 $y$ 和低位 $x$,其中高位 $y$ 就是我们已知的部分,低位 $x$ 就是我们未知的部分,并尝试建立 $y$ 和 $x$ 的关系:

因此可以构造一个这样的关系:

1

以 $x_{45}$ 为例,我们可以计算:
$$
x_{45}=\sum_{i=0}^{44}a_iy_i+\sum_{i=0}^{44}a_ix_i -y_{45}
$$
其中 $a$ 为 lfsr1 的MASK 值,这个我们是已知的,所有的 $y$ 也是我们已知的。

把所有 $y$ 看成一个整体,就有:
$$
v_0=\sum_{i=0}^{44}a_iy_i -y_{45}
$$
再提取所有 $x$ 的系数,就有矩阵 $\mathbf B$ 的第 $0$ 列为 $(a_0,a_1,…,a_{44})$。

同理,$x_{46}$ 可以用写成未知数 $x_{1}\sim x_{45}$ 表示,但 $x_{45}$ 可以化为 $x_{0}\sim x_{44}$ 的表示,因此 $x_{46}$ 也可以写成 $x_{0}\sim x_{44}$ 的表示。这个过程直接使用Sagemath的多项式环就可以直接求系数了。。。把系数构建成上面的矩阵 $\mathbf B$,就可以直接对上面的矩阵 LLL 求解,找最后一个分量为 $±h$ 的

恢复了lfsr1 的完整之后,我们就知道了 lfsr1lfsr2 异或的差值了,我们将差值转化成异或值,就可以得到 LFSR2 的 90 个输出结果了。有了 90 个输出结果就可以直接解方程恢复 lfsr2 的mask了。

当然,这里需要注意一个问题:lfsr2 的模数 $h$ 不是素数,而是三个素数的乘积。sagemath中不支持合数模的 solve_left。因此可以在三个素数域中求,求出来后使用中国剩余定理就OK了。

恢复了 lfsr1,lfsr2 之后,我们就可以往回回溯得到 token,然后再往后继续预测,把金币刷到 2000,就可以提交 token 获取flag了!

题目中的彩蛋:出题人偷偷夹带了私货:long_to_bytes(h)=='huangx607087'

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
from pwn import *
from sage.all import *
from tqdm import *
context.log_level='debug'
class LFSR:
def __init__(self,n,p,seed):
self.n=n
self.p=p
self.mask=[1]+[randint(0,p-1) for _ in range(n-1)]
self.state=seed[:n]
while(len(self.state)<n):
self.state.append(len(self.state))
def getstate(self):
ret=sum([u*v%self.p for u,v in zip(self.state,self.mask)])%self.p
self.state.append(ret)
self.state.pop(0)
return ret
h=32328345448461253988278351927
# sh=process(['python3','83.py'])
sh=remote('106.14.191.23',58221)
sh.recvuntil(b'=')
p=int(sh.recvline(keepends=False))
sh.recvuntil(b'=')
A=eval(sh.recvline(keepends=False))
print(p)
print(A)
D=[]
for i in range(90):
sh.recvuntil(b'>')
sh.sendline(b'1')
sh.recvuntil(b'>')
sh.sendline(b'1')
sh.recvuntil(b'Right answer:')
D.append(int(sh.recvline()))

V=PolynomialRing(Zmod(p),names='x0, x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15, x16, x17, x18, x19, x20, x21, x22, x23, x24, x25, x26, x27, x28, x29, x30, x31, x32, x33, x34, x35, x36, x37, x38, x39, x40, x41, x42, x43, x44')
xarr=list(V.gens())
print(xarr)

harr=D[:90]
for i in range(45):
f=sum([u*v for u,v in zip(A,harr[i:45+i])])+sum([u*v for u,v in zip(A,xarr[-45:])])-harr[45+i]
xarr.append(f)

B=[]
v=[]
for i in range(45,90):
f=xarr[i].coefficients()
B.append(f[:-1])
v.append(f[-1])
B=matrix(B)
print(B.nrows(),B.ncols())
M=block_matrix(ZZ,
[
[identity_matrix(45),matrix(B).T,0],
[zero_matrix(45),p*identity_matrix(45),0],
[zero_matrix(1,45),matrix(v),h],
])

M3L=M.LLL()
larr=None
for vec in M3L:
if(abs(vec[-1])==h):
larr=vec*sgn(vec[-1])
break


Z=[larr[i]+harr[i] for i in range(90)]
S=[Z[i]^harr[i] for i in range(90)]
print(Z)
print(S)


M=[S[i:i+45] for i in range(45)]
y=S[45:90]
p1,p2,p3=1754143 , 6669342923 , 2763347071643
Mp1,Mp2,Mp3=[matrix(Zmod(ppx),M) for ppx in [p1,p2,p3]]
vp1,vp2,vp3=[vector(Zmod(ppx),y) for ppx in [p1,p2,p3]]
up1,up2,up3=[mmm.solve_left(vvv).change_ring(ZZ) for mmm,vvv in zip([Mp1,Mp2,Mp3],[vp1,vp2,vp3])]
print(up1)
print(up2)
print(up3)
B=[crt([up1[i],up2[i],up3[i]],[p1,p2,p3]) for i in range(45)]
Y=S[-45:]
print(Y)
print(B)

Z=Z[-45:]

for i in tqdm(range(350)):
Next=sum([u*v for u,v in zip(A,Z)])%p
Mext=sum([u*v for u,v in zip(B,Y)])%h
sh.recvuntil(b'>')
sh.sendline(b'1')
sh.recvuntil(b'>')
sh.sendline(str(Next^Mext).encode())
sh.recvuntil(b'Right answer:')
S.append(int(sh.recvline(keepends=False))^Next)
Z.append(Next)
Z.pop(0)
Y.append(Mext)
Y.pop(0)


for i in range(350+90):
yi=Y.pop(-1)
zi=Z.pop(-1)
diffy=sum([u*v for u,v in zip(B[1:],Y)])%h
diffz=sum([u*v for u,v in zip(A[1:],Z)])%p
Y=[(yi-diffy)%h]+Y
Z=[(zi-diffz)%p]+Z
print(bytes(list(vector(Zmod(200),Z))))
print(bytes(list(vector(Zmod(200),Y))))
TKN=bytes(list(vector(Zmod(200),Z)))+bytes(list(vector(Zmod(200),Y)))
sh.recvuntil(b'>')
sh.sendline(b'3')
sh.recvuntil(b'>')
sh.sendline(TKN)
print(sh.recvall(timeout=4))
sh.close()

6.2 RedApple师傅的解题脚本

RedApple师傅使用的是矩阵法求lfsr状态。也可以给各位师傅们参考一下。

其实这个代码AI辅助痕迹还是很明显的,因为AI用起来真的很方便,但用AI还是需要你自身的基本知识积累的。如果你什么都不懂,直接把这个题丢AI,那这个题肯定是做不出来的。。。

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
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
from pwn import *
from sage.all import *
from sage.modules.free_module_integer import IntegerLattice
import numpy as np


context.log_level = True
# 连接设置 - 根据实际情况修改
# conn = process(['python3', '/home/zyz/sage/task.py']) # 本地测试
# conn = remote('ip', port) # 远程连接
conn = remote("106.14.191.23", 57549)
h = 32328345448461253988278351927

def xor(a, b):
return int(a) ^ int(b)

def collect_initial_data():
"""收集初始数据:p, mask, 和96次交互的right answer"""
# 接收初始输出
data = conn.recvuntil(b'DOLLAR:')
print(data)
p_line = data.split(b'\n')[0].decode()
mask_line = data.split(b'\n')[1].decode()

# 提取p和mask
p = int(p_line.split('=')[1])
mask_str = mask_line.split('=')[1].strip()
mask = eval(mask_str)

print(f"收集到 p = {p}")
print(f"收集到 mask = {mask}")

T = [] # 保存right answer

# 进行96次op=1交互
for i in range(96):
# 接收菜单
conn.recvuntil(b'Choice>')

# 选择1: Guess
conn.sendline(b'1')

# 随便猜一个数
conn.recvuntil(b'Your Guess>')
conn.sendline(b'0')

# 接收结果并提取right answer
result = conn.recvline().decode()
if 'Right answer:' in result:
right_answer = int(result.split('Right answer:')[1].strip())
T.append(right_answer)
print(f"第{i+1}次交互,收集到 right_answer = {right_answer}")

return p, mask, T

# 参考https://0xffff.one/d/1064
def solve_lfsr1_state(T, p, mask):
"""根据T,p,mask求解lfsr1的初始state"""
# 这里实现具体的LFSR状态恢复算法
# 返回lfsr1的初始state
def Babai(B, t):
# not square when using .LLL(), so use IntegerLattice ...
B = IntegerLattice(B, lll_reduce=True).reduced_basis
G = B.gram_schmidt()[0]
b = t
for i in reversed(range(B.ncols())):
b -= B[i] * ((b * G[i]) / (G[i] * G[i])).round()
return t - b


n = 45
m = len(T)

# 状态转移矩阵 A
A = Matrix(ZZ, n)
for i in range(n-1):
A[i,i+1] = 1
A[n-1,:] = vector(ZZ, mask)

# 初始化 C
C = []
mask_vec = vector(ZZ, mask)

# 构造每一行
A_power = identity_matrix(ZZ, n) # A^0
for i in range(m):
row = (mask_vec * A_power) % p # 对每个元素模 p
row = vector(ZZ, row) # 确保是 Sage 整数向量
C.append(row)
A_power = (A_power * A) % p # 下一步 A^(i+1) 也模 p

CC=C
# print(C[0])
C = Matrix(ZZ, C)

A = C
b = vector(ZZ, T)
p = p
r = A.nrows()
c = A.ncols()

pIr = p*identity_matrix(r)
#M = block_matrix([[A.transpose()], [pIr]]) # [x, k]*[[A.t], [pIr]] = (b-e).t (but not work ...
M = block_matrix([[pIr], [A.transpose()]]) # [k, x]*[[pIr], [A.t]] = (b-e).t (this works ...
br = Babai(M, b)

print('e = %s' % (b-br))
R = IntegerModRing(p)
Ar = matrix(R, CC)
state = Ar.solve_right(br)

print("求解lfsr1初始状态完成")
print("state:", state)
return state

def solve_lfsr2_and_token(T, p, mask, lfsr1_state):
"""根据T,p,mask,lfsr1_state求解lfsr2的mask、state和token"""
# 这里实现具体的求解算法
h = 32328345448461253988278351927

class LFSR:
def __init__(self,n,p,seed):
self.n=n
self.p=p
self.mask=[1]+[randint(0,p-1) for _ in range(n-1)]
self.state=seed[:n]
while(len(self.state)<n):
self.state.append(len(self.state))
def getstate(self):
ret=sum([u*v%self.p for u,v in zip(self.state,self.mask)])%self.p
self.state.append(ret)
self.state.pop(0)
return ret

# 这里需要修改,不能使用未定义的token变量
# 创建一个临时的LFSR实例来模拟lfsr1的行为
lfsr3 = LFSR(45, p, lfsr1_state)
lfsr3.mask = mask
lfsr3.state = list(lfsr1_state) # 确保是列表

T2 = []
for idx in range(96):
tlf1 = lfsr3.getstate()
u = T[idx]
tlf2 = xor(u, tlf1)
print(tlf1, tlf2)
T2.append(tlf2)

print(T2)
result = []
for i in range(45): # 共45行
row = T2[i:i+45] # 每行取45个连续元素
result.append(row)

res = T2[45:90]

print(len(res))
print(len(result), len(result[0]))

# 创建模p的矩阵和向量
A_mod = Matrix(Zmod(h), result)
b_mod = vector(Zmod(h), res)

# 求解 s * A = b (mod p)
s = A_mod.solve_right(b_mod)
lfsr2_mask = list(s)

n = 45

# 状态转移矩阵 A
A = Matrix(ZZ, n)
for i in range(n-1):
A[i,i+1] = 1
A[n-1,:] = vector(ZZ, lfsr2_mask)

# 初始化 C
C = []
mask_vec = vector(ZZ, lfsr2_mask)

# 构造每一行
A_power = identity_matrix(ZZ, n) # A^0
for i in range(96):
row = (mask_vec * A_power) % h # 对每个元素模 p
row = vector(ZZ, row) # 确保是 Sage 整数向量
C.append(row)
A_power = (A_power * A) % h # 下一步 A^(i+1) 也模 p

CC=C
# print(C[0])
C = Matrix(ZZ, C)

rr = T2
# 创建模p的矩阵和向量
AA_mod = Matrix(Zmod(h), CC)
bb_mod = vector(Zmod(h), rr)

# 求解 s * A = b (mod p)
ss = AA_mod.solve_right(bb_mod)
lfsr2_state = list(ss)
print(lfsr2_mask)
print(lfsr2_state) # 初始state

# 从状态中恢复token
token = ""
for idx in list(lfsr1_state):
token += chr(int(idx) % 200)
for idx in list(lfsr2_state):
token += chr(int(idx) % 200)

print(token)
print("求解lfsr2和token完成")
return lfsr2_mask, lfsr2_state, token

def calculate_future_u(lfsr1_state, lfsr2_state, lfsr1_mask, lfsr2_mask, p, h, rounds=350):
"""计算未来rounds轮的u值"""
# 这里实现具体的u值预测算法
class LFSR:
def __init__(self,n,p,seed):
self.n=n
self.p=p
self.mask=[1]+[randint(0,p-1) for _ in range(n-1)]
self.state=seed[:n]
while(len(self.state)<n):
self.state.append(len(self.state))
def getstate(self):
ret=sum([u*v%self.p for u,v in zip(self.state,self.mask)])%self.p
self.state.append(ret)
self.state.pop(0)
return ret

# 创建lfsr1和lfsr2的模拟实例
lfsr1 = LFSR(45, p, lfsr1_state)
lfsr1.mask = lfsr1_mask
lfsr1.state = list(lfsr1_state)

lfsr2 = LFSR(45, h, lfsr2_state)
lfsr2.mask = lfsr2_mask
lfsr2.state = list(lfsr2_state)

# 先推进96步到当前状态
for i in range(96):
lfsr1.getstate()
lfsr2.getstate()

urr = []
for i in range(rounds):
s1 = lfsr1.getstate()
s2 = lfsr2.getstate()
ans = xor(s1, s2)
urr.append(ans)

print(f"计算完成{rounds}轮未来的u值")
return urr

def main():
try:
# 第一阶段:收集数据
print("=== 第一阶段:数据收集 ===")
p, mask, T = collect_initial_data()

print(p)
print(mask)
print(T)

# 第二阶段:离线计算
print("\n=== 第二阶段:离线计算 ===")
lfsr1_state = solve_lfsr1_state(T, p, mask)
lfsr2_mask, lfsr2_state, token = solve_lfsr2_and_token(T, p, mask, lfsr1_state)

h = 32328345448461253988278351927 # 题目中给出的h值
urr = calculate_future_u(lfsr1_state, lfsr2_state, mask, lfsr2_mask, p, h, 350)

# 第三阶段:使用预测结果进行交互
print("\n=== 第三阶段:预测交互 ===")
for i in range(350):
# 接收菜单
conn.recvuntil(b'Choice>')

# 选择1: Guess
conn.sendline(b'1')

# 发送预测的u值
conn.recvuntil(b'Your Guess>')
conn.sendline(str(urr[i]).encode())

# 接收结果确认
result = conn.recvline().decode()
print(f"第{i+1}次预测交互: {result.strip()}")

# 第四阶段:提交token
print("\n=== 第四阶段:提交token ===")
conn.recvuntil(b'Choice>')
conn.sendline(b'3')

response = conn.recvuntil(b'>')
print(f"服务器响应: {response.decode()}")

conn.sendline(token.encode())

# 接收flag
result = conn.recvall(timeout=2).decode()
print(f"最终结果: {result}")

except Exception as e:
print(f"发生错误: {e}")
import traceback
traceback.print_exc()
finally:
conn.close()

if __name__ == "__main__":
main()

7.ECRSA(Medium, 2 Solves, 432pts)

本来这个题想考个同源的,但那玩意出题人自己也不太懂,于是决定简化成双线性对+MT,RSA只是套了个壳。

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
from Crypto.Util.number import *
import os
from sage.all import *
import random as random2
BANNER="""
###### ## ## ###### ###### ######## ######## ####### ##### ####### ########
## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ##
## ## ## ## ## ## ## ## ## ## ## ##
###### ## ## ###### ## ## ###### ####### ## ## ####### #######
## ## ## ## ## ## ## ## ## ## ## ##
## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ##
###### ####### ###### ###### ## ## ######### ##### ######### ######

###### ######## ## ## ######## ######## ####### ########
## ## ## ## ## ## ## ## ## ## ## ## ##
## ## ## #### ## ## ## ## ## ##
## ######## ## ######## ## ## ## ##
## ## ## ## ## ## ## ## ##
## ## ## ## ## ## ## ## ## ##
###### ## ## ## ## ## ####### ##
"""
print(BANNER)

globalPrime=26959946667150639794667015087019630673637144422540572481103610249153
def GetFlag():
flag=os.getenv('GZCTF_FLAG').encode()
upperBoundPrime=2**1280-2**512+2**128-2**40-2**16-8+1
p=previous_prime(random2.randint(0,upperBoundPrime))
q=next_prime(random2.randint(0,upperBoundPrime))
e=1435756429
n=p*q
c=pow(bytes_to_long(flag),e,n)
print(f'N={n}')
print(f'e={e}')
print(f'c={c}')
print(f'hint={q>>960}')

def Chall():
p=int(input('Give me your prime>'))
if(p.bit_length()<226 or p.bit_length()>333 or not isPrime(p)):
print('Invaid prime!')
exit(1)
a,b=[int(i)%p for i in input('Give me your parameters>').split()]
assert a**2+b**2
v=2
while(pow(v,p>>1,p)==1):
v+=1
Fq2=GF((p,2),modulus=[-v,0,1],name='sqv')
E=EllipticCurve(Fq2,[a,b])
x1,x2=[Zmod(p)(i) for i in input('Give me 2 base points(x_coordinate)>').split()]
G1=E.lift_x(x1)
G2=E.lift_x(x2)
assert G1.order()==G2.order()
orderG=G1.order()

def ListG(Gx):
Gxy=Gx.xy()
r=[]
r=list(Gxy[0])+list(Gxy[1])
return tuple(r)
print(f'Your Point G1: {ListG(G1)}')
print(f'Your Point G2: {ListG(G2)}')

for i in range(44):
u,v=random2.randint(0,globalPrime),random2.randint(0,globalPrime)
print(f'Your Point:{ListG(u*G1+v*G2)}')
u1,v1=[int(i) for i in input('Give me your answer Result>').split()]
assert u1==u and v1==v

for _ in range(2):
op=int(input('Give me your option>'))
if(op==1):
GetFlag()
elif(op==2):
Chall()
else:
exit(0)

7.1 出题人预期解

这个题需要发现: $p,q$ 都是 $1280$ 位,而题目中RSA的hint是 q>>960,也就是 $q$ 只泄露了 320 比特,远不够CopperSmith的求解。

提示: RSA给的hint也许有用,但使用hint并非常规方法,需要结合op=2部分一起使用

不过如果你对 python 中的 random 模块有所了解的话,就知道这个 random 模块中的 randint 用的是 MT19937,所以这个题主要是需要你使用 MT19937 求解的!并且如果你能够注意到(注意力真惊人) globalPrime 其实是 $2^{224}$ 的前一个素数,而 upperBoundPrime 的值中,$2^{512}$ 相对于 $2^{1280}$ 可以忽略不计,因此 random2.randint(0,upperBoundPrime) 以压倒性的概率等价于 getrandbits(1280)random2.randint(0,globalPrime) 以压倒性的概率等价于 getrandbits(224) 。这里之所以把 random 模块起别名叫 random2,是因为 sagemath 中也有个 random 函数,避免冲突。

而至于后面的双线性对,其实就比较简单了,这里可以选 $p=2^{x}3^{y}-1$ 型素数,也可以选 $k\cdot \mathrm{lcm}(1,2,…,u)$ 型素数,这样保证 $p\equiv 3\pmod 4$ 且 $p+1$ 极度光滑即可。这种素数其实并不难找。

给一下 illunight 师傅的找素数的脚本:

1
2
3
4
5
6
7
8
9
from functools import reduce
from Crypto.Util.number import getPrime, isPrime

while True:
p = reduce(lambda x,y: x*y, [getPrime(10) for _ in range(25)])*4 - 1
if(p%4 == 3 and isPrime(p)):
print(p)
break
#p=5143204670319561596213349668594160691006857613681759905713565676116637627

然后redapple师傅使用的是 $p= 2^{90} * 3^{97} - 1$。但其实我突然发现,使用 $k\times 2^x3^y-1$ 似乎看起来更顺眼:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
from Crypto.Util.number import *
for i in range(100,1000):
s=str(i)+'0'*80
p=int(s)-1
if(isPrime(p)):
print(p)
"""
13199999999999999999999999999999999999999999999999999999999999999999999999999999999
14099999999999999999999999999999999999999999999999999999999999999999999999999999999
16399999999999999999999999999999999999999999999999999999999999999999999999999999999
17399999999999999999999999999999999999999999999999999999999999999999999999999999999
32699999999999999999999999999999999999999999999999999999999999999999999999999999999
36499999999999999999999999999999999999999999999999999999999999999999999999999999999
37799999999999999999999999999999999999999999999999999999999999999999999999999999999
38399999999999999999999999999999999999999999999999999999999999999999999999999999999
39499999999999999999999999999999999999999999999999999999999999999999999999999999999
43699999999999999999999999999999999999999999999999999999999999999999999999999999999
72199999999999999999999999999999999999999999999999999999999999999999999999999999999
79199999999999999999999999999999999999999999999999999999999999999999999999999999999
86599999999999999999999999999999999999999999999999999999999999999999999999999999999
"""

然后后面就是双线性对在 $\mathbb F_{p^2}$ 上解离散对数。但需要注意: 虽然 $e(aG,bH)=e(G,H)^{ab}$,但若 $H=kG$,则这个配对是退化的。但如果你关注了题目的生成过程,你会发现它的取模多项式是 $x^2-v$,其中 $v$ 是模 $p$ 的二次非剩余。因此找两个坐标,就可以找一个 $y$ 坐标带 sqv 的,一个 $y$ 坐标不带 sqv 的就行了。(其实只有可能出现这两种情况,因为 $x$ 坐标被限制在了 $\mathbb F_p$ 而非 $\mathbb F_{p^2}$ 上)。

那这样我们就可以刷44组挑战了。但刷完 44 组挑战,你会发现:44组挑战只给出了 616 个State,还剩 8 个State不知道(因为逆MT19937需要 624 个State)。不过你会注意到: $q$ 的高位有320比特,这里有 10 个State,那再取最高的 8 个State不就行了吗?:P

其实,这个hint也并不一定有用,因为 $p$ 也是 MT 生成的。在MT中,有:
$$
s_{i+624}=f(s_{i},s_{i+397})
$$

因此,只有 616 个state,虽然无法恢复 $q$,但是可以恢复 $p$ 的(我随便丢8个State进去,就算计算结果,但不影响 $p$ 啊)!这样本题也可以解。(如果你是先选择1再选择2的话)。当然,如果你先选择2再选择1,没有 $q$ 高位,你随便丢8个State进去,$p$ 可能求不出来,但 $q$ 也是可以完整恢复的。

逆MT19937的脚本网上一大堆,自己随便找一个都可以。

脚本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
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
from pwn import *
from sage.all import *

sh=process(['sage','15.sage'])
sh.recvuntil(b'>')
sh.sendline(b'1')
rsa=[]
for i in range(4):
sh.recvuntil(b'=')
rsa.append(eval(sh.recvline(keepends=False)))
print(rsa)
sh.recvuntil(b'>')
sh.sendline(b'2')

p=11130688431486566733102370304229766445269014631910188729551951723268722596002353872210735999

sh.recvuntil(b'>')
sh.sendline(str(p).encode())
sh.recvuntil(b'>')
sh.sendline(b"1 0")
sh.recvuntil(b">")
sh.sendline(b"3 -3")
sh.recvuntil(b':')
v=2
while(pow(v,p>>1,p)==1):
v+=1
Fp2=GF((p,2),modulus=[-v,0,1],name='sqv')
G1L=list(eval(sh.recvline(keepends=False)))
sh.recvuntil(b':')
G2L=list(eval(sh.recvline(keepends=False)))
E=EllipticCurve(Fp2,[1,0])
print(G1L,G2L)
G1=E(Fp2(G1L[:2]),Fp2(G1L[2:]))
G2=E(Fp2(G2L[:2]),Fp2(G2L[2:]))
Gord=G1.order()
g1=G1.weil_pairing(G2,Gord)
g2=G2.weil_pairing(G1,Gord)
print(G1.order())
print(G2.order())
L=[]
for i in range(44):
print(f'Round {i}')
sh.recvuntil(b':')
HL=list(eval(sh.recvline(keepends=False)))
H=E(Fp2(HL[:2]),Fp2(HL[2:]))
h1=G1.weil_pairing(H,Gord)
h2=G2.weil_pairing(H,Gord)
k1,k2=discrete_log(h1,g1,ord=Gord),discrete_log(h2,g2,ord=Gord)
print(k1,k2)
L.append(k2%Gord)
L.append(k1%Gord)
sh.sendline(f'{k2%Gord} {k1%Gord}'.encode())
L32=[]
for number in L:
C=[]
for _ in range(7):
C.append(number&0xffffffff)
number>>=32
L32+=C

print(L32)
print(len(L32))
sh.interactive()

脚本2:逆MT的脚本(需要输入L32数组)

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
from sage.all import *
from Crypto.Util.number import *
D=# copy the L32(length:616) in script 1

N,E,C,qh=[87216570161982833430902035560412147135145681837621932618486613321608862913599151939219568958153311547038533567667171315025800801390839749679254540035616471811414840759407621709098084614227583518736383797201728857211835582326649463887873456102856104843905654782916333168085148622754035138548554733888680376882652393953479458476141892547568252266814561338313481866406783023719496762953779349914489941286959579133848282378941841661164127980306391616111178050277139782105316087058427655533044660489619043019846560822194853211128702555303824846665251091210479056780238663074400002848174849504475254577248465452087599800877145429200981996084796740953618072368579977308238148183176521128889075045551592118888768935640765809008665049492513950779464441358606873878789437195260243, 1435756429, 51873311924894259743738403461931986418501984388003256448601794920336903069816183820045646620456148123365352359646174692417636201100932835146139263745201687519602814581262201733211810074925585975986691425506064499628193443400229517771761827547986003200414810115081621901681073468599529811818247991788235845512013241026469719685089233436289779982160574977595195431263856366529319171468703237407716867809155572513960460395202174191625585399903570418870892656879333481439050243512487060865697022837664033887100981349707263939364832466743975377536025444151592694830704628373710665017317880908320690256565032677209170924646944982310083173959691777931368832770396184555557239424549961573899171460760607873824074468289061559214207573651704414847570339849583296180920683418698707, 472133320010860456366591585411701439846065287256051361744200840425980296947521185872001642456429]



qh32=[]
qhtmp=qh
for i in range(10):
qh32.append(qhtmp&0xffffffff)
qhtmp>>=32
print(qh32)


from mttool import MT19937
mt=MT19937()
mt.setstate(qh32[-8:]+D)
mt.invtwist()
mt.invtwist()
R=[]
for i in range(624+8):
R.append(mt.getstate())
q=0
for i in range(40):
q<<=32
q|=R.pop(-1)
print(q,q.bit_length())
q=next_prime(q)
print(N%q)
p=N//q
d=inverse(E,(p-1)*(q-1))
print(long_to_bytes(pow(int(C),int(d),int(N))))

脚本3:mttool.py(被脚本2引用)

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
from Crypto.Util.number import *
from hashlib import md5
import random
def _int32(x):
return int(0xFFFFFFFF & x)
class MT19937:
def __init__(self, seed=0):
self.mt = [0] * 624
self.mt[0] = seed
self.mti = 0
for i in range(1, 624):
self.mt[i] = _int32(1812433253 * (self.mt[i - 1] ^ self.mt[i - 1] >> 30) + i)
def getstate(self,op=False):
if self.mti == 0 and op==False:
self.twist()
y = self.mt[self.mti]
y = y ^ y >> 11
y = y ^ y << 7 & 2636928640
y = y ^ y << 15 & 4022730752
y = y ^ y >> 18
self.mti = (self.mti + 1) % 624
return _int32(y)
def twist(self):
for i in range(0, 624):
y = _int32((self.mt[i] & 0x80000000) + (self.mt[(i + 1) % 624] & 0x7fffffff))
self.mt[i] = (y >> 1) ^ self.mt[(i + 397) % 624]
if y % 2 != 0:
self.mt[i] = self.mt[i] ^ 0x9908b0df
def inverse_right(self,res, shift, mask=0xffffffff, bits=32):
tmp = res
for i in range(bits // shift):
tmp = res ^ tmp >> shift & mask
return tmp
def inverse_left(self,res, shift, mask=0xffffffff, bits=32):
tmp = res
for i in range(bits // shift):
tmp = res ^ tmp << shift & mask
return tmp
def extract_number(self,y):
y = y ^ y >> 11
y = y ^ y << 7 & 2636928640
y = y ^ y << 15 & 4022730752
y = y ^ y >> 18
return y&0xffffffff
def recover(self,y):
y = self.inverse_right(y,18)
y = self.inverse_left(y,15,4022730752)
y = self.inverse_left(y,7,2636928640)
y = self.inverse_right(y,11)
return y&0xffffffff
def setstate(self,s):
if(len(s)!=624):
raise ValueError("The length of prediction must be 624!")
for i in range(624):
self.mt[i]=self.recover(s[i])
#self.mt=s
self.mti=0
def predict(self,s):
self.setstate(s)
self.twist()
return self.getstate(True)
def invtwist(self):
high = 0x80000000
low = 0x7fffffff
mask = 0x9908b0df
for i in range(623,-1,-1):
tmp = self.mt[i]^self.mt[(i+397)%624]
if tmp & high == high:
tmp ^= mask
tmp <<= 1
tmp |= 1
else:
tmp <<=1
res = tmp&high
tmp = self.mt[i-1]^self.mt[(i+396)%624]
if tmp & high == high:
tmp ^= mask
tmp <<= 1
tmp |= 1
else:
tmp <<=1
res |= (tmp)&low
self.mt[i] = res
def example():
D=MT19937(48)
print(D.getstate())
print(D.mt[:5])
print(D.recover(90324435))
print(D.extract_number(90324435))
D.twist()
print(D.mt[:5])
D.invtwist()
print(D.mt[:5])
#Main Below#
# example()

8. Broadcast2(Medium+, 0 Solves, 500pts)

先看一下题目:

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
import random as random2
import os
from datetime import *
from sage.all import *

rng=random2.Random()
rng.seed(os.urandom(48))

class LFSR:
def __init__(self,n,p,seed,mask):
self.n=n
self.p=p
self.mask=mask[:n]
self.state=seed[:n]

def getstate(self):
ret=sum([u*v%self.p for u,v in zip(self.state,self.mask)])%self.p
self.state.append(ret)
self.state.pop(0)
return ret

q=251
R=PolynomialRing(Zmod(q),'X')
X=R.gen(0)

QR=R.quo(X**256+X+6)
ERR=list(range(q))
shuffle(ERR)


ESEED=[rng.randint(0,6) for _ in range(5)]
ESEED[rng.randint(0,4)]=rng.randint(1,6)
EMASK=[rng.randint(0,6) for _ in range(5)]
EMASK[rng.randint(0,4)]=rng.randint(1,6)
rng.seed(os.urandom(33))
rng.shuffle(ESEED)
rng.shuffle(EMASK)
lfsr57=LFSR(5,7,ESEED,EMASK)

token=''.join([random2.choice('0123456789ABCDEFGHJK')for _ in range(256)])
s=[ord(ch) for ch in token]
s=QR(s)
seedA=os.urandom(48).hex()
print('seedA= ',seedA)

rngA=random2.Random()
rngA.seed(seedA)
for i in range(548):
op=int(input('Give me your option>'))
if(op==1):
A=QR([rngA.randint(0,q-1) for _ in range(256)])
e=QR([ERR[lfsr57.getstate()] for _ in range(256)])
print('Your Cipher=',list(A*s+e))
elif(op==2):
token1=input('GIVE ME MY TOKEN>').strip()
if(token1==token):
print('Congraduations! Here is your flag:',os.getenv('GZCTF_FLAG'))
else:
print('Sorry, Wrong Token')

8.1 出题人预期解

这个题其实是抄的去年网鼎杯 Noisy-LFSR 的一个出题思想(把那个题的思想套到了RLWE上来)。有兴趣的朋友可以去网上搜一下那个题的wp。其核心解法有一条是:虽然模数 $p$,长度 $n$ 的 LFSR 最大周期是 $p^{n}-1$,但需要 LFSR 的 mask 必须是本源多项式。而如果我随机生成一个 LFSR,那么它极大概率是不满周期的。

本题就是利用了这样一个思想,其实如果有选手把题目中生成LFSR的过程跑多次看看,统计一下周期就可以发现,这个LFSR很有可能达不到 16806 的最大周期。题目中给了 548 次交互机会,有大约 1/3 的概率,LFSR的周期是小于 547 的。

因此,如果我们交互 547 次,我们就可以按一定次序得到 547×256=140032个类似于 $\sum_{i=0}^{255} a_is_i+e=b$ 的方程,将这些方程存入数组。然后暴力枚举周期,这样所有的 $e$ 都相同。然后再暴力枚举 $e$ (反正模数只有251)。然后根据token的特征(只有0123456789ABCDEFGHJK)就可以筛选出token,并在最后一次提交token,获取flag。

这个题格基规约是做不出来的,因为 $s,e$ 都是随机数,$e$ 你甚至不知道(当然就无法线性化)。并且 $q$ 只有 251,LLL大概率只能得到单位矩阵。

当然枚举周期也有个小技巧:你可以多次测试随机生成 LFSR ,并记录其周期出现的频率,把概率最大的放在前面(比如48,342,114,336,24,168)就可以快速出解了。当然,构建方程也可以用Sagemath很快地完成。

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
import random as random2
import os
from datetime import *
from sage.all import *
from tqdm import *
from pwn import *


# context.log_level='debug'
sh=process(['python3','task.py'])


sh.recvuntil(b'=')
seedA=sh.recvline().strip().decode()
rngA=random2.Random()
rngA.seed(seedA)
print(seedA)

q=251
R=PolynomialRing(Zmod(q),'X')
X=R.gen(0)
QR=R.quo(X**256+X+6)

eqArr=[]
for T in tqdm(range(547)):
sh.recvuntil(b'>')
sh.sendline(b'1')
sh.recvuntil(b'=')
b=eval(sh.recvline().strip())
A=QR([rngA.randint(0,q-1) for _ in range(256)])
Am=A.matrix().T
for j in range(256):
eqArr.append((Am[j],b[j]))

TCandidate=[48, 342, 114, 336, 24, 168, 480, 42, 171, 456, 300, 240, 400, 150, 84, 12, 228, 57, 120, 96, 16, 144, 399, 304, 160, 200, 75, 18, 38, 60, 30, 72, 21, 112, 6, 100, 50, 152, 80, 40, 126, 19, 25, 36, 76, 266, 9, 56, 8, 15, 28, 14, 32, 3, 63, 10, 7, 133, 1, 20, 2, 4, 5]

for T in tqdm(TCandidate):
eqs=eqArr[::T][:256]
M=[]
y=[]
for i in range(256):
M.append(eqs[i][0])
y.append(eqs[i][1])
M=matrix(Zmod(q),M)
for i in range(251):
vecy=vector(Zmod(q),[yj-i for yj in y])
try:
token=list(M.solve_right(vecy))
if(all([j in [48,49,50,51,52,53,54,55,56,57,65,66,67,68,69,70,71,72,74,75] for j in token])):
sh.recvuntil(b'>')
sh.sendline(b'2')
sh.recvuntil(b'>')
sh.sendline(bytes(token))
print(sh.recvall(timeout=4))
exit(0)
except Exception as e:
print(e)

9.总结

SUSCTF 2025也算是成功地举办了,自己从 2024 年的参赛,到 2025 年的出题,感觉一下子仿佛回到了 4 年前自己从参加 0xGame 到 0xGame出题的过程。2025年不知不觉也只剩下四分之一了,顺便回顾了一下自己的2025,之前CTF拿了个省奖,还拿到了密码数学挑战赛的国奖,最后自己规格化总分 86.18 排名年级 397 人第 2,南京校区 221 人第 1(上次拿年级第一甚至还是2015年;上次去西安也是2015年(甚至那一次和今年一样都是8月19日去的西安);笑死,10 years ago once more是吧)。科研的话,目前自己也开始跟着导师一起,步入了正式的轨道,开始了正式地理论推导 和 实验研究过程。

回顾一下自己去年CTF之路的话,其实自从 9 月打完之后,10月11月还是经历了一个快速的水平上升期,进一步搞懂了Lattice的构造法,纠正了以前错误的造格的姿势。然后对抗量子密码也了解了更多,以及各种求解SVP的方法。 1月简单接触了同源以及双线性对这些东西(其实双线性对很早自己就接触到了,但一直没有在CTF中用过双线性对,只觉得这玩意构造很有用)。

CTF的话,估计研二打得应该没有研一多了,后面肯定还是以科研为主,争取在孙老师带领下发 2 篇论文,然后顺利开题,顺利毕业吧。CTF的话简单参加参加吧,后面SUS需要看的话,有空就帮忙看看。(毕竟现在SUS似乎就我一个做 Crypto 的了,压力也是很大的,还有好多东西没学)。

虽然现在似乎自己稳定下来了,但还是有点怕自己毕不了业。。算了,走一步是一步吧。。。以及,自己明明很菜,为啥总有人把我当佬呢?


SUSCTF2025
http://example.com/2025/10/11/SUSCTF2025/
作者
huangx607087
发布于
2025年10月11日
许可协议