格密码 | Triode Field

参考资料：

A Gentle Tutorial for Lattice-Based Cryptanalysis

Improved low-density subset sum algorithms

Solving low-density multiple subset sum problems with SVP oracle

Extended Hidden Number Problem and Its Cryptanalytic Applications

Extending Wiener’s Attack in the Presence of Many Decrypting Exponents

格（Lattice）

格的概念

定义：一个 $n$ 维的格 $L$ 是 $R^{n}$ 的一个离散可加的子群. 对于格 $L$ ，其可以被表示为由 $R^{n}$ 上 $m$ 个线性无关的基向量 ${b b_{1}, b b_{2}, \dots, b b_{m}}$ 组成的基 $B B$ ，向量的个数 $m$ 被称为格 $L$ 的秩，所以格 $L$ 也能表示为： $L = L (B B) = {\sum_{i = 1}^{m} a_{i} b b_{i} | a_{i} \in Z, i = 1, 2, \dots, m}$ 格的很多性质与记号与线性空间（向量空间）类似。 逐次最小长度：对于一个秩维 $n$ 的格 $L$ ，对于 $i \in {1, 2, \dots n}$ ，若 $r$ 是使得格 $L$ 拥有 $i$ 个长度最大为 $r$ 且线性无关的向量的最小值，则称 $r$ 为格 $L$ 的第 $i$ 逐次最小长度，记为 $λ_{i} (L) = r$ 关于逐次最小长度，我们有闵可夫斯基（Minkowski）第一定理： 闵可夫斯基（Minkowski）第一定理：设 $L$ 是一个 $n$ 维满秩格，则： $λ_{1} (L) \leq \sqrt{n} | det (L) |^{1 / n}$ 闵可夫斯基第一定理表明我们可以以 $λ_{1} (L)$ 为标准来评判格中向量的长度.

关于格的问题

最短向量问题（Shortest Vector Problem, $SVP$ ）：给定格 $L$ 的基 $B B$ ，找到格 $L$ 上的一个非零向量 $v v$ 满足 $| | v v | | = λ_{1} (L)$ . 最近向量问题（Closest Vector Problem, $CVP$ ）：给定格 $L$ 的基 $B B$ 以及一个目标向量 $t t$ （不一定在格 $L$ 上），找到格 $L$ 上的一个非零向量 $v v$ 满足 $| | v v - t t | | = min_{w w \in L} | | w w - t t | |$ 上述问题均为NP-Hard问题，这些问题的宽松版本如下： 近似最短向量问题（Approximate Shortest Vector Problem, ${SVP}_{γ}$ ）：给定格 $L$ 的基 $B B$ 与近似因子 $γ$ ，找到格 $L$ 上的一个非零向量 $v v$ 满足 $| | v v | | \leq γ \cdot λ_{1} (L)$ . 近似最近向量问题（Approximate Closest Vector Problem, ${CVP}_{γ}$ ）：给定格 $L$ 的基 $B B$ 、一个目标向量 $t t$ （不一定在格 $L$ 上）以及一个近似因子 $γ$ ，找到格 $L$ 上的一个非零向量 $v v$ 满足 $| | v v - t t | | = γ \cdot min_{w w \in L} | | w w - t t | |$ 而 ${SVP}_{γ}$ 与 ${CVP}_{γ}$ 对于确定的参数均存在有效的解决方案，所以我们可以通过解决 ${SVP}_{γ}$ 与 ${CVP}_{γ}$ 来近似地解决 $SVP$ 与 $CVP$ . 我们可以通过格基规约来解决上述两个可计算问题.

格基规约

格基规约的目标是将一个任意一个格转化为另外一个基相同但是具有更短、更多的正交向量。由于我们要找的是“短向量”，所以格基规约可能会提供解决近似最短向量问题的方法.

LLL算法

LLL算法是一个迭代算法，由Lenstra、Lenstra与Lovász提出. 这个迭代算法的第一步是通过施密特正交化获得基 $B B = {b b_{1}, b b_{2}, \dots, b b_{n}}$ 的一组正交基，通过施密特正交化，我们可以将格基进行约减，对于上面的基 $B B$ ，施密特正交化过程如下： ${\begin{cases} b b_{i}^{*} = b b_{i}, & i = 1 \\ b b_{i}^{*} = b b_{i} - \sum_{j = 1}^{i - 1} μ_{i, j} b b_{j}^{*}, & 1 < i \leq n \end{cases} μ_{i, j} = \frac{⟨ b b_{i}, b b_{j}^{*} ⟩}{⟨ b b_{j}^{*}, b b_{j}^{*} ⟩}$ 而对于 $δ \in (\frac{1}{4}, 1)$ ，如果基 $B B = {b b_{1}, b b_{2}, \dots, b b_{n}}$ 满足：

（尺寸约减，size-reduction）对于任意 $i > j$ ，有 $| μ_{i, j} | \leq \frac{1}{2}$ ；
（Lovász条件，Lovász condition）对于任意 $i \in {1, 2, \dots, n - 1}$ ，有 $(δ - μ_{i + 1, i}^{2}) | | b b_{i}^{*} | |^{2} \leq | | b b_{i + 1}^{*} | |^{2}$

则称基 $B B$ 为 $δ$ -LLL约减基，通过结合这两个条件，Lenstra、Lenstra与Lovász给出了LLL算法：而对于格中最短向量的下界，我们有如下定理：设格基 $B B = {b b_{1}, b b_{2}, \dots, b b_{n}}$ 对应的施密特正交基为基 $B B^{*} = {b b_{1}^{*}, b b_{2}^{*}, \dots, b b_{n}^{*}}$ ，则有： $λ_{1} (L (B B)) \geq min_{i \in {1, \dots, n}} | | b b_{i}^{*} | |$ 通过这个定理，我们可以导出如下命题：假若 $B B = {b b_{1}, b b_{2}, \dots, b b_{n}}$ 是一个 $δ$ -LLL约减基，则必然有： $| | b b_{1} | | \leq {(\frac{2}{\sqrt{4 δ - 1}})}^{n - 1} \sqrt{n} \cdot | det (L) |^{1 / n}$

这条式子往往可以帮助我们判断一个格基是否能通过LLL来约减出最短向量. 在sage中内置了现成的LLL算法，例如我们要解决A Gentle Tutorial for Lattice-Based Cryptanalysis中的例3.12（如下图）：则可以通过下面的步骤来获得结果：显然可以得到结果为 $b b_{1}^{*} = (0, - 1), b b_{2}^{*} = (- 2, 0)$ .

解决CVP

LLL算法同样可以用来解决近似最近向量问题，但是需要结合Babai最近平面算法或者Kannan嵌入法

Babai最近平面算法（Babai’s Nearest Plane Algorithm）

Babai最近平面算法首先要获得输入格的约减基 $B B = {b b_{1}, b b_{2}, \dots, b b_{n}}$ ，然后对于目标向量 $t t$ ，我们令 $t t^{'} = t t - c_{n} b b_{n}$ ，其中： $c_{n} = ⌈ ⟨ t t, b b_{n}^{*} ⟩ / ⟨ b b_{n}^{*}, b b_{n}^{*} ⟩ ⌋$ （其中 $⌈ \cdot ⌋$ 表示四舍五入），然后对前 $n - 1$ 个向量与 $t t^{'}$ 进行操作，得到 $t t^{″} = t t^{'} - c_{n - 1} b b_{n - 1}$ ，其中 $c_{n} = ⌈ ⟨ t t^{'}, b b_{n - 1}^{*} ⟩ / ⟨ b b_{n - 1}^{*}, b b_{n - 1}^{*} ⟩ ⌋$ ，以此类推，就可以得到完整的Babai最近平面算法：

Kannan嵌入法

Kannan嵌入法是通过将目标向量嵌入格基，从而将CVP转化为SVP进行求解，设输入的格基为 $B B = {b b_{1}, b b_{2}, \dots, b b_{n}}$ ，而目标向量为 $t t = (t_{1}, t_{2}, \dots, t_{n})$ ，我们设CVP的解为 $c_{1} b b_{1} + c_{2} b b_{2} + \dots + c_{n} b b_{n}$ ，即： $t t \approx \sum_{i = 1}^{n} c_{i} b b_{i}$ 也就有： $t t = \sum_{i = 1}^{n} c_{i} b b_{i} + e e$ 其中 $| | e e | |$ 很小，所以我们就可以构造出一个 $n + 1$ 维的格： $B B^{'} = (\begin{matrix} B B & 0 \\ t t & q \end{matrix})$ 因为有： $(- c_{1}, - c_{2}, \dots, - c_{n}, 1) B B^{'} = (e e, q)$ 所以这个格显然包含短向量 $(e e, q)$ ，由此我们就可以得到CVP的解为 $t t - e e$ . 在这里，整数 $q$ 称为嵌入因子，它会影响到通过LLL算法寻找正确向量的成功率，应根据实际情况选取.

格在密码学中的应用

背包问题（Knapsack Problem）

背包问题是NP完全问题，其经常被用于作为公钥密码体系的陷阱门。在密码学中，背包问题的常见版本为子集和问题，即：给定 $n$ 个正数 $a_{1}, a_{2}, \dots, a_{n}$ 与一个整数 $s$ ，寻找集合 ${a_{1}, a_{2}, \dots, a_{n}}$ 的子集使得其和为 $s$ 。也就是找到 $e_{1}, e_{2}, \dots, e_{n} \in {0, 1}$ 使得： $s = \sum_{i = 1}^{n} e_{i} a_{i}$

低密度子集和问题

集合 ${a_{1}, a_{2}, \dots, a_{n}}$ 的密度 $d$ 可以通过下式计算： $d = \frac{n}{\log_{2} max_{i \in {1, 2, \dots, n}} (a_{i})}$ 研究表明，当 $d < 0.9408$ 时，我们可以将子集和问题转换为求解SVP. 一般策略为构造一个格，其中有一个短向量包含 ${e_{1}, e_{2}, \dots, e_{n}}$ ，这样我们就可以构造出下面的格基矩阵： $B B = (\begin{matrix} 1 & a_{1} \\ 1 & a_{2} \\ ⋱ & ⋮ \\ 1 & a_{n} \\ s \end{matrix})$ 显然线性组合 $(e_{1}, e_{2}, \dots, e_{n}, - 1)$ 会生成一个短向量 $(e_{1}, e_{2}, \dots, e_{n}, - 1) B B = (e_{1}, e_{2}, \dots, e_{n}, 0)$ ，所以我们的预期是通过LLL算法对上述格进行规约得到这个短向量，但是这个方法在密度比较高的时候会失效，所以Coster等人提出了CJLOSS算法，使得我们可以在 $d < 0.9408$ 的时候通过将子集和问题转换为SVP从而在多项式时间内求解这个问题，CJLOSS算法中构造的格为： $B B^{'} = (\begin{matrix} 1 & N a_{1} \\ 1 & N a_{2} \\ ⋱ & ⋮ \\ 1 & N a_{n} \\ \frac{1}{2} & \frac{1}{2} & \dots & \frac{1}{2} & N s \end{matrix})$ 其中整数 $N > \sqrt{n}$ ，在这个格内，线性组合 $(e_{1}, e_{2}, \dots, e_{n}, - 1)$ 会生成另外一个短向量： $(e_{1}, e_{2}, \dots, e_{n}, - 1) B B^{'} = (e_{1} - \frac{1}{2}, e_{2} - \frac{1}{2}, \dots, e_{n} - \frac{1}{2}, 0)$ 显然这条短向量的模为 $\frac{\sqrt{n}}{2}$ ，我们很容易可以通过LLL算法求解出这条短向量（这个短向量一般是规约后的格的第一个向量，且前 $n$ 个元素往往为 $\frac{1}{2} - e_{i}$ ）。使用sage通过CJLOSS算法求解低密度子集和的代码如下：

python

def CJLOSS(A, s):
    n = len(A)
    N = ceil(sqrt(n))
    L = matrix(QQ, n + 1)
    for i in range(n):
        L[i, i] = 1
        L[n, i] = 1/2
        L[i, n] = N * A[i]
    L[n, n] = N * s
    res = L.LLL()
    for v in res:
        if all(x in [-1/2, 1/2] for x in v[:-1]):
            out = [1/2 - a for a in v[:-1]]
            return out

例如，对于一个集合

{71, 73, 79, 107, 89, 91}

，求出满足和为

269

的一个子集，我们就可以通过CJLOSS算法进行求解（计算可得

d = \frac{6}{\log_{2} 107} \approx 0.8900 < 0.9408

）：

所以可以得到和为

269

的一个子集为

{73, 107, 89}

低密度多重子集和问题

通过对子集和问题的扩展，我们可以得到多重子集和问题：给定 $k n$ 个正整数 $a_{1, 1}, a_{1, 2} \dots, a_{k, n}$ 以及 $k$ 个整数 $s_{1}, \dots, s_{k}$ ，找到 $e_{1}, e_{2}, \dots, e_{n} \in {0, 1}$ 满足对任意 $j \in 1, 2, \dots, k$ ： $s_{j} = \sum_{i = 1}^{n} e_{i} a_{j, i}$ 实际上多重子集和问题总体与普通子集和问题差不多，但是集合更多，此时我们通过下式对密度 $d$ 进行计算： $d = \frac{n}{k \log_{2} max_{\begin{matrix} \end{matrix}} (a_{j, i})}$ 根据潘彦斌等人研究可以得出，当 $d < 0.9408$ 时，我们可以通过构造如下格来将低密度多重子集和问题转换为SVP进行求解： $B B = (\begin{matrix} 1 & 0 & N a_{1, 1} & N a_{2, 1} & \dots & N a_{k, 1} \\ 1 & 0 & N a_{1, 2} & N a_{2, 2} & \dots & N a_{k, 2} \\ ⋱ & ⋮ & ⋮ & ⋮ & ⋱ & ⋮ \\ 1 & 0 & N a_{1, n} & N a_{2, n} & \dots & N a_{k, n} \\ \frac{1}{2} & \frac{1}{2} & \dots & \frac{1}{2} & \frac{1}{2} & N s_{1} & N s_{2} & \dots & N s_{k} \end{matrix})$ 其中整数 $N > \sqrt{\frac{n + 1}{4}}$ ，此时在这个格内，线性组合 $(e_{1}, e_{2}, \dots, e_{n}, - 1)$ 会生成一个短向量： $(e_{1}, e_{2}, \dots, e_{n}, - 1) B B = (e_{1} - \frac{1}{2}, e_{2} - \frac{1}{2}, \dots, e_{n} - \frac{1}{2}, - \frac{1}{2}, 0, \dots, 0)$ 通过LLL算法我们就可以得到这个短向量.

低密度模子集和问题与低密度多重模子集和问题

通过对子集和问题的扩充，我们可以得到模子集和问题：给定 $n$ 个模 $M$ 下的正整数 $a_{1}, a_{2}, \dots, a_{n}$ ，再给出一个整数 $s$ ，找到 $e_{1}, e_{2}, \dots, e_{n} \in {0, 1}$ ，使得： $s \equiv \sum_{i = 1}^{n} e_{i} a_{i} (\mod M)$ 从而可以推广为多重模子集和问题：给定 $k n$ 个模 $M$ 下的正整数 $a_{1, 1}, a_{1, 2} \dots, a_{k, n}$ 以及 $k$ 个整数 $s_{1}, \dots, s_{k}$ ，找到 $e_{1}, e_{2}, \dots, e_{n} \in {0, 1}$ 满足对任意 $j \in 1, 2, \dots, k$ ： $s_{j} \equiv \sum_{i = 1}^{n} e_{i} a_{j, i} (\mod M)$ 实际上，模子集和问题问题可以视作 $k = 1$ 的多重模子集和问题，我们可以通过下式对多重模子集和问题的密度 $d$ 进行计算： $d = \frac{n}{k \log_{2} M}$ 根据潘彦斌等人研究可以得出，当 $d < 0.9408$ 且 $k = ο (\frac{n}{\log_{2} ((n + 1) \sqrt{n} + 1)})$ 时，我们可以通过构造如下格来将低密度多重模子集和问题转换为SVP进行求解： $B B = (\begin{matrix} 1 & 0 & N a_{1, 1} & N a_{2, 1} & \dots & N a_{k, 1} \\ 1 & 0 & N a_{1, 2} & N a_{2, 2} & \dots & N a_{k, 2} \\ ⋱ & ⋮ & ⋮ & ⋮ & ⋱ & ⋮ \\ 1 & 0 & N a_{1, n} & N a_{2, n} & \dots & N a_{k, n} \\ N M \\ N M \\ ⋱ \\ N M \\ \frac{1}{2} & \frac{1}{2} & \dots & \frac{1}{2} & \frac{1}{2} & N s_{1} & N s_{2} & \dots & N s_{k} \end{matrix})$ 使用LLL算法进行规约就可以得到目标短向量 $(e_{1} - \frac{1}{2}, e_{2} - \frac{1}{2}, \dots, e_{n} - \frac{1}{2}, - \frac{1}{2}, 0, \dots, 0)$ .

隐藏数问题（Hidden Number Problem，HNP）

隐藏数问题的形式一般为给定一个质数 $p$ ，令 $α \in [1, p - 1]$ 作为“被隐藏的数字”，给定 $m$ 个数对 ${(t_{i}, a_{i})}_{i = 1}^{m}$ 使得： $β_{i} - t_{i} α + a_{i} \equiv 0 (\mod p)$ 其中 $| β_{i} | < K < p$ ，我们需要从中恢复出 $α$ . 为解决这类问题，我们可以重写 $β_{i} - t_{i} α + a_{i} \equiv 0 (\mod p)$ 为 $β_{i} + a_{i} = t_{i} α + k_{i} p$ ，这样我们就可以构造出下面的格： $B B = (\begin{matrix} p \\ p \\ ⋱ \\ p \\ t_{1} & t_{2} & \dots & t_{m} & \frac{1}{p} \end{matrix})$ 对于向量 $v v = (k_{1}, \dots, k_{m}, α)$ 有 $v v B B = (β_{1} + a_{1}, \dots, β_{m} + a_{m}, α / p)$ ，显然这个向量并不是很短，但是我们注意到： $v v B B = (a_{1}, \dots, a_{m}, 0) + (β_{1}, \dots, β_{m}, α / p)$ 那么令 $t t = (a_{1}, \dots, a_{m}, 0), u u = (β_{1}, \dots, β_{m}, α / p)$ ，我们就可以得到： $v v B B - t t = u u$ 其中 $| | u u | | < \sqrt{m + 1} K$ ，显然我们可以通过将求解HNP转换为求解CVP，通过Kannan嵌入法，令嵌入因子为 $K$ ，我们就可以得到下面的格： $B B^{'} = (\begin{matrix} p \\ p \\ ⋱ \\ p \\ t_{1} & t_{2} & \dots & t_{m} & \frac{K}{p} \\ a_{1} & a_{2} & \dots & a_{m} & K \end{matrix})$ 其包含向量 $u u^{'} = (β_{1}, \dots, β_{m}, K α / p, - K)$ ，且 $| | u u^{'} | | < \sqrt{m + 2} K$ ， $det (B B^{'}) = p^{m - 1} K^{2}$ ，显然有： $| | u u^{'} | | < \sqrt{m + 2} K < {(\frac{2}{\sqrt{4 δ - 1}})}^{m + 1} \sqrt{m + 2} | det (B B^{'}) |^{1 / (m + 2)}$ 所以我们可以通过LLL来找到短向量 $u u^{'}$ ，但是这个向量并不是最短的，因为格上存在另一个向量 $(0, \dots, 0, K, 0)$ ，它比 $u u^{'}$ 更短，所以 $u u^{'}$ 一般在规约后的第二个向量.

扩展隐藏数问题（Extended Hidden Number Problem，EHNP）

通过对一般的隐藏数问题的扩展我们可以得到扩展隐藏数问题：给定素数 $p$ ，对整数 $x \in [1, p - 1]$ ，有： $x = \overset{―}{x} + \sum_{j = 1}^{m} 2^{π_{j}} x_{j}$ 其中 $\overset{―}{x}$ 以及 $π_{j}$ 均已知，而未知整数 $x_{j}$ 对于一个已知的整数 $ν_{j}$ 满足 $0 \leq x_{j} < 2^{ν_{j}}$ ，给出 $d$ 条方程： $α_{i} \sum_{j = 1}^{m} 2^{π_{j}} x_{j} + \sum_{j = 1}^{l_{i}} ρ_{i, j} k_{i, j} \equiv β_{i} - α_{i} \overset{―}{x} (\mod p)$ 其中对于 $1 \leq i \leq d$ ， $α_{i} ≢ 0 (\mod p)$ ， $ρ_{i, j}$ 以及 $β_{i}$ 均为已知的整数，未知正整数 $k_{i, j}$ 的上界为 $2^{μ_{i, j}}$ 且 $μ_{i, j}$ 已知，则扩展隐藏数问题（EHNP）则是通过上述条件恢复 $x$ . 为解决EHNP，我们可以构造格： $B B = (\begin{matrix} p I I_{d} \\ A A & X X \\ R R & K K \end{matrix})$ 其中： $\begin{aligned} A A = (\begin{array}{c} α_{1} 2^{π_{1}} & α_{2} 2^{π_{1}} & \dots & α_{d} 2^{π_{1}} \\ α_{1} 2^{π_{2}} & α_{2} 2^{π_{2}} & \dots & α_{d} 2^{π_{2}} \\ ⋮ & ⋮ & ⋱ & ⋮ \\ α_{1} 2^{π_{m}} & α_{2} 2^{π_{m}} & \dots & α_{d} 2^{π_{m}} \end{array}) \\ X X = d i a g (\frac{δ}{2^{ν_{1}}}, \frac{δ}{2^{ν_{2}}}, \dots, \frac{δ}{2^{ν_{m}}}) \\ R R = (\begin{array}{c} ρ_{1, 1} \\ ρ_{1, 2} \\ ⋮ \\ ρ_{1, l_{1}} \\ ⋱ \\ ρ_{d, 1} \\ ρ_{d, 2} \\ ⋮ \\ ρ_{d, l_{d}} \end{array}) \\ K K = d i a g (\frac{δ}{2^{μ_{1, 1}}}, \dots, \frac{δ}{2^{μ_{1, l_{1}}}}, \dots, \frac{δ}{2^{μ_{d, 1}}}, \dots, \frac{δ}{2^{μ_{d, l_{d}}}}) \end{aligned}$ 设 $L = l_{1} + l_{2} + \dots + l_{d}$ ， $D = d + m + L$ ，计算： $κ_{D} = \frac{2^{D / 4} (m + L)^{1 / 2} + 1}{2}$ 通过 $κ_{D}$ ，我们可以得到 $δ$ 满足 $0 < δ κ_{D} < 1$ 。令 $v v = (β_{1} - α_{i} \overset{―}{x}, \dots, β_{d} - α_{d} \overset{―}{x}, \frac{δ}{2}, \dots, \frac{δ}{2})$ 我们需要根据上述的 $δ$ 构造格 $L = L (B B, δ)$ ，在格 $L$ 中找到向量 $u u$ 使得： $| | u u - v v | | \leq 2^{\frac{D}{4}} min_{t t \in L} | | v v - t t | |$ 通过LLL算法对我们构造的格进行规约可以得到： $u u = (β_{1} - α_{i} \overset{―}{x}, \dots, β_{d} - α_{d} \overset{―}{x}, \frac{x_{1} δ}{2^{ν_{1}}}, \dots, \frac{x_{m} δ}{2^{ν_{m}}}, \frac{k_{1, 1} δ}{2^{μ_{1, 1}}}, \dots, \frac{k_{1, l_{1}} δ}{2^{μ_{1, l_{1}}}}, \dots, \frac{k_{d, 1} δ}{2^{μ_{d, 1}}}, \dots, \frac{k_{d, l_{d}} δ}{2^{μ_{d, l_{d}}}})$ 然后令 $x_{j}^{'} = \frac{1}{δ} (u u_{d + j} 2^{ν_{j}})$ （ $1 \leq j \leq m$ ），最后计算： $x^{'} = \overset{―}{x} + \sum_{j = 1}^{m} 2^{π_{j}} x_{j}^{'} \mod p$ 这样得到的 $x^{'}$ 就是我们需要的 $x$ . 在论文Extended Hidden Number Problem and Its Cryptanalytic Applications中还提及了一种通过狄利克雷近似计算双洞隐藏数问题（Hidden Number Problem with Two Holes， HNP-2H），具体方法与步骤在通过狄利克雷近似解决HNP-2H | Triode Field有写.

Coppersmith方法

Howgrave-Graham定理

设 $h (x_{1}, \dots, x_{n}) \in Z [x_{1}, \dots, x_{n}]$ 是一个由 $ω$ 个单项式组成的多项式，如果：

存在 $| r_{1} | < X_{1}, \dots, | r_{n} | < X_{n}$ ，有 $f (r_{1}, \dots, r_{n}) \equiv 0 (\mod N)$
$| | h (x_{1} X_{1}, \dots, x_{n} X_{n}) | | < \frac{N}{\sqrt{ω}}$

那么 $f (r_{1}, \dots, r_{n}) = 0$ 在整数域同样成立.

这个定理是Coppersmith方法的关键所在。

一元Coppersmith

对于度为 $k$ 的一元本原多项式 $p (x) = x^{k} + a_{k - 1} x^{k - 1} + \dots + a_{1} x + a_{0} \in Z [x]$ ，Coppersmith方法可以找到方程 $p (x) \equiv 0 (\mod N)$ （其中 $N$ 是一个合数）的一个小根 $x \equiv x_{0} (\mod N)$ （ $| x_{0} | < X$ ，其中 $X$ 是一个自然数，且 $X \leq N^{1 / k}$ ）这个算法的主要思想就是构造一个多项式 $h (x)$ 使得 $h (x_{0}) = 0$ ，而求解 $h (x) = 0$ 这个方程是很简单的，所以我们可以将求解 $p (x) \equiv 0 (\mod N)$ 这一任务转化为求解 $h (x) = 0$ 。我们可以构造格： $B B = (\begin{matrix} N \\ X N \\ X^{2} N \\ ⋱ \\ X^{k - 1} N \\ a_{0} & a_{1} X & a_{2} X^{2} & \dots & a_{d - 1} X^{d - 1} & X^{d} \end{matrix})$ 然后通过LLL规约得到一个矩阵： $B B^{'} = (\begin{matrix} b_{0} & b_{1} & \dots & b_{d - 1} & b_{d} \\ * & * & \dots & * & * \\ ⋮ & ⋮ & ⋮ & ⋮ \\ * & * & \dots & * & * \end{matrix})$ 则有： $h (X x) = b_{d} x^{d} + b_{d - 1} x^{d - 1} + \dots + b_{1} x + b_{0}$ 可以得到： $h (x) = (\frac{b_{d}}{X^{d}}) x^{d} + (\frac{b_{d - 1}}{X^{d - 1}}) x^{d - 1} + \dots + (\frac{b_{1}}{X}) x + b_{0}$ 解该方程得到的整数解就有可能是我们要的 $x_{0}$ 。在实际应用中，我们可以直接利用sage的small_roots来进行求解。

多元Coppersmith

那堆东西暂时没看懂，先贴个从某些地方搜刮来的板子

python

def small_roots(f, bounds, m=1, d=None):
	import itertools
    if not d:
        d = f.degree()
    R = f.base_ring()
    N = R.cardinality()
    f /= f.coefficients().pop(0)
    f = f.change_ring(ZZ)
    G = Sequence([], f.parent())
    for i in range(m + 1):
        base = N ^ (m - i) * f ^ i
        for shifts in itertools.product(range(d), repeat=f.nvariables()):
            g = base * prod(map(power, f.variables(), shifts))
            G.append(g)
    B, monomials = G.coefficients_monomials()
    monomials = vector(monomials)
    factors = [monomial(*bounds) for monomial in monomials]
    for i, factor in enumerate(factors):
        B.rescale_col(i, factor)
    B = B.dense_matrix().LLL()
    B = B.change_ring(QQ)
    for i, factor in enumerate(factors):
        B.rescale_col(i, 1 / factor)
    H = Sequence([], f.parent().change_ring(QQ))
    for h in filter(None, B * monomials):
        H.append(h)
        I = H.ideal()
        if I.dimension() == -1:
            H.pop()
        elif I.dimension() == 0:
            roots = []
            for root in I.variety(ring=ZZ):
                root = tuple(R(root[var]) for var in f.variables())
                roots.append(root)
            return roots
    return []

一般维纳攻击的格方法

维纳方法：对于 $N = p q$ ，假设 $λ (N)$ 与 $e$ 均与 $N$ 接近，而且解密指数 $d < N^{1 / 4}$ ，那么因为 $e$ 与 $d$ 满足 $e d - k λ (N) = 1$ ，所以令 $λ (N) = (p - 1) (q - 1) / g$ ，又令 $s = 1 - p - q$ ，就可以得到： $e d g - k N = g + k s$ 那么有： $\frac{e}{N} - \frac{k}{d g} = \frac{k s}{d g N} + \frac{1}{d N}$ 由于 $e \approx N$ ， $| s | \approx N^{1 / 2}$ ，那么可以得到 $\frac{k}{d g} \approx 1$ ，所以上述方程的值约等于 $N^{- 1 / 2}$ ，由勒让德定理，如果 $N^{- 1 / 2} < 1 / [2 (d g)^{2}]$ ，那么 $\frac{k}{d g}$ 会是 $e / N$ 的渐进分数，所以我们可以通过连分数来得到 $d$ ，或者分解出 $p, q$ ，上述讨论中一般情况下 $g = 1$ 。令 $g = 1$ ，实际上此时 $λ (N) = φ (N)$ ，我们注意到，在上述条件下得到的 $e d - k N = 1 + k s$ 一式存在线性关系，所以可以考虑使用格来求解，考虑构造如下格： $B B = (\begin{matrix} 1 & e \\ 0 & - N \end{matrix})$ 其中目标向量为 $v v = (d, 1 + k s)$ ，其中 $s = 1 - p - q$ ，可以知道 $| s | \approx N^{1 / 2}$ ， $d < N^{1 / 4}$ ，则有 $| det (B B) | = N$ ，可以知道 $| | v v | | = \sqrt{d^{2} + (1 + k s)^{2}} > \sqrt{2} N^{1 / 2} > \sqrt{2} | det (B B) |^{1 / 2}$ 显然，通过闵可夫斯基第一定理，我们几乎不可能通过规约得到我们的目标向量，那么我们要进行格基配平，根据分析，我们构造如下格： $B B^{'} = (\begin{matrix} 2^{α} & e \\ 0 & - N \end{matrix})$ （其中 $α$ 是 $N$ 的比特数的 $1 / 2$ ），这样就可以通过LLL算法规约得到目标向量 $(2^{α} d, 1 + k s)$ .

格（Lattice）

格的概念

关于格的问题

格基规约

LLL算法

解决CVP

Babai最近平面算法（Babai’s Nearest Plane Algorithm）

Kannan嵌入法

格在密码学中的应用

背包问题（Knapsack Problem）

低密度子集和问题

低密度多重子集和问题

低密度模子集和问题与低密度多重模子集和问题

隐藏数问题（Hidden Number Problem，HNP）

扩展隐藏数问题（Extended Hidden Number Problem，EHNP）

Coppersmith方法

Howgrave-Graham定理

一元Coppersmith

多元Coppersmith

一般维纳攻击的格方法

微信扫一扫：分享