关于格密码

​ 众所周知，公钥密码学的安全性，往往建立在数学问题的困难性上。如 RSA 基于大数分解的困难性，DH 和 Elgamal 以及 ECC，是基于有限域上求离散对数的困难性。我们接下来要考虑一类新的难题，它们支撑了格（lattice）密码学。

对比起之前的公钥密码学体系，格密码提供了许多优势：首先，加密、解密速度可以更快（RSA 慢得难以忍受）；可以抵抗量子攻击。目前来看，暂且没有量子算法可以高效解决 lattice 难题。

lattice 除了可以开创新的公钥密码体系之外，还提供了一整套新的数学方法，可以用来解决许多传统密码学的问题。攻击 RSA 时经常采用的 Coppersmith 方法，就是基于 lattice 的。

所谓“格”，是一种与向量空间类似的数学空间。实数空间 R 上的向量空间 V，是一些向量的集合；其中两个向量可以相加、向量可以和一个实数相乘，运算保持封闭。也就是说，向量空间支持向量加法和标量乘法。而 lattice 与向量空间的区别，就是将标量乘法中的乘数，从实数改为整数。

如下是三个lattice：

image-20240929172056452

对lattice给个定义：

格(lattice) 设 v~1~,…,v~n~∈R^m^ 是线性无关向量组。我们称 v~1~,…,v~n~ 生成(generate) 了 lattice L：
$$
L={a_1v_1+a_2v_2+⋯+a_nv_n:a_1,a_2,…,a_n∈Z}
$$
即 L 中的元素是 v~1~,…,v~n~ 的整系数线性组合。
我们定义 L 的一个基(basis)是任何一个能生成 L 的向量组。显然 lattice 的两个基会拥有相同的向量个数；基所包含的的向量个数称为 L 的纬度(dimension).

我们在线性空间中研究过基变换，现在我们也来看一下 lattice 中两个基的关系。假设 v~1~,…,v~n~ 是 lattice L 的一个基，而w~1~,…,w~n~ 是 L 中的一个向量组。接下来将 w~j~ 表示成 v~i~ 的线性组合：
$$
w_1\ =\ a_{11}v_1+a_{12}v_2+…+a_{1n}v_n\
w_2\ =\ a_{21}v_1+a_{22}v_2+…+a_{2n}v_n\
.\
.\
.\
w_n\ =\ a_{n1}v_1+a_{n2}v_2+…+a_{nn}v_n
$$
由于 w~j~ 是 lattice 中的向量，这里的系数 a~ij~ 全部是整数。

​ 接下来，我们考虑能不能使用w~j~来组合出v~i~，来考虑下面的矩阵：
$$
U\ =\ \begin{pmatrix}
a_{11} & a_{12} & \cdots & a_{1n}\
a_{21} & a_{22} & \cdots & a_{2n}\
\vdots & \vdots & \ddots & \vdots \
a_{n1} & a_{n2} & …& a_{nn}\
\end{pmatrix}
$$
显然，U · V = W，于是利用w~i~表示v~i~，系数是U^-1^W，但lattice中，线性组合的系数必须全都是整数，于是**U^-1^**里面的元素也必须全部是整数。

格密码中的难题：

在格问题中有两个知名难题：

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

上面两个问题都是NP完备的问题，求解十分困难，而且会随维数增加而变得越来越困难

LLL格基规约算法：

LLL算法就是在格上找到一组基，满足如下效果：

lll-def

即一种求解最短向量问题的近似算法。

其基本思路是：

将给定的格分解为一个格基，然后找到一个新的格基，其基向量更短，并且更接近于原格。这个过程可以通过不断地将格分解为更小的子格并找到更短的基向量来实现。

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

而通过上面得到的最优格基就是我们要的最短非零向量（很细节的原因就不要去纠结如果想知道可以自己去找），

但是LLL算法的使用是有条件的，需要满足Hermite定理

Hermite定理：

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

对于n维的格L，都有一个非零向量v属于L，满足：
$$
||v||\ \leq\ \sqrt{n}\ det(L)^{ \frac{1}{n} }
$$
其中||v||表示格基的数量积，n为维度，det(L)为格L(矩阵)的行列式

NTRU算法：

NTRU算法是基于格上最短向量问题(SVP)，多项式环结构设计出的密码系统，也就是所谓的代数结构格

基本问题介绍：

随机选取素数p,g，随机数f，满足g<f<p，我们计算
$$
h\ =\ gf^{-1}\ (mod\ p)
$$
公钥是**(h,p)，私钥是(f,g)**

定义加密方式为
$$
c\ =\ r·h+m\ (mod\ p)
$$
其中，r为随机数，满足f < p

定义解密方式为
$$
c·f\ =\ r·g+m·f\ (mod\ p)
$$
在这里要满足rg+mf < p，那么可以得知
$$
a\ = \ rg+mf\ ≡\ mf\ (mod\ \ g)
$$
那么求解问题就变为
$$
m\ =\ af^{-1}\ (mod\ \ g)
$$

此处简化了很多步骤，比如说保证gcd(f,g)=1等条件，其中rg+mf<p是通过控制h,p,f,g的大小实现的

攻击手段：

考虑等式
$$
h\ =\ gf^{-1}\ (mod\ p)
$$
对其变形得到
$$
f·h\ =\ g\ (mod\ p)\ = g+kp
$$
改写为矩阵乘法，得到
$$
(f,-k)*\begin{bmatrix}
1 & h\
0 & p
\end{bmatrix}\ =\ (f,g)
$$

注意：这里我们建立的矩阵就是一个格

下面我们令：
$$
L\ =\ \begin{bmatrix}
1 & h\
0 & p
\end{bmatrix}
$$
而上面那个矩阵乘法说明**(f,g)在格L上，所以我们能用svp问题的解法来解，也就是LLL格基规约算法**来解。

NTRU例题：

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
from Crypto.Util.number import getPrime, getRandomNBitInteger
from math import gcd

def gen_key():
    p = getPrime(2048)
    f = getRandomNBitInteger(1024)
    g = getPrime(768)
    assert gcd(f, p) == 1
    assert gcd(f, g) == 1
    h = pow(f, -1, p) * g % p
    return (h, p), (f, g)

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

def decrypt(f, g, c):
    a = c * f % p
    return a * pow(f, -1, g) % g

pubkey, prikey = gen_key()
h, p = pubkey
f, g = prikey
c = encrypt(h, p, m)

print(f'{p = }')
print(f'{h = }')
print(f'{c = }')

exp:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
from Crypto.Util.number import *
p = 27594003389147607369876674962283540812923723484764896504615301667891769682392830700505146565378653539119600813995142280915192657472008749757053428617533851699041596289206274929457178724207236537704942588471957686793501676280083577625938001845200938875371121059921018339291926310189890910674291154395560577741025165026637266300202408364846598547810207047635737497984357341153634605326370312560794859152109470507930707976266978869848114875210278872802460387560896289447402484841694897117444468955804897349232138924990711736063541879374827091472825348941445564520557929969273920235937179897137468129678469879486475239587
h = 2071693178846115365256723483327725178503050954465496579029808248184888643303185618308763733997615320553015405690744070807211482128071409950264282977319266191487261103502555226760220546234498149656711925740338844829729591708920986465468222690445385909699330163332174162914930634801187698298857635172034342938401155529241042690638568002082750744828569527268706825896607293470070519508750808672297737672589325372550690338703159708325314400119604285890879839665019432945211057077954724304391457748178158342102678647638675140789772803542969160681336018722064996045749041652415620028221116584104045162570850741666319496552
c = 7671911440878532433667489121828814206592905285054408925890957479601943566414379514033874765501550498736499255991516070982428829754215761379185332958698647996593036343058593367027949092535270126555289066891682542858251520630282615219113992893538755011967908072085016169215108544137084022073238869205354768601011253598570094011049868057911782544371039850541623949887912456762381409507704839535353567221746097905226925531782002899815658215746488155191552172645625894574414478454147438702085549693734515817389107129970039603841526722724017093665065816242864251172298040114963542718789445480202872102034318566489282326224

M = matrix([[1,h],[0,p]])
L = M.LLL()
ans = L[0]
if ans<0:
    ans = -ans
f,g = ans
def NTRU(f,g,c):
    a = c*f %p
    return a*pow(f,-1,g)%g
m = NTRU(f,g,c)
print(m)

参考：

格密码笔记（一） (ruanx.net)

crypto-从NTRU算法入门格密码 - 先知社区 (aliyun.com)

格基规约算法 - CTF Wiki (ctf-wiki.org)

NTRU密码体制笔记 | 独奏の小屋 (hasegawaazusa.github.io)