查看: 235|回复: 1

[Crypto] watevrCTF_CryptoBaby RLWE

[复制链接]
发表于 2020-3-10 15:10:29 | 显示全部楼层 |阅读模式
题目描述如下:
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.
RLWE是Ring learning with errors的简称,一个RLWE问题的基本模型如下:

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


温馨提示:
1.如果您喜欢这篇帖子,请给作者点赞评分,点赞会增加帖子的热度,评分会给作者加学币。(评分不会扣掉您的积分,系统每天都会重置您的评分额度)。
2.回复帖子不仅是对作者的最好奖励,还可以获得学币奖励,请尊重作者的劳动成果,拒绝做伸手党!
3.发广告、灌水回复等违规行为一经发现直接禁言,如果本帖内容涉嫌违规,请点击论坛底部的举报反馈按钮,也可以在【投诉建议】板块发帖举报。
善莫大焉-2019

0

主题

91

帖子

0

精华

中级会员

Rank: 8Rank: 8

学币
229
荣耀
0
rank
0
违规
0

    发表于 2020-3-10 22:28:32 | 显示全部楼层
    支持学逆向论坛,资源不错!
    关闭

    论坛公告上一条 /1 下一条

    快速回复 返回顶部 返回列表