watevrCTF_CryptoBaby RLWE
题目描述如下：Mateusz carried a huge jar of small papers with public keys written on them, but he tripped and accidentally dropped them into the scanner and made a txt file out of them! D: Note: This challenge is just an introduction to RLWE, the flag is (in standard format) encoded inside the private key.Files:baby_rlwe.sage, public_keys.txtRLWE是Ring learning with errors的简称，一个RLWE问题的基本模型如下：可以看到和我们题目当中给出的符号系统是是一致的，那么我们的任务就是：b1(x) = a(x)*s(x) + e1(x)b2(x) = a(x)*s(x) + e2(x)
...
b100(x) = a(x)*s(x) + e100(x)
其中b1(x)到b100(x)已知，a(x)已知，e1(x)到e100(x)未知，求s(x)通过观察可以发现，这里的a(x)都是通过gen_large_poly()函数生成的，其多项式中x^0、x^1、x^2 … x^(n-1)次方这n项的系数都不为0，其乘上s(x)后，这n项的系数仍然都不为0；而e(x)是通过gen_large_poly()函数生成的，其其多项式中x^0、x^1、x^2 … x^(n-1)次方这n项当中的很多项系数都为0，因此a(x)s(x)再加上e(x)后，得到的结果b(x)当中的很多项的系数是和a(x)s(x)当中对应项的系数是相同的。鉴于我们这里有较多的b(x)，因此我们可以进行一个统计，把这100个b(x)当中x^(n-1)这一项的系数中出现频率最高的系数当做是a(x)s(x)当中对应项的系数，把这100个b(x)当中x^(n-2)这一项的系数中出现频率最高的系数当做是a(x)s(x)当中对应项的系数，以此类推，一直到x^0次方，即恢复出a(x)*s(x)的结果，然后将其除以a(x)，即得到了s(x)的结果。从public_keys.txt文件中我们可以发现，b(x)的每一项当中的最高次幂为103，因此n=103+1=104，也即flag的长度为104个字符。另外这里需要注意的是，我们的a(x)和s(x)都是限制在S.<x> = R.quotient(y^n + 1)范围上的，因此我们也要先对每一个b(x)也进行b(x)=S(b(x))的处理，然后再进行运算。我们将上述推导过程写成脚本形式如下：keys = open("public_keys.txt", "r").read().split("n")[:-1]
keys = open("public_keys.txt", "r").read().split("n")[:-1]
temp1 = keys.find("^")
temp2 = keys.find(" ", temp1)
n = Integer(keys) + 1
q = 40961
F = GF(q)
R.<y> = PolynomialRing(F)
S.<x> = R.quotient(y^n + 1)
a = S(keys.replace("a: ", ""))
keys = keys
counters = []
for i in range(n):
counters.append({})
for key in keys:
b = key.replace("b: ", "")
b = list(S(b))
for i in range(n):
try:
counters] += 1
except:
counters] = 1
a_s = []
for counter in counters:
dict_keys = counter.keys()
max_key = 0
maxi = 0
for key in dict_keys:
if counter > maxi:
maxi = counter
max_key = key
a_s.append(max_key)
a_s = S(a_s)
s = a_s/a
print ''.join(map(chr,list(s)))执行脚本即可得到flag：watevr{rlwe_and_statistics_are_very_trivial_when_you_reuse_same_private_keys#02849jedjdjdj202ie9395u6ky}
支持学逆向论坛，资源不错！
页:
[1]