25Mar2

huangx607087 25年3月的做题2

0.Introduction

本来想出一期多项式专题的,不过最近在做导师项目,有亿点忙,上周还看了NCTF,因此一直咕咕咕。本来25Mar1和25Mar2的计划日期分别是 $3.10$ 和 $3.25$ 的,结果变成了 $3.21$ 和 $3.31$,甚至两个文章都有都有预制部分。。。所以第四个题直接把三月初做的一个题来凑数了。。。

后面准备把NSS上鸡块佬的Matrix系列和easy_mod系列再学习一下,到时候各出一期。有空的话就是 4 月,没空的话就继续咕咕咕。。。

1.[西湖论剑2025] New Year Ring 4

ref:2025-西湖论剑-New-Year-Ring4-wp | 糖醋小鸡块的blog (tangcuxiaojikuai.xyz)

又是一个多项式题,不过经过了25Jan1中两个NTRU的解题方法的了解,和25Feb1中那个VNCTF优化程序的方法,之前看着WP还是一头雾水,现在看了看,发现还是基本能看懂了(没有看出题人的exp)!跟着思路来做一下!

1x01 初步审题

还是先来看看题目:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
from random import randint, choice, shuffle
from Crypto.Util.number import *
from Crypto.Cipher import AES
from hashlib import md5
from secret import flag

p = getPrime(round(20.25))
a, b, d = randint(0, p), randint(0, p), 14
A, B, seed, secret = [], [], [randint(0, p) for _ in range(4)], [randint(0, p) for _ in range(d)]

PR.<x> = PolynomialRing(GF(p))
PRq = PR.quo(PR(list(b"DASCTF_XHLJ2025")))
for i in range(ord("🚩") % sum(list(map(ord, "flag")))): #351
A += [PRq.random_element().list()]
B += [(PRq(A[i]) * PRq(secret) + PRq([choice(seed) for _ in range(d)])).list()]
seed = [(a * _ + b) % p for _ in seed]

print("A =", [a] + A)
print("B =", ["b"]+B)
print("C =", AES.new(key=md5(str([b]+seed+secret).encode()).digest(), nonce=b"Xenny.fans.club", mode=AES.MODE_CTR).encrypt(flag).hex())

题目是一个明显的RLWE的题目,但和VNCTF那个题相比,其不同点如下:VNCTF那个题的两个 $e$ 是已知且静止的,但这个题有四个 $e$ 的可能取值,并且在一轮加密结束后,每个 $e$ 还会进行线性递推,也就是第二轮的 $e$ 的四个取值范围分别为 $ae_i+b,i=0,1,2,3$。这里递推式 $a$ 已知,$b$ 未知。题目还给出了每轮 $As+e=y$ (为了不和上面的 $b$ 混淆,这里用 $y$ 表示)。

在多项式商环的运算中,$A(x)\cdot s(x)$ 可以写作 $\vec s\cdot \mathbf A$,其中 $\mathbf A$ 是 $A(x)$ 的多项式矩阵形式,$\mathbf A$ 的第 $i$ 行为 $x^iA(x)$。请注意,这里行数取值范围是 $0\sim n-1$。那么这个题目就可以很好地转化成一个LWE问题,这也是题解中写到的,并且也是比较明显的事实,在这里就不说了。

既然都已经变成熟悉的内容了,那么咱们直接很快列出方程:
$$
(\sum_{i=0}^{13}a_is_i-y-e_0)(\sum_{i=0}^{13}a_is_i-y-e_1)(\sum_{i=0}^{13}a_is_i-y-e_2)(\sum_{i=0}^{13}a_is_i-y-e_3)=0
$$
然后对这个方程,写个代码展开,去分析一下系数,这里是Sage中的符号计算,我们将 $s,e$ 看作变量,!

测试代码:

1
2
3
4
5
6
7
8
9
a=[var(f"a{i}")for i in range(14)]
s=[var(f"s{i}")for i in range(14)]
e=[var(f"e{i}")for i in range(14)]
y=var("y")
z=sum([a[i]*s[i]for i in range(14)])
f=(z-y-e[0])*(z-y-e[1])*(z-y-e[2])*(z-y-e[3])
f=f.expand()
print(f.coefficient(s0)(s1=0,s2=0,s3=0,s4=0,s5=0,s6=0,s7=0,s8=0,s9=0,s10=0,s11=0,s12=0,s13=0,e0=0,e1=0,e2=0,e3=0))
#-4*a0*y^3

如果不考虑 $e$ 的存在,那么我们可以得到这些:

单变量 $s_i$ $s_i^2$ $s_i^3$ $s_i^4$
系数 $-4a_iy^3$ $6a_i^2y^2$ $-4a_i^3y$ $a_i^4$
双变量 $s_is_j$ $s_i^2s_j$ $s_is_j^2$ $s_i^3s_j$ $s_i^2s_j^2$ $s_is_j^3$
系数 $12a_ia_jy^2$ $-12a_i^2a_jy$ $-12a_ia_j^2y$ $4a_i^3a_j$ $6a_i^2a_j^2$ $4a_ia_j^3$
三变量 $s_is_js_k$ $s_i^2s_js_k$ $s_is_j^2s_k$ $s_is_js_k^2$
系数 $-24a_ia_ja_ky$ $12a_i^2a_ja_k$ $12a_ia_j^2a_k$ $12a_ia_ja_k^2$
四变量 $s_is_js_ks_l$
系数 $24a_ia_ja_ka_l$

其实还挺有规律的,xs,并且补充一句,显然,常数项为 $y^4$,这个可以移到等号右边去。

如果 $e$ 已知的话,那么就是VNCTF那个题了,到这里其实那个题就结束了。

1x02 初步尝试

但这边,我们还要考虑 $e$ 的动态性,重新列式子:
$$
(\sum_{i=0}^{13}a_is_i-y-Ke_0-Ub)(\sum_{i=0}^{13}a_is_i-y-Ke_1-Ub)(\sum_{i=0}^{13}a_is_i-y-Ke_2-Ub)(\sum_{i=0}^{13}a_is_i-y-Ke_3-Ub)=0
$$
经过测试,第 $n(0\le n\le350)$ 轮,$K=a^n,U=\sum_{i=0}^{n-1}a^i=\dfrac{a^n-1}{a-1}$。当然,我们发现,$b$ 每个等式中都有,索性把 $b$ 当作 $s_{14}$ 处理,$-U$ 当作$a_{14}$ 处理,这不还是上面那个式子吗,注意这里的符号! $a_{14}=\dfrac{1-a^n}{a-1}$。
$$
(\sum_{i=0}^{14}a_is_i-y-Ke_0)(\sum_{i=0}^{14}a_is_i-y-Ke_1)(\sum_{i=0}^{14}a_is_i-y-Ke_2)(\sum_{i=0}^{14}a_is_i-y-Ke_3)=0
$$
那么,这和上面的,不也没啥区别了吗?

然后就是手撕系数呗:

当然,我们可以发现一个小技巧:就是 $e$ 在这边具有轮换对称性,也就是 $s_je_1$ 和 $s_je_2$ 的系数一定相等,$s_is_je_1e_2$ 和 $s_is_je_2e_3$ 的系数一定相等。也就是,当 $s$ 的形式固定时,$e$ 的次数相同,那么其系数一定相同,无需考虑 $e_0,e_1,e_2,e_3$。但是这样一个一个测真麻烦。。。但我发现,Sage的代数式可以传字典进去,真不错!

然后我就写了一个这个,然而贼慢,12秒一组,5000组要60000秒,但复杂度其实并没有错,一行的长度确实是4844。。。(可能有小bug)

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
PR.<x>=PolynomialRing(GF(p))
R.<x> = PR.quo(PR(list(b"DASCTF_XHLJ2025")))
abars=[var(f"abar{i}")for i in range(15)]
sbars=[var(f"sbar{i}")for i in range(15)]
ebars=[var(f"ebar{i}")for i in range(4)]
ybar=var("ybar")
kbar=var("kbar")
ALLZEROS=dict(zip(abars+sbars+ebars+[ybar,kbar],[0]*(15+15+4+2)))
zas=sum([abars[i]*sbars[i]for i in range(15)])
f=(zas-ybar-kbar*ebars[0])*(zas-ybar-kbar*ebars[1])*(zas-ybar-kbar*ebars[2])*(zas-ybar-kbar*ebars[3])
f=f.expand()
from tqdm import *
Ams=[R(A[i]).matrix().change_ring(ZZ).T for i in range((351))]
M=[]
negy4=[]
for T in range(1):
a14=Integer(GF(p)((1-K**T)/(1-K)))
for i in trange(14):
lineA=list(Ams[][i])+[a14]
bi=B[T][i]
negy4.append((-bi**4)%p)
linevec=[]
coeffs=lineA+[bi]+[Integer(pow(K,T,p))]
coeffDict=dict(zip(abars+[ybar,kbar],coeffs))
fi=(f(coeffDict))
for j in range(15):
linevec.append(int(fi.coefficient(sbars[j])(ALLZEROS))%p)
for j in range(15):
linevec.append(int(fi.coefficient(sbars[j]**2)(ALLZEROS))%p)
for j in range(15):
linevec.append(int(fi.coefficient(sbars[j]**3)(ALLZEROS))%p)
for j in range(15):
linevec.append(int(fi.coefficient(sbars[j]**4)(ALLZEROS))%p)
#double symbol
for j1 in range(15):
for j2 in range(j1+1,15):
linevec.append(int(fi.coefficient(sbars[j1]*sbars[j2])(ALLZEROS))%p)
linevec.append(int(fi.coefficient(sbars[j1]**2*sbars[j2])(ALLZEROS))%p)
linevec.append(int(fi.coefficient(sbars[j1]*sbars[j2]**2)(ALLZEROS))%p)
linevec.append(int(fi.coefficient(sbars[j1]**2*sbars[j2]**2)(ALLZEROS))%p)
linevec.append(int(fi.coefficient(sbars[j1]**3*sbars[j2])(ALLZEROS))%p)
linevec.append(int(fi.coefficient(sbars[j1]*sbars[j2]**3)(ALLZEROS))%p)
for j1 in range(15):
for j2 in range(j1+1,15):
for j3 in range(j2+1,15):
linevec.append(int(fi.coefficient(sbars[j1]*sbars[j2]*sbars[j3])(ALLZEROS))%p)
linevec.append(int(fi.coefficient(sbars[j1]**2*sbars[j2]*sbars[j3])(ALLZEROS))%p)
linevec.append(int(fi.coefficient(sbars[j1]*sbars[j2]**2*sbars[j3])(ALLZEROS))%p)
linevec.append(int(fi.coefficient(sbars[j1]*sbars[j2]*sbars[j3]**2)(ALLZEROS))%p)
for j1 in range(15):
for j2 in range(j1+1,15):
for j3 in range(j2+1,15):
for j4 in range(j3+1,15):
linevec.append(int(fi.coefficient(sbars[j1]*sbars[j2]*sbars[j3]*sbars[j4])(ALLZEROS))%p)
for j1 in range(15):
linevec.append(4*int(fi.coefficient(sbars[j1]*ebars[0])(ALLZEROS))%p)
linevec.append(6*int(fi.coefficient(sbars[j1]*ebars[0]*ebars[1])(ALLZEROS))%p)
linevec.append(4*int(fi.coefficient(sbars[j1]*ebars[0]*ebars[1]*ebars[2])(ALLZEROS))%p)
linevec.append(4*int(fi.coefficient(sbars[j1]**2*ebars[0])(ALLZEROS))%p)
linevec.append(6*int(fi.coefficient(sbars[j1]**2*ebars[0]*ebars[1])(ALLZEROS))%p)
linevec.append(4*int(fi.coefficient(sbars[j1]**3*ebars[0])(ALLZEROS))%p)
for j1 in range(15):
for j2 in range(j1+1,15):
linevec.append(4*int(fi.coefficient(sbars[j1]*sbars[j2]*ebars[0])(ALLZEROS))%p)
linevec.append(6*int(fi.coefficient(sbars[j1]*sbars[j2]*ebars[0]*ebars[1])(ALLZEROS))%p)
linevec.append(4*int(fi.coefficient(sbars[j1]**2*sbars[j2]*ebars[0])(ALLZEROS))%p)
linevec.append(4*int(fi.coefficient(sbars[j1]*sbars[j2]**2*ebars[0])(ALLZEROS))%p)
for j1 in range(15):
for j2 in range(j1+1,15):
for j3 in range(j2+1,15):
linevec.append(4*int(fi.coefficient(sbars[j1]*sbars[j2]*sbars[j3]*ebars[0])(ALLZEROS))%p)
linevec.append(4*int(fi.coefficient(ebars[0])(ALLZEROS))%p)
linevec.append(6*int(fi.coefficient(ebars[0]*ebars[1])(ALLZEROS))%p)
linevec.append(4*int(fi.coefficient(ebars[0]*ebars[1]*ebars[2])(ALLZEROS))%p)
linevec.append(1*int(fi.coefficient(ebars[0]*ebars[1]*ebars[2]*ebars[3])(ALLZEROS))%p)

由此,这就是为什么题解中可以”取消内部置换”了。其实上面这个代码的系数 $4,6,4$ 也体现出来了。虽然这里写作:
$$
(\sum_{i=0}^{14}a_is_i-y-Ke_0)^4=0
$$
但其实这边的 $e,e^2,e^3,e^4$ 和原来的值虽然不同,但我们却可以注意到,对应 $s$ 的系数仍然是相同的,因此这样可以正确地解出 $s$。

1x03 最终结果

好家伙,这多项式题还能不能做了?!然后看了一下官方wp,结果又发现了sage中一些奇妙的东西:

官方wp中使用的是 PolynomialRing,而自己一开始在仅有思路时写的时候,使用的是符号,并且很多系数不能自行计算,还要建立一个字典,用ALLZEROS 去提取常数项。在 PolynomialRing 中的多项式中,可以使用 f.monomials() 获取 $f$ 中所有的单项式。然后还可以用 f.coefficients() 获取每个单项式的系数。不过这里是降幂排列,幂次相等的,按变量顺序逐步出现,差不多排序是这样的。

1
2
3
4
5
sage: TRR=PolynomialRing(GF(17),names=('s0','s1','s2','s3','s4'))
sage: s=TRR.gens()
sage: f=(sum(s)-1)**4
sage: print(f.monomials())
#[s0^4, s0^3*s1, s0^2*s1^2, s0*s1^3, s1^4, s0^3*s2, s0^2*s1*s2, s0*s1^2*s2, s1^3*s2, s0^2*s2^2, s0*s1*s2^2, s1^2*s2^2, s0*s2^3, s1*s2^3, s2^4, s0^3*s3, s0^2*s1*s3, s0*s1^2*s3, s1^3*s3, s0^2*s2*s3, s0*s1*s2*s3, s1^2*s2*s3, s0*s2^2*s3, s1*s2^2*s3, s2^3*s3, s0^2*s3^2, s0*s1*s3^2, s1^2*s3^2, s0*s2*s3^2, s1*s2*s3^2, s2^2*s3^2, s0*s3^3, s1*s3^3, s2*s3^3, s3^4, s0^3*s4, s0^2*s1*s4, s0*s1^2*s4, s1^3*s4, s0^2*s2*s4, s0*s1*s2*s4, s1^2*s2*s4, s0*s2^2*s4, s1*s2^2*s4, s2^3*s4, s0^2*s3*s4, s0*s1*s3*s4, s1^2*s3*s4, s0*s2*s3*s4, s1*s2*s3*s4, s2^2*s3*s4, s0*s3^2*s4, s1*s3^2*s4, s2*s3^2*s4, s3^3*s4, s0^2*s4^2, s0*s1*s4^2, s1^2*s4^2, s0*s2*s4^2, s1*s2*s4^2, s2^2*s4^2, s0*s3*s4^2, s1*s3*s4^2, s2*s3*s4^2, s3^2*s4^2, s0*s4^3, s1*s4^3, s2*s4^3, s3*s4^3, s4^4, s0^3, s0^2*s1, s0*s1^2, s1^3, s0^2*s2, s0*s1*s2, s1^2*s2, s0*s2^2, s1*s2^2, s2^3, s0^2*s3, s0*s1*s3, s1^2*s3, s0*s2*s3, s1*s2*s3, s2^2*s3, s0*s3^2, s1*s3^2, s2*s3^2, s3^3, s0^2*s4, s0*s1*s4, s1^2*s4, s0*s2*s4, s1*s2*s4, s2^2*s4, s0*s3*s4, s1*s3*s4, s2*s3*s4, s3^2*s4, s0*s4^2, s1*s4^2, s2*s4^2, s3*s4^2, s4^3, s0^2, s0*s1, s1^2, s0*s2, s1*s2, s2^2, s0*s3, s1*s3, s2*s3, s3^2, s0*s4, s1*s4, s2*s4, s3*s4, s4^2, s0, s1, s2, s3, s4, 1]

当然我们可以不必管他内部的顺序,但可以发现:我们所需要的值在最后。然后就是愉快地写代码的时间了。

但这样发现最后竟然没解出来!因为我这边是 p=next_prime(max([max(A[i]) for i in range (len(A))])),那就是选取的模数不对。但考虑到 $A$ 中最大的那个数还是很接近 $p$ 的,一次尝试大概是一分钟,那就多尝试几把,第 4 把能出。

然后最后枚举Key就直接抄过来了:Sage有个 permutations,可以直接给出list最终的排列结果。感觉这个题对于自己而言,因为这个套路已经掌握了,因此还是以学习SageMath中一些简化的代码为主。

最终代码:$\mathsf{61s,4.7GB}$。

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
#sage
A=[442656,[...]]
B=['b',[...]]
C='355799be839f2aece47ac7c125c026e86c5956a75b073aa29e645d6731b4336d998576cfe56f6ef0bfb33db5154b'
K,_=A.pop(0),B.pop(0)
n,m=len(A[0]),len(A)
p=next_prime(max([max(A[i]) for i in range (len(A))]))
for i in range(3):
p=next_prime(p)
PR.<x>=PolynomialRing(Zmod(p))
R.<x> = PR.quo(PR(list(b"DASCTF_XHLJ2025")))
TRR=PolynomialRing(Zmod(p),names=[f"sbar{i}" for i in range(15)]+["ebar"])
*sbars,ebar=TRR.gens()
vsbars=vector(sbars)
vecs13=vector(sbars[:-1])
listPoly=((sum(sbars)-ebar-1)**4)
monomialArr=listPoly.monomials()
# print(monomialArr)
MAarr=[R(Ax).matrix() for Ax in A]
vecs=vector(sbars[:14])
M=[]
y=[]
from tqdm import *
fs4arr=[]
for T in trange(351):
AT=MAarr[T].change_ring(ZZ)
vecsT=vecs*AT
for i in range(14):
linevec=[]
fs=vecsT[i]
fs+=sum([K**j for j in range(T)]) * sbars[14]+ K**T * ebar - B[T][i]
fs4 = (fs**4)
fs4arr.append(fs4)
print(len(fs4arr))
M=[]
y=[]
for i in range(len(fs4arr)):
coeff=fs4arr[i].coefficients()
if(len(coeff)==4845):
M.append(coeff[:-1])
y.append(-coeff[-1])
M=matrix(GF(p),M)
y=vector(GF(p),y)
s=M.solve_right(y)
*secret,b,_=s[-16:]
err=R(B[-1])-R(A[-1])*R(secret)
seterr=set([K*i+b for i in list(err)])
from itertools import *
from Crypto.Cipher import AES
from hashlib import md5
for seed in permutations(seterr):
flag = AES.new(key=md5(str([b]+list(seed)+secret).encode()).digest(), nonce=b"Xenny.fans.club", mode=AES.MODE_CTR).decrypt(bytes.fromhex(C))
if(b"DASCTF" in flag):
print(flag)
break
#b'DASCTF{jUsT_Lin34R1ZE_4nD_5OLv3_L1n3ar_SySt3m}'

2.[wdbfinal2024]piff

2x01 解题

来看一下题:

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 sage.rings.finite_rings.hom_finite_field import FiniteFieldHomomorphism_generic
from Crypto.Util.number import *
from Crypto.Cipher import AES
from secret import flag
import random

def pad(msg):
return msg + bytes([16 - len(msg) % 16]) * (16 - len(msg) % 16)

def generate_irreducible_polynomial(R, n):
while True:
f = R.random_element(degree=n)
while f.degree() != n:
f = R.random_element(degree=n)
if f.is_irreducible():
return f

def get_phi(R, t, stri):
t_str = str(t).split("a |--> ")[1].replace(stri,"x")
return R(t_str)

q = 41
n = 128
F = GF(q)
R = PolynomialRing(F,'x')
x = R.gen()
f = generate_irreducible_polynomial(R,n).monic()
F1 = generate_irreducible_polynomial(R,n).monic()
F2 = generate_irreducible_polynomial(R,n).monic()

k1 = GF(q^n, name = 'a', modulus = f)
k2 = GF(q^n, name = 'b', modulus = F1)
k3 = GF(q^n, name = 'c', modulus = F2)

t1 = FiniteFieldHomomorphism_generic(Hom(k1, k2))
t2 = FiniteFieldHomomorphism_generic(Hom(k1, k3))
phi1 = get_phi(R, t1, "b")
phi2 = get_phi(R, t2, "c")

k = [random.choice([0,1]) for _ in range(128)]
r = [random.choice([0,1]) for _ in range(128)]
m,r = R(k),R(r)
p = 2

C = (p*phi1(x)*r(phi1(x)) + m(phi1(x))) % F1(x)
key = int(''.join(str(i) for i in k) , 2)
aes = AES.new(long_to_bytes(key), mode=AES.MODE_ECB)
cipher = aes.encrypt(pad(flag))

print("F1 = {}".format(F1))
print("φ1 = {}".format(phi1))
print("F2 = {}".format(F2))
print("φ2 = {}".format(phi2))
print("C={}".format(C))
print("cipher={}".format(cipher))
"""
F1 = x^128 + 25*x^127 + 32*x^126 + 15*x^125 + 8*x^124 + 24*x^123 + 5*x^122 + 16*x^121 + 27*x^120 + 33*x^119 + 32*x^118 + 11*x^117 + 37*x^116 + 9*x^115 + 23*x^114 + 29*x^113 + 30*x^112 + 14*x^111 + 6*x^110 + 38*x^109 + 22*x^108 + 39*x^106 + 16*x^105 + 19*x^104 + 15*x^103 + 31*x^102 + 33*x^101 + 39*x^100 + 7*x^99 + 3*x^98 + 30*x^97 + 34*x^95 + 15*x^94 + 28*x^93 + 40*x^92 + 29*x^91 + 30*x^90 + 35*x^89 + 34*x^88 + 29*x^87 + 11*x^86 + 6*x^85 + 28*x^84 + x^83 + 12*x^82 + 2*x^81 + 7*x^80 + 12*x^79 + 5*x^78 + 35*x^77 + 6*x^76 + 23*x^75 + 21*x^74 + 6*x^73 + 32*x^72 + 23*x^71 + 11*x^70 + 8*x^69 + 18*x^68 + 38*x^67 + 13*x^66 + 38*x^64 + 19*x^63 + 36*x^62 + 21*x^61 + 12*x^60 + 28*x^59 + 22*x^58 + 19*x^57 + 8*x^56 + 7*x^55 + 34*x^54 + 9*x^53 + 15*x^52 + 37*x^51 + 6*x^50 + 22*x^49 + 19*x^48 + 33*x^47 + 2*x^46 + x^45 + 17*x^44 + 20*x^43 + 7*x^42 + 37*x^41 + 10*x^40 + 13*x^39 + 2*x^38 + 22*x^37 + 32*x^36 + 40*x^35 + 3*x^34 + 40*x^33 + 23*x^32 + 3*x^31 + 15*x^30 + 14*x^29 + 40*x^28 + 33*x^27 + 31*x^26 + 7*x^25 + 18*x^24 + 23*x^23 + 3*x^22 + 35*x^21 + 2*x^20 + 32*x^19 + 3*x^18 + 39*x^17 + 20*x^16 + 40*x^15 + 25*x^14 + 38*x^13 + 14*x^12 + 11*x^11 + 13*x^10 + 16*x^9 + 3*x^8 + 39*x^7 + 29*x^6 + 7*x^5 + 26*x^4 + 9*x^3 + 25*x^2 + 8*x + 4
φ1 = 22*x^126 + 37*x^125 + 33*x^124 + 23*x^123 + 9*x^122 + 12*x^121 + 22*x^120 + 7*x^119 + 12*x^118 + 23*x^117 + 22*x^116 + 16*x^115 + 12*x^114 + 6*x^113 + 23*x^112 + 9*x^111 + 9*x^110 + 23*x^109 + 27*x^108 + 38*x^107 + 21*x^106 + 38*x^105 + 19*x^103 + 12*x^102 + 20*x^101 + x^100 + 36*x^99 + 15*x^98 + 26*x^97 + 14*x^96 + 4*x^95 + 39*x^94 + 29*x^93 + 13*x^92 + 11*x^91 + 24*x^90 + 28*x^89 + 40*x^88 + 6*x^87 + x^86 + 30*x^85 + 33*x^84 + 21*x^83 + 38*x^82 + 24*x^81 + 3*x^80 + 29*x^79 + 32*x^78 + 14*x^77 + 28*x^76 + 19*x^75 + 21*x^74 + 16*x^73 + 32*x^72 + 4*x^71 + 24*x^70 + 30*x^69 + 18*x^68 + 19*x^67 + 16*x^66 + 12*x^65 + 24*x^64 + 26*x^63 + 10*x^62 + 25*x^61 + 15*x^60 + 22*x^59 + 35*x^58 + 27*x^57 + 35*x^56 + 25*x^55 + 3*x^54 + 4*x^53 + 27*x^52 + 12*x^51 + 20*x^50 + 29*x^49 + 29*x^48 + 11*x^47 + 34*x^46 + 13*x^45 + 5*x^44 + 5*x^43 + 26*x^42 + 29*x^41 + 15*x^40 + 21*x^39 + 24*x^38 + 26*x^37 + 2*x^36 + 22*x^35 + 40*x^34 + 14*x^33 + x^32 + 28*x^31 + 28*x^30 + 29*x^29 + 31*x^28 + 12*x^27 + 10*x^26 + 35*x^25 + 5*x^24 + 18*x^23 + 23*x^22 + 33*x^21 + 21*x^20 + 37*x^19 + 30*x^18 + 19*x^17 + 37*x^16 + 8*x^15 + 34*x^14 + 25*x^13 + 29*x^12 + 29*x^11 + 8*x^10 + 19*x^9 + 40*x^8 + 35*x^7 + 18*x^6 + 2*x^5 + 32*x^4 + 3*x^3 + 11*x^2 + 10*x + 36
F2 = x^128 + 39*x^127 + 16*x^126 + 24*x^125 + 18*x^124 + 31*x^123 + 12*x^122 + 37*x^121 + 11*x^120 + 15*x^119 + 34*x^118 + 25*x^117 + 27*x^116 + 4*x^115 + 16*x^114 + 18*x^113 + 31*x^112 + 40*x^111 + 9*x^110 + 15*x^109 + 23*x^108 + 24*x^107 + 26*x^106 + 6*x^105 + 32*x^104 + 16*x^103 + 38*x^102 + 2*x^101 + 3*x^100 + 40*x^99 + 30*x^98 + 27*x^97 + 24*x^96 + 7*x^95 + 40*x^94 + 28*x^93 + 11*x^92 + 30*x^91 + 36*x^90 + x^89 + 16*x^88 + 36*x^87 + 14*x^86 + x^84 + 33*x^83 + 5*x^82 + 15*x^81 + 33*x^80 + 28*x^79 + 39*x^78 + 16*x^77 + 29*x^76 + 34*x^75 + 38*x^74 + 34*x^73 + 25*x^72 + 9*x^71 + 5*x^70 + 19*x^69 + 39*x^68 + 23*x^67 + x^66 + 4*x^65 + 11*x^64 + 15*x^63 + 25*x^62 + 36*x^61 + 40*x^60 + 18*x^59 + 14*x^58 + 2*x^57 + 4*x^56 + 2*x^55 + 26*x^54 + 13*x^53 + 17*x^52 + 38*x^51 + 12*x^50 + 12*x^49 + 18*x^48 + 40*x^47 + 10*x^46 + 17*x^45 + 37*x^44 + 34*x^43 + 34*x^42 + 25*x^41 + 16*x^40 + 16*x^39 + 11*x^38 + 36*x^36 + 31*x^35 + 4*x^33 + 17*x^32 + 8*x^31 + 17*x^30 + 30*x^29 + 30*x^28 + 26*x^27 + 21*x^26 + 29*x^25 + 15*x^24 + 38*x^23 + 19*x^22 + 24*x^21 + 7*x^20 + 5*x^19 + 2*x^18 + 31*x^17 + 13*x^16 + 14*x^15 + 40*x^14 + 29*x^13 + 30*x^12 + 37*x^11 + 33*x^10 + 11*x^9 + 12*x^8 + 14*x^7 + 34*x^6 + 18*x^5 + 13*x^4 + 11*x^3 + 31*x^2 + 31*x + 25
φ2 = 29*x^126 + 38*x^125 + 25*x^124 + 11*x^123 + 13*x^122 + 23*x^121 + 2*x^120 + 34*x^119 + 3*x^118 + 40*x^117 + 19*x^116 + 17*x^115 + 31*x^114 + 6*x^113 + 28*x^112 + 34*x^111 + 37*x^110 + 25*x^109 + 39*x^108 + x^107 + 33*x^106 + 11*x^105 + 8*x^104 + 37*x^103 + 26*x^102 + 27*x^101 + 10*x^100 + 10*x^99 + 26*x^97 + 31*x^96 + 13*x^95 + 26*x^94 + 32*x^93 + 21*x^92 + 14*x^91 + 23*x^90 + 14*x^89 + 12*x^88 + 36*x^87 + 35*x^86 + 10*x^85 + 16*x^84 + 6*x^83 + x^82 + 13*x^81 + 23*x^80 + 27*x^79 + 23*x^78 + 31*x^77 + 2*x^76 + 7*x^75 + 39*x^74 + 17*x^73 + 23*x^72 + 3*x^71 + 37*x^70 + 17*x^69 + 17*x^68 + 29*x^67 + 4*x^66 + 30*x^65 + 11*x^64 + 21*x^63 + 11*x^62 + 8*x^61 + 32*x^60 + 26*x^59 + 7*x^58 + 37*x^57 + 4*x^55 + 26*x^54 + 37*x^53 + 27*x^52 + 40*x^51 + 6*x^50 + 9*x^49 + 14*x^48 + 23*x^47 + 9*x^46 + 18*x^45 + 21*x^44 + 37*x^43 + 13*x^42 + 24*x^41 + 11*x^40 + 40*x^39 + 5*x^38 + 32*x^37 + 7*x^36 + 31*x^35 + 4*x^34 + 12*x^33 + 24*x^32 + 40*x^31 + 16*x^30 + 23*x^29 + 29*x^28 + 12*x^27 + 32*x^26 + 25*x^25 + 12*x^24 + x^23 + 5*x^22 + 30*x^21 + 30*x^20 + 17*x^19 + 24*x^17 + 17*x^16 + 18*x^15 + 31*x^14 + 37*x^13 + 18*x^12 + 14*x^11 + 5*x^10 + 2*x^9 + 23*x^8 + 21*x^7 + 29*x^6 + 39*x^5 + 13*x^3 + 13*x^2 + 25*x + 30
C=20*x^127 + 31*x^126 + 21*x^125 + 19*x^124 + 30*x^123 + 4*x^122 + 32*x^121 + 19*x^120 + 24*x^119 + 33*x^118 + 40*x^117 + 39*x^116 + 3*x^115 + 32*x^113 + 24*x^112 + 31*x^111 + 15*x^110 + 7*x^109 + 25*x^108 + 16*x^107 + 13*x^106 + 5*x^105 + 11*x^104 + 38*x^103 + 38*x^102 + 28*x^101 + 33*x^100 + 32*x^99 + 24*x^98 + 26*x^97 + 36*x^96 + 32*x^95 + 38*x^94 + 26*x^93 + 28*x^91 + 37*x^90 + 35*x^89 + 25*x^88 + 14*x^87 + 9*x^86 + 33*x^85 + 15*x^84 + 18*x^83 + 12*x^82 + 34*x^81 + 12*x^80 + 35*x^79 + 40*x^78 + 9*x^77 + 23*x^76 + 23*x^75 + 12*x^74 + 7*x^73 + 27*x^72 + 7*x^71 + 14*x^69 + 40*x^68 + 34*x^66 + 39*x^65 + 30*x^64 + 23*x^63 + 8*x^62 + 28*x^61 + 37*x^60 + 34*x^59 + 35*x^58 + 33*x^57 + 3*x^56 + 28*x^55 + 39*x^54 + 13*x^53 + 31*x^52 + 7*x^51 + 38*x^49 + 40*x^48 + 11*x^47 + 30*x^46 + 19*x^45 + 38*x^44 + 37*x^43 + 21*x^42 + 9*x^41 + 8*x^40 + 31*x^39 + 22*x^38 + 24*x^37 + 8*x^36 + 17*x^35 + 16*x^34 + 29*x^33 + 32*x^32 + 17*x^31 + 39*x^30 + 20*x^29 + 4*x^27 + 40*x^26 + 6*x^24 + 27*x^23 + 25*x^22 + 4*x^21 + 5*x^20 + 8*x^19 + 28*x^18 + 21*x^17 + x^16 + 12*x^15 + 19*x^14 + 29*x^13 + 2*x^12 + 9*x^11 + 34*x^10 + 16*x^9 + 12*x^8 + 21*x^7 + 8*x^6 + 23*x^5 + 37*x^4 + 31*x^3 + 25*x^2 + 20*x + 21
cipher=b'\xc9\xe2\xcdzo\xa1\xcc\xe1\x0e(\x98W\xd3\xb9\x85X\xa3!P\xab\x00\x1cR r\xb4\xb8\xed\x8f\x83\x15r'
"""

题目给出了 $q=41,n=128$ 和三个域:$K_1,K_2,K_3$,它们的取模多项式分别为 $f,F_1,F_2$。其中 $f$ 未知,$F_1,F_2$ 已知。我们同时知道 $K_1\rightarrow K_2$ 和 $K_1\rightarrow K_3$ 的两个同态 $\phi_1,\phi_2$。此外还有两个未知多项式 $m(x),r(x)$,其所有系数只有 $0,1$ 两个取值。 最后我们要求出 $m$。题目给出的加密结果 $C$ :
$$
C\equiv 2\phi_1(x)r(\phi_1(x))+m(\phi_1(x)) \pmod {F_1}
$$
这个题的知识点就在于:同态是可以用矩阵表示的。假如我们知道了同态的表达式 $\phi_1(x)$,那么我们可以构造一个同态矩阵 $M$,其中 $M$ 的第 $i$ 行为 $(\phi_1(x))^i$ 对 $F_1$ 取模的值。注意这个 $F_1$ 是同态后的取模多项式,$i$ 取值为 $0\sim n-1$。

那么如果 $\phi(a(x))=b(x)$ 成立,那么这也可以写成:
$$
\vec aM=\vec b
$$
当然,如果给 $M$ 再多一行,也就是如果 $M$ 有 $n+1$ 行,每一行分别为 $\phi(x)^0$ 到 $\phi(x)^{n}$ ,那么实际上这就是个 $(n+1)\times n$ 的矩阵,其秩为 $n$,因此改该矩阵就存在了 left_kernel,值恰好为原域的取模多项式 $f$。

这边需要注意一个问题:之前在做RLWE的时候,我们也提到了RLWE的公共参数 $a(x)$ 也可以写成矩阵的形式,但那个矩阵每一行是 $x^ia(x)$ ,$i$ 取值为 $0\sim n-1$。而这边的同态映射的矩阵是 $(\phi(x))^n$,也同态映射多项式的 $n$ 次方,不是前面乘一个 $x^i$,这两者不能搞混了!

由于
$$
C\equiv 2\phi_1(x)r(\phi_1(x))+m(\phi_1(x))\pmod {F_1}
$$
那么根据上面的理论,该式子可以写成:
$$
\vec c\equiv 2\vec rM_1M_2+\vec mM_1 \pmod{41}
$$
分离出 $m$:
$$
\vec m=\vec cM_1^{-1}-2\vec rM_1M_2M_1^{-1}
$$
对应为:
$$
m(x)=\phi_1^{-1}(C)-\phi_1^{-1}(2\phi_1(x)r\phi_1(x))=\phi_1^{-1}(C)-2xr(x)
$$
由于 $m$ 和 $r$ 所有分量均为 $0,1$,这就说明 $2xr(x)$ 的系数不会很大,因此对 $\phi_1^{-1}(C)$ 模 $2$ 就能够得到 $m$ 了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
PR.<x>=PolynomialRing(GF(41))
F1 = x^128 + 25*x^127 + 32*x^126 + 15*x^125 + 8*x^124 + 24*x^123 + 5*x^122 + 16*x^121 + 27*x^120 + 33*x^119 + 32*x^118 + 11*x^117 + 37*x^116 + 9*x^115 + 23*x^114 + 29*x^113 + 30*x^112 + 14*x^111 + 6*x^110 + 38*x^109 + 22*x^108 + 39*x^106 + 16*x^105 + 19*x^104 + 15*x^103 + 31*x^102 + 33*x^101 + 39*x^100 + 7*x^99 + 3*x^98 + 30*x^97 + 34*x^95 + 15*x^94 + 28*x^93 + 40*x^92 + 29*x^91 + 30*x^90 + 35*x^89 + 34*x^88 + 29*x^87 + 11*x^86 + 6*x^85 + 28*x^84 + x^83 + 12*x^82 + 2*x^81 + 7*x^80 + 12*x^79 + 5*x^78 + 35*x^77 + 6*x^76 + 23*x^75 + 21*x^74 + 6*x^73 + 32*x^72 + 23*x^71 + 11*x^70 + 8*x^69 + 18*x^68 + 38*x^67 + 13*x^66 + 38*x^64 + 19*x^63 + 36*x^62 + 21*x^61 + 12*x^60 + 28*x^59 + 22*x^58 + 19*x^57 + 8*x^56 + 7*x^55 + 34*x^54 + 9*x^53 + 15*x^52 + 37*x^51 + 6*x^50 + 22*x^49 + 19*x^48 + 33*x^47 + 2*x^46 + x^45 + 17*x^44 + 20*x^43 + 7*x^42 + 37*x^41 + 10*x^40 + 13*x^39 + 2*x^38 + 22*x^37 + 32*x^36 + 40*x^35 + 3*x^34 + 40*x^33 + 23*x^32 + 3*x^31 + 15*x^30 + 14*x^29 + 40*x^28 + 33*x^27 + 31*x^26 + 7*x^25 + 18*x^24 + 23*x^23 + 3*x^22 + 35*x^21 + 2*x^20 + 32*x^19 + 3*x^18 + 39*x^17 + 20*x^16 + 40*x^15 + 25*x^14 + 38*x^13 + 14*x^12 + 11*x^11 + 13*x^10 + 16*x^9 + 3*x^8 + 39*x^7 + 29*x^6 + 7*x^5 + 26*x^4 + 9*x^3 + 25*x^2 + 8*x + 4
phi1 = 22*x^126 + 37*x^125 + 33*x^124 + 23*x^123 + 9*x^122 + 12*x^121 + 22*x^120 + 7*x^119 + 12*x^118 + 23*x^117 + 22*x^116 + 16*x^115 + 12*x^114 + 6*x^113 + 23*x^112 + 9*x^111 + 9*x^110 + 23*x^109 + 27*x^108 + 38*x^107 + 21*x^106 + 38*x^105 + 19*x^103 + 12*x^102 + 20*x^101 + x^100 + 36*x^99 + 15*x^98 + 26*x^97 + 14*x^96 + 4*x^95 + 39*x^94 + 29*x^93 + 13*x^92 + 11*x^91 + 24*x^90 + 28*x^89 + 40*x^88 + 6*x^87 + x^86 + 30*x^85 + 33*x^84 + 21*x^83 + 38*x^82 + 24*x^81 + 3*x^80 + 29*x^79 + 32*x^78 + 14*x^77 + 28*x^76 + 19*x^75 + 21*x^74 + 16*x^73 + 32*x^72 + 4*x^71 + 24*x^70 + 30*x^69 + 18*x^68 + 19*x^67 + 16*x^66 + 12*x^65 + 24*x^64 + 26*x^63 + 10*x^62 + 25*x^61 + 15*x^60 + 22*x^59 + 35*x^58 + 27*x^57 + 35*x^56 + 25*x^55 + 3*x^54 + 4*x^53 + 27*x^52 + 12*x^51 + 20*x^50 + 29*x^49 + 29*x^48 + 11*x^47 + 34*x^46 + 13*x^45 + 5*x^44 + 5*x^43 + 26*x^42 + 29*x^41 + 15*x^40 + 21*x^39 + 24*x^38 + 26*x^37 + 2*x^36 + 22*x^35 + 40*x^34 + 14*x^33 + x^32 + 28*x^31 + 28*x^30 + 29*x^29 + 31*x^28 + 12*x^27 + 10*x^26 + 35*x^25 + 5*x^24 + 18*x^23 + 23*x^22 + 33*x^21 + 21*x^20 + 37*x^19 + 30*x^18 + 19*x^17 + 37*x^16 + 8*x^15 + 34*x^14 + 25*x^13 + 29*x^12 + 29*x^11 + 8*x^10 + 19*x^9 + 40*x^8 + 35*x^7 + 18*x^6 + 2*x^5 + 32*x^4 + 3*x^3 + 11*x^2 + 10*x + 36
F2 = x^128 + 39*x^127 + 16*x^126 + 24*x^125 + 18*x^124 + 31*x^123 + 12*x^122 + 37*x^121 + 11*x^120 + 15*x^119 + 34*x^118 + 25*x^117 + 27*x^116 + 4*x^115 + 16*x^114 + 18*x^113 + 31*x^112 + 40*x^111 + 9*x^110 + 15*x^109 + 23*x^108 + 24*x^107 + 26*x^106 + 6*x^105 + 32*x^104 + 16*x^103 + 38*x^102 + 2*x^101 + 3*x^100 + 40*x^99 + 30*x^98 + 27*x^97 + 24*x^96 + 7*x^95 + 40*x^94 + 28*x^93 + 11*x^92 + 30*x^91 + 36*x^90 + x^89 + 16*x^88 + 36*x^87 + 14*x^86 + x^84 + 33*x^83 + 5*x^82 + 15*x^81 + 33*x^80 + 28*x^79 + 39*x^78 + 16*x^77 + 29*x^76 + 34*x^75 + 38*x^74 + 34*x^73 + 25*x^72 + 9*x^71 + 5*x^70 + 19*x^69 + 39*x^68 + 23*x^67 + x^66 + 4*x^65 + 11*x^64 + 15*x^63 + 25*x^62 + 36*x^61 + 40*x^60 + 18*x^59 + 14*x^58 + 2*x^57 + 4*x^56 + 2*x^55 + 26*x^54 + 13*x^53 + 17*x^52 + 38*x^51 + 12*x^50 + 12*x^49 + 18*x^48 + 40*x^47 + 10*x^46 + 17*x^45 + 37*x^44 + 34*x^43 + 34*x^42 + 25*x^41 + 16*x^40 + 16*x^39 + 11*x^38 + 36*x^36 + 31*x^35 + 4*x^33 + 17*x^32 + 8*x^31 + 17*x^30 + 30*x^29 + 30*x^28 + 26*x^27 + 21*x^26 + 29*x^25 + 15*x^24 + 38*x^23 + 19*x^22 + 24*x^21 + 7*x^20 + 5*x^19 + 2*x^18 + 31*x^17 + 13*x^16 + 14*x^15 + 40*x^14 + 29*x^13 + 30*x^12 + 37*x^11 + 33*x^10 + 11*x^9 + 12*x^8 + 14*x^7 + 34*x^6 + 18*x^5 + 13*x^4 + 11*x^3 + 31*x^2 + 31*x + 25
phi2 = 29*x^126 + 38*x^125 + 25*x^124 + 11*x^123 + 13*x^122 + 23*x^121 + 2*x^120 + 34*x^119 + 3*x^118 + 40*x^117 + 19*x^116 + 17*x^115 + 31*x^114 + 6*x^113 + 28*x^112 + 34*x^111 + 37*x^110 + 25*x^109 + 39*x^108 + x^107 + 33*x^106 + 11*x^105 + 8*x^104 + 37*x^103 + 26*x^102 + 27*x^101 + 10*x^100 + 10*x^99 + 26*x^97 + 31*x^96 + 13*x^95 + 26*x^94 + 32*x^93 + 21*x^92 + 14*x^91 + 23*x^90 + 14*x^89 + 12*x^88 + 36*x^87 + 35*x^86 + 10*x^85 + 16*x^84 + 6*x^83 + x^82 + 13*x^81 + 23*x^80 + 27*x^79 + 23*x^78 + 31*x^77 + 2*x^76 + 7*x^75 + 39*x^74 + 17*x^73 + 23*x^72 + 3*x^71 + 37*x^70 + 17*x^69 + 17*x^68 + 29*x^67 + 4*x^66 + 30*x^65 + 11*x^64 + 21*x^63 + 11*x^62 + 8*x^61 + 32*x^60 + 26*x^59 + 7*x^58 + 37*x^57 + 4*x^55 + 26*x^54 + 37*x^53 + 27*x^52 + 40*x^51 + 6*x^50 + 9*x^49 + 14*x^48 + 23*x^47 + 9*x^46 + 18*x^45 + 21*x^44 + 37*x^43 + 13*x^42 + 24*x^41 + 11*x^40 + 40*x^39 + 5*x^38 + 32*x^37 + 7*x^36 + 31*x^35 + 4*x^34 + 12*x^33 + 24*x^32 + 40*x^31 + 16*x^30 + 23*x^29 + 29*x^28 + 12*x^27 + 32*x^26 + 25*x^25 + 12*x^24 + x^23 + 5*x^22 + 30*x^21 + 30*x^20 + 17*x^19 + 24*x^17 + 17*x^16 + 18*x^15 + 31*x^14 + 37*x^13 + 18*x^12 + 14*x^11 + 5*x^10 + 2*x^9 + 23*x^8 + 21*x^7 + 29*x^6 + 39*x^5 + 13*x^3 + 13*x^2 + 25*x + 30
C=20*x^127 + 31*x^126 + 21*x^125 + 19*x^124 + 30*x^123 + 4*x^122 + 32*x^121 + 19*x^120 + 24*x^119 + 33*x^118 + 40*x^117 + 39*x^116 + 3*x^115 + 32*x^113 + 24*x^112 + 31*x^111 + 15*x^110 + 7*x^109 + 25*x^108 + 16*x^107 + 13*x^106 + 5*x^105 + 11*x^104 + 38*x^103 + 38*x^102 + 28*x^101 + 33*x^100 + 32*x^99 + 24*x^98 + 26*x^97 + 36*x^96 + 32*x^95 + 38*x^94 + 26*x^93 + 28*x^91 + 37*x^90 + 35*x^89 + 25*x^88 + 14*x^87 + 9*x^86 + 33*x^85 + 15*x^84 + 18*x^83 + 12*x^82 + 34*x^81 + 12*x^80 + 35*x^79 + 40*x^78 + 9*x^77 + 23*x^76 + 23*x^75 + 12*x^74 + 7*x^73 + 27*x^72 + 7*x^71 + 14*x^69 + 40*x^68 + 34*x^66 + 39*x^65 + 30*x^64 + 23*x^63 + 8*x^62 + 28*x^61 + 37*x^60 + 34*x^59 + 35*x^58 + 33*x^57 + 3*x^56 + 28*x^55 + 39*x^54 + 13*x^53 + 31*x^52 + 7*x^51 + 38*x^49 + 40*x^48 + 11*x^47 + 30*x^46 + 19*x^45 + 38*x^44 + 37*x^43 + 21*x^42 + 9*x^41 + 8*x^40 + 31*x^39 + 22*x^38 + 24*x^37 + 8*x^36 + 17*x^35 + 16*x^34 + 29*x^33 + 32*x^32 + 17*x^31 + 39*x^30 + 20*x^29 + 4*x^27 + 40*x^26 + 6*x^24 + 27*x^23 + 25*x^22 + 4*x^21 + 5*x^20 + 8*x^19 + 28*x^18 + 21*x^17 + x^16 + 12*x^15 + 19*x^14 + 29*x^13 + 2*x^12 + 9*x^11 + 34*x^10 + 16*x^9 + 12*x^8 + 21*x^7 + 8*x^6 + 23*x^5 + 37*x^4 + 31*x^3 + 25*x^2 + 20*x + 21
ciph=b'\xc9\xe2\xcdzo\xa1\xcc\xe1\x0e(\x98W\xd3\xb9\x85X\xa3!P\xab\x00\x1cR r\xb4\xb8\xed\x8f\x83\x15r'
K.<u>=GF((41,128),modulus=F1)
Kphi1=K(phi1)
from Crypto.Cipher import AES
from Crypto.Util.number import *
M=[list(Kphi1**i)for i in range(128)]
M=matrix(GF(41),M)
v=vector(GF(41),list(C))
s=list(v*M**-1)
for i in range(len(s)):
s[i]=Integer(s[i])&1
key = int(''.join(str(i) for i in s) , 2)
aes = AES.new(long_to_bytes(key), mode=AES.MODE_ECB)
msg = aes.decrypt((ciph))
print(msg)
#b'flag{eZ_iSOrmOr9h1sm_Y0u_kn0w}\x02\x02'

2x02 相关知识回顾

我们来回(xue)顾(xi)一下有限域同态相关方面的知识:

对于有限域 $\mathbb F_{p^n}$ ,当 $p,n$ 确定时,则所有的 $\mathbb F_{p^n}$ 均同构,无论其表达式为多少。假设 $K_1,K_2$ 的取模多项式分别为 $f,g$,则 $K_1\rightarrow K_2$ 的映射表达式可以通过 FiniteFieldHomomorphism_generic 确定同构映射的表达式 $\phi(x)$。也就是 $b(x)=\phi(a(x))$。上述关系也可以写成向量乘矩阵的形式,也就是 $\vec b=\vec aM$。其中 $M$ 为 $n\times n$ 矩阵,第 $i$ 行($i:0\sim n-1$)为 $(\phi(x))^n \pmod {g(x)}$ 的值。

当然,如果我们只是知道了 $g,\phi$ 的值,而不知道 $f$ 的值,我们也可以求出 $f$,其方法是构建 $(n+1)\times n$的矩阵,然后对该矩阵求 left_kernel 就OK。

需要注意的问题是:在RLWE中的 $b=as+e$ 的情况下,我们也可以构造矩阵,只不过这里构造的矩阵是 $x^ia(x)$,其中 $i$ 取值为 $0\sim n-1$。矩阵不同的原因,是因为其结构不同。多项式同态,是 $\phi(a(x))$,假如 $\phi=x^3+3x+1$,那么 $\phi(a(x))$ 就是 $a^3(x)+a(x)+1$,也就就是原式中所有的 $x$ 全换成 $a(x)$ 然后再取模。而RLWE中,其内在的关系是 $x^n=p(x)$ 的关系($p(x)$ 为取模多项式减去 $x^n$ 后整体取负的结果)。

3.[强网拟态2024]WaterMark

3x01 看题

一个其实看起来关系式不难,但不知道题目背景那真就没法做的题目。

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
from Crypto.Util.number import *
from Crypto.Cipher import AES
from hashlib import sha256
import socketserver
import signal
import os
import string
import random
from Crypto.PublicKey import RSA
from Crypto.Cipher import PKCS1_v1_5
from Crypto.Util.number import getPrime,getStrongPrime
from Crypto.Random import get_random_bytes
from sympy import nextprime

class Task(socketserver.BaseRequestHandler):
def _recvall(self):
BUFF_SIZE = 4096
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'> '):
self.send(prompt, newline=False)
return self._recvall()

def handle(self):
e=3
maxlens=4096
RSAparameter=None
signal.alarm(60)
watermark=os.urandom(512)

self.send(b"welcome to my proxy encryption program with watermarking")
messages=[]
while 1:
self.send(b"1 for free encrypt with time limit")
self.send(b"2 for check your watermarking ")
self.send(b"plz input function code")
try:
mode=int(self.recv())
except:
self.send(b"plz input right function code")
continue
if mode==1:
if maxlens<=0:
self.send(b"sorry, no free chance, try last time~")
continue
self.send(b"now choose your n bitlens")
self.send(b"1. 1024 2. 2048 3. 4096")
try:
mode=int(self.recv())
except:
self.send(b"plz input right function code")
continue
if mode==1:
newparameter=1024
if mode==2:
newparameter=2048
if mode==3:
newparameter=4096
if newparameter!= RSAparameter:
RSAparameter=newparameter
p=getStrongPrime(RSAparameter//2)
q=getStrongPrime(RSAparameter//2)
n=p*q
phi=(p-1)*(q-1)
self.send(b"your n is changed to")
self.send(hex(n).encode())
try:
rsa_key = RSA.construct((n, e))
public_key = rsa_key.publickey().export_key()
cipher = PKCS1_v1_5.new(RSA.import_key(public_key))
self.send(b"plz input your message with hex")
message=self.recv().decode()
#print(message,len(message))
messages.append(message)
message=watermark[:RSAparameter//16]+bytes.fromhex(message)
#print(message)

c = (cipher.encrypt(message)).hex().encode()
#print(c)
self.send(c)
e=nextprime(e)
maxlens-=RSAparameter
except:
self.send(b"wrong~ try again")
continue
elif mode==2:
if maxlens>0:
self.send(b"sorry, not even yet~")
continue
self.send(b"now give me your message without free chance")
e=65537
d=pow(e,-1,phi)
rsa_key = RSA.construct((n, e,d))
public_key = rsa_key.publickey().export_key()
cipher = PKCS1_v1_5.new(rsa_key)
cts=self.recv().decode()
cts=bytes.fromhex(cts)
try:
p = (cipher.decrypt(cts,b"bad cipertext"))
print(p)
except Exception as e:
print(e)
self.send(b"wrong~ try again")
continue
if p[:RSAparameter//16]!=watermark[:RSAparameter//16]:
self.send(b"not used the watermark!")
continue
if p[RSAparameter//16:].hex() in messages:
self.send(b"not cost!")
continue
f=open("./flag","rb")
flag=f.read()
f.close()
self.send(b"cong! your flag is "+flag)
self.request.close()

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

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


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

题目比较长,但第一眼看个大意内容还是相对清楚的:

1.题目提供不同的参数选择,如果前后两次参数不一样,那么模数会改变,如果参数一样,则模数不变,但加密机会是有限的,从题目来看至多 4 次。

2.加密指数从 $3$ 开始,每次取后一个素数作为下一次的加密指数。

3.题目使用RSA pkcs#1 v1.5填充,输入明文进行加密,明文本身会加入WaterMark后再进行RSA pkcs#1 v1.5 的填充和加密。

4.最后要构造出一个符合题目填充规则的密文,其解密后前缀为WaterMark,后面随意。

然后补充一下 RSApkcs的填充:填充内容至少为 $11$ 字节,格式为:

1
'\x00\x02'+padding+'\x00'+msg

其中 padding 是完全随机的内容,如果使用 $2048$ 位的密钥,那么最后的长度总为 $256$ 字节。也就是题目的加密结果是这样的

1
[00 02]+8字节完全随机内容 +[00]+[64/128/256字节的WaterMark]+[53/117/245字节的消息]

很自然地:想到用同一个消息加密两次,假设我们的消息为 $M$,那么就有:
$$
c_1=(X_1+M)^3,c_2=(X_2+M)^5
$$
如果 $M$ 全 $0$,那么有:
$$
c_1=(2^{k}X_1+2^{l}W)^3,c_2=(2^kX_2+2^lW)^5
$$
其中 $W$ 为WaterMark的值,$X_1,X_2$ 为随机字节。

然后呢?Coppersmith? $W=\sqrt[4]n$ 这放第二个式子很显然不太够的。

那如果消 $W$ 呢?直接做,貌似是不太够的。但考虑到 $X_1,X_2$ 虽然长度是 $11$ 字节,但实际上只有 $8$ 字节。因此可以取两次 $2048$ 的,就可以消元了:
$$
c_1=(2^kX+2^lW)^3,c_2=(2^k(X+\Delta X)+2^lW)
$$
在这里, $\Delta X$ 是小量,将 $c_1$ 看成一个整体,就有:
$$
c_1=t^3,c_2=(t+2^k\Delta X)^5
$$
但如何提取出 $X$ 来呢?那就要用到判别式与结式的功能了。

3x02 判别式与结式

首先定义什么是判别式:多项式 $f(x)=\sum_{i=0}^n a_ix^i$ 的判别式可以定义为:
$$
\Delta(f)=a_n^{2n-2}\prod_{i<j}(x_i-x_j)^2
$$
其中 $x_1\sim x_n$ 为 $f(x)=0$ 的根。特殊地,当 $n=2$ 时,判别式就是我们常见的 $a_1^2-4a_0a_2$。

如果两个多项式有相同的根,那么其西尔维斯特矩阵的行列式为 $0$。

西尔维斯特矩阵,就是将两个多项式(次数分别为 $n,m$) $f(x)$ 和 $g(x)$ 降幂分行顶格写,每次漂移一位,先写 $f(x)$ 再写 $g(x)$。举个例子:假设 $f(x)=x^3+2x^2+3x+4,g(x)=5x^2+6x+7$,那么 $f,g$ 构成的西尔维斯特矩阵就是,当然 $g$ 写在 $f$ 上面也是正确的。

5

在RSA中,结式的一个基本作用就是已知 $n,\phi$ 时,我们可以能够求出 $p,q$。假设 $n=pq=9991$ 和 $\phi=(p-1)(q-1)=9792$。

那么消元,有:
$$
pq-9991=0,p+q-200=0
$$
如果我们把 $p$ 看成常数,$q$ 看作自变量,那么设 $f=pq-9991,g=p+q-200$,构造西尔维斯特矩阵:

1
2
3
4
5
6
7
8
9
sage: R.<p,q>=PolynomialRing(ZZ)
sage: f=p*q-9991
sage: g=p+q-200
sage: M=f.sylvester_matrix(g)
sage: M
[ q -9991]
[ 1 q - 200]
sage: M.det()
q^2 - 200*q + 9991

然后解这个方程,就可以得到 $q=97$ 或 $q=103$ 了。

3x03 最终解题

有了上面的结论,那么这个题就比较简单了,我们可以直接手搓:发送 $117\times 2$ 个 $0$ 过去(也就是构造一条 $117$ 个 \x00 组成的消息,这样低位就全 $0$ 了),然后设
$$
f=c_1=t^3,g=c_2=(t+2^k\Delta X)^5
$$
然后构造西尔维斯特矩阵 $M$,求 $M$ 的行列式(带 $\Delta X$),然后对 $\Delta X$ 进行 small_roots 。拿到 $\Delta X$ 后,$f,g$ 就有公共部分 $t$ 了,求两个多项式的最大公约式,就能够得到 $t$。对 $t$ 除以 $256^{117}$ 后转 bytes,取末尾 $128$ 位就是 $W$ 了。拿到 $W$,随意构造一个就OK了。

因为懒了,所以直接手搓了,注意这个速度一定要快,因为题目限制了时间只有 $60$ 秒。

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
n=0xc867da2fc55897ec270a5027a183ae5670c1cd1634815df3bfef1085738a96f46b0c925f1966802fbf380e7f2b0f06a4a19ecd71ce406f0ef75c98c61a994d4a78b75cb71aebf61ee473db4182b56274f2827802969be318bdb913624105205144009d633d9ef7358ecc741dd97d258ebec76ac0e399e95a24b7eb7c8c108841e67672dba88ed1afe8500ec398b0c92d49311f832c91d4a4a57aec2357ebeaa9efef0edde7d491c60377650f8b27536e98d28ae8ac0a6f3caadb3f51884c001e7fa0a6888728f3a53a8baae27d91c96c39752d0cd28d1352e7f81e77817119e18a3e77468896708d4b06db40a26261196771bf22ad4501d12532990f49c39ad3
c1=0x1ff0c9bc55028e46be54a2c89d19eb109ee198e62d11794d863614d2e9584ffff34e4940982bfda7bd3301b893d3f40fff2a8ed61814e4e196856e8a6460c719d63780378700e3fa3fb393f19b647bd9f44965dcd42863a3287ffb4f51d5701241f081e57f9e78a386103570b0b9fbdad84067220d042dd1b77ff0e5977f9818d38046491e3cc65855001376a4a77f457b11ddf2a935a87f1e402b1e7619cdbfac4df3ff6a0b981a4b298ad8f3261f0740854ec835b94d19c901b030530bb6cb7970126960d439dbc1a224eadf960c4b9d4cd99972f36b5d876dce2b8bebadc2a8850abf38b62a6f14136520f186d69287969c2c3f4b7b1b9fc9ff4f3d0e417f
c2=0x3b572e7dfea67d4c0be1d55f5b7a4c97db6253c047306cf166e489a6938d6b773bb3e41abe1de2b76745ec57ea643dbe5a4d72ece9579e2ad5dadc6c2b0f0b0c774fe78502252b646c7593cd095131990a42091f0a0f2c1cc5f0afeffb1ab3665ec485bf7f19b7a755f4597232bedd61c027d608faf19c59ff7936543c24d86d0da95003c5cc1934698a9c763648e7bac9c0dd00202f07d25071ca6d89644c94dd0f82f55bf97bac23ee22759246e6b92c912bed0cc76726a946c76b15024ee2bea4076f0a058ab625ea05d4c12a41c0fe0da1d38e31d087d05476d5a5e9de1c7a25aeef487f78cc76d2389217bf1ebf6a27b886297bb7687cbd9ecb4e25841f
#先求结式
R.<msg1,detx>=PolynomialRing(Zmod(n))
f1=msg1**3-c1
f2=(msg1+detx*256**246)**5-c2
M=f2.sylvester_matrix(f1)
detM=det(M)
Rx.<detx>=PolynomialRing(Zmod(n))
detM=Rx(eval(str(detM).replace('^','**')))
dx=detM.monic().small_roots(X=256**8,epsilon=0.04)[0] #small_roots 拿dx
print(dx)

#求出dx后,求两个式子的最大公约式,就可以拿到msg1
Rm.<msg1>=PolynomialRing(Zmod(n))
f1=msg1**3-c1
f2=(msg1+dx*256**246)**5-c2
f1=f1.monic()
f2=f2.monic()
def Pgcd(fx1,fx2):
if(fx2==0):
return fx1
return Pgcd(fx2,fx1%fx2)
msg=list(-Pgcd(f1,f2).monic())[0]

W=msg>>(117*8)
print(W)
from Crypto.Util.number import *
mW=long_to_bytes(int(W))[-128:]
e=65537
msgA=bytes([0,2]+[0x31]*8+[0])+mW+bytes([0x31]*117)
print(hex(pow(bytes_to_long(msgA),e,n))[2:])
#bc62f79a13c74b6d5b2cd85238689d7d38b0a14fdc494597bfa8a8b674e83dd805b87f905e8c46c75768c0c138897a9056bd01327cb5caf49ad8c6ca8e0ecc4e2f413a8bf6dbc2faa3f5b4361801a9198bc50cbeaa9539d1c424117b07226d9bf17ed397c7258ebc5fe15ed0222f7df1ba1b1ec185c5a84021c1c8cf3dcbad83e0e59401f1e8e4d75330de3aa0fd95a931653e98798d151ce8e0a5953b1d910071e63d32bffbcf56916a5f52b40ff63e7f64fad323713d30fcca44ffb37239742439a95ae6046cb3024a001cd267c22f1c73fabe671468bd1c905ec2014ad738f8b1be61345c688661e80db23b47b4d2a1cffb38e07dee5a6a2c7e8752bfc37f

运行结果:

6

4.[西湖论剑2025] 已悟

4x01 看题

还是先看看题目:

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
from line_profiler import LineProfiler
from secret import get_key
from license import RicKV
import os

flag = os.getenv('DASFLAG')
smoke_key = get_key() # the key just printable, this function is to make all users key different


def login(password):
if len(password) != len(smoke_key):
return False
for i in range(len(password)):
if password[i] != smoke_key[i]:
return False
return True

def check_password(user_input,pro=False):
profiler = LineProfiler()
profiler.add_function(login)
profiler.enable_by_count()
is_valid = login(user_input)
profiler.disable_by_count()
x = profiler.get_stats().timings
hacker,hacker_pro = [],[]
for i in x:
for j in x[i]:
hacker.append((j[0],j[-1]))
hacker_pro.append(j)
return is_valid, hacker_pro if pro else hacker

banner = "🏞️ ⚔️ 2️⃣ 0️⃣ 2️⃣ 5️⃣ 👋 😊"

MEUN = """
1️⃣ ✨ 🔑 🚩
2️⃣ ✨ 🛍️ ⚡️💨5️⃣
3️⃣ ✨ ➡️ 🍐🍬
"""

if __name__ == "__main__":
print(banner)
pro = False
while True:
print(MEUN)
choice = int(input("> ")[0])
if choice == 3:
print("🏔️🐑❄️🐆🦦🦊🐹👩🏔️")
exit(0)
elif choice == 1:
password = input("🔑 > ").strip()
success,X = check_password(password,pro)
if success:
print("1️⃣ ❗5️⃣ ❗👴💨⚡️💨5️⃣")
print(f"🚩 {flag}")
exit(0)
else:
print(f"🤔 💨 {X} 💨")
elif choice == 2:
license_key = input("🔑 > ").strip()
license = input("📜 > ").strip()
rick = RicKV(license_key)
if rick.check(license):
pro = True
else:
print("👵🏻👵🏻🤰👶")

lisence.py

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
from functools import reduce
import base64
import random
import hashlib

Xor= lambda v: reduce(lambda res, x: res ^ x, v, 0)

class RicKV:
round = 15
S1 = [i for i in range(16)]
S2 = [i for i in range(16)]

def __init__(self, key):
key = hashlib.sha256(str(key).encode("utf-8")).digest()
random.seed(key)
self.roundkey = int(key.hex(), 16)
self.subkeys = [
[
((int(bin(self.roundkey)[2:].zfill(16 * (self.round+ 1))[16 * j + i]) & 1) - 1) & 0xf
for i in range(16)
]
for j in range(self.round + 1)
]
random.shuffle(self.S1)
random.shuffle(self.S2)

def add_round(self, s, k):
for i in range(4):
for j in range(4):
s[i*4+j] ^= k[i]

def sub(self,s):
for i in range(16):
index = self.S2[i]
temp = s[index]
s[i] = self.S1[temp]

def mix_1(self,s,r):
for i in range(16):
s[i] = s[i] ^ self.subkeys[i][r]

def mix_2(self,s,x):
for i in range(0,16,4):
x[i//4] = Xor(s[i:i + 4])

def flip(self, plaintext):
assert len(plaintext) == 8
S = [int(_, 16) for _ in list(plaintext.hex())]
X = [0 for _ in range(4)]
for r in range(self.round):
self.mix_1(S,r)
self.sub(S)
self.mix_2(S,X)
self.add_round(S,X)

S = [S[i] ^ self.subkeys[self.round][i] for i in range(16)]
return bytes.fromhex("".join("{:x}".format(_) for _ in S))

def check(self,liscense):
liscense= base64.b64decode(liscense)
assert len(liscense) % 8 == 0
l = b"\x00" * 8
for i in range(0,len(liscense),8):
l = bytes(d^j for d,j in zip(l,liscense[i:i+8]))
l = self.flip(l)
l = bytes(d^j for d,j in zip(l,liscense[i:i+8]))
return not any(l)

4x02 分析

最近Crypto题目怎么越来越抽象了,怎么代码里带emoji的越来越多,虽然不影响解题但这。。。。不好说

题目本质上有两个选项,一个是尝试输入Key解密,还有一个是通过Lisence升级为pro模式。在题目中的 check_password 中,执行 login 函数时用到了 LineProfiler,这是个用于输出调试信息的包。如果没有进入pro模式,那么最后会返回行号 $l$ 和执行时间 $t$,如果进入了pro模式,则会返回三个信息:行号 $l$,执行次数 $r$ 和执行时间 $t$。

既然题目都返回这些信息了,那么就必须回顾一下 login 函数:

1
2
3
4
5
6
7
def login(password):#10
if len(password) != len(smoke_key):#11
return False#12
for i in range(len(password)):#13
if password[i] != smoke_key[i]:#14
return False#15
return True#16

可以发现,login 函数在比较两个字符串是否相等时:先比较了字符串长度是否相等,然后是一个 for 循环进行的逐位比较而非 == 直接比较。加上前面返回的状态信息,因此可以考虑对状态进行爆破攻击。

然而,没有进入 pro 状态时,只会返回行号和时间 (单位为$10^{-6}s$)。在 login 函数中,如果长度不匹配,则会执行 11和12行的内容。如果行号匹配了,那么会执行11,13,14,15行内容。因此可以在没有进入pro状态时,根据返回状态,获取Key的长度(最终为24位)。但如果想要爆破,还要考虑每一行的执行时间,但由于机器波动,本地测试时,一般第一次时间为 0.9到1.6毫秒之间,但也有可能偶尔超过2毫秒,且超过2毫秒的概率不低,并且也不一定是正确的key。因此只判断时间是不可行的,必须进入pro模式,得到每一行的执行次数。。。

因此,进入pro模式,就需要通过 lisencecheck 函数。这里存在一个base64解码。我们先来看看题解的做法:

4.想要升级到pro版本,接下来就需要分析license.py了。在RicKV类在初始华的时候会接受一个用户输入的种子用来初始化S盒,同时check函数会接受一个license,如果满足在一些列运算之后结果全为\x00字节则返回True

5.分析加密部分可以发现有很多很奇怪的地方,比如subkey生成全是由0和f组成的数组,那么在flip 函数中,如果输入的字节是在模16下是互补的,抛开sub函数不谈,其实就是在一直不停地在取反或者保持不变。

6.那么接下来的就是控制sub函数的返回值了,这个返回值和S1数组有关,如果输入的种子使得S1种存在$S[i]=j,S[j]=i且 i+j=15$ 那么只需要控制输入内容每个字都为$i$或$j$即可,那么它们在进行异或运算之后只有可能成为$0$ 或 $15$。

7.在check的时候会每8位为一组和前一轮进行异或并flip后再异或,那么这里对两组16字节的license进行爆破即可
题解中还给了个代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
import random
import hashlib
for key in range(1,11111111111):
S1 = [i for i in range(16)]
x = hashlib.sha256(str(key).encode("utf-8")).digest()
random.seed(x)
random.shuffle(S1)
for i in range(16):
id = S1[i]
tmp = S1.index(id)
if tmp == S1[id] and S1[id]+id == 15:
print(S1[id],id)
print(key)
print(S1)
exit(0)

结果我发现了base64的漏洞:如果给出不可见字符,那么base64会跳过这些字符,并且题目也没有进行检查

1
2
3
>>> from base64 import *
>>> b64decode(bytes([0]*66))
b''

那就直接给一堆不可见字符,最后 lisence 的长度是 $0$,完美解决。

1
2
3
D=RicKV(1)
print(D.check(bytes([0]*666)))
#True

那最后就是根据服务器返回的状态,爆破Key的长度和每个Key值了。

4x03 exp

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
41
42
43
44
45
46
47
48
from pwn import *
from string import printable
context.log_level='debug'
table=printable[:-6].encode()
sh=remote('node1.anna.nssctf.cn',28317)
def sendsth(msgb):
sh.recvuntil(b'>')
sh.sendline(msgb)
return len(msgb)

sendsth(b'2')
sendsth(b'1')
sendsth(bytes([0]*0x535))


for i in range(98):
sendsth(b'1')
sendsth(bytes([99]*i))
recv=eval((sh.recvline().strip())[9:-4])
print(recv)
if(recv[-1][0]!=12):
break
n=i
print(n)
Ans=[999]*n
for T in range(n):
sendarr=Ans[:T]+(n-T)*[41]
for i in table:
sendarr[T]=i
sendsth(b'1')
#print(sendarr)
sendsth(bytes(sendarr))
res=(sh.recvline().strip())[9:-5]
if(T==n-1):
if(res[0] not in printable.encode()):
Ans[T]=i
print(sh.recvall(timeout=7))
break
res=eval(res)
#print(res)
if(res[1][1]==T+2):
Ans[T]=i
break
#print(Ans)
print(bytes(Ans[:T+1]))

#print(sh.recvall(timeout=7))
#sh.interactive()

运行结果:

1

9.Some situation

3 月以来一些事情,自己感到了冲击,于是 17 号晚上有了这个来自内心的灵魂拷问:

打CTF第 3 年,当年就是玩玩,现在可能真得思考思考人生。。。了吧。。。今年已经都 23 岁了,真的不是 19 岁(大一下)有大把时间自己探索的日子了。。。

几个密码佬都是读博的,我感觉自己读博概率不大,其实也不太想读,后面学密码的同时,还是带着学点实战的吧,比如应急响应(转web/pwn已经来不及了)。。。。不然密码手在线下真的就是坐牢。。。。线下 0 输出,自己都已经快过不去了呜呜呜。。。那天逛的时候,队友们聊二进制、渗透、HVV那些事,我在旁边一句话都不敢说,真别饿s在学Crypto的路上。

只能说以后应该狠狠学习应急响应 ——By 某二进制队友

和22级学弟的对话(备注是实名,所以名字P掉了),看来他快要跑路了,没记错的话,19级学长最后搞AI去了,21级学弟也跑路了。。。我这种,哎,先稳住吧,然后带着学点应急响应。最近文化课也快听不懂了(可证明安全理论),难过+2。

9


25Mar2
http://example.com/2025/03/31/25Mar2/
作者
huangx607087
发布于
2025年3月31日
许可协议