糖醋小鸡块的blog
0%

2023-NBCTF-wp-crypto

发表于 分类于 Valine：

由于一些机缘巧合，周日早晨突然知道有这个比赛，兴趣来了就去打了打，最后两道分组密码代码较长就没有看。

Caesar Salads

32+32=64

上面两个题，一个凯撒，一个base64，没有什么要说。



Rivest Shamir forgot Adleman

题目描述：

1
Exponents took too long. I decided to use an alternative. It won't about the same right? https://en.wikipedia.org/wiki/RSA(cryptosystem)

题目：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
from Crypto.Util.number import *

p = getPrime(1024)
q = getPrime(1024)

n = p*q
e = 123589168751396275896312856328164328381265978316578963271231567137825613822284638216416
m = bytes_to_long(b"nbctf{[REDACTED]}")

ct = (m^e) % n

print("n = ", n)
print("e = ", e)
print("ct = ", ct)

output：

1
2
3
n =  13431294979312769345517878088407659222785929563176888493659632690735510803353339825485161776891929296355466082338185199541755546384591261208929371208286410559187299345800125302598147388467283782373829399059130130575707550536466670447022349923395822077916588516101640779751198703879200863153859677174339078186779847910915309774616338231020176817201080756103027200290903849975398368943087868140010448011002364291104062990443568049879169811274854879262048473842331319786127894828031613201122015559660817797429013884663990368453887433480357502012963127000535358820517096295714967262963843868885674823702064175405493435873
e =  123589168751396275896312856328164328381265978316578963271231567137825613822284638216416
ct =  159269674251793083518243077048685663852794473778188330996147339166703385101217832722333

诈骗类题目。这个ct长度一看就不对，然后就会发现^其实是异或。

exp：

1
2
3
4
5
6
7
8
9
from Crypto.Util.number import *

n =  13431294979312769345517878088407659222785929563176888493659632690735510803353339825485161776891929296355466082338185199541755546384591261208929371208286410559187299345800125302598147388467283782373829399059130130575707550536466670447022349923395822077916588516101640779751198703879200863153859677174339078186779847910915309774616338231020176817201080756103027200290903849975398368943087868140010448011002364291104062990443568049879169811274854879262048473842331319786127894828031613201122015559660817797429013884663990368453887433480357502012963127000535358820517096295714967262963843868885674823702064175405493435873
e =  123589168751396275896312856328164328381265978316578963271231567137825613822284638216416
ct =  159269674251793083518243077048685663852794473778188330996147339166703385101217832722333

print(long_to_bytes(e^ct))

#nbctf{wh0_t0ld_m3_t0_u53_xors!?!?!?}



SBG-ABW’s Insanity

题目描述：

1
"Skill Issue" - AnonymousBlueWhale

题目：

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
from Crypto.Util.number import getPrime, bytes_to_long, isPrime, long_to_bytes
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
import hashlib

m = bytes_to_long(b'we give you this as a gift!')

p = getPrime(1096)
q1 = getPrime(1096)
q2 = getPrime(1096)
n1 = p*q1
n2 = p*q2

e = 11

ct1 = pow(m,e,n1)
ct2 = pow(m,e,n2)

key = hashlib.sha256(long_to_bytes(q1)).digest()
cipher = AES.new(key, AES.MODE_ECB)
enc_flag = cipher.encrypt(pad(b"nbctf{[REDACTED]}", 16))

print("ct1 =", ct1)
print("ct2 =", ct2)
print("enc_flag =", enc_flag.hex())

output：

1
2
3
ct1 = 196150896308015382573408099004515975466540094705348761587854272630906023749083911008835478259767648401709605726136589590310666858430120235218762651641330953170392784645631801449432061363776229651965539255255795373230255852992805188205639228954217034390731460194284731845705855212209524525682241998203303747513174581513168217999505436596818091279091144718119512522929858750349220346765422769476003604849600128605208123474607256344535541843454810706150705449483256361736428064150792476736751093915251743882647862500622465233906844054109281842278362125589335774364236155483783338907105809549449368926475631824722919958889450225026843225780470131268709445293157749
ct2 = 83507921327913521142443934492559420944369023782917085618978768157512494136296269338031471193927727958060037960270530278173852027186606624474398269053920321522448607751539858355179998108075848593814112217098612017462222420001262248144471923306139580601814218471659969728514600258330312623506466116333593434744460773476488134792248490905628242447603788884700795677619881924772996081377617066055448888668800826281711315468059146518373888252421991592124071284411947405472003802863596010724784730366575751160333120162778945930063499020829492960600318519615351417595308518636794008603089224459556289944808655338805251676963828327517925911000528943113536807796285824
enc_flag = ac2289b707b174c541cf0952bf3b2057561b0872451444a5bbecf18c007ea20fa2b7c8a1707a74a1657e5adb5c1a417f

题目给定了m值，同时生成三个素数p,q1,q2,并给出如下式子：

拆开同余式，就有：

求gcd并去除小因子就能得到p，然后就有：

然后得到的是一个1200左右数量级的数，factordb无法直接分解出q1，但是对这种素因子之间数量级差异较大的yafu可以轻松分解得到q1。得到q1后AES解密即可。

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

ct1 = 196150896308015382573408099004515975466540094705348761587854272630906023749083911008835478259767648401709605726136589590310666858430120235218762651641330953170392784645631801449432061363776229651965539255255795373230255852992805188205639228954217034390731460194284731845705855212209524525682241998203303747513174581513168217999505436596818091279091144718119512522929858750349220346765422769476003604849600128605208123474607256344535541843454810706150705449483256361736428064150792476736751093915251743882647862500622465233906844054109281842278362125589335774364236155483783338907105809549449368926475631824722919958889450225026843225780470131268709445293157749
ct2 = 83507921327913521142443934492559420944369023782917085618978768157512494136296269338031471193927727958060037960270530278173852027186606624474398269053920321522448607751539858355179998108075848593814112217098612017462222420001262248144471923306139580601814218471659969728514600258330312623506466116333593434744460773476488134792248490905628242447603788884700795677619881924772996081377617066055448888668800826281711315468059146518373888252421991592124071284411947405472003802863596010724784730366575751160333120162778945930063499020829492960600318519615351417595308518636794008603089224459556289944808655338805251676963828327517925911000528943113536807796285824
enc_flag = "ac2289b707b174c541cf0952bf3b2057561b0872451444a5bbecf18c007ea20fa2b7c8a1707a74a1657e5adb5c1a417f"
m = bytes_to_long(b'we give you this as a gift!')
e = 11

p = GCD(m**11-ct1,m**11-ct2)
for i in range(2,1000):
    while(p % i == 0):
        p //= i
q1 = (m**11-ct1) // p
q2 = (m**11-ct2) // p

#yafu
q1 = 603701201822386830907144477326706640694145605732107023753674808182665696931502012989218558077472289899849882120737934821898165435847435044518846871242860227586749788240998624721376490806164324545522115137075097300642534248374378375756928831273442124872283671893345317220496457140852434166575343690062190540448032738970711476061243

key = hashlib.sha256(long_to_bytes(q1)).digest()
cipher = AES.new(key, AES.MODE_ECB)
flag = cipher.decrypt(long_to_bytes(int(enc_flag,16)))
print(flag)

#nbctf{c0ngr4ts_0n_F1nish1n9_Th3_3_P4rt3r!!!!}



Too Little Information

题目描述：

1
My computer crashed generating my keys. :( Can you recover them for me?

题目：

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

p = getPrime(512)
q = getPrime(512)

n = p*q
e = 65537

m = bytes_to_long(b"nbctf{[REDACTED]}")

ct = pow(m,e,n)

print(f"{ct = }")
print(f"{e = }")
print(f"{n = }")

hint = (p+q) >> 200 # I can't be giving you that much!
print(f"{hint = }")

output：

1
2
3
4
ct = 20030315247290021934293927354887580426070566017560641204155610658927917290198737029903594702064351773446005018155094643288125396810753014936800515440652855824038470725838848349666236623899089094953181436465435270989651491997801177943499187812270081592263331832916362349716591828106306150603120693022149233534
e = 65537
n = 90166344558664675592644684556355545187373291859609367810958775310181360193141550862577281658089332577942193823477148064165061303827534169112815736618901965700400798345371758370344207077280925015891945591352156370597957742921722432314582261224366498475465730899163137511778647694175484386010210005826793007961
hint = 12227137598952006551839416663729660224872609953685427677011433223002140448682395830146750981200

题目给了p+q的高位，那么直接在实数域上解一个p、q的近似值就能得到p、q的部分高位，然后copper就可以还原p、q。具体可以见下面这篇文章的[WEEK3]easyrsa一题。

2023-SHCTF-wp-crypto | 糖醋小鸡块的blog (tangcuxiaojikuai.xyz)

exp：

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

ct = 20030315247290021934293927354887580426070566017560641204155610658927917290198737029903594702064351773446005018155094643288125396810753014936800515440652855824038470725838848349666236623899089094953181436465435270989651491997801177943499187812270081592263331832916362349716591828106306150603120693022149233534
e = 65537
n = 90166344558664675592644684556355545187373291859609367810958775310181360193141550862577281658089332577942193823477148064165061303827534169112815736618901965700400798345371758370344207077280925015891945591352156370597957742921722432314582261224366498475465730899163137511778647694175484386010210005826793007961
hint = 12227137598952006551839416663729660224872609953685427677011433223002140448682395830146750981200
 
PR.<x> = PolynomialRing(RealField(1000))
f = x*((hint<<200)-x) - n
phigh = int(f.roots()[0][0])

PR.<x> = PolynomialRing(Zmod(n))
f = phigh + x
res = f.small_roots(X=2^203, beta=0.4)[0]
p = int(phigh + res)
q = n // p
d = inverse(e,(p-1)*(q-1))
flag = pow(ct, d, n)

print(long_to_bytes(int(flag)))

#nbctf{cr34t1v3_fl4gs_4r3_s0_h4rd_t0_m4k3...}



weckes special dots

题目描述：

1
Will told me "special dots" were the key to a safe future in his senior speech. No one can break this now!

题目：

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
import random
from math import gcd
from Crypto.Util.number import bytes_to_long

ps = []
qs = []
Ns = []
for k in range(4):
	pk = random_prime(2^512)
	qk = random_prime(2^512)
	Nk = pk*qk

	Ns.append(Nk)
	qs.append(min([pk,qk]))
	ps.append(max([pk,qk]))

N = min(Ns)

sigma = 2/5
boundxy = int(N^sigma)

ys = [random.randint(0,boundxy^0.5) for _ in range(4)]
x = random.randint(0,boundxy^0.5)

zs = []
for i in range(4):
	while True:
		totient = (ps[i] - 1)*(qs[i] - 1)
		bound = (((ps[i] - qs[i])/(3*(ps[i] + qs[i])))*(N^0.25)*ys[i])
		z = x^2 - ((ys[i]^2*totient) % (x^2))
		if z < bound:
			zs.append(z)
			break

es = []
for i in range(4):
	totient = (ps[i] - 1)*(qs[i] - 1)
	e = int((zs[i] + ys[i]^2*totient) // (x^2))
	es.append(e)

for i in range(4):
	totient = (ps[i] - 1)*(qs[i] - 1)
	assert es[i]*x^2 - ys[i]^2*totient == zs[i]

flag = b"nbctf{[REDACTED]}"
flag = bytes_to_long(flag + b"\x00"*(96-len(flag)))

cts = []
for i in range(4):
	cts.append(pow(flag,es[i],Ns[i]))

print(f"{Ns = }")
print(f"{es = }")
print(f"{cts = }")

output：

1
2
3
Ns = [79318542136541826417612597596660834643671914515973102182498976301984280111125611669632823846015267254981697109191068942116179674821996091730724132232522669459181268000281459688374099425153883446718364090516450113945111388277714740550118306135431740594020937182873360208272710894895016684804607958075949695133, 73620484833145756244501717977835103380076744682983039922290483049672158047111966510859522138437769431716138137298259936284470889512904428081195919109790333410649589450722499689047086486571333509641779604419007313841778258586856504151936948073896147684327524777235874072534777351652973917997215707042745039, 25567799160991816074553198034509823797810060973711289655734457675171308566408457936150845181596568639914372515037031023929542359125171435839588679910314564825512727372468910067799908181137751860196370788101822863749454857243246521969085422186473905127037180668318492587145378409627601407617161940771406174623, 65071763950437164238938366754415184873344654677507103977306961020242719621804016673546174113934227134005963088283821979180914720130701199682696874906639328809744488247562390950833594949467958096044663193221343017165158503552111661788176097079347219868981893839451856448184329889738669967576791906875369529723]
es = [163881997250312143077577311321142404849510110022730027519841524838954460503265764485501239118416390422255671398354065587467328924937518353071926976183049309778433900104505929909070479622637555212931201711374123522784484341637235425202479392831399804064445100466207178276207564148782196781830314887823725189832, 14114640611493860872355817160136414165270219508200005762214095199196049054198477038003198877252353894909061943386978272311153387040493786080796653211845518325266842849631617545372849714431226045650236134021716939606393362859751098624567020564369882307686291793549819479604308305919836042412218861665016963, 6021761687771495056291680259956374008663738155623523343163979371241811568305520469667718414188710894377431630783877408981361616242409973408082914342254349346470350687705510188543822078489218263063729298311794558406594224113462022844931732745584206083650062784129605208520771028840463024026993962527469508707, 305906815539458020666821618127587191957535143850968847700167249142391325254448781348153814043301470572271570988313642866765873139950494446600570547610583085235402505512157793433348758057524189642765807684953443937879793914140254460252742917643916968190442668456346805601621538797502566160169877146542766687244]
cts = [66267745560300585985468152228016423241150920495212542509259172516947232345251993435829090668634479168090058911966060012541720146866074583358831328163803434699337764065923291118550405180597268885512613099511130580449432456456307146792623499994217173703991350840941912244081109369931025029775632953213044200271, 14395597551295958997059664307973264962628010825390828468115238607777474200647501964239691219481897108822076091140939406196515509355364167349373851586651112466295603613334610594911618523323632391986343531739508183539402436700042244044232766212319180792391049624994092394110853537914570229500199769608675818, 24072178192180559995785565341089955874000639469279763640542002879271308222691604323356211117577720990169974122948131228508590468889528148827099040444991836975901177761336693631754808097776829472553344285974090490712852129177088854501318759577556291221994101853328930531939762493180432184115780277197946895490, 13668478953182531569457552590244421972456707002774796250647371422727797201971991726365389973261401297178979634945892837439938123358013486834095447151162935738920438942990447265941268782810902258484610867172018735788552551710770434272963394474018005906256577011784836433381400871547206803343373870827711009870]

题目已知以下几组等式：

将phin拆开有：

把这个等式写成：

所以构造格：

这个格具有如下线性关系：

显然目标向量不是相等数量级，因此还需要配平一下。同时为了保证前四列规约出0，还需要乘上大系数K。

配平格之后，在LLL得到的符合条件的向量中寻找(前四列是0)，可以发现第一个满足要求的向量即为所求，然后就可以得出x^2和yi^2，之后就可以直接整除求出phini(虽然可能有zi的偏移，但最多也就需要爆破一小段)。

但是一开始，自己测试数据发现这个解法是概率性的，10组数据大概只能出5、6组左右。但是后面仔细思考觉得是配平系数的问题，果然，如果求不出结果，可以微调配平系数T，基本上上调或下调5之内一定能出结果。

解出phini后还会面对e和phi不互素的问题，这个就不需要多说了。

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
54
55
56
from Crypto.Util.number import *
from gmpy2 import *

Ns = [79318542136541826417612597596660834643671914515973102182498976301984280111125611669632823846015267254981697109191068942116179674821996091730724132232522669459181268000281459688374099425153883446718364090516450113945111388277714740550118306135431740594020937182873360208272710894895016684804607958075949695133, 73620484833145756244501717977835103380076744682983039922290483049672158047111966510859522138437769431716138137298259936284470889512904428081195919109790333410649589450722499689047086486571333509641779604419007313841778258586856504151936948073896147684327524777235874072534777351652973917997215707042745039, 25567799160991816074553198034509823797810060973711289655734457675171308566408457936150845181596568639914372515037031023929542359125171435839588679910314564825512727372468910067799908181137751860196370788101822863749454857243246521969085422186473905127037180668318492587145378409627601407617161940771406174623, 65071763950437164238938366754415184873344654677507103977306961020242719621804016673546174113934227134005963088283821979180914720130701199682696874906639328809744488247562390950833594949467958096044663193221343017165158503552111661788176097079347219868981893839451856448184329889738669967576791906875369529723]
es = [163881997250312143077577311321142404849510110022730027519841524838954460503265764485501239118416390422255671398354065587467328924937518353071926976183049309778433900104505929909070479622637555212931201711374123522784484341637235425202479392831399804064445100466207178276207564148782196781830314887823725189832, 14114640611493860872355817160136414165270219508200005762214095199196049054198477038003198877252353894909061943386978272311153387040493786080796653211845518325266842849631617545372849714431226045650236134021716939606393362859751098624567020564369882307686291793549819479604308305919836042412218861665016963, 6021761687771495056291680259956374008663738155623523343163979371241811568305520469667718414188710894377431630783877408981361616242409973408082914342254349346470350687705510188543822078489218263063729298311794558406594224113462022844931732745584206083650062784129605208520771028840463024026993962527469508707, 305906815539458020666821618127587191957535143850968847700167249142391325254448781348153814043301470572271570988313642866765873139950494446600570547610583085235402505512157793433348758057524189642765807684953443937879793914140254460252742917643916968190442668456346805601621538797502566160169877146542766687244]
cts = [66267745560300585985468152228016423241150920495212542509259172516947232345251993435829090668634479168090058911966060012541720146866074583358831328163803434699337764065923291118550405180597268885512613099511130580449432456456307146792623499994217173703991350840941912244081109369931025029775632953213044200271, 14395597551295958997059664307973264962628010825390828468115238607777474200647501964239691219481897108822076091140939406196515509355364167349373851586651112466295603613334610594911618523323632391986343531739508183539402436700042244044232766212319180792391049624994092394110853537914570229500199769608675818, 24072178192180559995785565341089955874000639469279763640542002879271308222691604323356211117577720990169974122948131228508590468889528148827099040444991836975901177761336693631754808097776829472553344285974090490712852129177088854501318759577556291221994101853328930531939762493180432184115780277197946895490, 13668478953182531569457552590244421972456707002774796250647371422727797201971991726365389973261401297178979634945892837439938123358013486834095447151162935738920438942990447265941268782810902258484610867172018735788552551710770434272963394474018005906256577011784836433381400871547206803343373870827711009870]

K = 2^2000
L = Matrix(ZZ,9,9+4)
for i in range(4):
    L[0,i] = es[i]*K
    L[2*i+1,i] = (Ns[i]+1)*K
    L[2*i+2,i] = K

T = 2^512
L[0,4] = T
for i in range(1,9):
    if(i % 2 == 0):
        L[i,i+4] = 1
    else:
        L[i,i+4] = T
res = L.LLL()

x2 = abs(res[0][4]) // T
print(iroot(x2,2)[1])
ys2 = [abs(res[0][5+2*i]) // T for i in range(4)]

t = 0
phi = es[t]*x2 // ys2[t]
pplusq = Ns[t]-phi+1
pminusq = iroot(pplusq^2-4*Ns[t],2)[0]
p = (pplusq + pminusq) // 2
q = Ns[t] // p

d = inverse(es[t]//8,phi)
c = pow(cts[t],d,Ns[t])

PR.<x> = Zmod(p)[]
f = x^8 - c
resp = f.roots()

PR.<x> = Zmod(q)[]
f = x^8 - c
resq = f.roots()


from sympy.ntheory.modular import crt
#M = crt(n,c)[0]
for i in resp:
    for j in resq:
        modlist = [p,q]
        clist = [int(i[0]),int(j[0])]
        M = crt(modlist,clist)[0]
        print(long_to_bytes(int(M)))

#nbctf{W3ck3s_t0ld_m3_sp3c14l_d0ts_w3r3_s3cur3}



Leet Crypto Generator

题目描述：

1
2
"For all you cryptoers out there I CAN LCG" - SuperBeetleGamer at his prime
nc chal.nbctf.com 30432

题目：

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
#!/usr/bin/sage
from sage.crypto.util import ascii_to_bin
from Crypto.Util.number import *
import hashlib
import random

print("starting...")

class LCG:
    def __init__(self, seed, p):
        self.seed = seed
        self.p = p
        self.a = random.randint(0,p)
        self.b = random.randint(0,self.a)

    def next(self):
        self.seed = (self.seed*self.a + self.b) % self.p
        return self.seed

p = random_prime(2^256)
a, b = 3, 4
E = EllipticCurve(GF(p), [a,b])
G = E.gens()[0]

lcg = LCG(random.randint(0,p), p)

flag = "nbctf{[REDACTED]}"
flag_bits = list(map(int, list(str(ascii_to_bin(flag)))))

while True:
    inp = int(input("Pick an index of a flag bit: "))
    assert inp >= 0 and inp < len(flag_bits)

    if flag_bits[inp] == 0:
        x = E.random_element()
        print("I wonder what this is: " + str(x.xy()))
    elif flag_bits[inp] == 1:
        x = G*bytes_to_long(flag.encode()) + E.random_element()*int(hashlib.sha256(flag.encode()).hexdigest(), 16)
        y = lcg.next()*x + G*bytes_to_long(flag.encode())
        print("I wonder what this is: " + str(y.xy()))

题目主要流程如下：

  • 连接上靶机后，随机生成一个素数p
  • 生成如下的椭圆曲线，并确定生成元点G：
  • 以p作为模数，初始化一个LCG
  • 将flag转化为对应的二进制列表后，可以进行如下交互操作：选择flag的任意一比特位，如果该比特位为0，则输出一个ECC上的随机点坐标；如果该比特为为1，则输出如下的点坐标：
  • 其中，seed是LCG当前值，m为flag值，Ei为随机点，h(m)为flag的sha256值，G为生成元。

那么解题的思路也很自然：想办法找到0和1输出的点的区别，逐比特确定flag值。

首先，由于有如下的断言式存在，很容易就可以确定flag的长度：

1
assert inp >= 0 and inp < len(flag_bits)

我们从0开始爆破长度，输入值不满足assert条件时，靶机就会返回报错，此时的长度就是flag的比特长度。如此就可以确定flag共232比特，一共是29个字符。

然后就是核心问题了：flag的当前比特为0和1时，输出的点到底有什么能作为判断条件的区别？对此我有以下两个想法：

时间区别

观察交互部分：

1
2
3
4
5
6
7
if flag_bits[inp] == 0:
        x = E.random_element()
        print("I wonder what this is: " + str(x.xy()))
elif flag_bits[inp] == 1:
        x = G*bytes_to_long(flag.encode()) + E.random_element()*int(hashlib.sha256(flag.encode()).hexdigest(), 16)
        y = lcg.next()*x + G*bytes_to_long(flag.encode())
        print("I wonder what this is: " + str(y.xy()))

最最直观的感受就是：0和1的运算量有显著差异。0的时候随机生成一个点并输出即可，而输入1的时候，他会经历以下多步计算：

  • 计算flag的整数值
  • 计算flag的哈希值
  • 计算LCG当前seed值
  • 计算点乘及点加

并且，flag的值与其哈希值是定值，因此完全没有必要每次都计算一遍，出题人这样写就像是释放了一个确定的信号：时间侧信道攻击。

同时，每一bit我们都可以反复访问，因此我们可以先本地验证一下这样时间是否会有区别：

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
#!/usr/bin/sage
from sage.crypto.util import ascii_to_bin
from Crypto.Util.number import *
import hashlib
import random
import time

print("starting...")

class LCG:
    def __init__(self, seed, p):
        self.seed = seed
        self.p = p
        self.a = random.randint(0,p)
        self.b = random.randint(0,self.a)

    def next(self):
        self.seed = (self.seed*self.a + self.b) % self.p
        return self.seed

p = random_prime(2^256)
a, b = 3, 4
E = EllipticCurve(GF(p), [a,b])
G = E.gens()[0]

lcg = LCG(random.randint(0,p), p)

flag = "nbctf{[REDACTED]}"
flag_bits = list(map(int, list(str(ascii_to_bin(flag)))))

T1 = time.time()
for i in range(100):
	x = E.random_element()
T2 = time.time()
print(T2-T1)

T1 = time.time()
for i in range(100):
	x = G*bytes_to_long(flag.encode()) + E.random_element()*int(hashlib.sha256(flag.encode()).hexdigest(), 16)
	y = lcg.next()*x + G*bytes_to_long(flag.encode())
T2 = time.time()
print(T2-T1)

结果为：

1
2
3
starting...
0.1539936065673828
6.5936033725738525

也就是说，如果我们对同一比特访问100次，时间区别就会变得比较显著，我们就可以以此为依据来确定这一比特究竟是0还是1。

但是由于是交互题，所以大部分时间其实花费在了交互上，这就导致两个弊端：一是时间的差异有时候体现的并不明显，所以0和1容易有一些小错误；二是每一比特的100次交互花费的时间过长，爆破完全部232个比特位要花费两三个小时，不是非常理想。

这种情况下有几个能尽可能减少耗时的方式：

  • 先刷出一条耗时较短的ECC，再往后交互。
  • 由于已知flag头尾，因此可以少爆破7个字符
  • 每个可见字符的八位二进制最高位均为0，因此可以少爆破一位

同时，经测试超过一定次数后靶机好像会断开连接，但是猜测flag为静态，因此每次爆破一个字符就好。

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

r = remote("chal.nbctf.com",30432)
r.recvline()

#finish gen G first(and get flag length = 232)
r.sendline(b"0")
r.recvuntil(b"I wonder what this is: ")

#get flag
#first get basic time
T1 = time.time()
for j in range(100):
    r.sendline(b"0")
    r.recvuntil(b"I wonder what this is: ")
T2 = time.time()
time_0 = T2-T1

#get flag
print("Begin!")
flag = ""
for i in range(8*6,232):
    T1 = time.time()
    for j in range(100):
        r.sendline(str(i).encode())
        r.recvuntil(b"I wonder what this is: ")
    T2 = time.time()
    if(T2-T1 > time_0 + 3):
        flag += "1"
    else:
        flag += "0"
    if(len(flag) % 8 == 0):
        print(long_to_bytes(int(flag,2)))

print(long_to_bytes(int(flag,2)))

这个思路大概率是非预期解，因为既没有用到ECC，也没有用到LCG，与题目本身基本没有关系。

ECC

回到题目本身，我阐述一下第二种思路。

首先，我们访问flag的某一比特位，无论其为0还是1，我们都能获得ecc上的若干点，然后由ECC方程求gcd并去除小因子就可以得到p。

得到p之后，如果访问的flag当前比特为1，我们就可以得到如下形式的点：

如果我们能随机到一个使ECC的order较光滑的p，那么该曲线上的DLP就易求，而G是生成元，也就是说我们可以把这些点均写成G点的倍数形式：

而我们知道flag开头是”nbctf{“，也就是我们能确定某些比特一定为1，因此我们可以反复访问为1的各个点，从而得到多组如上形式的点。

同时由于DLP易求，我们就可以轻松求解出若干组如下形式的值：

即：

这让我想起了Rosita一题：

Crypto趣题-曲线 | 糖醋小鸡块的blog (tangcuxiaojikuai.xyz)

在本题中，m是232比特的量，相较于order来说也可以算作一个小量，因此我们是否也可以同理造一个正交格，然后在核空间中去规约向量从而直接得到m？

这应该算一个想法，不过我没有去具体实施过，有时间的话会去尝试一下。

更新

今天比赛结束后，靶机还开着，就去试了试时间侧信道，断断续续逐字符爆破，并且由于存在误差，所以最终确定flag一共花了前前后后差不多三四个小时时间，结果得到的flag让我很惊讶：

1
nbctf{t1m1ng_4tt4ck_I_gu355?}

结果真就是个时间侧信道攻击的题目，笑死。所以说上面的ECC和LCG其实也都只是个伪装而已，可以说是为了这碟醋包了这碗饺子。

第二个想法也就不太需要尝试了，有一种受骗了的感觉。