[watevrCTF 2019]Baby RLWE

[watevrCTF 2019]Baby RLWE

from sage.stats.distributions.discrete_gaussian_polynomial import DiscreteGaussianDistributionPolynomialSampler as d_gauss

flag = bytearray(raw_input())
flag = list(flag)

n = len(flag)
q = 40961

## Finite Field of size q. 
F = GF(q)

## Univariate Polynomial Ring in y over Finite Field of size q
R. = PolynomialRing(F)

## Univariate Quotient Polynomial Ring in x over Finite Field of size 40961 with modulus b^n + 1
S. = R.quotient(y^n + 1)

def gen_small_poly():
    sigma = 2/sqrt(2*pi)
    d = d_gauss(S, n, sigma)
    return d()

def gen_large_poly():
    return S.random_element()


## Public key 1
a = gen_large_poly()

## Secret key
s = S(flag)


file_out = open("downloads/public_keys.txt", "w")
file_out.write("a: " + str(a) + "\n")


for i in range(100):
    ## Error
    e = gen_small_poly()

    ## Public key 2
    b = a*s + e
    file_out.write("b: " + str(b) + "\n")

file_out.close()
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

搜索DiscreteGaussianDistributionPolynomialSampler了解了一下。

可知 e 的生成运用高斯分布，c 默认为 0，sigm 看样子是极小的（ pi 未知），那么生成的系数就会集中在 0 处，也就是说 e 的多项式中的很多项系数都为 0。因为as 不变，所以可以通过统计多组b，取相应项中出现最多的系数作为该项的系数，由此猜测as，从而达到绕过 e 的干扰求 s。

keys = open("public_keys.txt", "r").read().split("\n")[:-1]
n = 104
q = 40961
F = GF(q)
R. = PolynomialRing(F)
S. = R.quotient(y^n + 1)
a = keys[0][3:]
a = S(a)
'''
b_list = []
for i in range(1,len(keys)):
    bi = (keys[i][3:]+'*').replace('+',' ').split()#防止find()未找到
    assert len(bi) == 104
    xs = []
    for each in bi:
        index = each.find('*')
        xs = [int(each[:index])] + xs#注意系数顺序
    print(xs)
    b_list.append(xs)
'''

b_list = []
for i in range(1,len(keys)):
    bi = list(S(keys[i][3:]))
    assert len(bi) == 104
    b_list.append(bi)

tmp = []
for i in range(104):#每项系数
    t = []
    for j in range(100):#每个b
        t.append(b_list[j][i])
    tmp.append(max(t,key = t.count))

tmp = S(tmp)
#print(tmp)
s = tmp / a
s = list(s)

flag = ''
for i in s:
    flag += chr(i)
print(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

---

参考：

watevrCTF 2019]Baby RLWE_无名函数的博客-CSDN博客