[Mirror] An Introduction to NTRUEncrypt Through a CTF Challenge

This is a mirror of the post at https://xz.aliyun.com/t/7163

Introduction

巅峰极客线上赛有一道密码题NTURE，是关于非对称密码算法NTRUEncrypt的题目，当时仅有2队解出。

由于知识水平有限，对格相关的密码算法一片空白，所以笔者当时并未解出这道题，但后来一直铭记在心。

赛后虽然有官方wp ，并给出了这一题的解法：

Screen Shot 2020-01-30 at 10.11.37 PM

不过对于从未接触过格密码的笔者来说，如此简洁的wp显然并没有给予多少帮助。

正好这几天在家有很多空闲时间，便去学习了一番格密码，学到了很多，也总算是把这一题解了出来。

Challenge

题目附件已经上传至网盘：

先贴一下题目的代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27


from Crypto.Util.number import *
import gmpy2
from flag import flag


def generate():
    p = getStrongPrime(2048)
    while True:
        f = getRandomNBitInteger(1024)
        g = getStrongPrime(768)
        h = gmpy2.invert(f, p) * g % p
        return (p, f, g, h)


def encrypt(plaintext, p, h):
    m = bytes_to_long(plaintext)
    r = getRandomNBitInteger(1024)
    c = (r * h + m) % p
    return c


p, f, g, h = generate()
c = encrypt(flag, p, h)
with open("cipher.txt", "w") as f:
    f.write("h = " + str(h) + "\n")
    f.write("p = " + str(p) + "\n")
    f.write("c = " + str(c) + "\n")

在另外一个cipher.txt文件中给出了h, p, c的具体数值。

我们先来审计一下：

generate函数生成了4个参数p, f, g, h，其中，

p: 一个2048-bit的强素数。 (“强”在于p-1和p+1都至少有一个很大的素因数，以防某些攻击)
f：一个1024-bit的随机数。
g：一个768-bit的强素数。
h：

可以视为一个在[0, p)这个区间内随机均匀分布的一个数，基本上2000多bit。

这里要特别留意一下的这四个参数的大小关系，后面会有用到。

encrypt函数对明文（也就是flag）进行了加密：

先生成了一个1024-bit的随机数r
然后加密：

这个加密方式很奇怪，从未遇到过。。。当时解题的时候很懵逼。。

我们再来看看给的参数：h, p, c。

显然，如果我们知道了r，那么就可以直接

Screen Shot 2020-01-30 at 10.45.28 PM

解出flag。

但是这里的r是一个随机（本质上是由os.urandom函数）生成的1024-bit数，不可能求得出来的。

如果我们将同余式改写成等式，

Screen Shot 2020-01-30 at 10.56.07 PM

我们来估量一下k的范围：

等式右边r：1024-bit，h：2000多bit，m正常来说几百bit，所以r*h + m大概3000多bit。

等式左边c：2000多bit，p：2000多bit。

因此k大概也有1000多bit，从k出发也无法求解。

况且非对称密码，本来就是需要使用一些数学上巧妙的变换来解密的，并非简简单单地暴力破解就能解决的。

所以想要求解，只能在剩下的两个未知参数f, g上作文章了。

What if

假设一下，如果我们知道了f, g，会怎么样？

我们来做一些代数变换：

Screen Shot 2020-01-30 at 11.40.43 PM

这是我们目前已知的两个模p的关系式，我们将上式代入下式，这样就能消去h：

Screen Shot 2020-01-30 at 11.41.15 PM

现在假设我们已经知道了f, g，那么只有r, m未知；还是需要知道r才能解出m。

不过我们在式子两边同时乘上f来试试看：

Screen Shot 2020-01-30 at 11.42.10 PM

看上去似乎并没有好一些？？不过这个时候，我们再来认真观察一下式子右边的内容：

Screen Shot 2020-01-30 at 11.42.30 PM

r：1024-bit
g：768-bit
m：flag字符串转成数字，一个字符8bit，一般来说flag不会太长，所以基本上是小于1000bit的。
f：1024-bit
p：2048-bit

有没有发现什么？？？

没错，式子右边的内容

Screen Shot 2020-01-30 at 11.43.15 PM

这意味着，式子右边根本就没有被mod p，是完完整整的r*g + m*f！！！

也就是说，如果我们令

Screen Shot 2020-01-30 at 11.43.38 PM

即使c*f 是肯定会大于p的，但是mod p后的结果，就是完完整整的r*g + m*f。

即，

Screen Shot 2020-01-30 at 11.43.58 PM

这里很关键，一定要弄明白！

也就是说，我们通过一些数学上的变换以及参数之间巧妙的大小关系，成功地在同余式里面找出了一个等式！

可是这又有什么用呢？

这就足以让我们能直接绕过r，算出m。

Screen Shot 2020-01-30 at 11.43.58 PM

对该等式取模g，

Screen Shot 2020-01-30 at 11.44.49 PM

这样，r*g这一项就直接消失了。

其中，a, f, g均已知，求m就很轻松了：

Screen Shot 2020-01-30 at 11.45.11 PM

注意：

这里是在mod g下运算，还记得g是一个768-bit的强素数么？这就保证了，虽然f是个1024-bit的数，但是在mod g下，f' = f - k*g的逆元必定存在。

此处的f^-1与h = f^-1 * g (mod p)里的不是同一个东西。

g有768-bit，768/8=96，flag字符串一般来说不会超过96个字符长，因此m比g小，所以最终算出来的就是完完整整m。

TL;DR

如果我们能够知道f, g，那么我们就能解密：

1
2
3
4
5
6


# sage

# Known: h, p, c, f, g
a = (c*f % p) % g
m = a*inverse_mod(f, g) % g
print(hex(m).decode('hex'))

Underlying

好了，只要我们能求出f, g，就能解密。

而我们唯一知道的关于f, g的关系式只有，

Screen Shot 2020-01-31 at 3.31.04 AM

我们如何从中求出f, g呢？

这里就是格（Lattice）的范畴了。

先简单介绍一下lattice。

大家应该都学过线性代数。

如果想温习一遍，推荐3b1b的Essence of linear algebra 。

给定一组线性无关的基向量（basis）v1, v2, ..., vn，那么这些基向量的所有线性组合(linear combinations)

Screen Shot 2020-01-31 at 3.31.29 AM

所形成的集合，就叫做这组基向量所张成的空间(span)。

例如，在二维平面中，如果我们选取两个单位正交向量作为基向量

Screen Shot 2020-01-31 at 3.31.46 AM

那么由这两组基向量的所有可能的线性组合

Screen Shot 2020-01-31 at 3.32.02 AM

张成的空间就是整个二维平面。

Screen Shot 2020-01-31 at 12.42.20 AM

反过来，这个二维平面上的任何一点，都可以由这两组基底的一个线性组合来表示：

Screen Shot 2020-01-31 at 12.44.55 AM

ok，其实lattice的定义跟这个差不多。

给定一组线性无关的基向量v1, v2, ..., vn，那么这些基向量的所有整系数线性组合

Screen Shot 2020-01-31 at 3.32.24 AM

所形成的集合，就叫做这组基向量所张成的格(lattice)。

系数不再是任何实数，变成了是任何整数

也就是说，从无数个连续的点变成了无数个离散的点。

Screen Shot 2020-01-31 at 1.17.12 AM

不同的基底，可能会张成不同的lattice：

Screen Shot 2020-01-31 at 1.22.42 AM

对原基底进行整系数线性转换得到的新的基底，张成的lattice仍旧不变：

Screen Shot 2020-01-31 at 1.18.01 AM

其中，

Screen Shot 2020-01-31 at 3.33.03 AM

注意：同一个lattice有很多组基底。

在lattice里面，有两个知名的难题：

SVP(最短向量问题，Shortest Vector Problem)：给定lattice和基向量，找到lattice中的一个长度最短的非零向量。
CVP(最近向量问题，Closest Vector Problem)：给定lattice和基向量，以及一个不在lattice上的目标向量，找到lattice中一个距离目标向量最近的格向量。

在广义上的这两大难题已经被证明是NP-hard。

这一题实质上就是一道求解SVP的题目。

虽说，SVP是NP-hard的，但是本题的lattice维度很低，只有2维，所以还是很容易求解的。

实际上，LLL算法及其变种算法是目前已知在较低维度的lattice中求解SVP的最好的算法，但是在较高维度中就比较乏力。

所以，并不是说NP-hard就不可能求解。

那么，如何将本题看作成一个lattice中求解SVP的题目呢？

针对

Screen Shot 2020-01-31 at 3.33.29 AM

也就是

Screen Shot 2020-01-31 at 3.33.44 AM

我们可以构造一个由下面这个矩阵M中的两个行向量(1,h), (0,p)所张成的lattice：

Screen Shot 2020-01-31 at 3.34.06 AM

下面我们来证明向量(f, g)是在这个lattice上的。

Proof：

我们可以将同余式

Screen Shot 2020-01-31 at 3.34.23 AM

改写成等式

Screen Shot 2020-01-31 at 3.34.35 AM

将u*p移至左边，

Screen Shot 2020-01-31 at 3.34.51 AM

我们可以发现

Screen Shot 2020-01-31 at 3.35.26 AM

向量(f,g)可以由两组基向量M的某种整系数线性组合(f, -u)来表示，因此向量(f,g)就在这个lattice上。

Q.E.D.

我们再来看看h, p, f, g的大小。

h：2000多bit
p：2048-bit
f：1024-bit
g：768-bit

相对于两个基底向量(1, h), (0, p)来说，向量(f, g)的长度要小得多得多：

Screen Shot 2020-01-31 at 3.35.42 AM

根据Gaussian heurstic可知，在这个lattice中最短向量的长度大概在sqrt(2^2048)=2^1024左右。因此，很大概率上，这个(f, g)就是这个lattice的最短向量。

可见，一开始参数的大小设置，是很关键的一点。

那么如何在lattice里求最短向量呢？

在2维里，早在200年前，高斯（Gauss）就发现了一个能稳定求解的算法（Gauss Lattice Reduction）。

令L是由两个基向量v1, v2所张成的2维lattice，假定|v1| < |v2|，我们现在通过减去v1的某个倍数来使得v2变短。

Screen Shot 2020-01-31 at 3.35.59 AM

这样我们就能够得到一个与v1正交（垂直）的新向量v2*，且使得v2变短了（且是通过这种方式能变的最短的情况）。

Screen Shot 2020-01-31 at 2.24.04 AM

但是，现在我们在lattice里面，不能减去任意倍数的v1，只能减去整数倍的v1。

所以，我们能做的就是，减去整数倍的v1且尽量使得v2变得最短：

Screen Shot 2020-01-31 at 3.36.13 AM

减完，如果v1 > v2，那么交换v1, v2，继续；否则，就结束。

这个算法很容易实现：

1
2
3
4
5
6
7
8
9


# sage
def GaussLatticeReduction(v1, v2):
    while True:
        if v2.norm() < v1.norm():
            v1, v2 = v2, v1
        m = round( v1*v2 / v1.norm()^2 )
        if m == 0:
            return (v1, v2)
        v2 = v2 - m*v1

例如，对于由v1 = (66586820,65354729), v2 = (6513996,6393464)张成的lattice使用上述算法：

download0

(66586820, 65354729), (6513996, 6393464)

download1

(6513996, 6393464), (1446860, 1420089)

download2

(1446860, 1420089), (-720304, -706981)

download3

(-720304, -706981), (6252, 6127)

download4

(6252, 6127), (-1324, -2376)

download5

(-1324, -2376), (2280, -1001)

download6

(2280, -1001), (-1324, -2376)

因此在这个lattice中，最短向量即为(2280, -1001)。

再回到这一题中，我们使用这个算法来求解M中的最短向量：

1
2
3
4
5
6
7


# sage

# h = ...
# p = ...
v1 = vector(ZZ, [1, h])
v2 = vector(ZZ, [0, p])
print GaussLatticeReduction(v1, v2)[0]

大概在20s后能得到结果：

1

(140165891500972861127767415311334757297477816480570735901532575717579672765221212171489392644327018202900088035383969034846193847149851961591661082906530495738734185460636601059708032788268225305120040067251226533612047405603785333261269570827395533567542600084996230099530440207162530350599289132101020447759, 1493239469420336600577802657161324795848374750185055876743560582622232360193779109171117333425338766341860983348309692998243289015442909620365263900067613009409717218816514258676437322125744209790095123709189541828478158286030084857)

经过检验，发现140165...759的确为1024bit，149323...857的确为768bit的质数。

即，求得的结果就是(f, g)。

TL;DR

(f, g)就是一个在特定的2维lattice上的最短向量，使用GaussLatticeReduction或者LLL算法即可解出。

Exploit

好了，现在万事俱备，就差最终exp了。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32


# sage

def GaussLatticeReduction(v1, v2):
    while True:
        if v2.norm() < v1.norm():
            v1, v2 = v2, v1
        m = round( v1*v2 / v1.norm()^2 )
        if m == 0:
            return (v1, v2)
        v2 = v2 - m*v1

h = 7257231567493321493497732423756001924698993879741072696808433246581786362611889417289029671240997843541696187487722285762633068287623369923457879458577466240950224087015909821079480431797917376609839097610864517760515986973340148901898582075413756737310797402537478388864632901178463429574227279668004092519322204990617969134092793157225082977967228366838748193084097651575835471869030934527383379794480007872562067799484905159381690179011192017159985260435844246766711550315143517066359521598424992244464723490166447105679062078049379153154659732304112563255058750656946353654402824529058734270363154894216317570784
p = 23969137365202547728693945383611572667294904799854243194734466236017441545927679469239814785947383727854265554138290421827510545078908517696536495567625593439996528098119344504866817224169113920532528233185011693829122447604993468817512696036673804626830507903206709121383065701222707251053362179946170981868061834734684494881504724254812067180384269711822738708203454131838741703416329765575995359232573740932069147491776326045743679105041246906081872936901848272288949389026129761726749334006319072981386763830897454245553866145620689939497868469730297795063648030738668273210516497399954626983672357236110363894081
c = 6388077150013017095358415295704360631706672647932184267739118115740221804173068089559645506533240372483689997499821300861865955720630884024099415936433339512125910973936154713306915269365877588850574948033131161679256849814325373882706559635563285860782658950169507940368219930971600522754831612134153314448445006958300840618894359885321144158064446236744722180819829183828290798747455324761671198097712539900569386477647697973195787663298318786718012522378981137877863153067057280649127202971806609339007027052518049995341356359016898069863799529357397514218249272201695539181908803360181347114492616706419618151757

# Construct lattice.
v1 = vector(ZZ, [1, h])
v2 = vector(ZZ, [0, p])
m = matrix([v1,v2]);

# Solve SVP.
shortest_vector = m.LLL()[0]
# shortest_vector = GaussLatticeReduction(v1, v2)[0]
f, g = shortest_vector
print(f, g)

# Decrypt.
a = f*c % p % g
m = a * inverse_mod(f, g) % g
print(hex(m).decode('hex'))

# flag{c3bb1f88-2c0b-48fc-9902-beada6d50df6}

事实上，sagemath中自带LLL算法的实现，比我们的这个自制GaussLatticeReduction（大概20s）要快上很多（不到1s）。

Summary

CTF密码题中，RSA是出现次数最多的非对称密码算法，而基于DLP的ElGamal和ECC以及一些基于格中难题的密码算法却很少出现。因此，适当地扩展自己的知识面还是很有必要的。

由于篇幅原因，未能阐释NTRUEncrypt非对称加密算法在高维度中的实现（可能需要具备一定的的数学基础才能理解）以及LLL算法，在最后只能给出一些链接供感兴趣的师傅深入学习了：

An Introduction to Mathematical Cryptography Section 7.9. - 7.14.
NTRUEncrypt wiki
Building Lattice Reduction (LLL) Intuition
Mathematics of Public Key Cryptography Section 17