watevrCTF_CryptoBaby RLWE

roger

题目描述如下：

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.txt

RLWE是Ring learning with errors的简称，一个RLWE问题的基本模型如下：

watevrCTF_CryptoBaby 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[0].find("^") 
temp2 = keys[0].find(" ", temp1)

n = Integer(keys[0][temp1+1:temp2]) + 1
q = 40961

F = GF(q)
R.<y> = PolynomialRing(F)
S.<x> = R.quotient(y^n + 1)

a = S(keys[0].replace("a: ", ""))

keys = keys[1:]

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[i][b[i]] += 1
        except:
            counters[i][b[i]] = 1

a_s = []
for counter in counters:
    dict_keys = counter.keys()
    max_key = 0
    maxi = 0
    for key in dict_keys:
        if counter[key] > maxi:
            maxi = counter[key]
            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}

monkeyman

支持学逆向论坛，资源不错！