crypto-从NTRU算法入门格密码

NTRU算法是格密码的一种，也是其中比较简单的，我们就以此来帮助大家入门一下格密码，主要解答的是最短向量问题（SVP，Shortest Vector Problem）以及介绍一下格基规约算法的使用方法。

1、格密码

格密码是一种备受关注的抗量子计算攻击的公钥密码体制，其研究涉及广泛的密码数学问题，学科交叉特色明显，研究方法趋于多元化。

格密码体制因其高可靠性、高安全性、高效性的特点，被广泛应用于金融、网络通信、电子商务、政府机关和军事领域等信息安全领域。

格密码算法具有安全性高、灵活性强、加/解密效率高等优点。它采用了置换和模运算等多种复杂的数学运算，能够有效抵御各种攻击手段。同时，格密码算法可以根据需要随时更换密钥矩阵，具有一定的灵活性和可扩展性。

1-1、格

格(lattice)是一种数学结构，给定一组线性无关的非零基向量 (basis)（称作格基）的整系数线性组合，格就是这些基向量的线性组合 (linear combinations) 。

简单来说给定一组格基(向量) a_1,a_2,……,a_n,对任意的整数 c_1,c_2,……,c_n,并将其作为格基的系数，则c_1a_1,c_2a_2,……,c_na_n都是属于这个格的向量，而n为该格的维数。

而这些线性组合所组成的集合，称作这组基向量所张成的空间 (span)，也被称作向量空间。

你可以想象一平面分布了很多点，而且是由一组基向量形成的，上面的（2,2）是由i(1,0),j(0,1)组成，（2,2）=2i+2j，这就是一个简单二维格。

在这个二维格上的任意一点都可以由这两个基向量组成，所以我们通常用格基代表格，例如上面的格就可以表示为：

也就是[1,0],[0,1]，有人可能以及想到了之所以写成矩阵形式是为了方便计算像（2,2）=2i+2j可以写为：

上面我们将向量这种图象有关的计算转变为了矩阵计算，反过来，我们也能将矩阵计算转化为空间中的图形，这也是我们在格密码的解决中经常用到的，和高中学的数与形的相互转换十分类似。

1-2、格密码的难题

而在格学说里，有两个知名难题：

SVP (最短向量问题，Shortest Vector Problem)：最短向量问题(The Shortest Vector Problem,SVP)是指在格L中找到一个最短的非零向量，即找到一个最短非零向量。
CVP (最近向量问题，Closest Vector Problem)：是指一个向量w不在格L中，然后在格L上找到一个向量v与w最接近。

上面的两个问题都在广义上被证明是 NP-hard 问题，求解起来十分困难，而且会随维数的增加而变得越来越困难。

这里因为NTRU加密和svp有关，我们主要介绍SVP问题，以及其解决方法LLL格基规约算法。

1-3、LLL格基规约算法

LLL算法（Lenstra-Lenstra-Lovász算法）是一种求解最短向量问题的近似算法。其基本思路是将给定的格分解为一个格基，然后找到一个新的格基，其基向量更短，并且更接近于原格。这个过程可以通过不断地将格分解为更小的子格并找到更短的基向量来实现。

具体来介绍就是根据给的格基，通过规约算法得到一组相对前面更简单的格基（都在一个格上，相当于以一个格为有限域，在里面计算），然后不断优化的到最优化的格基，和中国剩余定理的辗转相除法很像，就是一直迭代，直到没法再优化为止。

而通过上面得到的最优格基就是我们要的最短非零向量（很细节的原因就不要去纠结如果想知道可以自己去找），但是LLL算法的使用是有条件的，需要满足Hermite定理

1-3-1、Hermite定理

这个定理给出了最短向量的上界，也就是最大不会超过多少，定理内容如下：

对于n维的格L，都有一个非零向量v属于L，满足：

解释一下||v||表示格基的数量积，n为维度，det(L)为格L(矩阵)的行列式

还是以上面的为例：

所以要使用LLL格基规约算法要满足上面的条件。下面让我们进入正题NTRU算法。

2、NTRU算法

NTRU（Number Theory Research Unit）是一种由美国布朗大学的三位数学教授在1996年发明的公开密钥体制。这种算法的核心在于其密钥生成方法的简易性和加密、解密速度的高效性，相较于RSA等著名算法，NTRU具有显著的速度优势。

NTRU是一个带有专利保护的开源公开密钥加密系统，它使用基于格的加密算法来加密数据。系统包括两部分算法：NTRUEncrypt用于加密，NTRUSign用于进行数字签名。与其他流行的公钥加密系统不同，NTRU可以防止被Shor算法破解，并显著提升了性能。

NTRU算法的安全性基于格上的最短向量问题（SVP），这是一个在数学上被认为是困难的问题，目前还没有算法可以在多项式时间内解决。这使得NTRU算法在理论上具有抵抗量子计算机攻击的能力，而RSA和ECC等算法则无法抵抗量子计算的攻击。

此外，NTRU公钥密码体制的研究背景是基于对传统公钥密码体制中存在的问题和限制的思考和探索，旨在开发一种更加安全、高效的公钥密码体制。NTRU算法简洁、计算速度快、占用存贮空间小，特别适合用于诸如智能卡、保密蜂窝电话系统、保密传真、无线保密数据网以及认证系统等业务。

2-1、基本加密过程

2-1-1、生成公钥、私钥。

首先我们先随机选取素数p,g，随机数f，要求

通过上面的数我们计算

然后将(h,p),作为公钥，私钥为(f,g)。

2-1-2、用私钥加密

现在，随机去随机数r，并使得

这个可以通过调整h,p,f,g的大小来保证。

加密方式为：

2-2、解密原理及过程

2-2-1、使用公钥对加密公式进行变形

先对前面的加密公式进行变形

前面说了

那这里就能直接得到：

2-2-2、使用公钥解密

首先对h进行变形：

在变成矩阵乘法的形式：

注意：上面的变形过程是这个解密过程中最重要的，这里我们建立的矩阵就是一个格。

下面我们令：

而上面那个矩阵乘法说明(f,g)在格L上，所以我们能用svp问题的解法来解，也就是LLL格基规约算法来解。

下面我们通过几道例题来帮助理解NTRU算法的使用：

3、例题

[NSSRound#11 Basic]NTR

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

def init():
    p = getPrime(2048)
    while True:
        x = getRandomNBitInteger(1024)
        y = getPrime(768)
        z = gmpy2.invert(x, p) * y % p
        return (p, x, y, z)

def encrypt(cipher, p, z):
    message = bytes_to_long(cipher)
    r = getRandomNBitInteger(1024)
    c = (r * z + message) % p
    return c

p, x, y, z = init()
c = encrypt(flag, p, z)
with open("cipher.txt", "w") as f:
    f.write("binz = " + str(bin(z)) + "\n")
    f.write("binp = " + str(bin(p)) + "\n")
    f.write("binc = " + str(bin(c)) + "\n")

'''
binz = 0b10000100100000110000100001011001100110110111111110101001011100111001101101100100010010100110111010000001000001100011111011011000110000000111011100100010010001100110101001001110011000110000100101111001101010000101001101010001111001110000010100011001101010111000110111011111100101100100101100111000101011111101111011000101000100000010100100000110000001011100011100010001101001100101100100000101101101001100110100100101110000011001000000000010100010100011001100110101011000010000001111100101001001110111000110010001101111111110000111100001110011100001101010001101010011011110101100100110110011001111110111100100000011101000000100010011101110111100111100111100011001000111010110100101100110111101010010111110000100100001110101011000010101110010010100101110001001101010101001100000111010011110001000010100000100010000010000110011100111100110011100110111101011101001000110110011001011010101100110111111110001011110000100100011110111100011111011111011100110011011100010111010110010111101010001100010001010010111111101110011010101000010000011100000110001100110100001010011010111000000110001010110000110000000100111000101010000010100000110111111111001100100101001111001010010101101101100111010000001100101100100101010111010000011101000100011011111010101100000011100100101110001100100010010010100010000100100100111101101110110111101011001111011011101001110110100101111110001010110010000101111011110111011100111100110000110000010101001101001101000111010100110011000101010001110100110101101110011111010110010010111110111101100111100101110110011110100100000101000101100111000100011001111110001000010010001010101110001110000111100110001101111110110001001001100101110001010111111000111000100011001110001010101000100110001000101110110101000000001100010001000101110000000010001001001100110100100011100101101010010100001011111001011010011001000101101101001111001100101011101111110111101101100111110000100110110011110000111111011010010010011011100100101000000111110110010101110010011000111101101011111110001100101100011111110111111100111001011001010010101000011001110

binp = 0b10011001100000011101010111000011011000001101101000010101101110001111101010101100110000100111101101000100011101001011001100101000110010001000100001010011011100110011001110111001101010000111100000111110110101011101110000010111111101101111001011111111101100010011010001000011000100000010111111001000100000010001010001110101101011001100110001100000001100111010010011010101000011001101111011001110101111111011111101010100100000111101010101001101110000010101100011111001111100001100111010000111100110000001010001001101111111111100010010010001100110000011100110100100001000001001011010000000010100100011001000000000000010100111010011000111011010001010111010001000101100101011001001101101001101101001110101111011010110100101000000001111000001100101000000010101011011011100000001010001111000000100110011011001010011101000010101100101001000001100111001101000111101000000111001110010100001111100101001001101001101000011111001001000101001100101010001011010101111001001101110011101011001011110000001000100100110110001011010101000111001111001011001000001011111110000111000001100011110000011001110000010110101010000000101001111111011100010000000111001110100000010001101100110111010100000011101000100111011111011110001011001110000010001101010011110100110100111001000100010000110110110010111100101111010011110011110100000001001110111100111101000100011011100011101111100101100110110100011101110001111111110010001000001101111100100101011111110111110010100101010110111010111110010110111101011101111110110110101001111101101000010010100000101111000100010110100010011101000100111000011111100111010011010011101110110000100101100101010111111000110100010010101001000001111001100100110101000100110101001011110111101010101110001111101111001110000101000001010110011111000000010010100010000111011001000111000011000011110100000111101101011100000101000111011101110101100101001110001101000111100111011110000110010101010000100110100011010111110111100010111111101010110001000010010011110111101000110001100101111000111101010101101101100100010110011101111101000011101100000101001111001

binc = 0b1111010111110100110011100100001100111101111000010010000010010011101110101000101000100011111101011100110010010111111010000111001101010101010111100000000100111111001111110001111011110100001111001001010001000000011110000001001000011010100111100011110011011010011010011011111111100100110000110010011101110111001001011010101001101011100110101110001111111100100111011010011001001001100010110100000011100000000100110010101100000001010000101000100010000101101111010101000001000110011101100101010111110111000100001011110101010011010010110111010010100101001001010011000100110010010010110100101001111001111000011011000000110000111111001101001111010011110101001001111111110001001100011100101100011110110101000110010110110110101110110110111010110111100101101000111101101011000010011001111111010111000001100101001010010110111100100100100011110101010010010010010100100011001100011111010011101101101101000010101101011000100101101100001000000001101111111100100101111000101011001010010011000011001101101110101001011111010110000111111111011000101100000000011001010000000111110000001101101100101010010001101101010101000010010010110101110100100110011001001011101011111110011100000100001100010100000101011100001110101101011011110000101110011011100010100101010011101011001011011111100001100010000010110010001111010000110010000011100010010101110000101011110000111101001110001111111111101011000110001111011100100111000010110001111110100100011110000100010000011101110101111101000110100110111101110001011101110100001101101100011111000010101111100011100011011001011110010000000001010010101100111001111110110101000010110101110001011000101101110100110111100000110101101010010111001101000010001101110011101010111111011001110000001110000110001000101110110010001001001101010011110100000010100000100010110000001000011001011010000010111010100100101010100010011001100111011110111100101111100000100110110110101101110100011011101101100000101111000011110011000010000000100010000011110110010000010101001110000111110111110001001101000010011101010101101111101010100001101010111010000010000
'''

他这里给的z，p，c对应的就是前面的h，p，c，根据前面的解密过程写脚本,当然我们这里要看一下能否用LLL格基规约算法，看Hermite定理是否满足：

通过粗略计算，||v||约等于2^1024，因为有根号2右侧要比2^1024大，所以可以使用LLL格基规约算法。

from Crypto.Util.number import *
h = 0b10000100100000110000100001011001100110110111111110101001011100111001101101100100010010100110111010000001000001100011111011011000110000000111011100100010010001100110101001001110011000110000100101111001101010000101001101010001111001110000010100011001101010111000110111011111100101100100101100111000101011111101111011000101000100000010100100000110000001011100011100010001101001100101100100000101101101001100110100100101110000011001000000000010100010100011001100110101011000010000001111100101001001110111000110010001101111111110000111100001110011100001101010001101010011011110101100100110110011001111110111100100000011101000000100010011101110111100111100111100011001000111010110100101100110111101010010111110000100100001110101011000010101110010010100101110001001101010101001100000111010011110001000010100000100010000010000110011100111100110011100110111101011101001000110110011001011010101100110111111110001011110000100100011110111100011111011111011100110011011100010111010110010111101010001100010001010010111111101110011010101000010000011100000110001100110100001010011010111000000110001010110000110000000100111000101010000010100000110111111111001100100101001111001010010101101101100111010000001100101100100101010111010000011101000100011011111010101100000011100100101110001100100010010010100010000100100100111101101110110111101011001111011011101001110110100101111110001010110010000101111011110111011100111100110000110000010101001101001101000111010100110011000101010001110100110101101110011111010110010010111110111101100111100101110110011110100100000101000101100111000100011001111110001000010010001010101110001110000111100110001101111110110001001001100101110001010111111000111000100011001110001010101000100110001000101110110101000000001100010001000101110000000010001001001100110100100011100101101010010100001011111001011010011001000101101101001111001100101011101111110111101101100111110000100110110011110000111111011010010010011011100100101000000111110110010101110010011000111101101011111110001100101100011111110111111100111001011001010010101000011001110

p = 0b10011001100000011101010111000011011000001101101000010101101110001111101010101100110000100111101101000100011101001011001100101000110010001000100001010011011100110011001110111001101010000111100000111110110101011101110000010111111101101111001011111111101100010011010001000011000100000010111111001000100000010001010001110101101011001100110001100000001100111010010011010101000011001101111011001110101111111011111101010100100000111101010101001101110000010101100011111001111100001100111010000111100110000001010001001101111111111100010010010001100110000011100110100100001000001001011010000000010100100011001000000000000010100111010011000111011010001010111010001000101100101011001001101101001101101001110101111011010110100101000000001111000001100101000000010101011011011100000001010001111000000100110011011001010011101000010101100101001000001100111001101000111101000000111001110010100001111100101001001101001101000011111001001000101001100101010001011010101111001001101110011101011001011110000001000100100110110001011010101000111001111001011001000001011111110000111000001100011110000011001110000010110101010000000101001111111011100010000000111001110100000010001101100110111010100000011101000100111011111011110001011001110000010001101010011110100110100111001000100010000110110110010111100101111010011110011110100000001001110111100111101000100011011100011101111100101100110110100011101110001111111110010001000001101111100100101011111110111110010100101010110111010111110010110111101011101111110110110101001111101101000010010100000101111000100010110100010011101000100111000011111100111010011010011101110110000100101100101010111111000110100010010101001000001111001100100110101000100110101001011110111101010101110001111101111001110000101000001010110011111000000010010100010000111011001000111000011000011110100000111101101011100000101000111011101110101100101001110001101000111100111011110000110010101010000100110100011010111110111100010111111101010110001000010010011110111101000110001100101111000111101010101101101100100010110011101111101000011101100000101001111001

c = 0b1111010111110100110011100100001100111101111000010010000010010011101110101000101000100011111101011100110010010111111010000111001101010101010111100000000100111111001111110001111011110100001111001001010001000000011110000001001000011010100111100011110011011010011010011011111111100100110000110010011101110111001001011010101001101011100110101110001111111100100111011010011001001001100010110100000011100000000100110010101100000001010000101000100010000101101111010101000001000110011101100101010111110111000100001011110101010011010010110111010010100101001001010011000100110010010010110100101001111001111000011011000000110000111111001101001111010011110101001001111111110001001100011100101100011110110101000110010110110110101110110110111010110111100101101000111101101011000010011001111111010111000001100101001010010110111100100100100011110101010010010010010100100011001100011111010011101101101101000010101101011000100101101100001000000001101111111100100101111000101011001010010011000011001101101110101001011111010110000111111111011000101100000000011001010000000111110000001101101100101010010001101101010101000010010010110101110100100110011001001011101011111110011100000100001100010100000101011100001110101101011011110000101110011011100010100101010011101011001011011111100001100010000010110010001111010000110010000011100010010101110000101011110000111101001110001111111111101011000110001111011100100111000010110001111110100100011110000100010000011101110101111101000110100110111101110001011101110100001101101100011111000010101111100011100011011001011110010000000001010010101100111001111110110101000010110101110001011000101101110100110111100000110101101010010111001101000010001101110011101010111111011001110000001110000110001000101110110010001001001101010011110100000010100000100010110000001000011001011010000010111010100100101010100010011001100111011110111100101111100000100110110110101101110100011011101101100000101111000011110011000010000000100010000011110110010000010101001110000111110111110001001101000010011101010101101111101010100001101010111010000010000

#建立一个矩阵，并将它作为格进行格基规约算法，得到L为最优格基
M = matrix([[1, h], [0, p]])
L = M.LLL()

#如果得到的是负的向量转正
shortest_vector = L[0]
if shortest_vector < 0:
    shortest_vector = -shortest_vector


f, g = shortest_vector
a = c * f % p
m = a * pow(f, -1, g) % g
print(long_to_bytes(int(m)))
#b'NSSCTF{c6ff8aba-fda9-497a-91a7-ee1ac5da68ab}'

第二届黄河流域网络安全技能挑战赛-easyntru

from secret import flag
import libnum

bits = 2048
while True:
  q = random_prime(2^bits, lbound=2^(bits - 1))
  f = random_prime(2^(3*bits//4 - 1))
  g = random_prime(2^(bits//4 - 1))
  if gcd(f, q*g) == 1:
    h = f.inverse_mod(q) * g % q
    break
r = random_prime(2^(3*bits//4 - 1))
m = libnum.s2n(flag)
assert m < 2^(bits//4)
c = (r * h + m) % q

print('q = %d' % q)
print('h = %d' % h)
print('c = %d' % c)
q = 24445829856673933058683889356407393860808522483552243481673407476395441107312130500945533047834993780864465577896968035259377721441466959027298166974554621753030728893320770628116412892838297326949997096948374940319126319050202262831370086992122741039059235809755486170276098658609363789670834482459758766315965501103856358827004129316458293962968758091319313119139703281758409686502729987426264868783862562150543872477975124482520151991822540312287812454562890993596447391870392038170902308036014733295394468384998808411243690466996284064331048659179342050962003962851315539367769981491650514319735943099663094899893
h = 4913183942329791657370364901346185016154546804260113829799181697126245901054001842015324265348151984020885129647620152505641164596983663274947698263948774663097557712000980632171097748594337673511102227336174939704483645747401790373320060474777199502879236509921155985395351647045776678540066383822814858118010995298071799515355111562392871675582742450331679030377003011729873888234401630551097244308473512890467393558048369156638425711104036276296581364374424105121033213701940135560177615395895359023414249846471332180098181632276243857635719541258706892559869642925945927703702696983949003370155033272664851406633
c = 23952867341969786229998420209594360249658731959635047659110331734424497403162506614140213749790708068086973241468969253395309243550869149482017583754015801740198734485871141965939993554966887039832701333623276590311516052334557237678750680087492306461195312290860900992532859827406262394480605001436094705579158919540851727801502678160085863180222123880690741582667929660533985778430252783414931317574267109741748071838599712027351385462245528001743693258053631099442571041984251010436099847588345982312217135023484895981833846397834589554744611429133085987275209019352039744743479972391909531680560125335638705509351

这道题也是NTRU算法，但它和上面那道题不一样的是，他不是直接符合Hermite定理，需要我们取做一些处理使他符合具体操作如下：

首先，就我们构造的格

而f大约为1536位，根号p大约1024位，显然不够，于是我们就要通过对h、p乘以一个数，起到平衡范数的作用，也就是让Hermite定理成立

现在||v||大约为2^1024,右侧大约为2^1024，虽然右边确实比较大，但我们也能遍历一些T使不会错过解，脚本如下：

from sage.all import *
from Crypto.Util.number import *
from tqdm import *
p = 24445829856673933058683889356407393860808522483552243481673407476395441107312130500945533047834993780864465577896968035259377721441466959027298166974554621753030728893320770628116412892838297326949997096948374940319126319050202262831370086992122741039059235809755486170276098658609363789670834482459758766315965501103856358827004129316458293962968758091319313119139703281758409686502729987426264868783862562150543872477975124482520151991822540312287812454562890993596447391870392038170902308036014733295394468384998808411243690466996284064331048659179342050962003962851315539367769981491650514319735943099663094899893
h = 4913183942329791657370364901346185016154546804260113829799181697126245901054001842015324265348151984020885129647620152505641164596983663274947698263948774663097557712000980632171097748594337673511102227336174939704483645747401790373320060474777199502879236509921155985395351647045776678540066383822814858118010995298071799515355111562392871675582742450331679030377003011729873888234401630551097244308473512890467393558048369156638425711104036276296581364374424105121033213701940135560177615395895359023414249846471332180098181632276243857635719541258706892559869642925945927703702696983949003370155033272664851406633
c = 23952867341969786229998420209594360249658731959635047659110331734424497403162506614140213749790708068086973241468969253395309243550869149482017583754015801740198734485871141965939993554966887039832701333623276590311516052334557237678750680087492306461195312290860900992532859827406262394480605001436094705579158919540851727801502678160085863180222123880690741582667929660533985778430252783414931317574267109741748071838599712027351385462245528001743693258053631099442571041984251010436099847588345982312217135023484895981833846397834589554744611429133085987275209019352039744743479972391909531680560125335638705509351

def decrypt(f, g, c):
    a = c * f % p
    return a * pow(f, -1, g) % g
for e in trange(1000,1030):
    T=2**e
    M = matrix([[1, T*h], [0, T*p]])
    L = M.LLL()
    shortest_vector = L[0]
    if shortest_vector < 0:
        shortest_vector = -shortest_vector
    f, g = shortest_vector
    f=abs(f)
    g=g//(2**e)

    try:
        m = int(decrypt(f, g, c))
        flag=long_to_bytes(m)
        if b'flag' in flag:
            print(long_to_bytes(m))
    except:
        None
#b'flag{7c95453a-e577-40d8-9ad0-993655b83b69}'