0%

2023-鹏城杯-wp-crypto

包含全四道赛题的题解

LeakyRSA

题目描述:

1
这个RSA好像泄露了什么?

题目:

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 *
from secret import flag

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

leakBits = 262
leak = (p ^ q) >> (nbits - leakBits)

n=p*q
e=65537
m = bytes_to_long(flag)
c = pow(m,e,n)
print(p)
print(q)
print("n=%d" %n)
print("c=%d" %c)
print("leak=%d" %leak)
# n=73822410148110759760164946405270228269255384237831275745269402590230495569279769799226813942899942423718229747478982630879557319063920515141217164980012063064986634632452289290326704640527699568662492105204165609614169349755365956569362139057327962393611139347462018186440108621311077722819578905265976612923
# c=71808322808599218331233291542779486534747913572475630198802984648982830332628443972652322590637382696027943799004331488098592525306523343649935216419522329722152742610560398216737030893090641493326477786720839849938277402743820773957184083430369443325368720115515840174745825798187125454448297155036065857691
# leak=2223117424030234543005449667053988296724455736030907136592525175314696509716321

题目给了一个泄漏了高262位的leak,满足:

那么运用深搜,可以找到多组满足条件的p、q高位,不明白深搜思路的师傅可以看我之前写的这篇,第二题第一小问:

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

那么接下来的自然想法,就是对找到的这些可能的p、q高位依次进行copper恢复低位。但是有一点小问题:

  • 未知的低位有250比特,对于copper来说比较紧

所以我们要想办法提高可解根的上界,而我们知道,copper的可解根上界如下:

其中,d是构造的待求解多项式的度,这里也就是1;beta是指多项式建立在有限域Z(p)上,p是n的因子且满足b>n^beta;epsilon就是small_roots的一个参数。

那么可以运用下面三个思路更好的利用copper:

  • 每一组比较p、q高位的大小,取较大的那一个值来恢复低位,这样可以将beta取为0.5,提高能求解的理论上界
  • epsilon取0.01,这样会变慢,但同样可以提高能求解的理论上界
  • 由于p为素数,将待求的p最低位赋为1,可以缩小根的上界(同理,可以爆破几位进一步缩小上界,但这里不需要了)

然后就可以恢复p,进而求解明文。

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
57
58
59
from Crypto.Util.number import *
import sys
sys.setrecursionlimit(1500)

nbits=512
leakBits = 262
leakbits = nbits - leakBits
e = 65537

n=73822410148110759760164946405270228269255384237831275745269402590230495569279769799226813942899942423718229747478982630879557319063920515141217164980012063064986634632452289290326704640527699568662492105204165609614169349755365956569362139057327962393611139347462018186440108621311077722819578905265976612923
c=71808322808599218331233291542779486534747913572475630198802984648982830332628443972652322590637382696027943799004331488098592525306523343649935216419522329722152742610560398216737030893090641493326477786720839849938277402743820773957184083430369443325368720115515840174745825798187125454448297155036065857691
leak=2223117424030234543005449667053988296724455736030907136592525175314696509716321

leak = leak << leakbits


a1 = "0" + str(bin(leak)[2:])
def find(p,q):
l = len(p)
tmp0 = p + (512-l)*"0"
tmp1 = p + (512-l)*"1"
tmq0 = q + (512-l)*"0"
tmq1 = q + (512-l)*"1"
if(int(tmp0,2) < int(tmq0,2)):
return
if(int(tmp0,2)*int(tmq0,2) > n):
return
elif(int(tmp1,2)*int(tmq1,2) < n):
return

if(l == 512 - leakbits):
pp = int(tmp0,2)
PR.<x> = PolynomialRing(Zmod(n))
f = pp + x*2 + 1
f = f.monic()
res = f.small_roots(X=2^leakbits-1, beta=0.5, epsilon=0.01)
if(res):
try:
plow = int(res[0])
p = pp + plow * 2 + 1
q = n // p
d = inverse(e,(p-1)*(q-1))
print(long_to_bytes(int(pow(c,d,n))))
except:
pass

else:
if(a1[l] == "1"):
find(p+"1",q+"0")
find(p+"0",q+"1")
else:
find(p+"0",q+"0")
find(p+"1",q+"1")

tempp = ""
tempq = ""
find(tempp,tempq)

#flag{6eb67115-38b1-4e75-b3fc-de3a9697e565}



SecretShare

题目描述:

1
Alice把flag分享了给你,快把他恢复吧。flag格式:flag{可见字符串}

题目:

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
import random 
from secret import flag, secret
from Crypto.Util.number import *

n = 21
t = 21

A = [secret]
for i in range(n-1):
A.append(random.getrandbits(1024))

X = []
for i in range(n):
X.append(random.getrandbits(1024))

p = getPrime(1026)

def f(x):
res = 0
tmp = 1
for i in range(n):
res = (res + tmp * A[i]) % p
tmp = tmp * x % p
return res % p

R = []
for i in range(n):
R.append(f(X[i]))

P = secret
Q = getPrime(1024)
N = P * Q
m = bytes_to_long(flag)
e = 65537
c = pow(m, e, N)
phi=(P - 1) * (Q - 1)
d = pow(e,-1,phi)
print(long_to_bytes(pow(c,d,N)))

fi = open('output.txt','w')
for i in range(t-1):
fi.write(str(X[i])+' '+str(R[i])+'\n')
print("leak = %d"%R[-1])
print("p = %d"%p)
print("c = %d"%c)
print("N = %d"%N)

# leak = 158171468736013100218170873274656605219228738469715092751861925345310881653082508445746109167302799236685145510095499361526242392251594397820661050281094210672424887670015189702781308615421102937559185479455827148241690888934661637911906309379701856488858180027365752169466863585611322838180758159364570481257
# p = 667548632459029899397299221540978856425474915828934339291333387574324630349258515018972045406265448494845331262999241448002076917383740651362641947814545076390796789402373579283727117618532504865966299599663825771187433223531022829811594806917984414530614469374596457149431218829297339079019894262229453357029
# c = 9658009093151541277762773618550582280013680172161026781649630205505443184765264518709081169475689440555639354980432557616120809346519461077355134139495745998317849357705381020225760061125236265304057301286196004542729553944161451832173970613915423841610378207266606500956362098150141825329354727367056070349148059780287916811442861961254066733726576151134458892613951223277692935141880749737598416235307087782001086096114978527447987308876878393763055893556123029990282534497668077854186604106027698257663251502775547705641708624619340185646943640576690633662704397191379303254341343433077302686466850600522990402912
# N = 11790604055677230214731474049594783873473779547159534481643303694816346271798870343160061559787963631020684982858033776446193418629055210874285696446209220404060653230407249409973790191858423402504530660556839353260629987853933304089439885784684686555554108157760445567974629355878575105480273451284714281430590737346099023372211403461861104391534461524711472734572409128196536805998116015230502045333769525693468193385557827209520108839913096017750428926467123493650506193757937746017474062985480713594474378324234033232933140389879312722642144536418253323908290256009510135710208223393009237664704631175216240376891

这个题目将最终RSA的一个私钥P当作secret,藏在A数组的第一个,然后分别按如下方式生成各个数组:

1
2
3
4
5
6
7
A = [secret]
for i in range(n-1):
A.append(random.getrandbits(1024))

X = []
for i in range(n):
X.append(random.getrandbits(1024))

并以A、X数组为基础,计算R数组,R数组的每个值如下:

直观一点举个例子就是:

然后,题目给了模数p和完整的R数组,以及缺了最后一个的X数组。可以想到,目的是用这些值还原出A数组,从而用上面的等式解出A0,然后得到最终RSA的分解进而求解明文。

很显眼的一点是,他随机数采用了:

1
random.getrandbits(1024)

然后又知道X数组的20个值,20个1024大于32*624,因此有足够的state来逆向twist,就可以得到全部A,然后随便挑一个Ri的计算等式就能解出A0,就有n的分解了。

对MT19937逆向过程不太明白的可以看这两篇文章,前段时间尝试完成西湖论剑的Oracle时才研究过,所以还有印象:

浅析MT19937伪随机数生成算法-安全客 - 安全资讯平台 (anquanke.com)

MT19937 - Cryptography-Wiki

我的exp也基本是用的这里面的脚本。

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
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
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
import random 
from Crypto.Util.number import *

#twist
def inverse_right_mask(res, shift, mask=0xffffffff, bits=32):
tmp = res
for i in range(bits // shift):
tmp = res ^ tmp >> shift & mask
return tmp

def inverse_left_mask(res, shift, mask=0xffffffff, bits=32):
tmp = res
for i in range(bits // shift):
tmp = res ^ tmp << shift & mask
return tmp

def recover(y):
y = inverse_right_mask(y,18)
y = inverse_left_mask(y,15,4022730752)
y = inverse_left_mask(y,7,2636928640)
y = inverse_right_mask(y,11)
return y&0xffffffff


def inv_twist(state):
high = 0x80000000
low = 0x7fffffff
mask = 0x9908b0df

def recover(i):
y = state[i + 624] ^ state[i + 397]
if y & high == high: # 异或了常数
y ^= mask
y <<= 1
y |= 1
else: # 没有异或常数
y <<= 1
return y

for i in range(len(state)-625, -1, -1):
# 得到s_i的最高位
state[i] = recover(i) & high
# 对s_{i-1}做同样操作得到2-32位
state[i] |= recover(i-1) & low
return state


#recover state
def inverse_right(res,shift,bits=32):
tmp = res
for i in range(bits//shift):
tmp = res ^ tmp >> shift
return tmp
# right shift with mask inverse
def inverse_right_values(res,shift,mask,bits=32):
tmp = res
for i in range(bits//shift):
tmp = res ^ tmp>>shift & mask
return tmp
# left shift inverse
def inverse_left(res,shift,bits=32):
tmp = res
for i in range(bits//shift):
tmp = res ^ tmp << shift
return tmp
# left shift with mask inverse
def inverse_left_values(res,shift,mask,bits=32):
tmp = res
for i in range(bits//shift):
tmp = res ^ tmp << shift & mask
return tmp
def recover_state(out):
state = []
for i in out:
i = inverse_right(i,18)
i = inverse_left_values(i,15,0xefc60000)
i = inverse_left_values(i,7,0x9d2c5680)
i = inverse_right(i,11)
state.append(i)
return state

X = []
R = []
with open(r"E:\题\鹏城杯 2023\secretshare\output.txt","r") as f:
for i in range(20):
temp = f.readline().split(" ")
X.append(int(temp[0]))
R.append(int(temp[1]))

state = []
for i in range(20):
temp = X[i]
for j in range(32):
state.append(temp&0xffffffff)
temp >>= 32

state = inv_twist([0]*640 + recover_state(state[:624]))
state = state[:624]

from random import Random
prng = Random()
prng.setstate((3,tuple(state+[0]),None))
A = []
for i in range(20):
A.append(prng.getrandbits(1024))

tX = []
for i in range(21):
tX.append(prng.getrandbits(1024))

#print(tX[:20] == X)

leak = 158171468736013100218170873274656605219228738469715092751861925345310881653082508445746109167302799236685145510095499361526242392251594397820661050281094210672424887670015189702781308615421102937559185479455827148241690888934661637911906309379701856488858180027365752169466863585611322838180758159364570481257
p = 667548632459029899397299221540978856425474915828934339291333387574324630349258515018972045406265448494845331262999241448002076917383740651362641947814545076390796789402373579283727117618532504865966299599663825771187433223531022829811594806917984414530614469374596457149431218829297339079019894262229453357029
c = 9658009093151541277762773618550582280013680172161026781649630205505443184765264518709081169475689440555639354980432557616120809346519461077355134139495745998317849357705381020225760061125236265304057301286196004542729553944161451832173970613915423841610378207266606500956362098150141825329354727367056070349148059780287916811442861961254066733726576151134458892613951223277692935141880749737598416235307087782001086096114978527447987308876878393763055893556123029990282534497668077854186604106027698257663251502775547705641708624619340185646943640576690633662704397191379303254341343433077302686466850600522990402912
N = 11790604055677230214731474049594783873473779547159534481643303694816346271798870343160061559787963631020684982858033776446193418629055210874285696446209220404060653230407249409973790191858423402504530660556839353260629987853933304089439885784684686555554108157760445567974629355878575105480273451284714281430590737346099023372211403461861104391534461524711472734572409128196536805998116015230502045333769525693468193385557827209520108839913096017750428926467123493650506193757937746017474062985480713594474378324234033232933140389879312722642144536418253323908290256009510135710208223393009237664704631175216240376891

R.append(leak)

secret = R[0]
for i in range(1,21):
secret = (secret - pow(tX[0],i)*A[i-1]) %p

P = secret
Q = N//P
d = inverse(65537,(P-1)*(Q-1))
print(long_to_bytes(pow(c,d,N)))

#flag{2f43430b-3c31-03ee-0a92-5b24826c015c}



Neltharion and Arthas

题目描述:

1
Neltharion and Arthas

题目:

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

key1 = os.urandom(32)
key2 = b'tn*-ix6L*tCa*}i*'
key_len = len(key2)
assert flag.startswith(b'flag{')
assert (flag[13] == 45 and flag[18] == 45 and flag[23] == 45 and flag[28] == 45)
flag1 = b"2023: "+flag[:13]+flag[14:18]+flag[19:23]
flag2 =

h = binascii.unhexlify(hashlib.sha256(key2).hexdigest())[:11]
gift1 = b'***********************************************************************************************'
gift2 = b'I tell you this, for when my days have come to an end , you, shall be King.'+h


def encrypt1(message, key):
cipher = AES.new(key, AES.MODE_CTR, counter=Counter.new(128))
ciphertext = cipher.encrypt(message)
return ciphertext.hex()


def encrypt2(message, key, iv):
padding = bytes((key_len - len(message) % key_len) * '&', encoding='utf-8')
message += padding
cipher = AES.new(key, AES.MODE_CBC, iv)
ciphertext = cipher.encrypt(message)
return ciphertext.hex()


print("enc_gift1 = "+encrypt1(gift1, key1))
print("enc_flag = "+encrypt1(flag1, key1))
print("enc_gift2 = "+encrypt2(gift2, key2, flag2))

output:

1
2
3
enc_gift1 = bad7dbcff968d7cdbf51da011fe94e176fc8e7528e4dd85d2d5fc20ba69cefb7bfd03152a2874705bd2d857ea75b3216a830215db74772d9b9e9c218271d562694d3642d2917972fdb8c7363d8125730a50824cd8dc7e34cd4fa54be427cca
enc_flag = c1c78891e30cd4c0aa5ed65c17e8550429c4e640881f9f1d6a56df
enc_gift2 = ********c********b**************4***5********3****6a*****a**2********c*8******7***********3***5***2********e*5*************a******5**c***74***********fee046b4d2918096cfa3b76d6622914395c7e28eef

我个人觉得这个题复杂度设置的有点高了,导致debug有点不是很方便,中途发现写错了,幸好及时修改,差点就没出。

回到题目,他将题目分为了两部分,对应flag的两半:

  • 第一部分,将flag1用AES_CTR加密,并对gift1同样进行AES_CTR加密,并给出两个密文。同时,隐去gift1,并且密钥key是未知的随机字节
  • 第二部分,将flag2当作AES_CBC模式的iv,对gift2加上一段哈希并padding的明文进行加密,并给出部分密文

接下来分两个部分分别阐述:

第一部分

首先能注意到,对flag1和gift1的加密共用了一个counter以及密钥,因此由CTR的加密方式我们知道:

对CTR加密不太清楚的可以看我写的另一篇文章的第三题:

Crypto趣题-分组密码 | 糖醋小鸡块的blog (tangcuxiaojikuai.xyz)

那么也就是说,如果我们能有gift1,就可以还原出flag1.但是问题就是:gift1被隐去了。

但是我们有flag的前六个字节”2023: “,同样运用异或就可以得到gift1的前六个字节,是:

1
"I am D"

接下来略脑洞(不过其实也还好,提示很明显),由题目标题Neltharion and Arthas可以搜到这是两个魔兽世界的人物,而gift2是第二个人物的台词。那么结合这个前缀,合理推测gift1也是一句台词,果然就搜到:

1
I am Deathwing, the destroyer, the end of all things. Inevitable. Indomitable. I. am. the Cataclysm...!

对其中一些大小写以及空格略作修改后,上面这一行gift1就可以解密出正确flag1了。

第二部分

有一个地方我看了很久才反应过来,就是这个key2:

1
key2 = b'tn*-ix6L*tCa*}i*'

由于它本身也有一些不是字母数字的字符,这导致我开始没有意识到这个*符号是对key2的涂抹,还以为他本来就是key2的字符。

弄清楚这一点就好办了,爆破四个可见字符,并以enc_gift2的最后一个完整密文分组为基础,依次解每个密文分组,就能得到正确的iv也就是flag2。

只是4个可见字符确实要的时间也比较久,再晚一点发现程序写错了的话,比赛时间内还真出不了了。

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

#part1 CTR
gift1 = b"I am Deathwing, the destroyer, the end of all things. Inevitable. Indomitable. I. am. the Cataclysm...!"
enc_gift1 = "bad7dbcff968d7cdbf51da011fe94e176fc8e7528e4dd85d2d5fc20ba69cefb7bfd03152a2874705bd2d857ea75b3216a830215db74772d9b9e9c218271d562694d3642d2917972fdb8c7363d8125730a50824cd8dc7e34cd4fa54be427cca"
enc_flag = "c1c78891e30cd4c0aa5ed65c17e8550429c4e640881f9f1d6a56df"
enc_gift1 = long_to_bytes(int(enc_gift1,16))
enc_flag = long_to_bytes(int(enc_flag,16))

print(xor(xor(enc_gift1,enc_flag),gift1)[:27])

#part2 CBC
def decrypt2(c, kkey, m):
temp = long_to_bytes(int(c,16))
cipher = AES.new(kkey, AES.MODE_ECB)
ciphertext = cipher.decrypt(temp)
return xor(ciphertext,m).hex().zfill(32)

key2 = b'tn*-ix6L*tCa*}i*'
key_len = 16
gift2 = b'I tell you this, for when my days have come to an end , you, shall be King.'
padding = 10*b"&"

enc_gift2 = "********c********b**************4***5********3****6a*****a**2********c*8******7***********3***5***2********e*5*************a******5**c***74***********fee046b4d2918096cfa3b76d6622914395c7e28eef"
suffix = enc_gift2[-32:]
table = [chr(i) for i in range(32,128)]

#21
for i in table[21:]:
for j in tqdm(table):
for k in table:
for oo in table:
kkey = b'tn'+ i.encode() + b"-ix6L" + j.encode() + b"tCa" + k.encode() + b"}i" + oo.encode()
h = binascii.unhexlify(hashlib.sha256(kkey).hexdigest())[:11]
C = [suffix]

temp11 = gift2 + h + padding
M = [temp11[16*tt:16*tt+16] for tt in range(6)]
temp = decrypt2(C[0], kkey, M[5])

if(temp.endswith("fee046b4d2")):
for tt in range(6):
C.append(decrypt2(C[tt], kkey, M[5-tt]))
flag2 = long_to_bytes(int(C[-1],16))
for nn in C[::-1]:
print(nn,end = "")
print(flag2)

#2023: flag{4ff732dd-2b74-45fd-a3ea-e82b4c491e0e}



colorful_matrix

题目描述:

1
colorful_matrix

题目:

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
import random
from Crypto.Util.number import *
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
import gmpy2
import os
import hashlib
def xor(a, b):
return bytes([a[i%len(a)] ^ b[i%len(b)] for i in range(max(len(a), len(b)))])
flag = b'flag{xxxxxx}'
key1 = hashlib.md5(os.urandom(16)).hexdigest().encode()
key2 = hashlib.md5(os.urandom(16)).hexdigest().encode()
num1 = 5
p = int(gmpy2.next_prime(bytes_to_long(key1 + os.urandom(64))))
ms = [random.getrandbits(256) for _ in range(num1)]
qs = [getPrime(1024) for _ in range(num1)]
ns = [p * qs[_] + ms[_] for _ in range(num1)]

num2 = 37
x = bytes_to_long(key2 + os.urandom(32))
A = []
B = []
for i in range(num2):
a = random.getrandbits(512)
b = a * x % p
gift = (2 ** 128 - 1) * 2 ** 400
A.append(a)
B.append((b & gift) >> 400)

iv = long_to_bytes(random.getrandbits(128))
key = xor(key1,key2)
aes = AES.new(key1,AES.MODE_CBC,iv)
enc = aes.encrypt(pad(flag,48))
print(f'ns = {ns}')
print(f'A = {A}')
print(f'B = {B}')
print(f'enc = {enc}')
# ns = [38630062416586710341458654419912504176237737247477839749085033080367529539859992076587411537805430366799412095876782912512744262957062106155418341531142309858429218208463637096843365217114990765965110566415965985105403996944993619708417839598461935470469097206342256014086162845948208599334925650727933097059538199199685364793545286980392966271769914201657672004082101110775504946586957241075964270454872257405872181588544468173017149763827540561921126826597515171761064800381983526515300315517818122598179574900255685121991744205071544970, 41522753602903133841910260331594875922287719226997542592715810409935551768308104573333760854332533376702631593490915962706512143045107096658851885513727202513616813054397657610854303071682604806070009002234312854968365250748142324994926715544722158698813288131533399544263105858513134170084625526223987620550110255872688155827773099232631041345207194483609514502522566888883736218471849075697433311580004701384847571029783514418685068903758509270527252444771313048094566344002411364378658592832008194309873599342916391769027015343562030852, 41542983120532762175372001624404625565366126179958909731196555044290633581761361918706298428954501507557598076910710787422049443564800530253137695341299743714514361560156305534490483794181933110893966453220306980682146624294992100948497284459992930850081254114996830645068636306625330524465991656430799359422407117440063911943625477783216502523414967017151717597372146324488526509879620785458016456593044828784565522423332830549325397893426472247197776412026158371655860380929692662547882654137064941217130915364306358205055760044763651406, 42853015443318352230776688785915441259875645365236808434164117288657978345098324019250085686482568413223085548506789311679316323466083886556772338612177680666217592255234589446979456714341877135596118517098603502394776049958587301113539552072352462301070489369653155854389890761241450743607560719433910573462283304103064437843063566946231984094581307498714742271881862348689297267558023093643893310002803310596286441071314219020032740336515363830250477649030557311461077069407775907176409762823453607196260454965048316567154365877848652918, 31152961872836435078296602982779340735140569916125711058616435902653202922218293684857125091648631460215120167354825278469413413558325850576700866199515219603448136082693185200558425103833947831228064760642508443585470729998592994719564254894176473779555436230174300038353978808432410463449170865897259181312953584408177790825688497584119467820716449210429423337019604137134889051973100340798405991782200038835066294194815913887924272593864934325496116821854183293510325217934617021428710898873475027666892706022106386340733691632884942848]
# A = [12789809461864875489953273982997537541385904671489556544122095227619591140533414669794423644619127980362623481580128258914287474542792728686579090501397390, 10463950513938701625808784986819665844287315724639315128677227520960105897990256530542006653611594269012930935073966767351788182657861624733138283749460454, 5253244650607533810967862436125419800679723144526973463211784033045021824966560017919956773745212139142517766154626849426827164032731516615725539069585525, 5644589184984504085855423002268477365020278981591337230721358313393863912025011466727192648804002734561676112555123877764178690726130713927642577324443238, 4231732567865883627242742552738439372803539125622706171540910152922080004603138662537022248675968288205781990968838888633816697065257733344028576518431020, 2483388920404524165854675814798022834892112957478917588986471421083048888193527751575039626887367465858751417977246719312923814782809309525841102293919541, 3252353812256192711411255830105475125944842449239880454539397067913664088094160819193268643401968970009466652179043139341471403913410402646923633696154454, 11575010486066232687430367040977113580882826853104996856464797182632266635060724100357205810604915010810884387573114266349621457564659060272935537811111850, 116107444921917032985259963199427176510900273385517435613848456370557161312731449337837406563733552524777525870560544042690403987311424820755256727586807, 5859050133610438843641532306693688255014116940390205022708310454673159702673207152462501010791971695002865650407033762568636006764435795015869726867643634, 5954075553161305677556950650395792531753502207483036473422070018485916621872566706504374038792527687442272405589975343003802956899043321092006127828986114, 4571747544457157571652286537158051402285727327066029382085461714597609990601683125994983291866807816649968826930652068427193317966970789937746419206862747, 7166507561570980603812241332170524724051295937096000768984168029904561160020043035660087151672164814332446644696618077835020463308343415953131944864257266, 4852042788460566411381271873349329096978244586097817622748766708426751073559942708861852208085367014057217116211249133109246735634468823924185525972777655, 11962941918999276757181090570698839032103646409734781047194175833198626142790676141060052011581957980660140931408560130449153056874213033784715711461403345, 10324508881746579337486319574059121005227580732153432145860775835052420139026016902518605634385512021513380467928195663920843022679549517463264144660593354, 13276257094435850052122403884510025189232513948002582716865201271569293297601525601586036713056700716929820641888489806178376555435219630186396004003438962, 6525051273399089095687950615197786094425890004112675057642687348101531212837185750558500720306108976630502328600886080197626115513445112562084719104488315, 12922888505610354933000354792496863801007995464403098763485264334670452387681468617068312646367483171083114539083453125614861357751571161533921864394641576, 9489726784141062031514945333087338495823600723655465328127755755022980083351477888038160719541864899912899592065620071698977397662002448273876711116012763, 10630316198843195148937849513165933809121991192035364160395429088101265852052098101114542104327663563661384303617672183366879116750889320604308038959012109, 12675564142993964272844760955973914547747654087592111324261755301551267959231076883765863344473167582531968290671984039948163579495803204811731286282708940, 11847724105274460405216443356582445218232627275228120716891711887600046501095390733716854871561352002320819466803698088448952127166615410820121973485089326, 5131676593756685549522564504727003861447389891839469018437277330988047271086971907217360711863971849879439418231726349935396008040776952541710218842744018, 8049060452950901277510497437779182190254362319091882684392717180429468875432078713802857488901441344429723298843967365750616860588029426099852763482179470, 2365060249260571713545479629411006471094806409182638354076861269679377537605360223984548798658469783472746989448405310909017645138161178501458084966625559, 7467521246204465304438401242342633361751371318557249418344587207503257890765643838557008735305668588521988487342275527781708126255070883848829062790678347, 5841608816993144092409175658260479687582056537041472535819914412630519543198558564258699185557903902095773598614097026740427138629173672250387442834578787, 3935779917509948624841228665498558015416911059417306651751360048412619176423173794541812556512582747588138532941031730797102738268660078594473168666677171, 1459083415233950534805962555425717865938763752937036513111696179351002303817986848490146888626704327653287774806488952733813718461674376764427084478395399, 6426876689549337938550615491086475536072547585103523407263007393570982327518298678278232288342601754164640081474537962710401178482959474762541185760732929, 5241364650650467046722868257809607948071188801137204831449976666385482519613365369974704486723941517654753205012497273820309153659423928739972270634209996, 6387483223002092292686097811446217867743566298067033295601210265979889577756648605354064672061975949925472022416479935990178719227937307079186916383092053, 170562164015232424518655058158727202269056868720093972639058422975773575660534168774299548952867348396798580779605954510297102765330549642318362861226163, 10004133230245713370426176448219282796530473722412487408402635996842671302539458739305597027107498342509248085998067976408732789438099488867425813748783724, 12325342879747412722323355648741345730921040452129462974449188258885453690169624888480720109964630270938743431623479816739889661554987977051169401841580388, 641543989928732942291347866597230552820621633110802944556141221591498546555080480758772801043509130524233886009444044150447511986129019395067102094826363]
# B = [108715652691370707411987210267535348806, 131676833696101475747102644851662113271, 122436706338521558335484593966234623745, 255864866572301552398412638474857375629, 81098761191414480003681301866161112100, 322322463176364397336266169283851913620, 198167679309202772183020662350938553923, 326360662842236388778385468938922853242, 241812832858991643670485138860832357660, 69768236619183466076110136290750715548, 32383134960394164339076842474280712870, 147747232748027508904245311745435517130, 25327826075608705748116808975774398964, 65295332681674581261444632606267440749, 236756211690281667988216748814564193312, 106435149910135092172124474857722935730, 270727089812520941022075406571244846193, 206881193220261276126028739930244917728, 131961838897694897398340205404861333362, 219211823942216355573832791993673934321, 150960424777134558142309786444952807101, 51112048255939343109218372373173385772, 182065623911902509203036774197184164110, 168420344895532090057957641972492853410, 301808673225362418769168353084541667053, 132272458662433671393247350648662880688, 495672626901999558635736361346563007, 182444159345379042372018248514964944782, 144584137563407779776361378564517880036, 338518705859818740467225748906995999694, 205885429741815676881969528495365151019, 233897982464483450790005953366237992668, 279307677123402840425362992920185630901, 133493426228159673166382443820069696429, 316624110847744871475435405969944304329, 187931604382397525131117897387179435812, 220019728924915067987393012581921164417]
# enc = b'cTmkMb\xfc\x05|\x1d\xc7\x13\xbaSe\xe0\xbd\xc0\xd9\xa3\x8cwo\x82yN[B&\x80\xd7KPwQ`\x9c\xbf<y\x8e\x8a\x97e\xa074\xb2'

这个题目弄的心情有点烦躁,因为求解key1很容易,难度主要在求解key2。但是出题人失误了,最后AES用的仍然是key1,而不是key1和key2异或得到的key,这样难度就一点都没有了。

不过我还是会把两个部分都讲一下。

首先,第一部分很显然是个AGCD问题,不清楚的指路la佬博客:

格密码 | Lazzaro (lazzzaro.github.io)

那么就可以求解出ms数组和p以及key1。

其实这道题问题到这里就已经结束了,由于A数组已经给定,并且A和ms生成的方式都是:

1
getrandbits()

那么又可以利用MT19937,只是这一次我们是向后预测iv。预测完iv后直接解AES就得到flag。

然后接下来就说一下我做出来了发现没用的第二部分,第二部分难度我觉得相对来说大很多。

第二部分里,我们有多组如下式子:

但是bi只泄漏了中间一些位,高位和低位是没有的,因此我们需要构造HNP,构造思路如下:

首先,x是一个512比特的数,肯定不能出现在我们要规约的短向量中,因此要消元,消元方式就是两两作差,在这里我们选择将所有项与第0项作差,如下:

由于:

所以有:

作差即可得到:

然后把a0乘过去:

由于已知bi的中间128位,所以我们可以把bi和b0拆为三部分:

两边均出现了已知的bleak项,提取到一边去:

把常数项凑起来:

然后,令:

就有形式:

然后把模p去掉化成等式:

就是个HNP问题了,只不过是二元的。而这个形式正好前段时间有师傅问过我,是这篇的SSSMMM一题:

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

构造形式完全一样,不明白的师傅可以去看看。

然后这题目里,LLL后的第一行就是目标向量,因此我们就可以求解出所有完整的b,从中随便选一组等式也就有key2。但是求完了key2惊奇地发现,居然没用!最后也没上这题的revenge,心痛。

exp(完整的两部分,包含两个key的求解):

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

#part1 AGCD
kbits = 256

Q = [38630062416586710341458654419912504176237737247477839749085033080367529539859992076587411537805430366799412095876782912512744262957062106155418341531142309858429218208463637096843365217114990765965110566415965985105403996944993619708417839598461935470469097206342256014086162845948208599334925650727933097059538199199685364793545286980392966271769914201657672004082101110775504946586957241075964270454872257405872181588544468173017149763827540561921126826597515171761064800381983526515300315517818122598179574900255685121991744205071544970, 41522753602903133841910260331594875922287719226997542592715810409935551768308104573333760854332533376702631593490915962706512143045107096658851885513727202513616813054397657610854303071682604806070009002234312854968365250748142324994926715544722158698813288131533399544263105858513134170084625526223987620550110255872688155827773099232631041345207194483609514502522566888883736218471849075697433311580004701384847571029783514418685068903758509270527252444771313048094566344002411364378658592832008194309873599342916391769027015343562030852, 41542983120532762175372001624404625565366126179958909731196555044290633581761361918706298428954501507557598076910710787422049443564800530253137695341299743714514361560156305534490483794181933110893966453220306980682146624294992100948497284459992930850081254114996830645068636306625330524465991656430799359422407117440063911943625477783216502523414967017151717597372146324488526509879620785458016456593044828784565522423332830549325397893426472247197776412026158371655860380929692662547882654137064941217130915364306358205055760044763651406, 42853015443318352230776688785915441259875645365236808434164117288657978345098324019250085686482568413223085548506789311679316323466083886556772338612177680666217592255234589446979456714341877135596118517098603502394776049958587301113539552072352462301070489369653155854389890761241450743607560719433910573462283304103064437843063566946231984094581307498714742271881862348689297267558023093643893310002803310596286441071314219020032740336515363830250477649030557311461077069407775907176409762823453607196260454965048316567154365877848652918, 31152961872836435078296602982779340735140569916125711058616435902653202922218293684857125091648631460215120167354825278469413413558325850576700866199515219603448136082693185200558425103833947831228064760642508443585470729998592994719564254894176473779555436230174300038353978808432410463449170865897259181312953584408177790825688497584119467820716449210429423337019604137134889051973100340798405991782200038835066294194815913887924272593864934325496116821854183293510325217934617021428710898873475027666892706022106386340733691632884942848]

L = Matrix(ZZ,5,5)
L[0,0] = 2^(kbits)
for i in range(1,5):
L[0,i] = Q[i]
L[i,i] = -Q[0]
res = L.LLL()[0]
q0 = int(abs(res[0]) // L[0,0])
p = int(abs(Q[0]) // q0)

key1 = long_to_bytes(p)[:32]

#recover ms
q1 = int((q0*Q[1]+res[1]) // Q[0])
q2 = int((q0*Q[2]+res[2]) // Q[0])
q3 = int((q0*Q[3]+res[3]) // Q[0])
q4 = int((q0*Q[4]+res[4]) // Q[0])
m0 = Q[0] - p*q0
m1 = Q[1] - p*q1
m2 = Q[2] - p*q2
m3 = Q[3] - p*q3
m4 = Q[4] - p*q4
ms = [m0,m1,m2,m3,m4]

#part2 HNP
length = 36
a = [12789809461864875489953273982997537541385904671489556544122095227619591140533414669794423644619127980362623481580128258914287474542792728686579090501397390, 10463950513938701625808784986819665844287315724639315128677227520960105897990256530542006653611594269012930935073966767351788182657861624733138283749460454, 5253244650607533810967862436125419800679723144526973463211784033045021824966560017919956773745212139142517766154626849426827164032731516615725539069585525, 5644589184984504085855423002268477365020278981591337230721358313393863912025011466727192648804002734561676112555123877764178690726130713927642577324443238, 4231732567865883627242742552738439372803539125622706171540910152922080004603138662537022248675968288205781990968838888633816697065257733344028576518431020, 2483388920404524165854675814798022834892112957478917588986471421083048888193527751575039626887367465858751417977246719312923814782809309525841102293919541, 3252353812256192711411255830105475125944842449239880454539397067913664088094160819193268643401968970009466652179043139341471403913410402646923633696154454, 11575010486066232687430367040977113580882826853104996856464797182632266635060724100357205810604915010810884387573114266349621457564659060272935537811111850, 116107444921917032985259963199427176510900273385517435613848456370557161312731449337837406563733552524777525870560544042690403987311424820755256727586807, 5859050133610438843641532306693688255014116940390205022708310454673159702673207152462501010791971695002865650407033762568636006764435795015869726867643634, 5954075553161305677556950650395792531753502207483036473422070018485916621872566706504374038792527687442272405589975343003802956899043321092006127828986114, 4571747544457157571652286537158051402285727327066029382085461714597609990601683125994983291866807816649968826930652068427193317966970789937746419206862747, 7166507561570980603812241332170524724051295937096000768984168029904561160020043035660087151672164814332446644696618077835020463308343415953131944864257266, 4852042788460566411381271873349329096978244586097817622748766708426751073559942708861852208085367014057217116211249133109246735634468823924185525972777655, 11962941918999276757181090570698839032103646409734781047194175833198626142790676141060052011581957980660140931408560130449153056874213033784715711461403345, 10324508881746579337486319574059121005227580732153432145860775835052420139026016902518605634385512021513380467928195663920843022679549517463264144660593354, 13276257094435850052122403884510025189232513948002582716865201271569293297601525601586036713056700716929820641888489806178376555435219630186396004003438962, 6525051273399089095687950615197786094425890004112675057642687348101531212837185750558500720306108976630502328600886080197626115513445112562084719104488315, 12922888505610354933000354792496863801007995464403098763485264334670452387681468617068312646367483171083114539083453125614861357751571161533921864394641576, 9489726784141062031514945333087338495823600723655465328127755755022980083351477888038160719541864899912899592065620071698977397662002448273876711116012763, 10630316198843195148937849513165933809121991192035364160395429088101265852052098101114542104327663563661384303617672183366879116750889320604308038959012109, 12675564142993964272844760955973914547747654087592111324261755301551267959231076883765863344473167582531968290671984039948163579495803204811731286282708940, 11847724105274460405216443356582445218232627275228120716891711887600046501095390733716854871561352002320819466803698088448952127166615410820121973485089326, 5131676593756685549522564504727003861447389891839469018437277330988047271086971907217360711863971849879439418231726349935396008040776952541710218842744018, 8049060452950901277510497437779182190254362319091882684392717180429468875432078713802857488901441344429723298843967365750616860588029426099852763482179470, 2365060249260571713545479629411006471094806409182638354076861269679377537605360223984548798658469783472746989448405310909017645138161178501458084966625559, 7467521246204465304438401242342633361751371318557249418344587207503257890765643838557008735305668588521988487342275527781708126255070883848829062790678347, 5841608816993144092409175658260479687582056537041472535819914412630519543198558564258699185557903902095773598614097026740427138629173672250387442834578787, 3935779917509948624841228665498558015416911059417306651751360048412619176423173794541812556512582747588138532941031730797102738268660078594473168666677171, 1459083415233950534805962555425717865938763752937036513111696179351002303817986848490146888626704327653287774806488952733813718461674376764427084478395399, 6426876689549337938550615491086475536072547585103523407263007393570982327518298678278232288342601754164640081474537962710401178482959474762541185760732929, 5241364650650467046722868257809607948071188801137204831449976666385482519613365369974704486723941517654753205012497273820309153659423928739972270634209996, 6387483223002092292686097811446217867743566298067033295601210265979889577756648605354064672061975949925472022416479935990178719227937307079186916383092053, 170562164015232424518655058158727202269056868720093972639058422975773575660534168774299548952867348396798580779605954510297102765330549642318362861226163, 10004133230245713370426176448219282796530473722412487408402635996842671302539458739305597027107498342509248085998067976408732789438099488867425813748783724, 12325342879747412722323355648741345730921040452129462974449188258885453690169624888480720109964630270938743431623479816739889661554987977051169401841580388, 641543989928732942291347866597230552820621633110802944556141221591498546555080480758772801043509130524233886009444044150447511986129019395067102094826363]
b = [108715652691370707411987210267535348806, 131676833696101475747102644851662113271, 122436706338521558335484593966234623745, 255864866572301552398412638474857375629, 81098761191414480003681301866161112100, 322322463176364397336266169283851913620, 198167679309202772183020662350938553923, 326360662842236388778385468938922853242, 241812832858991643670485138860832357660, 69768236619183466076110136290750715548, 32383134960394164339076842474280712870, 147747232748027508904245311745435517130, 25327826075608705748116808975774398964, 65295332681674581261444632606267440749, 236756211690281667988216748814564193312, 106435149910135092172124474857722935730, 270727089812520941022075406571244846193, 206881193220261276126028739930244917728, 131961838897694897398340205404861333362, 219211823942216355573832791993673934321, 150960424777134558142309786444952807101, 51112048255939343109218372373173385772, 182065623911902509203036774197184164110, 168420344895532090057957641972492853410, 301808673225362418769168353084541667053, 132272458662433671393247350648662880688, 495672626901999558635736361346563007, 182444159345379042372018248514964944782, 144584137563407779776361378564517880036, 338518705859818740467225748906995999694, 205885429741815676881969528495365151019, 233897982464483450790005953366237992668, 279307677123402840425362992920185630901, 133493426228159673166382443820069696429, 316624110847744871475435405969944304329, 187931604382397525131117897387179435812, 220019728924915067987393012581921164417]

A = []
B = []
for i in range(1,length):
temp = inverse(a[0],p)*a[i] % p
A.append(temp)
for i in range(1,length):
temp = inverse(a[0],p)*a[i] % p
temp = temp * b[0]*(2^400) - b[i]*(2^400)
temp = temp % p
B.append(temp)

O = matrix(ZZ,(length-1),(length-1)+3)
E = diagonal_matrix([2^160]*((length-1)+3))
T1 = diagonal_matrix([p]*((length-1)))
T2 = matrix(ZZ,(length-1)+3,length-1)
for i in range(length-1):
T2[i,i] = 2^528
T2[-1,i] = -B[i]
T2[-2,i] = -A[i]
T2[-3,i] = -A[i] * 2^528

L = block_matrix(ZZ,[[T1,O],[T2,E]])

K = 2^400
L[-1,-1] = K
L[-2,-2] = 1
L[-3,-3] = 2^160

temp = L.LLL()[0]

bh0 = abs(temp[-3] // (2^160))
bl0 = abs(temp[-2])
b0 = bh0*2^528 + b[0]*2^400 + bl0
x = inverse(a[0],p) * b0 % p
key2 = long_to_bytes(int(x))[:32]


#part3 decrypt
enc = b'cTmkMb\xfc\x05|\x1d\xc7\x13\xbaSe\xe0\xbd\xc0\xd9\xa3\x8cwo\x82yN[B&\x80\xd7KPwQ`\x9c\xbf<y\x8e\x8a\x97e\xa074\xb2'

iv = b'\xe9\x19\xbcU?\xd5\x1a>\xaa\x9c\xb2\xe6@\xbd\xbd9'
aes = AES.new(key1,AES.MODE_CBC,iv)

flag = aes.decrypt(enc)
print(flag)

#flag{86baa4ed-5ec7-11ee-ae14-ac1203ab14da}