ciscn2025wp1

CISCN2025 Crypto Writeup

0.Introduction

最后15分钟，一个题突然有了思路！然后框框做。剩三分钟的时候出了结果。

然后，发现flag有一位不对，但时间不够了，连交16发，过了。

2

1.rasnd

签到题

1x01 第一问

第一问是两个 $xp+yq$ 的方程组，其中两个 $x$ 均为 $11$ bit，而 $y$ 比较大。先把干扰项0x114 和 0x514 加上去那个再考虑问题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def crypto1():
    p = getPrime(1024)
    q = getPrime(1024)
    n = p * q
    e = 0x10001
    x1=randint(0,2**11)
    y1=randint(0,2**114)
    x2=randint(0,2**11)
    y2=randint(0,2**514)
    hint1=x1*p+y1*q-0x114
    hint2=x2*p+y2*q-0x514
    c = pow(bytes_to_long(flag1), e, n)
    print(n)
    print(c)
    print(hint1)
    print(hint2)

设 $h_1=ap+uq,h_2=bp+vq$，这里 $a,b,u,v$ 分别代表原题中的 $x_1,x_2,y_1,y_2$。因此，有 $h_1\equiv ap \pmod q$ 和 $h_2 \equiv bp \pmod q$。

那么既然这样，就可以得到：
$$
bh_1-ah_2\equiv 0\pmod q
$$
也就是只需要计算 $bh_1-ah_2$ 对 $n$ 取模的值，然后求这个值与 $n$ 的最大公约数就行。有因为这边 $a,b$ 比较小，因此直接爆破就OK了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
n=19248664689530123393339750857691758159828998141083113433318210575707422181489994495258568353664585884974589784326344875616422623723134787567523135053918656358818197978064530098405128694160259578347511022497921607363550797990918049734722532831572612769156259971404777247374524932064252338601246476354828069402346646655148066484265861458411755063666748004293786860672431085761001135092249308802515486462877548621098190062391716183875115012331375463955835485096757222226810547395731394800944696108335750671156420296030042196532586476376809261086236384076130490521533794626278538191680511190432034822246405284567044535737
c=16453581113263628465402092791273671627253499425447855398153502324952305815396643914684535248142751183677820566647078077684635808968023794878415787181748005037265484795254931463576254805033054376345359635944723694122534587670849618937642199417698103245704677524885526618274177589192207268821472812014491228744087019681084825136309747168220038888386631991014234901274101176732935273456684918926783662195903675201338561673573750363288113393253956526505273390732848815303616961944660066711735531801399259938551249259161863955642767344503658923718752086167261196386024011356237085630947227087647937956059125524152447531046
h1=1142155587999054452936236690724846373317633853126793089144726626669657375885752630969112453860698940164376661793846305685672149286102455708196921631520363911372723899902966372266397544814322619319044169128946954204738673025539895226335296999362788265718140587423185015428744709814309161721272465730611687942859087016764569757722320187632936089
h2=6805681534385851179775478266005282964511861953948523771351357282112956013491219260195830638806682420098299511263106560638896904299407473460758909050042070258290378172452854156007202430941147523420211671963915796599471635868375761210639654134882971355856028137677035546043236438576341615763406191904837152865917403676918731794126663654959372843668491934375801326063783580396546640850799544632110824221535250489490336046772019863423668554252214257321844182545387418
h1+=0x114
h2+=0x514
from Crypto.Util.number import *
from tqdm import *
found=0
for a in trange(2**11):
    if(found):
        break
    for b in range(2**11):
        q = GCD(a * h1 - b * h2, n)
        if q != 1 and q < n:
            found=1
            print(q, n)
            break
#q=173412142663396382437110320378676957702956603225161519151255211880350143773589704812177489820788273353229406821960488375289526428322543015221422549411580243762548438732318695065025392633248468667975976279310511629585619218884427826162013207814208144971619806977124558725541302263038307640311180609750589387139

然后就是正常的解密了

1
2
3
4
5
q=173412142663396382437110320378676957702956603225161519151255211880350143773589704812177489820788273353229406821960488375289526428322543015221422549411580243762548438732318695065025392633248468667975976279310511629585619218884427826162013207814208144971619806977124558725541302263038307640311180609750589387139 
p=n//q
d=inverse(0x10001,(p-1)*(q-1))
long_to_bytes(pow(c,d,n))
#flag{c4a8755f-e3ee-

1x02 第二问

1
2
3
4
5
6
7
8
9
10
def crypto2():
    p = getPrime(1024)
    q = getPrime(1024)
    n = p * q
    e = 0x10001
    hint = pow(514*p - 114*q, n - p - q, n)
    c = pow(bytes_to_long(flag2),e,n)
    print(n)
    print(c)
    print(hint)

注意到 $\varphi(n)=(p-1)(q-1)=n-p-q+1$ 以及欧拉定理 $a^{\varphi(n)}\equiv 1 \pmod n$。而这边少了一个 $+1$。

因此，题目中的hint其实是 $514p-114q$ 的逆元，即 $h\equiv \dfrac{1}{514p-114q}$。因此求逆之后，sage可以一把梭。

1
2
3
4
5
6
7
8
n=18469971394567700555887545287738030390998670849233400121622608332076900381636174405583926146207911760514526165345411119372695640879373233807010796828189247487881583450802018570094118969936556808837735331742986354386573070679971526372651273191418416553892526494787200424504794508644408739520632218791263187635391385857246002374949380609580488294584115876165520379716472501738721881865651392018210313227950727959918876612379099361481409818981815277337620592265054900554332804125089828492735185173430695836219401530601136278511063507531410018405775105282450190556279513289553601110429728232438726893960214994464326642501
c=8384245358517209206638591536430089936750872075931157496159484493219224715458106957074197415753212306103270383975531507561845531202902990237136664716166981869184244988309170499142927622452946928886208659190260182148074631735133891762719723325840541605207148731809561384567275222023097150960503034472178349354131047589997261802023668033259892426337260551376445994419408154784104500004806681716393027194354460841110067278287117340780462399365432976004668936950623590082446226194389401021047094109734198271887111013770971020353155639875222275579921784263393549902894072613204186386891381226594909524653335513046000779913
h=10613527688726423579754152693752973064592747678519716670281951817557565124963478644451998246232654577070335083234391448787101641842881480848146247384045578217961864919867766100286869024387066802728323491078123363075076998082908591788534532074882105038688917723726272300258577874995515845057668640104924642429913694188593719906989625368537851337574010386820985695951602020986744321047364238143041381580204581757698773733909442002829918853274102631318801737704555525749901970771051179058453501567637677171608531708913198318266934162394058243794913193446935461537732717610020726853015268231704202587137995580373031429184
from Crypto.Util.number import *
h11=inverse(h,n)
var('p q')
solve([p * q == n, 514 * p - 114 * q == h11],(p, q))
#[[p == 124374482713744254421196146561721734370797689508289476755605840389633983382899202977355204274399588551326418117247498420139367095759757770970096113272582067707802898348673920735904464508743418701977275366218690118662098779221336992548858532837641630846364672805473992679529496368359318673509345992314976898271, q == 148502900205643540040835714929977680824759735566050594322503799979640528741251944541387833043478598810328443666188068011083556939321771693171145515982180549200450564885451040239556674788106253037174232984849335478469598925152366683693097813645050646728552643163657439369582006776770981653061881169323572439131], [p == (-8464665311721681782327635751008727807011304927264883876382716598839510138251360838859106483478280132188721288972719876631762745541340986510755294410984291304425682198470709293654730462922056423118931280136412122272767138733684900970506575377767886863527500660328474044066174386275945954224527226651443629030467/257), q == (-31964242057432273386247409666362485733295006203630395526190700980135933729405095165180287498520694257690889456132607093975817343610257747139314701111053591400905344875609197629127447378747058606408159769118203360496159386259883607085056642939273899127515720911006816118639080566668344899091901920024949062855647/57)]]

然后复制第一组解就行了

1
2
3
4
5
6
pp=124374482713744254421196146561721734370797689508289476755605840389633983382899202977355204274399588551326418117247498420139367095759757770970096113272582067707802898348673920735904464508743418701977275366218690118662098779221336992548858532837641630846364672805473992679529496368359318673509345992314976898271
qq=148502900205643540040835714929977680824759735566050594322503799979640528741251944541387833043478598810328443666188068011083556939321771693171145515982180549200450564885451040239556674788106253037174232984849335478469598925152366683693097813645050646728552643163657439369582006776770981653061881169323572439131
d=inverse(0x10001,(pp-1)*(qq-1))

long_to_bytes(pow(c,d,n))
#4451-9804-56becf5a4151}

最终flag：flag{c4a8755f-e3ee-4451-9804-56becf5a4151}

2.fffffhash

一眼看到这个，发现和SUSCTF那个题竟然差不多，假设我们要求的目标值为 $G$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
import os
from Crypto.Util.number import *
def giaogiao(hex_string):
        base_num = 0x6c62272e07bb014262b821756295c58d
        x = 0x0000000001000000000000000000013b
        MOD = 2**128
        for i in hex_string:
                base_num = (base_num * x) & (MOD - 1) 
                base_num ^= i
        return base_num
giao=201431453607244229943761366749810895688
print("1geiwoligiaogiao")
hex_string = int(input(),16)
s = long_to_bytes(hex_string)

if giaogiao(s) == giao:
        print(os.getenv('FLAG'))
else:
        print("error")

SUSCTF中写的思路：

由于 $m_i$ 很小，因此 $h \oplus m_i$ 可以写成 $h+\delta_i$，其中 $\delta_i$ 也很小。把异或换加，就可以发现，最后 $H$ 可以写成一个关于 $t$ 的多项式，其中 $\delta_i $ 很小 。

仍然以四个值为例：

那个题是：
$$
H(m)\equiv \delta_1A^4+\delta_2A^3+\delta_3A^2+\delta_4A\pmod q
$$
但这个题带初值，表达式变成了：
$$
H(m)\equiv BA^4+\delta_1A^3+\delta_2A^2+\delta_3A+\delta_4\pmod q
$$
那就微调一下矩阵（$K=2^{2600}$）：

4

但这边的 $D$ 就不是目标值了 $G$ 了。因为这边带有初值。这里 $D$ 的值应该是：
$$
D=G-BA^n
$$
其中 $n$ 是待构造字符串的位数。

因此初步构造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
49
50
51
52
53
#sage
import os
from Crypto.Util.number import *
def H(hex_string):
    base_num = 0x6c62272e07bb014262b821756295c58d
    x = 0x0000000001000000000000000000013b
    MOD = 2**128
    for i in hex_string:
        base_num = (base_num * x) & (MOD - 1) 
        base_num ^^= i
    return base_num
q=2**128
n=96
D=201431453607244229943761366749810895688-(0x6c62272e07bb014262b821756295c58d*pow(0x0000000001000000000000000000013b,n,q)%q)
D=D%q
t=0x0000000001000000000000000000013b

def getVec(mod,g,targ):
    K=2**2600
    M=[[0 for _ in range(n+3)] for __ in range(n+2)]
    for i in range(n+2):
        M[i][i]=1
    for i in range(n):
        M[i][n+2]=Integer(pow(g,n-i-1,mod))*K
    M[n][n+2]=-targ*K
    M[n+1][n+2]=mod*K
    M=matrix(ZZ,M)
    return M.LLL()
A=getVec(q,t,D)
vv=A[0]
for i in range(n+2):
    if(A[i][-3]==1):
        vv=A[i]
        break
R=vv if vv[0]>=0 else -vv
s=[]
b=0x6c62272e07bb014262b821756295c58d
h=b
for i in range(n):
    h=(t*h)%q
    s.append(h^^(h+R[i]))
    h+=R[i]
print(s)
#[0, 6, 28, 0, 6, 31, 3, 2, 6, 3, 59, 6, 2, 60, 29, 0, 3, 2, 7, 28, 1, 5, 0, 127, 1, 0, 1, 7, 1, 2, 3, 2, 7, 5, 0, 4, 2, 1, 31, 13, 1, 3, 2, 3, 124, 5, 5, 1, 2, 31, 0, 31, 1, 0, 0, 7, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
print(H(bytes(s)))
#201431453607244229943761366749810895688
print(201431453607244229943761366749810895688)
#201431453607244229943761366749810895688
ans=''
for i in s:
    ans+='{:02x}'.format(i)
print(ans)
#00061c00061f030206033b06023c1d000302071c0105007f01000107010203020705000402011f0d010302037c050501021f001f0100000701000000000000000000000000000000000000000000000000000000000000000000000000000000

结果发现交上去，竟然不对。因为原题用的是long_to_bytes，因此如果字符串以 0x00 开头，那么高位就被省略掉了。

然后换了几个 $n$，好像也不太行的样子。主要试了 $128,160$，然后才试到了 $96$。太低的话，$64$ 会出现超过 $255$ 的数字，也不行。

赛后补充：经测试，好像 $66\sim80$ 出的概率挺高的

1
2
3
4
5
6
7
8
n=66
ff0407010e1d03000e0f03020f00013b0603060f01050002010301000003010103027f0d000f0105020000060307023e030101010701000300030000000000000f00
n=69
fe070100060001000606033d0f0300fd000103000f04070502010f0305000506030001030e06ff0c0200010100000102020001010103010001000000000000000000000000
n=72
ff00000300067d0f0a04070000010201031d1f02040101030f01011c0201010c0103011e1e0d02031f0102000f020203001f07010f01000300030000000000000000000000000001
n=80
fc02017b010307010200070201020007061e1e0600020002000304190100030005060e00000103000602020200050303030100007f010000070100000000000000000000000000000000000000000000

但比赛中我在那种情况下，加之心态比较急，可没那么想法去测试。不过我发现：

1
H(b'1')=279349696642264188298419300151331525710

那就在前面强行加一个字符 1 ，然后改变初值就行了。

最终WP：

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 os
from Crypto.Util.number import *
def CH(hex_string): #原始的hash函数
    base_num = 0x6c62272e07bb014262b821756295c58d
    x = 0x0000000001000000000000000000013b
    MOD = 2**128
    for i in hex_string:
        base_num = (base_num * x) & (MOD - 1) 
        base_num ^^= i
    return base_num
def H(hex_string): #以字符1开头的hash函数
    base_num = 279349696642264188298419300151331525710
    x = 0x0000000001000000000000000000013b
    MOD = 2**128
    for i in hex_string:
        base_num = (base_num * x) & (MOD - 1) 
        base_num ^^= i
    return base_num
q=2**128
n=96
D=201431453607244229943761366749810895688-(279349696642264188298419300151331525710*pow(0x0000000001000000000000000000013b,n,q)%q)
D=D%q
t=0x0000000001000000000000000000013b

def getVec(mod,g,targ):
    K=2**2600
    M=[[0 for _ in range(n+3)] for __ in range(n+2)]
    for i in range(n+2):
        M[i][i]=1
    for i in range(n):
        M[i][n+2]=Integer(pow(g,n-i-1,mod))*K
    M[n][n+2]=-targ*K
    M[n+1][n+2]=mod*K
    M=matrix(ZZ,M)
    return M.LLL()
A=getVec(q,t,D)
vv=A[0]
for i in range(n+2):
    if(A[i][-3]==1):
        vv=A[i]
        break
R=vv if vv[0]>=0 else -vv
s=[]
b=279349696642264188298419300151331525710
h=b
for i in range(n):
    h=(t*h)%q
    s.append(h^^(h+R[i]))
    h+=R[i]
print(s)
#[1, 0, 7, 7, 14, 2, 1, 7, 5, 2, 1, 5, 6, 5, 0, 1, 0, 0, 0, 3, 7, 0, 4, 13, 15, 14, 7, 13, 3, 0, 2, 2, 3, 4, 0, 10, 12, 5, 2, 2, 3, 3, 1, 7, 60, 1, 0, 0, 0, 3, 1, 1, 0, 0, 1, 0, 63, 1, 7, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
print(CH(bytes([0x31]+s)))
#201431453607244229943761366749810895688
print(201431453607244229943761366749810895688)
#201431453607244229943761366749810895688
bytes([0x31]+s).hex()
#31010007070e0201070502010506050001000000030700040d0f0e070d030002020304000a0c050202030301073c01000000030101000001003f010701000000000000000000000000000000000000000000000000000000000000000000000000

5

flag:flag{d57bee7d-c49a-49f8-86a2-b7fd36889d00}

3.LWEWL

3x01 第一问

第一问给了 612 组 $b=\vec a\cdot \vec s+257 e$，没有取模。然后加密方式是 $b\equiv \vec a\cdot \vec s+257 e+m \pmod {1048583}$，有取模。

因为第一问的LWE是 $b=\vec a\cdot \vec s+257 e$。因此两边模 $257$ ，误差就没有了。可以直接解出向量 $\vec s$ 的每个分量模 $257$ 的值 。

1
2
3
4
5
6
7
8
9
10
LWEPK=load('lwe_public_key')
LWEC=load('lwe_ciphertext')
pka,pkb=LWEPK
ca,cb=LWEC
mtxpA=Matrix(GF(257),pka[:512])
vecpb=vector(GF(257),pkb[:512])
vecs257=(mtxpA**-1)*vecpb
for i in range(513,612):
    assert vector(GF(257),pka[i])*vecs257==pkb[i]%257
#assert 通过。

注意到没有取模操作，并且给了那么多数据。盲猜存在私钥 $\vec s$ 泄露。

求出了 $\vec s$ 每个分量模 $257$ 的准确值之后，那就可以把 $\vec s$ 分成 $\vec s=257\vec s_H+\vec s_L$。其中 $\vec s_L$ 是我们刚求出来的 $\vec s$ 每个分量模 $257$ 的结果。

那么就有 $b=\vec a\cdot \vec s_L+257\vec a\cdot\vec s_H+257 e$。整理一下，就有 $\dfrac{b-\vec a\cdot \vec s_L}{257}=\vec a \cdot \vec s_H +e$。这里 $e$ 的的绝对值不超过 $15$， $\vec s_H$ 的每个分量上限值略低于 $4096$ （大概是四千零八十几）。尝试强行求解。

1
2
3
4
5
pkbr=[(pkb[i]-vector(ZZ,pka[i])*vecs257.change_ring(ZZ))//257 for i in range(612)]
RF1K=RealField(1000)
A=matrix(RF1K,pka[:512])
vrb=vector(RF1K,pkbr[:512])
f=A.solve_right(vrb)

测一下解出来的值，发现小数部分不是 $0000$ 就是 $9999$，并且每个量的大小符合预期（上限四千零八十几，均匀分布的话，平均值应该是两千多一点），看来解的挺成功的。果然有思路了感觉可以，还是要敢做才敢赢。

6

1
2
print(sum(f)/len(f))
#2009.96874997776160337770580881274982166822040808118839110467659132914509888108790192401929747758265873815462669464429511425547300791249092612758307303074944364972205465412080525094462257069285726770549633697572244153728953621331352055730480085919509414632437397365432465233683065741178107243748044155

那就对 $\vec s_H$ 四舍五入，直接出了！

1
2
3
4
5
6
7
8
9
10
11
sh=[i.round()for i in f]
s=[sh[i]*257+Integer(vecs257[i])for i in range(512)]
pp=[]
q=1048583
for i in range(18):
    pp.append(vector(GF(q),ca[i])*vector(GF(q),s))
s=''
for i in range(18):
    s+=chr((int(cb[i])%257-int(pp[i])%257)%257)
s
#a3bc5491-fa53-4}47

但，有一位不对。。。原因见 **3x04 **部分。

3x02 第二问

第二问是一个RLWE问题。没有给什么其他的信息，flag应该是 18 位，盲猜只包括 0123456789abcdef- 这 17 个字符。

先导入测一下吧：

1
2
3
4
5
6
7
8
9
10
CRLWE=load('rlwe_ciphertext')
a, b, f, p=CRLWE
print(a)
#长度为 64  的list
print(b)
#63次多项式
print(f)
#64次多项式
print(p)
#294258122831803380997956804968164525729

这边，公共参数是 $a(x)$，密文是 $b(x)=a(x)s(x)+e(x)$，不可约多项式是 $f(x)$，模数 $p$ 为 $128$ 位素数。其中 $s(x)$ 的系数是 flag后半部分。而 $e(x)$ 的每个分量的绝对值不超过 $5$。然后题目就没给其他的东西了。

既然大数字下面又有小数字，考虑 LLL求解。但怎样构建LLL呢？

记符号 $f_i$ 为 $f(x)$ 中 $x^{i}$ 的系数。

因此有等式（注意下标字母，这个 $b_r$ 表示对于指定的一个 $b$ 值）：
$$
b_r=\sum_{i=0}^{63} (x^ia)_r \cdot s_i+e_r-k_rp
$$
注意那个 $xa$ 是连在一起取下标的的。有人要说：那超过 $64$ 了怎么办？不是有 $f(x)$ 取模吗？因此这个 $xa$ 也是对 $f(x)$ 取模的结果。

去同余，也就是
$$
b_r=\sum_{i=0}^{63} (x^ia)_r \cdot s_i+e_r-k_rp
$$
这样就可以构造LLL了。还是以三个为例：

7

对这个矩阵LLL就行。(发现 quotient 还是比 GF(p**n,modulus=list(f)) 好用，因为 quotient 中的元素可以用 list() 去提取)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
OP.<x>=PolynomialRing(GF(p))
R.<x>=OP.quotient(OP(f))
c=[list(R(a)*(x**i)) for i in range(19)]
c=matrix(c)
M=block_matrix(ZZ,
    [[p*identity_matrix(64),zero_matrix(64,19)],
    [c.change_ring(ZZ),identity_matrix(19)],
    [matrix(ZZ,list(b)),matrix(ZZ,[0]*18+[1])]])
M3L=M.LLL()
res=None
for vv in M3L:
    if(abs(vv[-1])==1):
        res=vv
        break
print(res)
#(2, -2, -2, -2, -2, -1, -5, -3, 0, -3, -3, -1, 3, 0, -4, -4, -2, 5, 1, 5, -5, 4, -5, 4, 3, -1, -2, 4, 5, -3, -1, 2, 4, -5, -4, -5, -2, -5, 3, 1, 4, 3, -1, -1, 2, 5, -4, 4, -2, -2, -1, -4, -4, -4, 2, -2, -1, -2, -1, -1, 3, 3, -1, -5, -45, -56, -56, -49, -57, -45, -56, -53, -54, -97, -56, -102, -101, -53, -97, -100, -97, -48, 1)

最后结果可见：前面应该是 $-e$ ，中间是 $-s$，最后一个 $1$ 为哨兵。

至于为什么是 $19$，因为我开始用了 $18$，发现最后一位是 $-45$ 很明显不对，我还要在最后放个哨兵 $1$，不够放了，所以应该是 $19$，最后一位是 $-48$ ，取反后就是字符 0。

那就直接提取吧

1
2
3
C=-vector([-45, -56, -56, -49, -57, -45, -56, -53, -54, -97, -56, -102, -101, -53, -97, -100, -97, -48])
bytes(list(C))
#-8819-856a8fe5ada0

3x03 考试到16:56的情况

两部分拼接：

8

那中间还有一位不对呢！此时已经是 16:56了。来不及细想了，直接三分钟连交 16 次，从 0 试到了 f。结果最后一次出了（脸真黑）

flag{a3bc5491-fa53-4f47-8819-856a8fe5ada0}

16:59:03交了flag，400分到手，中间被提示两次提交过于频繁，真刺激啊，还好没有限制CTF的flag提交次数，让我这个水平并不太行的cryptoer也偷鸡成功了。

（不过据说这个题有原题？看来还要多练啊，但期末考试要到了）

9

3x04 (赛后思考)为啥那一位解不出来

再测一下：

1
2
3
4
5
6
7
8
pp=[]
q=1048583
for i in range(18):
    pp.append(vector(GF(q),ca[i])*vector(GF(q),s))
print(pp)
print(cb)
#[463996, 243852, 639733, 817669, 561259, 349164, 74393, 545321, 988914, 632572, 726690, 568995, 560062, 709951, 861692, 24980, 278164, 701247]
#[407039, 330769, 564787, 841669, 573134, 356926, 65198, 474952, 1006178, 600549, 693377, 546175, 551889, 660909, 925737, 980117, 319336, 682798]

发现 pp 倒数第三个分量是 $24980$，而 cb 倒数第三个分量是 $980117$。计算一下 $\Z(\vec{pp})-\Z(\vec{cb})$，每个分量结果如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
for i in range(18):
    print(ZZ(pp[i])-ZZ(cb[i]))
"""
56957
-86917
74946
-24000
-11875
-7762
9195
70369
-17264
32023
33313
22820
8173
49042
-64045
-955137
-41172
18449
"""

可以发现，其他的值都不超过十万，因为误差本身就很小，在这边扩展一次，也不会带来特别大的误差。而倒数第三个分量差值竟然达到了 $-955137$，说明 cb 到 pp 加上误差后，刚好越过了取模线，导致结果对 $1048583$ 取模了一次。

因为 $-1048583 \equiv -23 \pmod {257}$，因此倒数第三位刚好多了 $23$。而 $125-23=102$，恰好对应 f，原因就找到了。。。

所以加个特判，这样就对了：

1
2
3
4
5
6
7
8
s=''
for i in range(18):
    chi=ZZ(cb[i])-ZZ(pp[i])
    if(abs(chi)>500000):
        chi=sgn(chi)*(chi-q)
    s+=chr(chi%257)
print(s)
#a3bc5491-fa53-4f47

3x05 oc师傅的wp

16日晚上，oc师傅告诉我这个题可以直接最小二乘法，因为samples*error_bound<mod。

并且代码看着更简洁，他没有考虑高低位的问题。当然，因为他取的是 $(-p/2,p/2)$ 的范围，而不是 $[0,p-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
from Crypto.Util.number import *
import numpy as np

lwe_pubkey1,lwe_pubkey2=load("lwe_public_key")
lwe_cipher1,lwe_cipher2=load("lwe_ciphertext")
rlwe_ciphertext=load("rlwe_ciphertext")

lwe_dimension = 2**9
lwe_num_samples = 2**9 + 2**6 + 2**5 + 2**2
lwe_plaintext_modulus = next_prime(256)
lwe_ciphertext_modulus = next_prime(1048576)
rlwe_dim = 64
a, b, f, rlwe_modulus = rlwe_ciphertext

lwe_secret_key=np.linalg.lstsq(np.array(lwe_pubkey1),np.array(lwe_pubkey2))[0].round().astype(int)

flag='flag{'
for tmp1, tmp2 in zip(lwe_cipher1, lwe_cipher2):
    t=int(tmp2-tmp1*vector(lwe_secret_key))
    if t>lwe_ciphertext_modulus//2:
        t+=((lwe_ciphertext_modulus-t)//lwe_plaintext_modulus+1)*lwe_plaintext_modulus-lwe_ciphertext_modulus
    else:
        t-=t//lwe_plaintext_modulus*lwe_plaintext_modulus
    flag+=chr(t)

m=len(lwe_cipher2)+1
P.<x> = PolynomialRing(Zmod(rlwe_modulus))
PR = P.quo(f)
M=block_matrix(ZZ,[[matrix(b.list()),zero_matrix(1,m),matrix([100])],
                 [PR(a).matrix()[:m],identity_matrix(m),zero_matrix(m,1)],
                 [rlwe_modulus*identity_matrix(rlwe_dim),zero_matrix(rlwe_dim,m),zero_matrix(rlwe_dim,1)]])
L=M.LLL()
flag+=bytes(L[0][rlwe_dim:rlwe_dim+m]).rstrip(b'\x00').decode()+'}'
print(flag)

4.[待补题]babypqc

后面看情况补充，据说有非预期，但我也很好奇预期解是啥，这个题好像是一个LWE签名，自己对CTF中的LWE还不太会呢。。。咋感觉现在CTF题目越来越奇怪了？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
🦌 2024/12/15 21:11:04
对的

🦌 2024/12/15 21:11:09
我复现了一些

🦌 2024/12/15 21:11:16
m随便传

🦌 2024/12/15 21:11:22
signatures传[]

🦌 2024/12/15 21:11:29
会使得answers=0

🦌 2024/12/15 21:11:39
而num有1/16的概率为0

🦌 2024/12/15 21:11:43
这个就一直nc刷就好了

9. 总结

不知不觉已经3个月了，感觉自己这3个月还是学了挺多的，手感恢复了。靠着学长们带我，打了些比赛，收获了不少。

第一次在比赛中做出了 个位数 解的题目，记录一下。

队里的学长们还是tql，能把我这个不太行的ctfer带动。但后面也得靠自己发力了，争取能和学长们一样成功吧。

CTFSeason4
#WriteUp
ciscn2025wp1
http://example.com/2024/12/16/ciscn2025wp1/
作者
huangx607087
发布于
2024年12月16日
许可协议