DASCTF2023年7月比赛复盘-密码部分 快过年了发现一点存货
同期题目 逆向部分
ezRSA
RSA is not easy, huh?
这是两道 RSA 的缝合题
第一关：知道 P^(Q>>16) 要分解N
第二关：知道前后缀、密文以及带前后缀的密文求明文
从第 0 位一直到第 495 位每一位的组合只有两种情况
752K9s2c8@1M7q4)9K6b7g2)9J5c8W2)9J5c8Y4N6%4N6#2)9J5k6i4M7K6i4K6u0W2L8%4u0Y4i4K6u0r3x3e0V1&6z5q4)9J5c8V1#2S2N6r3S2Q4x3V1k6y4j5i4c8Z5e0f1H3`.">∗ ( m o d l ) ≡ P ∗ Q ( m o d l ) = N ( m o d l ) \bar{P}*\bar{Q}\pmod{2^l}\equiv P*Q\pmod{2^l}=N\pmod{2^l} P ˉ ∗ Q ˉ ( mod 2 l ) ≡ P ∗ Q ( mod 2 l ) = N ( mod 2 l )
其中 l 是位数
直接进行一个深度优先的搜索即可
Q 的低 16 位完全未知只能纯粹枚举
注意这里有一点比较坑
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 tqdm import tqdm
N = 75000029602085996700582008490482326525611947919932949726582734167668021800854674616074297109962078048435714672088452939300776268788888016125632084529419230038436738761550906906671010312930801751000022200360857089338231002088730471277277319253053479367509575754258003761447489654232217266317081318035524086377
gift = 8006730615575401350470175601463518481685396114003290299131469001242636369747855817476589805833427855228149768949773065563676033514362512835553274555294034
cn = 14183763184495367653522884147951054630177015952745593358354098952173965560488104213517563098676028516541915855754066719475487503348914181674929072472238449853082118064823835322313680705889432313419976738694317594843046001448855575986413338142129464525633835911168202553914150009081557835620953018542067857943
_gift=[(gift>>d)&1 for d in range(512)]
def dfs(pp,qq,d):
if d==512:
if pp*qq==N:
print(f"{pp=}\n{qq=}")
return
if d==0:
if _gift[d]==0:
dfs(1,qq+(1<<(d+16)),d+1)
else:
dfs(1,qq,d+1)
else:
if pp*qq%(1<<d)!=N%(1<<d):
return
if _gift[d]==0:
dfs(pp+(1<<d),qq+(1<<(d+16)),d+1)
dfs(pp,qq,d+1)
else:
dfs(pp+(1<<d),qq,d+1)
dfs(pp,qq+(1<<(d+16)),d+1)
for qlow in tqdm(range(1<<16,1<<17)):
dfs(0,qlow%(1<<16),0)
然后是一个 related message attack
可以考虑 coppersmith
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
pp=8006847171912577069085166877758626954304824756138758266557706391662987806065132448544117840031499707938227955094109779732609035310252723066470330862622641
qq=9366986529377069783394625848920106951220134111548343265311677163992169555436421569730703291128771472885865288798344038000984911921843088200997725324682297
phiphi=(pp-1)*(qq-1)
ee=11
dd=int(inverse(ee,phiphi))
n=pow(cn,dd,N)
print(len(bin(n)[2:]))
n+=N
print(f'n={n}')
print(len(bin(n)[2:]))
from sage.all import PolynomialRing,Zmod
prefix=b"dasctf{"
suffix=b"}"
e=11
c1=69307306970629523181683439240748426263979206546157895088924929426911355406769672385984829784804673821643976780928024209092360092670457978154309402591145689825571209515868435608753923870043647892816574684663993415796465074027369407799009929334083395577490711236614662941070610575313972839165233651342137645009
c2=46997465834324781573963709865566777091686340553483507705539161842460528999282057880362259416654012854237739527277448599755805614622531827257136959664035098209206110290879482726083191005164961200125296999449598766201435057091624225218351537278712880859703730566080874333989361396420522357001928540408351500991
x=PolynomialRing(Zmod(n),'x').gen()
def related_message(mbar):
g1=x**e-c1
g2=(x*256+mbar)**e-c2
g2=g2.monic()
def gcd(g1,g2):
while g2:
g1,g2=g2,g1%g2
return g1.monic()
f=gcd(g1,g2)
return int(-f[0])
for msglen in tqdm(range(10, 50)):
m0=bytes_to_long(prefix+b'\x00'*msglen+suffix)
m=related_message(m0)
try:
flag=long_to_bytes(m).decode()
print(prefix.decode()+flag+suffix.decode())
except:
continue
dasctf{C0pper_Sm1th_Mak3s_T1ng5_Bet4er}
ezDHKE
DHKE is easy, huh?
Diffie Hellman 的模数任选
98eK9s2c8@1M7q4)9K6b7g2)9J5c8W2)9J5c8Y4N6%4N6#2)9J5k6i4M7K6i4K6u0W2L8%4u0Y4i4K6u0r3x3e0V1&6z5q4)9J5c8V1#2S2N6r3S2Q4x3V1k6y4j5i4c8Z5e0f1H3`.">g k ≡ ( m o d p ) g^k \equiv 1 \pmod p g k ≡ 1 ( mod p )
则
c90K9s2c8@1M7q4)9K6b7g2)9J5c8W2)9J5c8Y4N6%4N6#2)9J5k6i4M7K6i4K6u0W2L8%4u0Y4i4K6u0r3x3e0V1&6z5q4)9J5c8V1#2S2N6r3S2Q4x3V1k6y4j5i4c8Z5e0f1H3`.">= g x ( m o d p ) = g x m o d k C_x = g^x \pmod{p} = g^{x \bmod k} C x = g x ( mod p ) = g x mod k
我们直接对 Cx 取 g 为底的对数即得到 x mod k
对 y 同理然后可以得到
303K9s2c8@1M7q4)9K6b7g2)9J5c8W2)9J5c8Y4N6%4N6#2)9J5k6i4M7K6i4K6u0W2L8%4u0Y4i4K6u0r3x3e0V1&6z5q4)9J5c8V1#2S2N6r3S2Q4x3V1k6y4j5i4c8Z5e0f1H3`.">g x y ( m o d p ) = g x y m o d k = g ( x m o d k ) ( y m o d k ) g^{xy}\pmod{p}=g^{xy \bmod k}=g^{(x\bmod k)(y \bmod k)} g x y ( mod p ) = g x y mod k = g ( x mod k ) ( y mod k )
本题中 g=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
from Crypto.Util.number import *
from Crypto.Cipher import AES
from hashlib import sha256
from random import randbytes, getrandbits
P = 0
for i in range(1024, 2048, 1):
P = 2 ** i - 1
if (isPrime(P)):
print(f'P = 2 ** {i} = {P}')
P = 10407932194664399081925240327364085538615262247266704805319112350403608059673360298012239441732324184842421613954281007791383566248323464908139906605677320762924129509389220345773183349661583550472959420547689811211693677147548478866962501384438260291732348885311160828538416585028255604666224831890918801847068222203140521026698435488732958028878050869736186900714720710555703168729087
Cx = 2630067950774186753620494941440064332775169901411586929749140451534366077148540411056833268138794225613491484428089108856509716125091901931563907385325940424977611835564222299095831878942161358635646625867890688
Cy = 18014398509481984
x0 = len(bin(Cx)) - 3
y0 = len(bin(Cy)) - 3
key = sha256(long_to_bytes(pow(2, x0 * y0, P))).digest()
iv = b"dasctfdasctfdasc"
aes = AES.new(key, AES.MODE_CBC, iv)
enc = b'\x9d\n\x8f\xb1\xb3YO\x94;1\xb1r\xa0f\x015K>\xb4\xe0t\x04\xdd\xb9\x12\x9a[I\xc6\xd1\xdc\xb4\xbbj1\x1b\xde\xcd\xc2\x18\xd408CCM\xa5\xcc'
flag = aes.decrypt(enc)
print(flag)
DASCTF{eefa6be7-57e6-4a48-99d6-936feff93108}
ezAlgebra
Algebra is not easy!
算法如下：
取 3 个质数
随机摇一个 t:32
然后输出
注意到 c1 = 1997 + t + t^2 + t^3 + t^^4 = 0 (mod p)
回顾一下 coppersmith 的约束
647K9s2c8@1M7q4)9K6b7g2)9J5c8W2)9J5c8Y4N6%4N6#2)9J5k6i4M7K6i4K6u0W2L8%4u0Y4i4K6u0r3x3e0V1&6z5q4)9J5c8V1#2S2N6r3S2Q4x3V1k6y4j5i4c8Z5e0f1H3`.">X ∼ N − ϵ p β = N δ = deg f X \sim N^{\frac{\beta^2}{\delta}-\epsilon}\\
p^\beta=N\\
\delta=\deg{f} X ∼ N δ β 2 − ϵ p β = N δ = deg f
简单估算一下参数
7e0K9s2c8@1M7q4)9K6b7g2)9J5c8W2)9J5c8Y4N6%4N6#2)9J5k6i4M7K6i4K6u0W2L8%4u0Y4i4K6u0r3x3e0V1&6z5q4)9J5c8V1#2S2N6r3S2Q4x3V1k6y4j5i4c8Z5e0f1H3`.">δ = β ∼ − ϵ > = \delta = 4\\
\beta \sim \frac{1}{2}\\
\frac{\beta^2}{\delta}-\epsilon>\frac{32}{1024}=\frac{1}{32} δ = 4 β ∼ 2 1 δ β 2 − ϵ > 1024 32 = 32 1
取 epsilon 为 1/33 即可
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
from sage.all import *
from Crypto.Util.number import *
from tqdm import tqdm
n = 119156144845956004769507478085325079414190248780654060840257869477965140304727088685316579445017214576182010373548273474121727778923582544853293534996805340795355149795694121455249972628980952137874014208209750135683003125079012121116063371902985706907482988687895813788980275896804461285403779036508897592103
c1 = 185012145382155564763088060801282407144264652101028110644849089283749320447842262397065972319766119386744305208284231153853897076876529326779092899879401876069911627013491974285327376378421323298147156687497709488102574369005495618201253946225697404932436143348932178069698091761601958275626264379615139864425
c2 = 722022978284031841958768129010024257235769706227005483829360633993196299360813
c3 = 999691052172645326792013409327337026208773437618455136594949462410165608463231
R=Zmod(n)
t = R['t'].gen()
ft = 1997 + t + t**2 + t**3 + t**4 - c1
tt = ft.small_roots(beta=1/2, epsilon=1/33)[0]
assert len(bin(tt)[2:]) == 32
print(f"{tt=}")
pp = gcd(int(ft(tt)), n)
assert len(bin(pp)[2:]) == 512 and n % pp == 0
print(f"{pp=}")
得到 t 后，带入 c1 的公式和 n 作 gcd 从而得到 p
在模 n 多项式环上对 f(m)-c2 和 g(m)-c3 应用欧几里得法
有了 q 之后
令 m=-m0+kq 爆破明文
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
tt=int(tt)
pp=int(pp)
nn = n//pp
R=Zmod(nn)
m = R['m'].gen()
f = 0*m+1997-c2
g = 0*m+1997-c3
for i in range(1, 20):
f += (tt*m)**i
g += (tt+m)**i
f,g=f.monic(),g.monic()
while g.degree():
f,g=g,f%g
q=int(gcd(g[0],nn))
q
R=Zmod(q)
m = R['m'].gen()
f = 0*m+1997-c2
g = 0*m+1997-c3
for i in range(1, 20):
f += (tt*m)**i
g += (tt+m)**i
f,g=f.monic(),g.monic()
while g:
f,g=g,f%g
f=f.monic()
mm=int(-f[0])
mm
for _ in tqdm(range(2**24)):
try:
print(long_to_bytes(mm).decode())
break
except:
mm += q
continue
long_to_bytes(mm).decode()
dasctf{ShangPoXiaPoYaSiLeYiQianDuo}
24年1月29日于仙林
[培训]内核驱动高级班，冲击BAT一流互联网大厂工作，每周日13:00-18:00直播授课
最后于 2025-3-14 01:42
被狗敦子编辑
，原因： 修改了一些内容
上传的附件：
