格

格的基本概念

离散数学中 格是一个满足每两个元素都有最大上界和最小下界的偏序关系(partial ordering)集。

线性代数中，我们将整数环上 \(Z_{q}\) 一组大小为 \(k\) (\(k \leq n\)) 且线性无关的向量，称为一组基。如果 \(k = n\)，则称该组基是满秩的。
该组基整系数线性组合所有向量的集合（ \(v_{i} \in Z_{q} ，L = \{v_{i} \cdot M\}\)），称为一个格。

举个例子：
在中国象棋中，象可能到达的坐标集合假设棋盘无限大且没有楚河汉界的存在就是一个格。
直观上看，在棋盘上有很多格点是象无法到达的（比如其初始位置周围一圈皆然）。数学的角度来说，我们可以认为象移动向量的基就是 \(v_1 = (2,2), v_2 = (2,-2)\)。
而 \(v_1\) 与 \(v_2\) 的线性组合就是象能到达的所有点，形如 \(L = \{(0,0),(2,2),(2,-2),(4,0),(0,4) ... \}\)

“格”之名即来源于这些结果向量都是离散而非连续分布的；以点的方式表示之，就像一个个格点。

格中的困难问题

现代密码学中，很多数学工具的应用依赖于其中的“难题”。格中比较重要的难题有两个：

• SVP(Shortest Vector Problem，最短向量问题)：给定 \(n\) 维格 \(L\)，确定向量 \(v \in L\)，使得 \(\forall u \in L\) 且 \(u \neq 0\)，\(\|v\| \leq \|u\|\)。
  
• CVP(Closest Vector Problem，最近向量问题)：给定 \(n\) 维格 \(L\) 和 \(R_n\) 上的向量 \(t\)，确定向量 \(v \in L\)，使得 \(\forall u \in L\)，\(\|t-v\| \leq \|t-u\|\)。

在棋盘中，上述两个问题可以转述作：
假设存在一个具备一定移动规则的棋子，
SVP：一个棋子在经过若干次移动后，能达到的离自身最近的点是哪里（不允许原路返回）？
CVP：一个棋子在经过若干次移动后，能达到的离某个给定点最近的点是哪里？

格基规约算法

格基规约简介

“人话”简介

格基规约，就是对一组给定的格基进行数学处理，来获得一组“简化”的基向量，这组基构成的格和原基构成的格相同。
具体地，假设原格基是 $ M = {v_1,v_2,v_3,...,v_n}$，
为令新格基 \(M^{'} = \{v_1^{'},v_2^{'},...,v_n^{'}\}\) 组成的格与原格相同，则新格基应当由原格基和整数域上的矩阵相乘而得（即，$v_i^{'}, i $ 都能表示成原格基的整系数线性组合）。

而格基规约的目标是在满足上述条件的前提下，令新格基的模(norm)尽可能短（即，获得新格基的各向量长度尽可能短）。

依然举一个比较直观的例子：
考虑一个由基 \(v_1 = (0,1), v_2 = (1,1)\) 组成的二维格。不难发现所有整数坐标的格点都在这个格上。
对 \(M = \{v_1,v_2\}\) 进行格基规约的结果是 \(M^{'} = \{v_1^{'} = (0,1),v_2^{'} = (1,0)\}\)。
可以发现新的这组基更短，质量更高。

“鬼话”简介

二维空间下的格基规约

在二维空间中，格基规约的算法最早由高斯提出，其计算过程非常近似于施密特正交化(Schmidt Orthogonalization)。不同的是：

• 由于格基规约的运算均在整数环上进行，因此对于施密特正交化步骤中的“比例”计算应当取整处理（这也提示了格基规约得到的向量组是高度正交化的，但不保证是正交矩阵）。
  
• 格基规约本质上是一种贪心算法，即不断地将两组基互相规约，直至满足循环结束的条件（不能再变得更短）。

对比来看，设一个二维格中的两个向量分别为 \(v_1\) 和 \(v_2\)，线性代数的知识可知对之进行正交化的步骤为：
令 \(v_1^{'} = v_1\)， \(v_2^{'} = v_2 - \frac{v_2 \cdot v_1^{'}}{v_1^{'} \cdot v_1^{'}} v_1^{'}\)。
输出的正交基即为 \((v_1^{'},v_2^{'})\)。

而对 \((v_1,v_2)\) 进行规约的操作则有所不同：

约定，\(\lceil x \rfloor\) 表示取距离 \(x\) 最近的整数；对于 \(x \in Z\)，\(\lceil x+\frac{1}{2} \rfloor = x\)。

令 \(v_2 = v_2 - \lceil \frac{v_2 \cdot v_1}{v_1 \cdot v_1} \rfloor v_1\)；
若此时 \(\|v_1\| \leq \|v_2\|\)，则输出\((v_1,v_2)\)，算法运行结束；否则 \(v_1 \leftrightarrow v_2\)，回到上一步。

例：某棋子在一个棋盘中只允许有两个行走向量（允许后退）：(2,3)和(0,2)，计算该棋子（等价的）最简行走向量及可达点。

解：记 \(v_1 = (2,3),v_2 = (0,2)\)。
根据规约公式，代入数据得 \(v_2 = (0,2) - \lceil \frac{6}{13} \rfloor \cdot (2,3) = (0,2)\)，由于 \(\|v_1\| = \sqrt{13} > \|v_2\| = 2\)，故\(v_1 \leftrightarrow v_2\)；
再计算 \(v_1 = (0,2)\)，\(v_2 = (2,3) - \lceil \frac{6}{4} \rfloor \cdot (0,2) = (2,1)\)；此时 \(\|v_1\| = 2 \leq \|v_2\| = \sqrt{5}\)，故规约结束，输出 \(\{(0,2),(2,1)\}\)。

因此，该棋子等价于只能以 \(\{(0,2),(2,1)\}\) 的方式行走。数学推导可得可以到达的点 \((x,y)\) 满足：

• 若 \(x \equiv 2 (mod 4)\)，则 \(y \equiv 1 (mod 2)\)，对应的点包括 \(\{(2,1),(2,3),(2,5),(-2,7),\cdots\}\)；
• 若 \(x \equiv 0 (mod 4)\)，则 \(y \equiv 0 (mod 2)\)，具体点略。

纵观算法的执行过程，不难得出输出基有一个 size-reduced 性质：\(|\mu_{1,2}| \leq \frac{1}{2}\)。
其中 \(\mu_{i,j} = \frac{v_i \cdot v_j^{'}}{v_j^{'} \cdot v_j^{'}}\) （换言之，\(\mu_{i,j}\) 为施密特正交化中减去 \(v_j^{'}\) 的系数）。

若 \(v_1,v_2 \in L\) 线性无关且满足 size-reduced 的条件，则称之为二维格 \(L\) 中的最小基（亦名 Minkowski约化基 ）。

LLL(Lenstra-Lenstra-Lovasz)：拓展到高维的格基规约

LLL算法可以视为上述算法在高维格中的推广，其可以在多项式时间内输出一组约化基。
设 \(\{v_1,v_2,\cdots,v_n\}\) 是 \(L\) 上的一组格基，若其满足以下两个性质：

1. size-reduced ：\(\forall 1 \leq i < j \leq n， |\mu_{i,j}| \leq \frac{1}{2}\)。
   
2. Lovasz-condition ： \(\forall i \in [1,n]\)，\(\delta \|v_i\|^2 \leq \|v_{i+1} + \mu_{i,i+1}v_i\|^{2}\) 。

则称 \(\{v_1,v_2,\cdots,v_n\}\) 是格 \(L\) 的一组 \(\delta\)-LLL约化基(\(\delta\)-LLL reduced)。显然参数 \(\delta \in (0.25,1]\)。

第二个条件亦可写作 \(\|v_{i+1}\|^2 \geq (\delta - \mu_{i,i+1}^2) \|v_i\|^2 \geq (\delta - \frac{1}{4}) \|v_i\|^2\)。

第一个条件表明了 LLL-reduced 的向量是相对较短且高度正交的；
第二个条件是为根据向量的范数(norm)对之进行大致排序。

相应地，LLL算法的执行过程如下：

输入 \(\{v_1,v_2,\cdots,v_n\}\) 与参数 \(\delta \in (\frac{1}{4},1]\)，置 \(k = 2\)。
每个循环进行以下两步：

1. 规约步：令 \(v_i = v_i - \lceil \mu_{i}{k} \rfloor v_k\)，\(i \in [1,k)\)；
   
2. 排序步：若 \(\|v_k\|^2 \geq (\delta - \mu_{k,k-1}^{2})\|v_{k-1}\|^2\)，则 \(k += 1\)，否则置 \(k = max(k-1,2)\)。

若 \(k \leq n\)，则继续循环，否则循环结束。

可以发现LLL算法的核心和高斯算法是类似的：第一步在“不断地”满足 size-reduced 条件，第二步则对应 Lovasz-condition。

LLL在密码分析中的应用

数学理论终究还需付诸实践。
LLL对格进行规约的效率和参数 \(\delta\) 的选取密切相关。密码学分析中，多数情况下取 \(\delta = 0.99\) 可以达到比较好的规约质量-运行速度的平衡。
先介绍LLL算法的规约能力、时间复杂度：

规约能力：
假设 \(\{v_1,v_2,\cdots,v_n\}\) 是格 \(L\) 的一组 \(\delta\)-LLL 约化基，则 \(\|v_1\| \leq (\frac{2}{\sqrt{4\delta - 1}})^{n-1} \lambda_1(L)\)。

显然LLL的输出向量长度和参数 \(\delta\) 成负相关： \(\delta = 0.99\) 时，\(\|v_1\| \leq (1.35)^{\frac{n-1}{2}} \lambda_1(L)\)。
实践中，LLL的输出基质量会明显优于上述定理给出的上界（即上述定理给出的是最坏情况的估计）。

时间复杂度：
LLL算法会在 \(O(n^{6} \ln^{3} B)\) 的时间内运行完毕，其中 \(\forall i \in [1,n], \|v_i\| \leq B\)。
同样地，这也是最坏情况下的时间复杂度。

同时，由于规约目标是寻找“短向量”，故事先构造目标向量使之“变短”是规约的重要准备步骤。

Hermite定理则表明了一个格 \(L\) 的最短基的模长：
\(\|v_1\| \leq \|v_2\| \leq \cdots \leq \|v_i\| \leq 2^{\frac{n(n-1)}{4(n+1-i)}} det(L)^{\frac{1}{n+1-i}}\)

显然通过矩阵性质构造，大幅增大 \(\frac{det(L)}{\|v_t\|}\) 是一种可行方案。

密码分析的构造格实践中，下述方法的应用非常广泛：
对于 \(v_i = (x_1,x_2,\cdots,x_n)\) ， \(\|v_i\| = \sqrt{\sum_{i=0}^{n} x_i^2}\)
若 \(|x_k| >> |x_i| (i \neq k)\) ，令 \(x_i^{'} = Cx_i (C << \frac{|x_k|}{x_i})\)，则 \(\|v_i^{'}\| \approx \|v_i\|\)。 同时对于构造格 \(L\)，其为三角矩阵时，设 \(x_k\) 在对角线上，显然 \(det(L^{'}) = Cdet(L)\)。

格核心性质的利用方法

在应用格攻击时，会经常碰到的一个概念即为“构造”格。
格的重要性质：格中向量一定是基向量的整系数线性组合，但这个线性组合的具体值并不重要（考虑 \(v_0 \cdot M = v_r\) ，如果已知 \(v_r\) 在基 \(M\) 构成的格上，则只需要 \(v_0\) 是整数环上的向量，就可以进行格攻击）。
实践中，联系线性代数和线性方程组的关系不难发现，对于一个“部分量已知，部分量未知且恒定，部分量未知且可变”的方程组，就可能可以格攻击之，获得那个“未知且恒定”的量。

但假如不知道 \(v_0\) 的具体值，怎么还原出 \(v_r\) ？此处即为格基规约的用武之地了。

只要我们可以构造出 \(v_r\) 是由 \(M\) 为基的格上的一个比较短的向量，那么对 \(M\) 进行格基规约就可能得到 \(v_r\)。
而构造方法则参照格的定义即可：利用已知条件，写出一个矩阵乘法方程 \(a \cdot M = v_r\)，其中 \(a\) 只需确定是整系数n维向量即可，无需知道其确值不然你直接一乘结果不就出来了嘛
相对地，\(v_r\) 也只需确定其各维均为整数即可，但 \(v_r\) 应尽可能地短；\(M\) 则需要都为已知量。

格基规约可行的依据在于其本质上是一种贪心算法，会不断规约直至向量模达到下界为止。
更直观地，参考“辗转相除”中的贪心：求 \(gcd(4,6)\) 的过程和求 \(gcd(65538,65540)\) 的过程本质无异。

构造格的一般步骤：

1. 列出线性方程组，保证所有系数均为整数，并将较小的未知量放在等式的一侧；
   
2. 对格进行配平，确保目标向量属于短向量且符合规约上界要求；
   
3. 对格进行规约，提取其中首个行向量作为结果向量，校验其是否符合要求。

碧海——格的“增广”攻击

矩阵乘法最初被用于解线性方程组，但只要我们让方程组的已知系数构成了一个矩阵，或许，即使余下的“向量”未知又何妨？

HNP问题及其应用

HNP问题简介及攻击

HNP问题，全称Hidden Number Problem，即隐藏数问题。

其描述如下：
给定质数 \(p\)、一些整数 \(\{t_i\}\) 以及 \(MSB_{\alpha}(xt_i mod p)\)，解出 \(x\)。

\(MSB_{\alpha}(n)\) 表示整数 \(n\) 的最高 \(\alpha\) 个有效位。
记 \(n\) 的位数为 \(\beta (\beta > \alpha)\)，亦可描述作 \(MSB_{\alpha}(n) = (n+e)，e \in (-2^{\beta-\alpha},2^{\beta-\alpha})\)。

很显然即使给定的 \((xt_i + e_i) mod p\) 再多，由于 \(e_i\) 的存在，其未知量始终比方程数多1，故无法列出直接可解的线性方程组；
但若 \(e_i\) 相较 \(t_i,x\) 比较小，则可以将之转化为一个格上的CVP问题求解。

CVP问题求解：“增广”为SVP，或用Babai's Algorithm

HNP问题使得现有的大量非对称密码算法（RSA、ECC、DSA等）在实际应用中暴露出弱点。
非对称密码算法所依赖的数学难题多数存在一个隐藏前提，即单次应用（只给定一组特定的公钥、密文等等进行攻击），但实践中因为种种原因（交互、密文传输需求等等）攻击者可以得到多组有一定联系的参数。
这种“联系”如果比较强（多数由于应用不符合密码算法设计原则，比如DSA中复用随机数、RSA广播攻击之复用(m,e)等等），攻击者即可得到一个线性方程组，由此可以很轻易地得到私钥、明文等。

但即使这种“联系”比较弱或模糊，不能直接列出线性方程组得到确定解时（形如“变量比方程数多1”），仍可能通过格攻击来获得某个不变的隐藏变量。
在密码学应用中，这点亟需防范——多数场景下攻击者可以通过主动交互/观察交互过程来达成其目的。

如在DSA中，随机数生成参数选取不当，或位信息泄露（侧信道等）的攻击：

from Crypto.Util.number import *
from random import randint,getrandbits
from hashlib import sha256

class DSA:
    def __init__(self):
        self.q = getPrime(160)
        while True:
            self.p = q * getrandbits(884)
            if isPrime(self.p):
                break

        self.g = pow(randint(1,self.p),(self.p-1)//self.q,self.p)

        self.x = randint(0,self.q)
        self.y = pow(self.g,self.x,self.p)

    def sign(self,m:bytes):
        k = getrandbits(128)
        H = int.from_bytes(sha256(m).digest()) 
        r = pow(self.g,k,self.p)
        s = (H+ self.x*r) * pow(k,-1,self.q) % self.q
        return r,s

    def verify(self,m:bytes,r:int,s:int):
        H = int.from_bytes(sha256(m).digest())
        u1 = H * pow(s,-1,self.q) % self.q
        u2 = r * pow(s,-1,self.q) % self.q
        v = pow(self.g,u1,self.p) * pow(self.y,u2,self.p) % self.q
        return v == r

    def get_pubkey(self):
        return self.p,self.q,self.g,self.y

    

本例中DSA的设计看似天衣无缝，只是随机数 \(k\) 的位数相较 \(p\) 小了一些。但恰是这分毫之差，即让攻击者有可乘之机。
考虑一下DSA中生成签名的同余方程，对之进行转化：
\(s \equiv (H(m) + xr)k^{-1} mod q\)
\(k \equiv (H(m) + xr)s^{-1} mod q\)
\(k \equiv H(m)s^{-1} + rs^{-1}x mod q\)
\(k = H(m)s^{-1} + rs^{-1}x + lq (l \in Z)\)

已知 \(k << q\)，上述等式中的 \(H(m)\)、\(s^{-1}\)、\(r\)均已知，则其就等价于一个HNP问题。
攻击者能收集到对任意已知 \(H(m)\) 足够多的签名集 \((r,s)\) 后，即可构造格进行攻击，获取私钥 \(x\)。

将该问题抽象为一个CVP问题，记 \(A_i = r_is_i^{-1} (mod q)\)，\(B_i = H(m)s_i^{-1}\) ，则为：
我们需要在格 \(L = \begin{bmatrix}q\\&q\\&&q\\&&& \ddots \\&&&&q\\ A_1 & A_2 & A_3 & \cdots & A_n & C_0 \end{bmatrix}\) 中， 找到一个最靠近向量 \(v = \begin{bmatrix}B_1 & B_2 & B_3 & \cdots&B_n & C_0x \end{bmatrix}\) 的向量。

CVP问题的一种解法是通过增加一个维度来转化为SVP问题。
具体而言，将 \(v\) 的前置已知系数整合进 \(L\) 中，令锚定的线性组合 \(a\) 最后一维的值为 \(1\)，完整构造结果形如：
\(\begin{bmatrix}l_1&l_2&l_3&\cdots&l_n&x&1\end{bmatrix} \cdot \begin{bmatrix}q\\&q\\&&q\\&&&\ddots\\&&&&q\\ A_1&A_2&A_3&\cdots&A_n&C_0\\ B_1&B_2&B_3&\cdots&B_n&&C_1\end{bmatrix} = \begin{bmatrix}k_1&k_2&k_3&\cdots&k_n&C_0x&C_1\end{bmatrix}\)
通过调整 \(C_0\)与 \(C_1\)，可以令目标向量在格中成为短向量，进而通过规约直接求解。

#sage
from os import urandom
from hashlib import sha256

dsa = DSA()
rlist = []
slist = []
msg = urandom(16)
hashv = int.from_bytes(sha256(msg).digest())
rep = 20

for i in range(rep):
    temp = dsa.sign(msg)
    rlist.append(temp[0])
    slist.append(temp[1])

mt = matrix(QQ,rep+2,rep+2)
p,q,g,y = dsa.get_pubkey()

#Assistant variable
Bls = [hashv * pow(i,-1,q) % q for i in slist]
Als = [i*pow(j,-1,q) % q for i,j in zip(rlist,slist)]

for i in range(rep):
    mt[i,i] = q
    mt[-2,i] = Als[i]
    mt[-1,i] = Bls[i]

C1 = 2^(-32)
C2 = 2^128

mt[-2,-2] = C1
mt[-1,-1] = C2

mt = mt.LLL()
for r in mt:
    if r[-1].abs() == C2:
        print(f'x = {ZZ(r[-2] / C1).abs()}')
        break

针对CVP问题，另一种性能更好的解法是 Babai's nearest plane algorithm，其步骤及实现如下：
输入一个n维空间上的格 \(L\) 和 \(t \in Z^{n}\)，输出 \(v \in L\) 且其满足 \(\|v-t\| \leq 2^{\frac{n}{2}} dist(t,L)\) （相当于求的是CVP的近似解）。

1. 对L进行LLL格基规约（取 \(\delta = 0.75\)）
   
2. 置 \(b = t\)，令 \(i\) 遍历 \(n \rightarrow 1\)，对每个 \(i\) 执行 \(b = b - \lceil \frac{b \cdot v_i}{v_i \cdot v_i} \rfloor v_i\)。

最终输出向量 \(v = t - b\)。

该算法可以理解为在规约并正交化后的 \(L\) 中试图找到一个最靠近 \(v\) 的线性组合。

#sage
def babai(A, w):
    A = A.LLL(delta=0.75)
    G = A.gram_schmidt()[0]
    t = w
    for i in reversed(range(A.nrows())):
        c = ((t * G[i]) / (G[i] * G[i])).round()
        t -= A[i] * c
    return w - t

“巧击”背包密码

背包问题

“背包”问题是一个老生常谈的算法问题。
原始问题的抽象描述形如：
已知整数数列 \(\{w_1,w_2,\cdots,w_n\}\) 和整数 \(w_t\)，找出数列 \(\{m_1,m_2,\cdots,m_n\} (m_i \in \{0,1\})\)，使得 \(w_t = \sum_{i=1}^{n} m_iw_i\)。
较具象地来说，若存在质量分别为 \(\{w_i\}\) 的 \(n\) 个物件各一个，则需找出一个能够恰好装满质量为 \(w_t\) 的背包的物件组合。

直观上，这个问题的时间复杂度为 \(O(2^n)\)，因为我们必须要枚举所有可能的组合的和——因而随着n增大，该算法的时间复杂度将急速上升。

但并非所有的背包集 \({w_i}\) 都必须暴力枚举才能完成攻击：假设 \({w_i}\) 是超递增序列，那么获得其解的难度将大幅下降。

超递增序列即满足 \(\forall i \in (1,n], \sum_{j=1}^{i-1} x_j < x_i\) 的序列；通俗些说，就是“每个元素大于前面所有元素的和”的序列。
如 \(\{1,2,5,11,26,73,\cdots \}\) 就是一个超递增序列。

如果 \(w_t\) 是一个超递增背包序列的和，不难发现只需从 \(i = n\)开始向下遍历，若 \(w_t > w_i\)，则令 \(w_t\) 减去之并置 \(m_i = 1\)，否则置 \(m_i = 0\)。

若希望使用背包问题进行信息的加密，显然又不能使用超递增序列作为密钥——此时其仍为对称密码，信息的加/解密难度是对称的人家利用这个也能快速解密，相当于encryption退化成encoding。
此时需要利用陷门的乘数和模数对背包集进行一些处理，将之改造为公私钥密码体制。

背包密码详述

背包密码的描述如下：

随机生成超递增序列 \(\{x_1,x_2,\cdots,x_n\}\) 、模数 \(p > x_n\) 与乘数 \(r\)。
计算 \({y_i}, i \in [1,n], y_i = rx_i mod p\) 作为公钥，\((p,r)\)为私钥。

公钥加密：记待加密的信息为 \(\{m_1,m_2,\cdots,m_n\} (m_i \in \{0,1\})\)，输出密文 \(c = \sum_{i=1}^{n} m_iy_i\)。
私钥解密：先计算 $m = r^{-1}c mod p $，同时还原递增序列 \(\{x_i\} (x_i = r^{-1}y_i, i \in [1,n])\)，随后即可较简单地获得 \(\{m_i\}\)。

在只知道公钥的前提下，传统观点认为攻击者需要枚举所有的 \(\{m_i\}\)，当 \(n \geq 64\) 时几乎可以认为暴力攻击在计算上不可行。

但在格的帮助下，攻击者可以将既有的公钥集和密文构造一个格，对之进行规约后即可从中提取 \(\{m_i\}\)。
依赖的方程也非常简单：本场景下，就是将既有的一个方程 \(\sum_{i=1}^{n} m_iy_i\) 展开为向量与矩阵乘积的形式，重点是需要对矩阵进行一定的构造。

需要注意的是，这种攻击方法并不涉及对私钥的攻击（即并没有还原递增序列 \(\{x_i\}\)），相当于攻击的目标只是解密给定的密文。

靶子：

#sage
from Crypto.Util.number import *
from random import randint
from functools import reduce

class Bag:
    def __init__(self):
        total = randint(16,128)
        self.prikey = [total]

        for _ in range(127):
            temp = randint(total,int(1.2*total))
            total += temp
            self.prikey.append(temp)
            
        self.p = getPrime(256)
        self.r = getPrime(255)

        self.pubkey = [i*r%p for i in self.prikey]

    def encrypt(self,msg:bytes):
        assert len(msg) % 32 == 0
        result = []

        for i in range(len(msg)//32):
            plain = [int(c) for c in bin(int.from_bytes(msg[i*8:(i+1)*8],'big'))[2:]]
            enc = reduce(lambda x,y: x*y,plain,self.pubkey)
            result.append(enc)

        return result

    def get_pubkey(self):
        return self.pubkey
        

#sage
bag = Bag()
ls = bag.get_pubkey()

cipher = bag.encrypt(urandom(32))[0]

mt = matrix(ZZ,129,129)
mt[0] = [cipher] + [1] * 128
for i in range(128):
    mt[i+1,0] = ls[i]
    mt[i+1,i+1] = 2

mt=mt.LLL()
assert mt[0,0] == 0

output = list(map(lambda x: 1 if x==1 else 0,mt[0][1:])

这种攻击方式有两个要点：

1. output的结果解析出来可能和预期值恰好相反（想想为什么？下面NTRU部分有解答），需利用背包集的原方程校验之。
   
2. 对于该格的构造，将对角元素设置为2、含有背包值的行设置为1这种构造方式的动机不太直观。其缘由依然是大幅增加 \(det(L)\) 的同时保证 \(\|v_t\|\) 基本不变，提高规约成功率。

记两种方式（对角1、对角2）构造的n维格分别为 \(L_1\)、\(L_2\)，目标向量分别为 \(v_{t1}\) 和 \(v_{t2}\)。
直观上，\(det(L_2) = 2^{n-1}det(L_1)\)，且 \(E(\frac{\|v_{t1}\|}{\|v_{t2}\|}) = \frac{\sqrt{2}}{2}\)。

青天——从少量方程组中析取信息

从NTRU入门“短格”

利用“青天”之术，尝试一下对NTRU(Number Theory Research Unit)的攻击。

NTRU Encryption原理：

密钥生成：
选定质数 \(q\) ，随机选取 \(f \in (2,q-2)\)， \(g \in (\frac{q}{2},q)\)，保证 \(gcd(f,g) = 1\)。
计算 \(h \equiv f^{-1}g (mod q)\)，公钥为 \((q,h)\)，私钥为 \((f,g)\)。

公钥加密：
选取一个临时数 \(r\)，记待加密的消息为 \(m\)，通过约束其上界使 \(rg + mf < q\)成立。
计算密文 \(c \equiv rh + m (mod q)\)。

私钥解密：
计算 \(a \equiv cf (mod q)\)，显然 \(a \equiv rhf + mf \equiv rg + mf (mod q)\)。
输出明文 \(m \equiv af^{-1} (mod g)\)，其解密正确性显然。

注意到NTRU的公钥生成中，存在 \(fh \equiv g (mod q)\)，转化为等式即为 \(fh + kq = g (k \in Z)\)。
将该等式“构造”为一个向量乘法的形式：
\(\begin{bmatrix} f & k \end{bmatrix} \cdot \begin{bmatrix} 1 & h \\ 0 & q \end{bmatrix} = \begin{bmatrix} f & g \end{bmatrix}\)。

若参数选取不当（密钥生成中 \(f,g\) 过小，最常见的就是 \(g << \frac{q}{2}\)），使得结果向量在格中是一个短向量，则对该格进行规约即可得到 \(\begin{bmatrix} f & g \end{bmatrix}\)，直接获得两个私钥。

#sage
from Crypto.Util.number import *
from random import getrandbits

class NTRU:
    def __init__(self):
        self.q = getPrime(1024)
        self.f = getPrime(256)
        self.g = getPrime(512)
        self.h = ZZ(self.g * pow(self.f,-1,self.q) % self.q)

    def encrypt(self,m:int):
        r = getrandbits(512)
        assert m < 2^8

        return ZZ((r*self.h + m) % self.q)

    def decrypt(self,c:int):
        a = ZZ(c*self.f) % self.q
        return ZZ(a * pow(self.f,-1,self.g))

    def get_pubkey(self):
        return self.q,self.h

“短格”的攻击代码多数都极为精炼，如本例中：

#sage

def NTRU_attack(q:int,h:int):
    mt = matrix(ZZ,[[1,h],[0,q]])
    mt = mt.LLL()
    return mt[0] if mt[0,0] > 0 else -mt[0]


ntru = NTRU()
q,h = ntru.get_pubkey()
f,g = NTRU_attack(q,h)
print(f'(f,g)=({f},{g})')

切记LLL的规约结果很多时候并不“理想”，构造目标向量足够短的情况下，有两个常见的原因：
1. 格中存在比目标向量更短的向量（在一些构造比较“模糊”的格中容易出现），由于格基规约的贪心特性，会令调用者错过“预期”结果；
2. 最终的短向量确由向量与矩阵的乘法产生，但LLL并不预先知道这个系数向量，最常见的结果就是输出向量与目标向量恰好相反，如上题NTRU_attack()中返回值的处理就是应对这种情况。

对既有密码体系的攻击——以Wiener's Attack的格形式为例

分析一下RSA的等式：
\(ed \equiv 1 (mod \varphi(N))\)
\(ed + k\varphi(N) - 1 = 0\)
\(ed + kN = p + q + 1 - k\)

所有运算数均为整数，d较小，k为未知整数，右侧 \(p + q + 1 - k\) 可视为小量（比较显然）。

将上述等式转化为向量乘法： \(\begin{bmatrix} d & k \end{bmatrix} \cdot \begin{bmatrix} e & \sqrt{N} \\ N & 0 \end{bmatrix} = \begin{bmatrix} ed + kN & d\sqrt{N} \end{bmatrix}\)

此处 \(\sqrt{N}\) 的作用是配平格，提高规约成功率。
设矩阵[0,1]位置的元素为 \(C\)，显然矩阵的行列式（绝对值）为 \(CN\)，同时目标向量是 \(\begin{bmatrix} ed + kN & dC \end{bmatrix}\)。
在 $dC << (p + q + 1 - k) $ 时，改变C的值对目标向量的模长影响可以忽略。
通过增加 \(C\) 进而增大 \(det(M)\) ，根据Hermite定理可以增大解出目标向量 \(v\) 的概率。
注意到 \(p + q + 1 \approx 2\sqrt{N}\)，又 \(|k| = \frac{ed - 1}{\varphi(N)} \approx \frac{ed}{N}\)，在 \(e \approx N\) 时，C取 \(\sqrt{N}\) 基本就够用了。
配平格是格基规约中非常重要的一步，很多场景下配平质量几乎决定了规约成功率。

对该格进行格基规约，即有机会得到结果向量；取其第二维数值除以 \(\sqrt{N}\)（亦可以校验其是否整除来判定攻击成功与否），取绝对值即可得到私钥 \(d\)。

#sage
def attack(N:int,e:int):
    mt = matrix(ZZ,[[e,isqrt(N)],[N,0]])
    mt = mt.LLL()
    if mt[0,1] % isqrt(N) != 0:
        return None

    return ZZ(mt[0,1] /isqrt(N)).abs()

看到None第一反应还是逆向联动回了cpp的std::optional

春滋——基于格问题的后量子密码体系

后量子密码学(post-quantum cryptography) 是一个近年的新兴概念。其起源于在对量子计算机的研究中，诸多量子算法的提出对许多既有数学问题的安全性提出了极大考验。
目前现代密码学中，非对称密码算法依赖的许多数学难题（著名的如大整数分解、有限域上/椭圆曲线上的离散对数问题）理论上在高效的量子计算机中可以在多项式时间(Polynomial Time)内被攻破：其中最有名的就是舒尔算法(Shor's Algorithm)。
所幸目前这些都是算法理论上的分析——由于目前我们对量子计算的实践研究依然非常浅薄，截至2022年，已知现实中被舒尔算法分解的最大整数是21。

但密码学研究是具有极强的理论性和前瞻性的：任何密码算法一旦被提出可能存在高效的攻击方法，则无论攻击已经被实现与否，都应当认为这个算法是脆弱的，应当对之多加巩固或另寻出路。
后量子密码学的研究即在这一背景下被提出，其研究目标是提出迄今理论上连量子计算机都无法攻破的密码体系。

目前后量子密码学的研究方向主要有四个，格即为其中之一。

AGCD问题

AGCD问题，全称Approximate Greatest Common Divisor Problem，即近似最大公约数问题。

其是传统的最大公约数(GCD)问题的延申：
假设我们有一组数 \(x_1,x_2,...,x_n\)，已知 \(x_i = pq_i\)，则我们有很多种算法可以快速求出 \(p\) 。
但若加入误差 \(e_i (e_i < q_i)\)，将条件变为 \(x_i = pq_i + e_i\)，那么就难以直接求解最大公约数了。

当 \(i\) 和 \(e_i\)较小时，可以尝试爆破 \(e_i\) 来获得 $p = gcd(x_1-e_1,x_2-e_2,...,x_n-e_n) $，但多数情况下如此做在计算上是不现实的。

对AGCD的近似格攻击如下：
首先将上述问题的参数精确化，记 \(p,|e_i|,x_i\) 的大小分别为 \(\eta,\rho,\gamma\) 位。

注意到 \(q_0x_i - q_ix_0 = q_0(pq_i+e_i) - q_i(pq_0+e_0)\)
即 \(q_0x_i - q_ix_0 = q_0e_i - q_ie_0\)。

显然，\(\{q_0,q_1,...,q_n\}\) 是大小未知的整系数，\(q_0e_i - q_ie_0\) 是比较小的整系数。

于是可以构造“碧海”格：记 \(E_i = q_0e_i-q_ie_0\)，则有

\(\begin{bmatrix} q_1 & q_2 & q_3 & \cdots & q_0 \end{bmatrix} \cdot \begin{bmatrix} x_1\\&x_2\\&&x_3\\&&&\ddots\\&&&&x_n\\ -x_0&-x_0&-x_0&\cdots&-x_0&C \end{bmatrix} = \begin{bmatrix} E_1&E_2&E_3&\cdots&E_n&Cq_0\end{bmatrix}\)

显然目标向量在格中是一个短向量。配平中可以令 \(C=2^{\rho+1}\)。
规约得到短向量后从中得到 \(q_0\)，计算 \(e_0 = x_0 mod q_0\)，\(p = \frac{x_0-e_0}{q_0}\) 即可。

需要满足 \(n > \frac{\gamma-\rho}{\eta-\rho}\)，格攻击才有解。

基于AGCD问题的FHE（全同态加密）

一个运算 \(F(x)\) 满足全同态是其满足加法同态和乘法同态的充要条件。

加法同态： \(\forall \{x_n\}, F(\sum_{i=1}^{n} x_i) = \sum_{i=1}^{n} F(x_i)\)
乘法同态： \(\forall \{x_n\}, F(\prod_{i=1}^{n} x_i) = \prod_{i=1}^{n} F(x_i)\)

若对于 \(F(x)\)，在一定条件下n存在上界，则称之为部分同态。
很容易举出很多同态运算的例子，比如 \(g(x) = 2x\) 满足加法同态，\(h(x) = x^2\) 满足乘法同态。
部分非对称加密算法同样具有同态性，典型的如RSA就满足乘法同态，其也成为部分场景下RSA伪造签名攻击的一个切入点。

全同态加密在分布式计算等领域中有极为广泛的应用前景。
比如一个服务器希望将某些计算任务分布至大量终端上进行计算，但出于信赖性、数据隐私等问题，又不希望这些计算终端接触明文。

由于加法和乘法运算是一切计算的基础，因此只需满足加法和乘法同态，即可对任意其它基本数学计算满足同态。

而基于AGCD提出的一种加密方案则可以实现（部分的）全同态加密，如下：

取较大的质数 \(p\)、明文上界 \(s\) 进行加密，保证 \(p >> s\)，其中 \(p\) 为私钥。
每加密一位 \(m_i (m_i < s)\)时选取随机数 \(q_i,r_i\)，计算一位密文 \(c_i = pq_i + sr_i + m_i\)。
解密时，计算 \(m_i = (c_i mod p) mod s\)，其正确性很显然。

攻击者在只拥有 \(\{c_i\}\) 和 \(s\) 的情况下极难解出 \(m\)，因为观察解密过程，其必须要爆破能够得到合理明文结果的 \(p\)。

保证同态一直成立的关键是原多项式中系数不是 \(kp\)（\(k\) 为整系数多项式）的项和的绝对值不能超过 \(p\)，否则第一步取模时结果将会出错。

同态性证明：
加法同态：设 \(c_1 = pq_1 + sr_1 + m_1\)，\(c_2 = pq_2 + sr_2 + m_2\)，
存在\(c_1 + c_2 = p(q_1+q_2) + s(r_1+r_2) + (m_1+m_2)\)，定义 \(\{m_i\}\) 的运算均在 \(F_{256}\)上进行，则在 \(sr_i << p\) 时该式显然是成立的。

乘法同态：依然以上述的 \(c_1\)、\(c_2\)为例，
\(c_1c_2 = p^2q_1q_2 + ps(q_1r_2+q_2r_1) + p(q_1m_2+q_2m_1) + s^2r_1r_2 + s(r_1m_2+r_2m_1) + m1m2\)，对于数量较少的 \(m\)，该式依然满足正确解密的条件。

可以发现，加法同态的错误累加为较为缓慢的线性叠加，而乘法同态的错误累加为指数叠加，非常快速。
实践中为了保证同态性，一般需要对 \(s\)、\(r_i\) 的上界做较严格的约束，同时 \(p\) 选取更大的质数来避免解密出错，因此基于AGCD的FHE方案基本都有密文极大的特点。

实践中对于此类错误逐渐累加的方案，亦可以通过不断地解密-再加密来“重置”错误大小，牺牲效率以换取同态性成立。

虽然理论上拥有足够多的密文时，对AGCD问题的格攻击必定可以成立；但在构造格的维度较高时，格基规约的运行效率会大幅下降，\(n \geq 500\) 时计算上基本不可行。

全同态加密之从对称到非对称（私钥密码学到公钥密码学）的拓展

上述方案显然需要有一个服务端负责保管密钥 \(p\) 来进行加密/解密。现将之改造为一个非对称密码体系：
利用私钥 \(p\)，多次加密 \(m_i = 0\) 得到 \(\{k_i\} (k_i = pq_i + sr_i)\)，将 \(\{k_i\}\) 作为公钥。
加密消息时，可以任意选取 \(\{k_i\}\) 的一个整系数线性组合，其和依然可以表示成 \(pq_i + sr_i\)的形式；将其结果和 \(m\) 相加，即可获得密文 \(c\)。

AGCD公钥密码体系及攻击代码如下：

from Crypto.Util.number import *
from random import getrandbits

class AGCD:
    def __init__(self):
        self.eta = 256
        self.rho = 64
        self.gamma = 1024

        self.p = getPrime(self.eta)
        self.s = 256 #2^8

    def encrypt(self,m:int):
        assert abs(m) < self.limit
        
        q = getrandbits(self.gamma)
        r = getrandbits(self.rho - 8)

        return self.p*q + self.s*r + m

    def gen_pubkey(self,len:int = 16):
        return [encrypt(0) for _ in range(len)]

    def decrypt(self,c:int):
        temp = c % self.p
        return temp % self.s


if __name__=='__main__':
    agcd = AGCD()
    ls = agcd.gen_pubkey()

    mt=matrix(ZZ,16,16)

    for i in range(15):
        mt[i,i] = ls[i+1]
        mt[-1,i] = -ls[0]

    C = 2^64

    mt[-1,-1] = C
    mt = mt.LLL()

    assert mt[0,-1] % C == 0
    q0 = ZZ(mt[0,-1] /C).abs() 
    e0 = ls[0] % q0
    p = (ls[0] - e0) / q0

    print(f'p={p}')