羊城杯 2023 Wp（复现）
NSS刷题复现笔记，过程写的可能比较简单，有问题欢迎指出交流(・∀・)つ⑩
esyRSA
题目：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18from gmpy2 import invert
from md5 import md5
from hashlib import md5
from secret import p, q
e = ?????
n = p*q
phi = (p-1)*(q-1)
d = invert(e, phi)
ans = gcd(e,phi)
print n, e, d
print "Flag: DASCTF{%s}" %md5(str(p + q)).hexdigest()
"""
n = 8064259277274639864655809758868795854117113170423331934498023294296505063511386001711751916634810056911517464467899780578338013011453082479880809823762824723657495915284790349150975180933698827382368698861967973964030509129133021116919437755292590841218316278732797712538885232908975173746394816520256585937380642592772746398646558097588687958541171131704233319344980232942965050635113860017117519166348100569115174644678997805783380130114530824798808098237628247236574959152847903491509751809336988273823686988619679739640305091291330211169194377552925908412183162787327977125388852329089751737463948165202565859373
d = 14218766449983537783699024084862960813708451888387858392014856544340557703876299258990323621963898510226357248200187173211121827541826897886277531706124228848229095880229718049075745233893843373402201077890407507625110061976931591596708901741146750809962128820611844426759462132623616118530705745098783140913
"""
分析：
维纳攻击，把d当作原本的e就行，进行连分数展开便能求解。
值得注意的是，本题附件存在问题，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#sage
from hashlib import md5
def wiener(N:int, d:int, debug = True):
N = Integer(N)
d = Integer(d)
cf = (d / N).continued_fraction().convergents()
for f in cf:
k = f.numer()
e = f.denom()
if k == 0:
continue
phi_N = int(ceil((e * d / k) - 1))
b = -(N - phi_N + 1)
delta = b ^ 2 - 4 * N
if delta >= 0:
delta_sqrt = sqrt(delta)
p = (-b + delta_sqrt) / 2
q = (-b - delta_sqrt) / 2
if p.is_integer() and q.is_integer() and (p * q) % N == 0:
if debug:
p = int(p % N)
q = int(q % N)
return p, q
n = 80642592772746398646558097588687958541171131704233319344980232942965050635113860017117519166348100569115174644678997805783380130114530824798808098237628247236574959152847903491509751809336988273823686988619679739640305091291330211169194377552925908412183162787327977125388852329089751737463948165202565859373
d = 14218766449983537783699024084862960813708451888387858392014856544340557703876299258990323621963898510226357248200187173211121827541826897886277531706124228848229095880229718049075745233893843373402201077890407507625110061976931591596708901741146750809962128820611844426759462132623616118530705745098783140913
p,q = wiener(n,d)
print("Flag: DASCTF{%s}" %md5(str(p + q).encode()).hexdigest())
Danger_RSA
题目：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
27from Crypto.Util.number import *
m = bytes_to_long(flag)
def get_key(a, nbit):
assert a >= 2
while True:
X = getRandomInteger(nbit // a)
s = getRandomRange(pow(2, a ** 2 - a + 4), pow(2, a ** 2 - a + 5))
p = X ** a + s
if isPrime(p):
return (p, s)
p, s = get_key(a, 1024)
q, t = get_key(a, 1024)
N = p * q
e = s * t
c = pow(m, e, N)
print("N =", N)
print("e =", e)
print("c =", c)
# N = 20289788565671012003324307131062103060859990244423187333725116068731043744218295859587498278382150779775620675092152011336913225797849717782573829179765649320271927359983554162082141908877255319715400550981462988869084618816967398571437725114356308935833701495015311197958172878812521403732038749414005661189594761246154666465178024563227666440066723650451362032162000998737626370987794816660694178305939474922064726534186386488052827919792122844587807300048430756990391177266977583227470089929347969731703368720788359127837289988944365786283419724178187242169399457608505627145016468888402441344333481249304670223
# e = 11079917583
# c = 13354219204055754230025847310134936965811370208880054443449019813095522768684299807719787421318648141224402269593016895821181312342830493800652737679627324687428327297369122017160142465940412477792023917546122283870042482432790385644640286392037986185997262289003477817675380787176650410819568815448960281666117602590863047680652856789877783422272330706693947399620261349458556870056095723068536573904350085124198592111773470010262148170379730937529246069218004969402885134027857991552224816835834207152308645148250837667184968030600819179396545349582556181916861808402629154688779221034610013350165801919342549766
分析：
已知X = getRandomInteger(nbit // a)，则有$2\leq a \leq 1024$
已知s = getRandomRange(pow(2, a ** 2 - a + 4), pow(2, a ** 2 - a + 5))，则有$2^{a^2-a+4}\leq s \leq 2^{a^2-a+5}$
同时e分解可以得到$e = 3\cdot 7 \cdot 7 \cdot 19 \cdot 691 \cdot 5741，且2^{33}\leq e \leq 2^{34}$
尝试不同的a的值：
- a=2时，$2^4\leq s \leq 2^5$
- a=3时，$2^{10} \leq s \leq 2^{11}$
- a=4时，$2^{16}\leq s \leq 2^{17}$
结合e的取值范围，可以得到$a=4$
之后对e的因子进行排列组合拆成两组，可以发现有两种组合
- $s = 5741\cdot 19,t=691\cdot 3 \cdot 7 \cdot 7$
- $s=5741\cdot 3 \cdot 7,t=691\cdot 7 \cdot 19$
$\therefore N=(X_1^4+s)(X_2^4+t)$
$\because X_1^4X_2^4 >> tX_1^4+sX_2^4+st$
$\therefore gmpy2.iroot(N,4)[0] = X_1X_2$
$\therefore$两个未知数两个方程，列方程组求解即可得到$p,q$
但是后续求解出$p,q$后会发现$e$和$phi$不互素，后来尝试后发现$3|(p-1),7|(q-1)$，由于明文的比特一般不会大于$p$的1024比特，因此尝试在模$p$下求解，将$m^3$当作整体，求$d=invert(e//3,p-1)$，最后求出$m^3$再在模$p$下求根即可。
解答：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#sage
import gmpy2
from sympy import symbols, Eq, solve
from sympy import totient
from Crypto.Util.number import *
N = 20289788565671012003324307131062103060859990244423187333725116068731043744218295859587498278382150779775620675092152011336913225797849717782573829179765649320271927359983554162082141908877255319715400550981462988869084618816967398571437725114356308935833701495015311197958172878812521403732038749414005661189594761246154666465178024563227666440066723650451362032162000998737626370987794816660694178305939474922064726534186386488052827919792122844587807300048430756990391177266977583227470089929347969731703368720788359127837289988944365786283419724178187242169399457608505627145016468888402441344333481249304670223
e = 11079917583
c = 13354219204055754230025847310134936965811370208880054443449019813095522768684299807719787421318648141224402269593016895821181312342830493800652737679627324687428327297369122017160142465940412477792023917546122283870042482432790385644640286392037986185997262289003477817675380787176650410819568815448960281666117602590863047680652856789877783422272330706693947399620261349458556870056095723068536573904350085124198592111773470010262148170379730937529246069218004969402885134027857991552224816835834207152308645148250837667184968030600819179396545349582556181916861808402629154688779221034610013350165801919342549766
x, y = symbols('x y', real=True, positive=True)
S = [5741*19,5741*3*7]
T = [691*3*7*7,691*19*7]
for s,t in zip(S,T):
#print(s*t)
eq1 = Eq((x**4+s)*(y**4+t), N)
eq2 = Eq(x*y,gmpy2.iroot(N,4)[0])
sol = solve((eq1, eq2), (x, y))
for root in sol:
a = int(root[0])
b = int(root[1])
p = int(a**4+s)
q = int(b**4+t)
if a > 0 and b > 0 and p*q == N:
#print(sol)
#print(s,t)
#print(p,q)
#转为在模p下求解
phi = p-1
g = gmpy2.gcd(e,phi)
t = e//g
d = gmpy2.invert(t,phi)
#print(g)
m3 = pow(c,d,p)
P.<m> = PolynomialRing(Zmod(p))
f = m^3 - m3
roots = f.roots()
for r in roots:
m_can = int(r[0])
ans = long_to_bytes(m_can)
if b'CTF' in ans:
print(ans)
exit()
break
Easy_3L
题目：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
57from gmpy2 import *
from Crypto.Util.number import *
from secret import flag
m = bytes_to_long(flag)
def get_key():
p = getPrime(1400)
f = getRandomNBitInteger(1024)
while True:
q = getPrime(512)
if gcd(f, q) != 1:
continue
else:
break
h = (invert(f, p) * q) % p
return p, h
def encrypt1(m):
a = getPrime(250)
b = getRandomNBitInteger(240)
n = getPrime(512)
seed = m
s = [0] * 6
s[0] = seed
for i in range(1, 6):
s[i] = (s[i - 1] * a + b) % n
return s
def encrypt2(msg, p, h):
s = getRandomNBitInteger(512)
c = (s * h + msg) % p
return c
s = encrypt1(m)
print("S1 =", s[1])
print("S2 =", s[2])
print("S4 =", s[4])
print("S5 =", s[5])
p, h = get_key()
c = encrypt2(s[3], p, h)
print("p =", p)
print("h =", h)
print("c =", c)
# S1 = 28572152986082018877402362001567466234043851789360735202177142484311397443337910028526704343260845684960897697228636991096551426116049875141
# S2 = 1267231041216362976881495706209012999926322160351147349200659893781191687605978675590209327810284956626443266982499935032073788984220619657447889609681888
# S4 = 9739918644806242673966205531575183334306589742344399829232076845951304871478438938119813187502023845332528267974698273405630514228632721928260463654612997
# S5 = 9755668823764800147393276745829186812540710004256163127825800861195296361046987938775181398489372822667854079119037446327498475937494635853074634666112736
# p = 25886434964719448194352673440525701654705794467884891063997131230558866479588298264578120588832128279435501897537203249743883076992668855905005985050222145380285378634993563571078034923112985724204131887907198503097115380966366598622251191576354831935118147880783949022370177789175320661630501595157946150891275992785113199863734714343650596491139321990230671901990010723398037081693145723605154355325074739107535905777351
# h = 2332673914418001018316159191702497430320194762477685969994411366563846498561222483921873160125818295447435796015251682805613716554577537183122368080760105458908517619529332931042168173262127728892648742025494771751133664547888267249802368767396121189473647263861691578834674578112521646941677994097088669110583465311980605508259404858000937372665500663077299603396786862387710064061811000146453852819607311367850587534711
# c = 20329058681057003355767546524327270876901063126285410163862577312957425318547938475645814390088863577141554443432653658287774537679738768993301095388221262144278253212238975358868925761055407920504398004143126310247822585095611305912801250788531962681592054588938446210412897150782558115114462054815460318533279921722893020563472010279486838372516063331845966834180751724227249589463408168677246991839581459878242111459287
Part1：NTRU求S3
已知（1）$c\equiv sh + s_3 \mod p$
还有（2）$h \equiv f^{-1}*q \mod p$
（1）两边同时乘以$f$，有$cf\equiv sq + s_3f\mod p$
再对$q$取模得，$cf\equiv s_3f \mod q$，令$a=cf$，则有$a\equiv s_3f \mod q$
因此我们要求$(f,q)$
根据$hf\equiv q\mod p$构造格：
求得$s_3$
Part2：LCG求seed
利用已知连续5个序列值先求模$n$，方法如下：
$m=gcd(t_{n+1}t_{n-1} - t_n^2,t_{n+2}t_{n} - t_{n+1}^2 )$
具体推导可以看我另一篇博客：Crypto基础篇-LCG Ramoor
再求$a,b,seed$即可
解答：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
40from Crypto.Util.number import *
S1 = 28572152986082018877402362001567466234043851789360735202177142484311397443337910028526704343260845684960897697228636991096551426116049875141
S2 = 1267231041216362976881495706209012999926322160351147349200659893781191687605978675590209327810284956626443266982499935032073788984220619657447889609681888
S4 = 9739918644806242673966205531575183334306589742344399829232076845951304871478438938119813187502023845332528267974698273405630514228632721928260463654612997
S5 = 9755668823764800147393276745829186812540710004256163127825800861195296361046987938775181398489372822667854079119037446327498475937494635853074634666112736
p = 25886434964719448194352673440525701654705794467884891063997131230558866479588298264578120588832128279435501897537203249743883076992668855905005985050222145380285378634993563571078034923112985724204131887907198503097115380966366598622251191576354831935118147880783949022370177789175320661630501595157946150891275992785113199863734714343650596491139321990230671901990010723398037081693145723605154355325074739107535905777351
h = 2332673914418001018316159191702497430320194762477685969994411366563846498561222483921873160125818295447435796015251682805613716554577537183122368080760105458908517619529332931042168173262127728892648742025494771751133664547888267249802368767396121189473647263861691578834674578112521646941677994097088669110583465311980605508259404858000937372665500663077299603396786862387710064061811000146453852819607311367850587534711
c = 20329058681057003355767546524327270876901063126285410163862577312957425318547938475645814390088863577141554443432653658287774537679738768993301095388221262144278253212238975358868925761055407920504398004143126310247822585095611305912801250788531962681592054588938446210412897150782558115114462054815460318533279921722893020563472010279486838372516063331845966834180751724227249589463408168677246991839581459878242111459287
M = Matrix(ZZ,[[1,h],[0,p]])
L = M.LLL()[0]
f , q = L
f = abs(f)
q = abs(q)
print(f,q)
a = (c*f) %p
S3 = a*inverse(f,q)%q
#print(S3.nbits())
#求模n
X_seq=[S1,S2,S3,S4,S5]
t=[]
for i in range(len(X_seq)-1):
t.append(X_seq[i+1]-X_seq[i])
T=[] #T_i=T_ip2 * T_i - T_ip1**2
for i in range(len(t)-2):
T.append(t[i+2]*t[i]-t[i+1]**2)
n=GCD(T[0],T[1]) #n的候选值
for i in range(2,len(T)):
n=GCD(n,T[i])
print(n)
#求a,b,seed
a=inverse(S2-S1,n)*(S3-S2) %n
b=S2-a*S1 %n
m = inverse(a,n)*(S1-b) %n
print(long_to_bytes(m))
XOR贯穿始终
massage.txt:1
自由和谐和谐富强公正友善爱国公正法治法治文明和谐自由法治自由法治平等公正友善公正公正民主法治自由公正敬业和谐富强公正友善爱国和谐平等平等友善敬业法治敬业和谐富强法治平等平等友善敬业公正公正公正友善敬业法治平等平等诚信自由公正自由平等友善敬业公正友善法治和谐和谐
社会主义核心价值观编码解码得到1
C0ngr4tulati0n5_y0u_fou^d_m3
将其作为压缩包密码进行解压缩
pri.pem1
2
3
4
5
6
7
8
9
10
11
12-----BEGIN PRIVATE KEY-----
MIICdwIBADANBgkqhkiG9w0BAQEFAASCAmEwggJdAgEAAoGBALmtMy+2uH1ZtbIL
SuiAukFthyQRH5mp7UmLyzZQkdg9zEP9/5tgffikQ7ytx5kHySHnazgAO1sOzmYE
N4Axlev6uafiP8B1Eij97v5VkYJ1I9e3mtBNheTbXKoT8op+ASQ1fQaF4A8UzLuW
eZeZI8JTH/SH+bolAK3kiZXDFdkTAgMBAAECgYEAl067LaC7Cvs2A5cMPhfYsESv
IgcKN1CwW4Sd3u8dSphhgu7TgyzIuvwxbuo2g1BC6WwKhaI6vGN+csfw6nh98GEn
/p3D0huNroAYvf/DRRB9UnHdttX7wB+Mv3P0RBDWHgBiCDVvHFuFUV78cIs0tnbn
jxjU07aPV2XRC3AfA2ECQQDqWUNPVg3i6vTyHCL7EGkbeUheYpAAfcKCQrxjc5+5
X6A+XtgHAA1JHwykPlCpHUOmlA85DJF1ejuoImzlgRLJAkEAytTCnQF+MN2r1gaA
UETZyj5qMYT7Th8zKEVVVJjDawLnuX4usJ2FyRnjCkk86U75QSJhw5mMc0QnG25u
Gz3++w==
-----END PRIVATE KEY-----
task.py1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18from gmpy2 import gcd
from Crypto.Util.number import getPrime
from secret import enflag
p = getPrime(512)
q = getPrime(512)
n = q * p
phi = (p - 1) * (q - 1)
e = getPrime(17)
assert gcd(e, phi) == 1
# 以上信息生成了私钥文件,但文件被损坏了你能提取有用信息吗
c = pow(enflag, e, n)
print('c = ' + str(c))
'''
c = 91817924748361493215143897386603397612753451291462468066632608541316135642691873237492166541761504834463859351830616117238028454453831120079998631107520871612398404926417683282285787231775479511469825932022611941912754602165499500350038397852503264709127650106856760043956604644700201911063515109074933378818
'''
提示私钥文件被损坏，因此我们首先对私钥文件进行base64解码并转换为十六进制数据1
30 82 02 77 02 01 00 30 0d 06 09 2a 86 48 86 f7 0d 01 01 01 05 00 04 82 02 61 30 82 02 5d 02 01 00 02 81 81 00 b9 ad 33 2f b6 b8 7d 59 b5 b2 0b 4a e8 80 ba 41 6d 87 24 11 1f 99 a9 ed 49 8b cb 36 50 91 d8 3d cc 43 fd ff 9b 60 7d f8 a4 43 bc ad c7 99 07 c9 21 e7 6b 38 00 3b 5b 0e ce 66 04 37 80 31 95 eb fa b9 a7 e2 3f c0 75 12 28 fd ee fe 55 91 82 75 23 d7 b7 9a d0 4d 85 e4 db 5c aa 13 f2 8a 7e 01 24 35 7d 06 85 e0 0f 14 cc bb 96 79 97 99 23 c2 53 1f f4 87 f9 ba 25 00 ad e4 89 95 c3 15 d9 13 02 03 01 00 01 02 81 81 00 97 4e bb 2d a0 bb 0a fb 36 03 97 0c 3e 17 d8 b0 44 af 22 07 0a 37 50 b0 5b 84 9d de ef 1d 4a 98 61 82 ee d3 83 2c c8 ba fc 31 6e ea 36 83 50 42 e9 6c 0a 85 a2 3a bc 63 7e 72 c7 f0 ea 78 7d f0 61 27 fe 9d c3 d2 1b 8d ae 80 18 bd ff c3 45 10 7d 52 71 dd b6 d5 fb c0 1f 8c bf 73 f4 44 10 d6 1e 00 62 08 35 6f 1c 5b 85 51 5e fc 70 8b 34 b6 76 e7 8f 18 d4 d3 b6 8f 57 65 d1 0b 70 1f 03 61 02 41 00 ea 59 43 4f 56 0d e2 ea f4 f2 1c 22 fb 10 69 1b 79 48 5e 62 90 00 7d c2 82 42 bc 63 73 9f b9 5f a0 3e 5e d8 07 00 0d 49 1f 0c a4 3e 50 a9 1d 43 a6 94 0f 39 0c 91 75 7a 3b a8 22 6c e5 81 12 c9 02 41 00 ca d4 c2 9d 01 7e 30 dd ab d6 06 80 50 44 d9 ca 3e 6a 31 84 fb 4e 1f 33 28 45 55 54 98 c3 6b 02 e7 b9 7e 2e b0 9d 85 c9 19 e3 0a 49 3c e9 4e f9 41 22 61 c3 99 8c 73 44 27 1b 6e 6e 1b 3d fe fb
按照顺序各个部分得特点进行拆分：
02 81 81表示0x81即129字节的模数n：00 b9 ad 33 2f b6 b8 7d 59 b5 b2 0b 4a e8 80 ba 41 6d 87 24 11 1f 99 a9 ed 49 8b cb 36 50 91 d8 3d cc 43 fd ff 9b 60 7d f8 a4 43 bc ad c7 99 07 c9 21 e7 6b 38 00 3b 5b 0e ce 66 04 37 80 31 95 eb fa b9 a7 e2 3f c0 75 12 28 fd ee fe 55 91 82 75 23 d7 b7 9a d0 4d 85 e4 db 5c aa 13 f2 8a 7e 01 24 35 7d 06 85 e0 0f 14 cc bb 96 79 97 99 23 c2 53 1f f4 87 f9 ba 25 00 ad e4 89 95 c3 15 d9 1302 03表示e：01 00 01即e=6553702 81 81表示0x81即129字节的私钥指数d：00 97 4e bb 2d a0 bb 0a fb 36 03 97 0c 3e 17 d8 b0 44 af 22 07 0a 37 50 b0 5b 84 9d de ef 1d 4a 98 61 82 ee d3 83 2c c8 ba fc 31 6e ea 36 83 50 42 e9 6c 0a 85 a2 3a bc 63 7e 72 c7 f0 ea 78 7d f0 61 27 fe 9d c3 d2 1b 8d ae 80 18 bd ff c3 45 10 7d 52 71 dd b6 d5 fb c0 1f 8c bf 73 f4 44 10 d6 1e 00 62 08 35 6f 1c 5b 85 51 5e fc 70 8b 34 b6 76 e7 8f 18 d4 d3 b6 8f 57 65 d1 0b 70 1f 03 61
使用脚本获取m：1
2
3
4
5
6
7d = 0x00974ebb2da0bb0afb3603970c3e17d8b044af22070a3750b05b849ddeef1d4a986182eed3832cc8bafc316eea36835042e96c0a85a23abc637e72c7f0ea787df06127fe9dc3d21b8dae8018bdffc345107d5271ddb6d5fbc01f8cbf73f44410d61e006208356f1c5b85515efc708b34b676e78f18d4d3b68f5765d10b701f0361
e = 0x10001
n = 0x00b9ad332fb6b87d59b5b20b4ae880ba416d8724111f99a9ed498bcb365091d83dcc43fdff9b607df8a443bcadc79907c921e76b38003b5b0ece660437803195ebfab9a7e23fc0751228fdeefe5591827523d7b79ad04d85e4db5caa13f28a7e0124357d0685e00f14ccbb9679979923c2531ff487f9ba2500ade48995c315d913
c = 91817924748361493215143897386603397612753451291462468066632608541316135642691873237492166541761504834463859351830616117238028454453831120079998631107520871612398404926417683282285787231775479511469825932022611941912754602165499500350038397852503264709127650106856760043956604644700201911063515109074933378818
from Crypto.Util.number import *
m = pow(c,d,n)
print(long_to_bytes(m))
获取明文m：1
DASCTF{0e287wQ\x08R\x17\x00FGXYFZ\x07V\x03kIUCn\x02VDg\x01f\x0cN
发现后半段没正常显示，根据题目猜测需要将第一步得到的字符串和该串进行异或1
2
3b = b'C0ngr4tulati0n5_y0u_fou^d_m3'
ans = bytes_to_long(b) ^ m
print(long_to_bytes(ans))
得到：1
DASCTF{0e2874af5e422482378640e61d919e9a}
SigninCrypto
题目：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
70from random import *
from Crypto.Util.number import *
from Crypto.Cipher import DES3
from flag import flag
from key import key
from iv import iv
import os
import hashlib
import secrets
K1= key
hint1 = os.urandom(2) * 8
xor =bytes_to_long(hint1)^bytes_to_long(K1)
print(xor)
def Rand():
rseed = secrets.randbits(1024)
List1 = []
List2 = []
seed(rseed)
for i in range(624):
rand16 = getrandbits(16)
List1.append(rand16)
seed(rseed)
for i in range(312):
rand64 = getrandbits(64)
List2.append(rand64)
with open("task.txt", "w") as file:
for rand16 in List1:
file.write(hex(rand16)+ "\n")
for rand64 in List2:
file.write(hex((rand64 & 0xffff) | ((rand64 >> 32) & 0xffff) << 16) + "\n")
Rand()
K2 = long_to_bytes(getrandbits(64))
K3 = flag[:8]
KEY = K1 + K2 + K3
IV=iv
IV1=IV[:len(IV)//2]
IV2=IV[len(IV)//2:]
digest1 = hashlib.sha512(IV1).digest().hex()
digest2 = hashlib.sha512(IV2).digest().hex()
digest=digest1+digest2
hint2=(bytes_to_long(IV)<<32)^bytes_to_long(os.urandom(8))
print(hex(bytes_to_long((digest.encode()))))
print(hint2)
mode = DES3.MODE_CBC
des3 = DES3.new(KEY, mode, IV)
pad_len = 8 - len(flag) % 8
padding = bytes([pad_len]) * pad_len
flag += padding
cipher = des3.encrypt(flag)
ciphertext=cipher.hex()
print(ciphertext)
# 334648638865560142973669981316964458403
# 0x62343937373634656339396239663236643437363738396663393438316230353665353733303939613830616662663633326463626431643139323130616333363363326631363235313661656632636265396134336361623833636165373964343533666537663934646239396462323666316236396232303539336438336234393737363465633939623966323664343736373839666339343831623035366535373330393961383061666266363332646362643164313932313061633336336332663136323531366165663263626539613433636162383363616537396434353366653766393464623939646232366631623639623230353933643833
# 22078953819177294945130027344
# a6546bd93bced0a8533a5039545a54d1fee647007df106612ba643ffae850e201e711f6e193f15d2124ab23b250bd6e1
分析：
根据题目分析，我们的主要目的是根据存在的漏洞恢复$key$和$IV$
Part1：恢复key
（1）恢复K1
使用long_to_bytes(xor)可以发现，前8个字节是四组重复的，符合$hint1$的特点，猜测$K1$应该只有8个字节，因此使用前八个字节异或上后8个字节便可以恢复$K1$
（2）恢复K2
对于MT19937提交624个32bit数，便能够预测后边的随机数，但题目中并没有直接给出624个32bit数。1
2
3
4for rand16 in List1:
file.write(hex(rand16)+ "\n")
for rand64 in List2:
file.write(hex((rand64 & 0xffff) | ((rand64 >> 32) & 0xffff) << 16) + "\n")
已知List1和List2都是从头开始生成的，且输出到文件中的list2序列是不完整的，只输出了每个$rand64$的[:16]和[32:48]。因此我们需要想想办法恢复出624个32bit数getrandbits(16)的生成规则是每次生成一个32bit数，再从这个32bit数中截取16位作为生成的随机数。
因此List1就是List2的缺失部分，我们可以通过拆分拼接List1和List2得到624个32bit数。
（3）恢复K3
K3为flag[:8]，已知前7个字节为DASCTF{，因此爆破一个字节便可以
Part2：恢复IV
（1）恢复IV1
$IV$共8个字节，而$hint2$为$IV$向左移动了4个字节之后和8个字节的随机字节进行异或，说明高4个字节，即$IV1$未参与运算，$hint2$的高4个字节便是$IV1$
（2）恢复IV2
根据（1）算出的$IV1$可以计算出$digest1$，同时题目给出了$digest$，在$digest$中去除$digest2$之后便剩下了$digest2$
。虽然我们这里只获得了$IV2$的哈希值，可能需要爆破，但是求出来之后我们发现$digest2=digest1$，我们默认不存在碰撞，即$IV2=IV1$
解答：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
63from Crypto.Util.number import *
from randcrack import RandCrack
from Crypto.Cipher import DES3
from pwn import xor
import hashlib
ciphertext = 0xa6546bd93bced0a8533a5039545a54d1fee647007df106612ba643ffae850e201e711f6e193f15d2124ab23b250bd6e1
#恢复IV1和IV2
dig = 0x62343937373634656339396239663236643437363738396663393438316230353665353733303939613830616662663633326463626431643139323130616333363363326631363235313661656632636265396134336361623833636165373964343533666537663934646239396462323666316236396232303539336438336234393737363465633939623966323664343736373839666339343831623035366535373330393961383061666266363332646362643164313932313061633336336332663136323531366165663263626539613433636162383363616537396434353366653766393464623939646232366631623639623230353933643833
dig_int = int(dig)
dig0 = long_to_bytes(dig_int).decode()
hint2 = 22078953819177294945130027344
IV1 = long_to_bytes(hint2>>64)
print(IV1)
dig1 = hashlib.sha512(IV1).digest().hex()
if dig1 == dig0[:len(dig1)]:
dig2 = dig0[len(dig1):]
#print(dig2)
IV2 = IV1
#恢复K1
xor1 = 334648638865560142973669981316964458403
xor_bytes = long_to_bytes(xor1)
K1 = xor(xor_bytes[:8], xor_bytes[8:])
#print(K1)
#恢复K2
rc = RandCrack()
file = open('task.txt','r')
lines = file.readlines()
List1 = lines[:624]
List2 = lines[624:]
#print(List1)
#print(List2)
List22 = []
for i in List2:
val = int(i.strip(),16)
low = val & 0xFFFF
high = (val >> 16) & 0xFFFF
List22.append(low)
List22.append(high)
#print(len(List22))
randlist = []
for i in range(624):
val = int(List1[i].strip(),16)
randlist.append(val << 16 | List22[i])
rc.submit(randlist[i])
K2 = long_to_bytes(rc.predict_getrandbits(64))
#print(K2)
#爆破K3并尝试解密
K3_t = bytes_to_long(b'DASCTF{')<<8
IV = IV1 + IV2
print(IV)
for i in range(2**8):
K3 = long_to_bytes(K3_t + i)
key = K1 + K2 + K3
#print(key)
des3 = DES3.new(key, DES3.MODE_CBC, IV)
decrypt = des3.decrypt(long_to_bytes(int(ciphertext)))
if b'DASCTF{' in decrypt:
print(decrypt)
break
MCeorpkpleer
题目：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
46from Crypto.Util.number import *
from secret import flag
def pubkey(list, m, w):
pubkey_list = []
for i in range(len(e_bin)):
pubkey_list.append(w * list[i] % m)
return pubkey_list
def e_cry(e, pubkey):
pubkey_list = pubkey
encode = 0
for i in range(len(e)):
encode += pubkey_list[i] * int(e[i]) % m
return encode
p = getPrime(1024)
q = getPrime(1024)
n = p * q
e = getPrime(64)
m = bytes_to_long(flag)
c = pow(m, e, n)
e_bin = (bin(e))[2:]
list = [pow(3, i) for i in range(len(e_bin))]
m = getPrime(len(bin(sum(list))) - 1)
w = getPrime(64)
pubkey = pubkey(list, m, w)
en_e = e_cry(e_bin, pubkey)
print('p = {}\n'
'n = {}\n'
'c = {}\n'
'pubkey = {}\n'
'en_e = {}'.format((p >> 435) << 435, n, c, pubkey, en_e))
'''
p = 139540788452365306201344680691061363403552933527922544113532931871057569249632300961012384092481349965600565669315386312075890938848151802133991344036696488204791984307057923179655351110456639347861739783538289295071556484465877192913103980697449775104351723521120185802327587352171892429135110880845830815744
n = 22687275367292715121023165106670108853938361902298846206862771935407158965874027802803638281495587478289987884478175402963651345721058971675312390474130344896656045501040131613951749912121302307319667377206302623735461295814304029815569792081676250351680394603150988291840152045153821466137945680377288968814340125983972875343193067740301088120701811835603840224481300390881804176310419837493233326574694092344562954466888826931087463507145512465506577802975542167456635224555763956520133324723112741833090389521889638959417580386320644108693480886579608925996338215190459826993010122431767343984393826487197759618771
c = 156879727064293983713540449709354153986555741467040286464656817265584766312996642691830194777204718013294370729900795379967954637233360644687807499775502507899321601376211142933572536311131955278039722631021587570212889988642265055045777870448827343999745781892044969377246509539272350727171791700388478710290244365826497917791913803035343900620641430005143841479362493138179077146820182826098057144121231954895739989984846588790277051812053349488382941698352320246217038444944941841831556417341663611407424355426767987304941762716818718024107781873815837487744195004393262412593608463400216124753724777502286239464
pubkey = [18143710780782459577, 54431132342347378731, 163293397027042136193, 489880191081126408579, 1469640573243379225737, 4408921719730137677211, 13226765159190413031633, 39680295477571239094899, 119040886432713717284697, 357122659298141151854091, 1071367977894423455562273, 3214103933683270366686819, 9642311801049811100060457, 28926935403149433300181371, 86780806209448299900544113, 260342418628344899701632339, 781027255885034699104897017, 2343081767655104097314691051, 7029245302965312291944073153, 21087735908895936875832219459, 63263207726687810627496658377, 189789623180063431882489975131, 569368869540190295647469925393, 1708106608620570886942409776179, 601827224419797931380408071500, 1805481673259393794141224214500, 893952418336266652976851386463, 2681857255008799958930554159389, 3523079163584485147344841221130, 1524252287869625983140881149316, 50264262166963219975822190911, 150792786500889659927466572733, 452378359502668979782399718199, 1357135078508006939347199154597, 4071405235524020818041597463791, 3169230503688232995231149877299, 462706308180869526799807117823, 1388118924542608580399421353469, 4164356773627825741198264060407, 3448085117999647764701149667147, 1299270151115113835209806487367, 3897810453345341505629419462101, 2648446157152195057994615872229, 3422845870014670444537026359650, 1223552407160181874717436564876, 3670657221480545624152309694628, 1966986461557807413563286569810, 1378466783231507511243038452393, 4135400349694522533729115357179, 3361215846199738142293703557463, 1038662335715384967987468158315, 3115987007146154903962404474945, 302975818554635252993570910761, 908927455663905758980712732283, 2726782366991717276942138196849, 3657854499533237101379593333510, 1928578295715881845245137486456, 1263242285705730806288591202331, 3789726857117192418865773606993, 2324195368467747797703678306905, 2450093503961328663664213663678, 2827787910442071261545819733997, 3960871129884299055190637944954, 2837628186769067706678271320788]
en_e = 31087054322877663244023458448558
'''
分析：
根据题目，可以发现，我们需要求$p_{low}$和$e$，其中$p_{low}$可以利用coppersmith定理来求解。
而对于$e$来说，观察$e_cry$发现它是将$e$的二进制的每一位用于背包加密了。
解答：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
54from Crypto.Util.number import *
en_e = 31087054322877663244023458448558
nbits=64
pubkey = [18143710780782459577, 54431132342347378731, 163293397027042136193, 489880191081126408579, 1469640573243379225737, 4408921719730137677211, 13226765159190413031633, 39680295477571239094899, 119040886432713717284697, 357122659298141151854091, 1071367977894423455562273, 3214103933683270366686819, 9642311801049811100060457, 28926935403149433300181371, 86780806209448299900544113, 260342418628344899701632339, 781027255885034699104897017, 2343081767655104097314691051, 7029245302965312291944073153, 21087735908895936875832219459, 63263207726687810627496658377, 189789623180063431882489975131, 569368869540190295647469925393, 1708106608620570886942409776179, 601827224419797931380408071500, 1805481673259393794141224214500, 893952418336266652976851386463, 2681857255008799958930554159389, 3523079163584485147344841221130, 1524252287869625983140881149316, 50264262166963219975822190911, 150792786500889659927466572733, 452378359502668979782399718199, 1357135078508006939347199154597, 4071405235524020818041597463791, 3169230503688232995231149877299, 462706308180869526799807117823, 1388118924542608580399421353469, 4164356773627825741198264060407, 3448085117999647764701149667147, 1299270151115113835209806487367, 3897810453345341505629419462101, 2648446157152195057994615872229, 3422845870014670444537026359650, 1223552407160181874717436564876, 3670657221480545624152309694628, 1966986461557807413563286569810, 1378466783231507511243038452393, 4135400349694522533729115357179, 3361215846199738142293703557463, 1038662335715384967987468158315, 3115987007146154903962404474945, 302975818554635252993570910761, 908927455663905758980712732283, 2726782366991717276942138196849, 3657854499533237101379593333510, 1928578295715881845245137486456, 1263242285705730806288591202331, 3789726857117192418865773606993, 2324195368467747797703678306905, 2450093503961328663664213663678, 2827787910442071261545819733997, 3960871129884299055190637944954, 2837628186769067706678271320788]
p_high = 139540788452365306201344680691061363403552933527922544113532931871057569249632300961012384092481349965600565669315386312075890938848151802133991344036696488204791984307057923179655351110456639347861739783538289295071556484465877192913103980697449775104351723521120185802327587352171892429135110880845830815744
n = 22687275367292715121023165106670108853938361902298846206862771935407158965874027802803638281495587478289987884478175402963651345721058971675312390474130344896656045501040131613951749912121302307319667377206302623735461295814304029815569792081676250351680394603150988291840152045153821466137945680377288968814340125983972875343193067740301088120701811835603840224481300390881804176310419837493233326574694092344562954466888826931087463507145512465506577802975542167456635224555763956520133324723112741833090389521889638959417580386320644108693480886579608925996338215190459826993010122431767343984393826487197759618771
c = 156879727064293983713540449709354153986555741467040286464656817265584766312996642691830194777204718013294370729900795379967954637233360644687807499775502507899321601376211142933572536311131955278039722631021587570212889988642265055045777870448827343999745781892044969377246509539272350727171791700388478710290244365826497917791913803035343900620641430005143841479362493138179077146820182826098057144121231954895739989984846588790277051812053349488382941698352320246217038444944941841831556417341663611407424355426767987304941762716818718024107781873815837487744195004393262412593608463400216124753724777502286239464
#格基规约解背包密码求e
A=Matrix(ZZ,nbits+1,nbits+1)
print(len(pubkey))
for i in range(nbits):
A[i,i]=2
A[i,-1]=pubkey[i]
for i in range(nbits+1):
A[-1,i]=1
A[-1,-1]=en_e
L=A.LLL()
for l in L:
f = 1
for i in l[:-1]:
if i != 1 and i !=-1:
f = 0
break
if f==0:
continue
else:
print(l)
r = list(l[:-1])
break
e_bin = ''
for i in range(len(r)):
if r[i] == -1:
e_bin = e_bin + '1' #观察首位是1还是-1，由于要保证e的位数，因此首位是什么，什么就是1
elif r[i] == 1 :
e_bin = e_bin + '0'
e = int(e_bin, 2)
print(e)
#coppersmith求p_low
pbits=1024
kbits=435
R.<x> = PolynomialRing(Zmod(n))
f = p_high + x
roots = f.small_roots(X=2^kbits,beta=0.4)
p = p_high + int(roots[0])
q = n // p
phi = (p-1) * (q-1)
d = inverse(e,phi)
m = pow(c,d,n)
ans= long_to_bytes(m)
print(ans)
