Lattices and Cryptography(格理论与密码学)

本文是阅读 Introduction of Mathematical Cryptography Second Edition 一书中关于格密码一章的Review,只讲述简单的总结,具体内容请翻阅该书的第七章(下文中大部分图片均来自此书)

同余密码体系与背包密码

同余(Congruence)密码 流程如下,可以看做一个低维的格密码,破解该种密码可以相当于找一个向量,这个向量就是私钥
Lattices and Cryptography(格理论与密码学)
Lattices and Cryptography(格理论与密码学)
将上面这个问题用向量的形式写出来,就是要找一个a1,a2Za_1,a_2\in \mathbb{Z}a1​,a2​∈Z来找到一个小的向量,如下面的表达式所示
L={a1v1+a2v2:a1,a2Z}L=\{a_1v_1+a_2v_2:a_1,a_2\in\mathbb{Z}\}L={a1​v1​+a2​v2​:a1​,a2​∈Z}
使用格理论可以解出。
背包密码 (Knapsack Cryptosystem)关注于背包问题,一个简单的例子是Subset-sum problem,在这一章里作者举出了Merkle-Hellman subset-sum cryptosystem作为例子,如下所示:
Lattices and Cryptography(格理论与密码学)
要破解这个密码系统,我们要根据密文S获得明文x\boldsymbol{x}x,就是说找到一个x=(x1,,xn)\boldsymbol{x}=\left(x_{1}, \ldots, x_{n}\right)x=(x1​,…,xn​) ,使得S=x1m1+x2m2+...+xnmnS=x_1m_1+x_2m_2+...+x_nm_nS=x1​m1​+x2​m2​+...+xn​mn​,将问题转换为下面的向量问题:
v1=(2,0,0,,0,m1)v2=(0,2,0,,0,m2)vn=(0,0,0,,2,mn)vn+1=(1,1,1,,1,S) \begin{array}{c} {\boldsymbol{v}_{1}=\left(2,0,0, \ldots, 0, m_{1}\right)} \\ {\boldsymbol{v}_{2}=\left(0,2,0, \ldots, 0, m_{2}\right)} \\ {\vdots} \\ {\boldsymbol{v}_{n}=\left(0,0,0, \ldots, 2, m_{n}\right)} \\ {\boldsymbol{v}_{n+1}=(1,1,1, \ldots, 1, S)} \end{array} v1​=(2,0,0,…,0,m1​)v2​=(0,2,0,…,0,m2​)⋮vn​=(0,0,0,…,2,mn​)vn+1​=(1,1,1,…,1,S)​
L={a1v1+a2v2++anvn+an+1vn+1:a1,a2,,an+1Z} L=\left\{a_{1} \boldsymbol{v}_{1}+a_{2} \boldsymbol{v}_{2}+\cdots+a_{n} \boldsymbol{v}_{n}+a_{n+1} \boldsymbol{v}_{n+1}: a_{1}, a_{2}, \ldots, a_{n+1} \in \mathbb{Z}\right\} L={a1​v1​+a2​v2​+⋯+an​vn​+an+1​vn+1​:a1​,a2​,…,an+1​∈Z}
x=(x1,,xn)\boldsymbol{x}=\left(x_{1}, \ldots, x_{n}\right)x=(x1​,…,xn​) 是明文,我们可以得到L变为t\boldsymbol{t}t
t=i=1nxivivn+1=(2x11,2x21,,2xn1,0) \boldsymbol{t}=\sum_{i=1}^{n} x_{i} \boldsymbol{v}_{i}-\boldsymbol{v}_{n+1}=\left(2 x_{1}-1,2 x_{2}-1, \ldots, 2 x_{n}-1,0\right) t=i=1∑n​xi​vi​−vn+1​=(2x1​−1,2x2​−1,…,2xn​−1,0)
根据比对L中所有可能的结果,我们可以知道t\boldsymbol{t}t是L中所有可能结果中长度最小的向量,这样的话,也可以使用格理论来解出明文。

背包问题是一个难解的 NPcomplete\mathcal{NP}-completeNP−complete 问题,一般而言不适合用来做密码系统,因为它没有trapdoor(可以理解为秘钥),但是书中的例子选用了superincreasing的公钥,使得拥有私钥的人可以很快地得出明文

向量空间

格理论

Lattice的定义如下
Lattices and Cryptography(格理论与密码学)
Lattices and Cryptography(格理论与密码学)
从第一个Definition到第二个Definition的证明见MIT-lattice notes

涉及到Lattice的一个重要概念是fundamental domain——F\mathcal{F}F,如下图所示:
Lattices and Cryptography(格理论与密码学)
F\mathcal{F}F的Volume(体积?)由下面的定理给出:
Lattices and Cryptography(格理论与密码学)
当基向量相互正交,Det(L)=Vol(FDet(\mathcal{L})=Vol(\mathcal{F}Det(L)=Vol(F)获得最大值

SVP and CVP

SVP:Shortest Vector Problem
CVP:Cloest Vector Problem,给定一个不在L\mathcal{L}L 中的向量ω\omegaω,我们需要在L\mathcal{L}L中找到一个与ω\omegaω最近的向量
ApprSVP:
Lattices and Cryptography(格理论与密码学)
寻找SVP和CVP是格理论中最基本的问题,一般而言CVP比SVP更难,例如n维的CVP可以转换为n+1维的SVP问题

Hermite’s Theorem and Minkowski’s Theorem

Hermite定理是关于在L\mathcal{L}L中的最短非零向量长度的upper bound
Lattices and Cryptography(格理论与密码学)
对于这一定理有更精确的说明如下:
Lattices and Cryptography(格理论与密码学)
γn\gamma_nγn​是赫米特常数
赫米特定理的证明依赖于闵可夫斯基定理:
Lattices and Cryptography(格理论与密码学)
这个定理描述了Rn\mathbb{R}^nRn的一个有界对称凸(甚至于闭)子集S若满足上述的体积与det(L)相关的不等式,那么S包含就会包含L中的向量。
举个具体的例子,在闵可夫斯基定理的百度百科,其中的L具体化为了二维坐标平面,那么坐标平面的n=2,det(L)=1,因此只要S的面积大于等于4,那么S就会至少包含一个横纵坐标都是整数的坐标,也就包含了L中的向量。

The Gaussian Heuristic

The Gaussian Heuristic(高斯启发式?)是对赫米特常数的进一步缩小(从supercube变成supersphere)
Lattices and Cryptography(格理论与密码学)

Babai’s Algorithm

这个算法是解决CVP问题的一个算法,下文中求aia_iai​的方法其实就是四舍五入。
Lattices and Cryptography(格理论与密码学)
该算法对于一个“好”的基而言比较准确,对于“坏”的基而言就不是很准了,如下图所示,给定一个Target Point,利用上面的算法得到的顶点是Closest Vertex,然而直观来看最近的点应该是下图中的Closest Lattice Point,因此,当你所拥有的基是“坏”的,不容易解出CVP问题。
Lattices and Cryptography(格理论与密码学)

GGH密码

Lattices and Cryptography(格理论与密码学)
因为公钥是“坏”基,因此对于攻击者而言,使用Babai算法解出 m 可能不太现实。

NTUR密码

NTUR密码的流程如下所示:
Lattices and Cryptography(格理论与密码学)

NTUR的破解

构建这么一个矩阵:
LhNTRU=(100h0h1hN1010hN1h0hN2001h1h2h0000q00000qq000000q) L_{\boldsymbol{h}}^{\mathrm{NTRU}}=\left(\begin{array}{cccc|cccc} {1} & {0} & {\cdots} & {0} & {h_{0}} & {h_{1}} & {\cdots} & {h_{N-1}} \\ {0} & {1} & {\cdots} & {0} & {h_{N-1}} & {h_{0}} & {\cdots} & {h_{N-2}} \\ {\vdots} & {\vdots} & {\ddots} & {\vdots} & {\vdots} & {\vdots} & {\ddots} & {\vdots} \\ {0} & {0} & {\cdots} & {1} & {h_{1}} & {h_{2}} & {\cdots} & {h_{0}} \\ \hline 0 & {0} & {\cdots} & {0} & {q} & {0} & {\cdots} & {0} \\ {0} & {0} & {\cdots} & {0} & {q} & {q} & {\cdots} & {0} \\ {\vdots} & {\vdots} & {\ddots} & {\vdots} & {\vdots} & {\vdots} & {\ddots} & {\vdots} \\ {0} & {0} & {\cdots} & {0} & {0} & {0} & {\cdots} & {q} \end{array}\right) LhNTRU​=⎝⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎛​10⋮000⋮0​01⋮000⋮0​⋯⋯⋱⋯⋯⋯⋱⋯​00⋮100⋮0​h0​hN−1​⋮h1​qq⋮0​h1​h0​⋮h2​0q⋮0​⋯⋯⋱⋯⋯⋯⋱⋯​hN−1​hN−2​⋮h0​00⋮q​​⎠⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎞​
可以证明这个Lattice包含了(f,g)(\boldsymbol{f}, \boldsymbol{g})(f,g)
一个定理: Let (N,p,q,d)(N, p, q, d)(N,p,q,d) be NTRUNTRUNTRU Encrypt parameters, where for simplicity we will assume that
p=3 and dN/3 and q6pd2pN p=3 \quad \text { and } \quad d \approx N / 3 \quad \text { and } \quad q \approx 6 p d \approx 2 p N p=3 and d≈N/3 and q≈6pd≈2pN
Let LhNTRUL_{\boldsymbol{h}}^{\mathrm{NTRU}}LhNTRU​ be an NNNTRU lattice associated to the private key(f,g)k e y(\boldsymbol{f}, \boldsymbol{g})key(f,g)
(a) det(LhNTRU)=qN\operatorname{det}\left(L_{h}^{\mathrm{NTRU}}\right)=q^{N}det(LhNTRU​)=qN
(b) (f,g)4d4N/31.155N\|(\boldsymbol{f}, \boldsymbol{g})\| \approx \sqrt{4 d} \approx \sqrt{4 N / 3} \approx 1.155 \sqrt{N}∥(f,g)∥≈4d​≈4N/3​≈1.155N
(c) The Gaussian heuristic predicts that the shortest nonzero vector in the NTRU lattice has length
σ(LhNTRU)Nq/πe0.838N \sigma\left(L_{\boldsymbol{h}}^{\mathrm{NTRU}}\right) \approx \sqrt{N q / \pi e} \approx 0.838 N σ(LhNTRU​)≈Nq/πe​≈0.838N
Hence if NNN is large, then there is a high probability that the shortest nonzero vectors in LhNTRUL_{\boldsymbol{h}}^{\mathrm{NTRU}}LhNTRU​are(f,g)(\boldsymbol{f}, \boldsymbol{g})(f,g) and its rotations. Further,
(f,g)σ(L)1.38N \frac{\|(\boldsymbol{f}, \boldsymbol{g})\|}{\sigma(L)} \approx \frac{1.38}{\sqrt{N}} σ(L)∥(f,g)∥​≈N​1.38​
so the vector (f,g)(\boldsymbol{f}, \boldsymbol{g})(f,g) is a factor of O(1/N)\mathcal{O}(1 / \sqrt{N})O(1/N​) shorter than predicted by the Gaussian heuristic.
根据这个定理我们可以看出(f,g)(\boldsymbol{f}, \boldsymbol{g})(f,g)大概率是这个格里面最短的向量,因此破解NTUR变成SVP。

LLL算法

Lattices and Cryptography(格理论与密码学)
这个算法在Size Reduction的地方有点像施密特正交化(施密特正交化脱离了整数环),下面增加了一步swap以确保满足Lovasz Condition,这样子是为了最后的基大小是从小到大排列,且最小化算法过程中的detLldet L_ldetLl​(LlL_lLl​是由v1,...,vlv_1,...,v_lv1​,...,vl​生成的subLattice)subLattice)subLattice)
在sage中使用LLL算法:

sage: M=Matrix(ZZ,[(1, 39245579300),(0, 122430513841)])
sage: M.LLL()
[-231231 -195698]
[-368222  217835]

使用LLL算法就可以破解比较低维的以上密码,具体例子参见课本

Lattices and Cryptography(格理论与密码学)Lattices and Cryptography(格理论与密码学) RayLee23333 发布了23 篇原创文章 · 获赞 1 · 访问量 1636 私信 关注
上一篇:推荐系统笔记:基于SVD的协同过滤


下一篇:获取STM32系列APB1/APB2/HCLK/SYSCLK系统时钟频率使用J-Link-RTT打印