DozerCTF2020 Crypto Writeup

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
alist =[676925625956162308640440384513641800484007571172765907587788753822524625886466775231277771042941489028262666310432971226347239159610578557398930744109116520511683241330297225842402047426257469872970722899582613650330333873897738069086401590425868778063410175082016815291733067452224991979871565552660189849639722716548786679884923344263056791694624386287112163629706350251470741671769077949837316891891279793800449093565021687092840832109843362, ... # 省略
s = 228862367905112846435125495836684969685244206177089883972406316244571058132358438154686388102214594700265851943070107855680749476953727777551265998314725019016756179212484251912362977161770102006665027376766727392697803585415557024256269878709312925232384759585745970507949822941566661558214978183701781820379482080818559028972731356541590207048221309803246228183067235249099629556624425434839730057758695696421990358728894131114750084109358332375
from Crypto.Util.number import long_to_bytes

n = len(alist)

blist = [[] for j in range(n + 1)]
for i in range(len(blist)):
if i < len(blist) - 1:
blist[i] = [2 if i == j else 0 for j in range(n)]
blist[i] += [n * alist[i], 0]
else:
blist[i] = [1 for i in range(n)]
blist[i] += [(n * s), 1]
print(n/RR(log(max(map(abs, element)),2)))
print('reduce...')
m = matrix(ZZ,blist)
ans = m.LLL()
ans = list(ans[0][:-2])
print(ans)
for i in range(len(ans)):
if ans[i] == 1:
ans[i] = 0
print(ans)
tmp = 0;
for i in range(len(ans)):
tmp += alist[i] * ans[i]
print(tmp)
flag = ''
for i in ans:
flag += str(-i)
print(long_to_bytes(int(flag,2)))
>>> b'Dozerctf{big_bag_big_bang_pppp}'

评论