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)

我们对其进行翻译一下。首先随机选择三个素数,\(q,f,g\),其中随机数\(g,q\)需要满足\(\frac{q}{4} < g^2 < \frac{q}{2}\)。然后求出\(f^{-1},h\),其中\(h=f^{-1}g\) mod \(q\)。最后选择一个随机数\(r\)并计算出密文\(e=(rh+m)\) mod \(q\)。程序最后输出了4个重要的参数,换句话说在已知\(f,g,q,e\)的情况下求解出\(m\)。

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

\[h=f^{-1}g\ (mod\ q)\] \[e=rh+m\ (mod\ q)\]

假如说现在已知私钥\(r\),那么可以求解出\(m\)

\[m=e-rh\ (mod\ q)\]

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

\[e=rf^{-1}g+m\ (mod\ q)\] \[ef=rg+mf\ (mod\ q)\]

由上述的条件中,\(r\)的长度为510 bits,\(g\)的长度为511 bits,而\(q\)的长度为1024 bits,并且满足\(\frac{q}{4} < g^2 < \frac{q}{2}\),因此我们会发现\(rg\)是比\(q\)小的。另一方面,\(mf\)中的消息\(m\)是flag值转换成数字,按理来说flag值的字符串应该很短,很大概率上\(mf\)的值很小,因此\(rg+mf\)可能是比\(q\)值要小。进而我们可以得到

\[ef\ (mod\ q) = rg+mf\] \[ef\ (mod\ q)\ (mod\ g) = mf\ (mod\ g)\]

注意此时随机数\(r\)已经消去,进一步的我们求出\(f\)在模\(g\)的逆\(F^{-1}\)。这里更换了符号是因为避免与上面公式中\(f^{-1}\)出现混淆。此时我们可以求解出\(m\)

\[T = ef\ (mod\ q)\] \[m = TF^{-1}\ (mod\ g)\]

下面是解密的代码:

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

第二题

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

\[h=f^{-1}g\ (mod\ q)\]
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)

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

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

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