miniLCTF NTRUEncrypto

2020/05/12 CTF

前两天我参加了西电校内的miniLCTF比赛,下面我分享一下Crypto部分的两道密码题的WriteUp。

第一题

题目给出了两份文件,一份是源代码文件,另一份是输出参数文件。代码经过Brainfuck的转义,网上很容易可以找到相对应的解码程序,这里不做叙述。下面是加密算法的源代码:

from Crypto.Util.number import *
q=getPrime(1024)
f=getPrime(511)
g=getPrime(511)
while g<pow(q/4,0.5) and g>pow(q/2,0.5):
	g=getPrime(511)
f_inv_q=inverse(f,q)
h=f_inv_q*g%q
m=bytes_to_long(b'flag')#flag is base**(flag)
r=getPrime(510)
e=(r*h+m)%q
print(f)
print(g)
print(q)
print(e)

我们对其进行翻译一下。首先随机选择三个素数,,其中随机数需要满足。然后求出,其中 mod 。最后选择一个随机数并计算出密文 mod 。程序最后输出了4个重要的参数,换句话说在已知的情况下求解出

在这段程序中,我认为随机数是加密密钥,因为在上面公开参数基础上还需要知道的值才能求出。梳理一下,我们有这么几条数学公式:

假如说现在已知私钥,那么可以求解出

因为是一个510 bits的随机素数,直接暴力破解显然是不行的。下面给出解决的思路,首先将两式子合并,得到

由上述的条件中,的长度为510 bits,的长度为511 bits,而的长度为1024 bits,并且满足,因此我们会发现是比小的。另一方面,中的消息是flag值转换成数字,按理来说flag值的字符串应该很短,很大概率上的值很小,因此可能是比值要小。进而我们可以得到

注意此时随机数已经消去,进一步的我们求出在模的逆。这里更换了符号是因为避免与上面公式中出现混淆。此时我们可以求解出

下面是解密的代码:

print(long_to_bytes((e*f%q)*inverse(f,g)%g))
# b'y0u_ar3_s0_f@st'

第二题

第二道题目依旧是这个加密算法,但是条件变得更加严苛,只公开了三个参数,相比上一题缺少了。从公开参数上我们知道了下面这个等式:

from Crypto.Util.number import *
q=getPrime(1024)
f=getPrime(511)
g=getPrime(511)
while g<pow(q/4,0.5) and g>pow(q/2,0.5):
	g=getPrime(511)
f_inv_q=inverse(f,q)
h=f_inv_q*g%q
m=bytes_to_long(b'flag')#flag=flag.itself
r=getPrime(510)
e=(r*h+m)%q
print(q)
print(h)
print(e)

换言之如果我们能根据求解出,那么就能用第一道题目的解法来做了。这一块我卡住了很久,我认为自己的数学知识不足够去解这个式子,花了好几个小时都没有头绪。最后在网上找到了一篇文章,事实上这道题目是巅峰极客线上赛的一道密码题NTURE,并且有一篇论文指出对于这个加密算法的攻击方法。实际上要解开上面这条式子需要使用格(Lattice)的数学知识,这一块真的是让人头疼,点击这里了解更详细的数学分析,这里篇幅有限不做累述。

使用sage数学工具的LLL算法可以直接求解出一组的值,注意得出的结果是负数,将负号去掉即可。

v1 = vector(ZZ, [1, h])
v2 = vector(ZZ, [0, p])
m = matrix([v1,v2]);
shortest_vector = m.LLL()[0]
f, g = shortest_vector
print(f, g)

然后代入到公式中即可。

print(long_to_bytes((e*f%q)*inverse(f,g)%g))
# b'l1Ii5n0tea5y'

总结

一般在Crypto的题目中,常见的有RSA和ECC等公钥密码体系,这是我第一次遇见基于格的加密算法,一开始看起来会很难,但仔细分析下去其实相比起其他WEB和PWN题难度不算很大。Keep Learning。

Search

    Table of Contents