DASCTF复盘之密码学(2023.07) DASCTF 2023年7月 密码学题解共3题
快过年了闲下来发现一点存货，遂记录之。
同期题目 DASCTF逆向2023.07
ezRSA
RSA is not easy, huh?
这是两道RSA的缝合题。
第一关：知道P^(Q>>16)，要分解N。
第二关：知道前后缀、密文以及带前后缀的密文，求明文。
一开始注意到P的高位字节已知，想用coppersmith求，但发现未知的位数太多，遂放弃。
从第0位一直到第495位每一位的组合只有两种情况，并且可以部分检验(l是部分bit长)：
∗ ( m o d l ) = P ∗ Q ( m o d l ) = N ( m o d l ) \bar{P}*\bar{Q}\pmod{2^l}=P*Q\pmod{2^l}=N\pmod{2^l} P ˉ ∗ Q ˉ ( mod 2 l ) = P ∗ Q ( mod 2 l ) = N ( mod 2 l )
直接进行一个深度优先的搜索。
Q的低16位完全未知，只能纯粹枚举。
然后是一个明文相关的板子题，使用多项式求gcd的方式求解，明文的长度需要枚举哈。
注意这里有一点比较坑，n求解之后长度只有1020完全不够，需要加上N，卡了我很久(如果加上2*N长度就超过了)。
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
from sage.all import *
from Crypto.Util.number import *
N = 75000029602085996700582008490482326525611947919932949726582734167668021800854674616074297109962078048435714672088452939300776268788888016125632084529419230038436738761550906906671010312930801751000022200360857089338231002088730471277277319253053479367509575754258003761447489654232217266317081318035524086377
gift = 8006730615575401350470175601463518481685396114003290299131469001242636369747855817476589805833427855228149768949773065563676033514362512835553274555294034
cn = 14183763184495367653522884147951054630177015952745593358354098952173965560488104213517563098676028516541915855754066719475487503348914181674929072472238449853082118064823835322313680705889432313419976738694317594843046001448855575986413338142129464525633835911168202553914150009081557835620953018542067857943
def nextP(Pstr, Qstr):
l = len(Pstr)
if l == 512:
P = int(Pstr, 2)
Q = int(Qstr, 2)
if P * Q == N:
print(f"P={P}\nQ={Q}")
elif l == 0:
assert(len(Qstr) == 16)
Qbar = int(Qstr, 2)
b = (gift >> l) & 1
if b == 0:
nextP('1', '1' + Qstr)
nextP('0', '0' + Qstr)
else:
nextP('1', '0' + Qstr)
nextP('0', '1' + Qstr)
else:
Pbar = int(Pstr, 2)
Qbar = int(Qstr, 2)
if (Pbar * Qbar) % (2**l) == N % (2**l):
b = (gift >> l) & 1
if b == 0:
nextP('1' + Pstr, '1' + Qstr)
nextP('0' + Pstr, '0' + Qstr)
else:
nextP('1' + Pstr, '0' + Qstr)
nextP('0' + Pstr, '1' + Qstr)
for Qlow in range(1<<16, 1<<17):
Qbar = bin(Qlow)[3:]
nextP('', Qbar)
e = 11
P = 8006847171912577069085166877758626954304824756138758266557706391662987806065132448544117840031499707938227955094109779732609035310252723066470330862622641
Q = 9366986529377069783394625848920106951220134111548343265311677163992169555436421569730703291128771472885865288798344038000984911921843088200997725324682297
Phi = (P - 1) * (Q - 1)
D = int(inverse_mod(e, Phi))
n = pow(cn, D, N)
n += N
prefix = b"dasctf{"
suffix = b"}"
n = 83410392685813224685786027640778560521035854332627839979281105731457044069408118952629284089869335506983096270269822559619624906180108256504440296527471536363057103101146262613593336072556587341466840510200003498265457285439149541137127199088938421905041387224795918868443175561632999479925818053898100117419
e = 11
c1 = 69307306970629523181683439240748426263979206546157895088924929426911355406769672385984829784804673821643976780928024209092360092670457978154309402591145689825571209515868435608753923870043647892816574684663993415796465074027369407799009929334083395577490711236614662941070610575313972839165233651342137645009
c2 = 46997465834324781573963709865566777091686340553483507705539161842460528999282057880362259416654012854237739527277448599755805614622531827257136959664035098209206110290879482726083191005164961200125296999449598766201435057091624225218351537278712880859703730566080874333989361396420522357001928540408351500991
def rsa_cpa(c1, c2, m0, e, n):
x = PolynomialRing(Zmod(n), 'x').gen()
shift = 8*len(suffix)
g1 = x**e - c1
g2 = (x*2**shift+m0)**e - c2
while g2:
g1, g2 = g2, g1 % g2
f = g1.monic()
return int(-f[0])
for msglen in range(10, 50):
m0 = bytes_to_long(prefix + b'\x00' * msglen + suffix)
m = rsa_cpa(c1, c2, m0, e, n)
try:
flag = long_to_bytes(m).decode()
assert msglen == len(flag)
print(prefix.decode() + flag + suffix.decode())
except:
continue
dasctf{C0pper_Sm1th_Mak3s_T1ng5_Bet4er}
ezDHKE
DHKE is easy, huh?
Diffie Hellman密钥交换的模数任选，令 p = g k − p = g^k - 1 p = g k − 1 g x ≡ g x m o d k ( m o d p ) g^x \equiv g^{x \bmod k} \pmod p g x ≡ g x mod k ( mod p )
所以
= g x m o d k = x \log_gC_x = \log_gg^{x \bmod k} = x log g C x = log g g x mod k = x
= g y m o d k = y \log_gC_y = \log_gg^{y \bmod k} = y log g C y = log g g y mod k = y
(k取的比较大)。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
from Crypto.Util.number import *
from Crypto.Cipher import AES
from hashlib import sha256
from random import randbytes, getrandbits
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个质数pqr，p长512bit，q长256bit，r长256bit，乘积为n，n给定。
随机摇一个32bit的t，输出密文:
= + ( p + t ) + ( p + t ) + ( p + t ) + ( p + t ) ( m o d n ) c_1 = 1997 + (p+t) + (p+t)^2 + (p+t)^3 + (p+t)^4 \pmod n c 1 = 1997 + ( p + t ) + ( p + t ) 2 + ( p + t ) 3 + ( p + t ) 4 ( mod n )
= + ( m t ) + ( m t ) + . . . + ( m t ) ( m o d q ) c_2 = 1997 + (mt) + (mt)^2 + ... + (mt)^{19} \pmod q c 2 = 1997 + ( m t ) + ( m t ) 2 + ... + ( m t ) 19 ( mod q )
= + ( m + t ) + ( m + t ) + . . . + ( m + t ) ( m o d q ) c_3 = 1997 + (m+t) + (m+t)^2 + ... + (m+t)^{19} \pmod q c 3 = 1997 + ( m + t ) + ( m + t ) 2 + ... + ( m + t ) 19 ( mod q )
注意到f ( t ) = + t + t + t + t − c = ( m o d p ) f(t) = 1997 + t + t^2 + t^3 + t^4 - c1 = 0 \pmod p f ( t ) = 1997 + t + t 2 + t 3 + t 4 − c 1 = 0 ( mod p )
可以求小根，根据coppersmith方法有
< = n − ϵ , ϵ = < = β , p > = n β t_0<=\frac{1}{2} n^{\frac{\beta^2}{\delta}-\epsilon},\epsilon=\frac{\beta}{\gamma}<=\frac{1}{7}\beta,p>=n^\beta t 0 <= 2 1 n δ β 2 − ϵ , ϵ = γ β <= 7 1 β , p >= n β
δ \delta δ β \beta β
t有32bit，n有1024bit，大约解得γ > = \gamma>=16.5 γ >= 16.5
得到t后，带入f(t)的公式和n作gcd，得到p，将n缩为qr的乘积。
令
( m ) = + ( m t ) + ( m t ) + . . . + ( m t ) − c g_1(m)=1997+(mt)+(mt)^2+...+(mt)^{19}-c2 g 1 ( m ) = 1997 + ( m t ) + ( m t ) 2 + ... + ( m t ) 19 − c 2
( m ) = + ( m + t ) + ( m + t ) + . . . + ( m + t ) − c g_2(m)=1997+(m+t)+(m+t)^2+...+(m+t)^{19}-c3 g 2 ( m ) = 1997 + ( m + t ) + ( m + t ) 2 + ... + ( m + t ) 19 − c 3
现在，在Z / n Z [ x ] \Z/n\Z[x] Z / n Z [ x ]
( m ) = ( m ) − ( m ) \bar{g_1}(m)=g_1(m)-g_2(m) g 1 ˉ ( m ) = g 1 ( m ) − g 2 ( m )
( m ) = ( m ) − m ( m ) \bar{g_2}(m)=g_2(m)-m\bar{g_1}(m) g 2 ˉ ( m ) = g 2 ( m ) − m g 1 ˉ ( m )
如果g1，g2同次数且都是首一多项式，进行该过程后次数均递减。
不断地进行这个过程，最后要么出现g1为常数且是q的倍数，
无论哪种情况，将其和n作gcd得到q和r。
有了q之后，在Z / p Z [ x ] \Z/p\Z[x] Z / p Z [ x ] m + m+m_0 m + m 0
然后，令m = − + i q m=-m_0+iq m = − m 0 + i q
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
from sage.all import *
from Crypto.Util.number import *
n = 119156144845956004769507478085325079414190248780654060840257869477965140304727088685316579445017214576182010373548273474121727778923582544853293534996805340795355149795694121455249972628980952137874014208209750135683003125079012121116063371902985706907482988687895813788980275896804461285403779036508897592103
c1 = 185012145382155564763088060801282407144264652101028110644849089283749320447842262397065972319766119386744305208284231153853897076876529326779092899879401876069911627013491974285327376378421323298147156687497709488102574369005495618201253946225697404932436143348932178069698091761601958275626264379615139864425
c2 = 722022978284031841958768129010024257235769706227005483829360633993196299360813
c3 = 999691052172645326792013409327337026208773437618455136594949462410165608463231
t = Zmod(n)['t'].gen()
f1 = 1997 + t + t**2 + t**3 + t**4 - c1
t0 = f1.small_roots(beta=0.5, epsilon=0.5/17)[0]
assert len(bin(t0)[2:]) == 32
p0 = gcd(int(f1(t0)), n)
assert len(bin(p0)[2:]) == 512 and n % p0 == 0
t = 2915836867
p = 12674045065380963936369006640913707206092165254372327547575287589116533343005456615635388048683828685030860153531390706945709086518510926980644275915726413
n = n // p
m = Zmod(n)['m'].gen()
f2 = 0*m+1997-c2
f3 = 0*m+1997-c3
for i in range(1, 20):
f2 += (t*m)**i
f3 += (t+m)**i
f2, f3 = f2.monic(), f3.monic()
try:
while True:
f2 = f2 - f3
f2 = f2.monic()
f3 = f3 - m*f2
f3 = f3.monic()
except:
a = int(list(f2)[-1])
q = gcd(a, n)
if q == 1:
a = int(list(f3)[-1])
q = gcd(a, n)
assert len(bin(q)[2:]) == 256 and n % q == 0
r = n // q
assert len(bin(r)[2:]) == 256 and n % r == 0
q = 87038069032840052005520908272237788908169043580221040711149494083975743478969
r = 108016959681605076830977486416860687442307791371372085930591884056258926759899
m = Zmod(q)['m'].gen()
f2 = 0*m+1997-c2
f3 = 0*m+1997-c3
for i in range(1, 20):
f2 += (t*m)**i
f3 += (t+m)**i
while f3:
f2, f3 = f3, f2 % f3
fm = f2.monic()
m0 = int(-fm[0])
m = 56985796272753226120469211992443340429346162287195965942430959147227534853120
assert(m < q)
for _ in range(2**24):
try:
print(long_to_bytes(m).decode())
break
except:
m += q
continue
dasctf{ShangPoXiaPoYaSiLeYiQianDuo}
如果你知道这个梗，甚至可以猜出flag
完结撒花
[招生]科锐逆向工程师培训(2024年11月15日实地，远程教学同时开班, 第51期)
最后于 2024-1-29 22:58
被狗敦子编辑
，原因： 修改了一些内容
上传的附件：
