Again, I do not know how to solve this problem. Leave it to the future me to digest how to solve lattice problems and understand a bit more about group theory.
The original attack is from Shamir et al., but a low-density attack that leverages the LLL algorithm. A version is mentioned in this awesome paper.
Sage Implementation:
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
|
a = [
#public key
]
s = #ciphertext
n = len(a)
N = ceil(sqrt(n) / 2)
b = []
for i in range(n):
vec = [0 for _ in range(n + 1)]
vec[i] = 1
vec[-1] = N * a[i]
b.append(vec)
b.append([1 / 2 for _ in range(n)] + [N * s])
BB = matrix(QQ, b)
l_sol = BB.LLL()
for e in l_sol:
if e[-1] == 0:
msg = 0
isValidMsg = True
for i in range(len(e) - 1):
ei = 1 - (e[i] + (1 / 2))
if ei != 1 and ei != 0:
isValidMsg = False
break
msg |= int(ei) << i
if isValidMsg:
print('[*] Got flag:', long_to_bytes(msg))
break
|