本文主要通过分析一些例题来学习格。

NTRU

摘自Lazzaro

三个整数参数$(N,p,q)$和四个次数为$N-1$得整数多项式集合 $L_f,L_g,L_φ,L_m$。$N$为素数，$p,q$可以是合数，但要求$gcd(p,q) = 1$，且$q$远大于$p$。

NTRU工作于多项式整数环$R = Z[x]/(x^N-1)$，当$F∈R$时，可以把$F$表示为多项式或向量形式：
$$
F=\sum_{i=0}^{N-1}{F_ix^i}=[F_0,F_1,…,F_{N-1}]
$$
选取三个确定的整数$d_f,d_g,d_φ$，多项式集合$L_f=L(d_f,d_{f-1}),L_g=L(d_g,d_g),L_φ=L(d_φ,d_φ)$，而$L_m={m∈R|m的系数位于区间[-\dfrac{p-1}{2},\dfrac{p-1}{2}],其中p为素数}$。

密钥生成

选择多项式$f$和$g$，$f∈L_f$，$g∈L_g$。要求$f$关于模$p$和模$q$的逆元$F_p$，$F_q$都存在，否则重新选取$f$。
加密

A发送的消息$m∈L_m$，根据参数$d_φ$随机选取一个$φ∈L_φ$，利用公钥$h$计算
$$
c ≡ φ*h+m\quad(mod\ q)
$$
A把密文c发给了B。
解密

B收到密文c后，利用私钥$f$计算
$$
a≡f*c\quad(mod\ q)
$$
选择a的系数位于$[-\dfrac{p-1}{2},\dfrac{p-1}{2}]$之间，计算
$$
b≡a\quad(mod\ p)\
m≡F_p*b\quad(mod\ p)
$$
多项式m即是明文。

例题：

巅峰极客线上赛的一道密码题NTURE。

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")

从一道CTF题初探NTRU格密码 - 先知社区 (aliyun.com)中有非常详细的解析。（大可不必继续往下翻）

根据题目有
$$
\begin{align}
h = f_p*g\quad (mod\ p) \tag{1}\\
c = r*h+m\quad (mod\ p) \tag{2}
\end{align}
$$
(2)式等式两边同$×f$，得
$$
c*f = r*g + m*f\quad (mod\ p)\tag{3}
$$
分析各个数的bit：

(贴过来)

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

发现$r*g + m*f$小于$p$，故令$a = c*f%p$，则有等式
$$
a = r*g+m*f\tag{4}
$$
(4)式对g取模得
$$
a = m*f\quad(mod\ g)\tag{5}
$$
很可惜，我们并不知道$f,g$。

这里就需要用到格了。

我们已知$h,p,c$，要求$f,g$。

如何构造呢？以下是我的初步理解（可能有误）：

1 2	`利用关系等式、已知量以及常量构造格（矩阵），通过矩阵变化求出含f,g的矩阵。求解未知数的个数一般是矩阵的行和列。`

那么就有：

1 2	`构造2×2的矩阵M 矩阵B = [f,g]为我们的最终结果`

根据关系等式(1)，改写得$f*h = g\quad(mod\ p)$，进一步有$f*h = g + k*p$，将$k*p$移至等式左边得$g = f*h-k*p$。

很显然，$f,g,p$之间存在关系，将矩阵$B = [f,g]$化成$[f,f*h-k*p]$，讨论它是由怎样一个2×2的矩阵$M$得来的以及如何得到的。

易知$[f,g]$是由一个1×2的矩阵$A$乘一个2×2的矩阵$M$得来的。反推一下，就有$A = [f,-k]$，$M=\left[\matrix{1&h\\0&p}\right]$。

因为与$f$有关的关系等式已经用来代换$g$了，所以推出$A=[f，？]$
然后可以推出$M=\left[\matrix{1&?\\0&?}\right]$
根据$B=[f,f*h-k*p]$第二个数，可知$A = [f,-k]$，$M=\left[\matrix{1&h\\0&p}\right]$。

（可能向量维度一高，逆向分析就很难了）

但好在接这类题目有通用矩阵

继续分析，求出的矩阵$B = [f,g]$为什么就是最短向量呢？

Gaussian heurstic：

以及

可知，在这个M中最短向量的长度大概在$sqrt(det(M))= sqrt(p)=sqrt(2^{2048})=2^{1024}$左右。

而$sqrt(det(B)) = sqrt(\sqrt{f^2+g^2}) ≈ 2^{1024}$。

因此，很大概率上，这个$[f, g]$就是这个lattice的最短向量。

代码：

#sage
h = 7257231567493321493497732423756001924698993879741072696808433246581786362611889417289029671240997843541696187487722285762633068287623369923457879458577466240950224087015909821079480431797917376609839097610864517760515986973340148901898582075413756737310797402537478388864632901178463429574227279668004092519322204990617969134092793157225082977967228366838748193084097651575835471869030934527383379794480007872562067799484905159381690179011192017159985260435844246766711550315143517066359521598424992244464723490166447105679062078049379153154659732304112563255058750656946353654402824529058734270363154894216317570784
p = 23969137365202547728693945383611572667294904799854243194734466236017441545927679469239814785947383727854265554138290421827510545078908517696536495567625593439996528098119344504866817224169113920532528233185011693829122447604993468817512696036673804626830507903206709121383065701222707251053362179946170981868061834734684494881504724254812067180384269711822738708203454131838741703416329765575995359232573740932069147491776326045743679105041246906081872936901848272288949389026129761726749334006319072981386763830897454245553866145620689939497868469730297795063648030738668273210516497399954626983672357236110363894081
c = 6388077150013017095358415295704360631706672647932184267739118115740221804173068089559645506533240372483689997499821300861865955720630884024099415936433339512125910973936154713306915269365877588850574948033131161679256849814325373882706559635563285860782658950169507940368219930971600522754831612134153314448445006958300840618894359885321144158064446236744722180819829183828290798747455324761671198097712539900569386477647697973195787663298318786718012522378981137877863153067057280649127202971806609339007027052518049995341356359016898069863799529357397514218249272201695539181908803360181347114492616706419618151757

m = matrix([[1,h],[0,p]])
shortest_vector = m.LLL()[0]
f,g = shortest_vector
print(f'f = {f}')
print(f'g = {g}')

a = c*f%p%g
m = a*inverse_mod(f,g)%g
print(f'm = {m}')