各种格上问题积累与理解

1. $Ax \equiv y \pmod{P} (对应 \ Wiener’s \ Attack)$

$A, P$ 已知，$x, y$ 相对为小量

可以将其转化为

$Ax+kP = y$

$wiener$ 里则为

$ed+k\phi(n)=1$

构造

$(x,k)*\begin{bmatrix} 1 & A\\ 0&P\end{bmatrix} = (x,y)$

满足 $||w|| = (x^2+y^2)^{\frac{1}{2}} \le \sqrt{2}det(M)^{\frac{1}{2}}$

则很大可能 $w$ 为最短向量

（若 x,y 大小不相当，就可以适当配平使其界更紧）

2. $A_ix_i\equiv Y \pmod{P}$

已知 $A_i, P$ ; $Y$ 为未知大数

问题转换1:

$A_ix_i\equiv Y \pmod{P}$ 变为 $x_iY^{-1} \equiv A_{i}^{-1} \pmod{P}$

即 $x_iY\equiv A_i \pmod{P}$ 的问题

问题转换2:

$A^{‘} = x_{2} * x_{1}^{-1} \equiv A_{2} Y^{-1} Y A_{1}^{-1}\equiv A_{2} A_{1}^{-1} \pmod{P} $

$x^{‘} = x_1 \pmod{P} $
$ y^{‘} = x_2 \pmod{P}$

即 $A^{‘}x^{‘} \equiv y^{‘} \pmod{P}$

3. $\Sigma^{n}_{i=1} A_ix_i \equiv y \pmod{P}$

已知 $A_i,P$

构造

$(x_1, x_2, \cdots,x_n,k)*\begin{bmatrix}1&0&\cdots&0&A_1 \\ 0&1&\cdots&0&A_2 \\ \vdots&\vdots&\ddots&\vdots&\vdots\\ 0&0&\cdots&1&A_n \\ 0&0&\cdots&0&P\end{bmatrix} = (x_1,x_2,\cdots,x_n,y)$ $x_{max} \le P^{\frac{1}{n+1}}$

4. $\Sigma^{n}_{i=1} A_ix_i \equiv B \pmod{P}$

已知 $A_i, P, B$

背包格

构造

$(x_1, x_2, \cdots,x_n,k, -1)*\begin{bmatrix}1&0&\cdots&0&0&A_1 \\ 0&1&\cdots&0&0&A_2 \\ \vdots&\vdots&\ddots&\vdots&\vdots&\vdots\\ 0&0&\cdots&1&0&A_n \\ 0&0&\cdots&0&1&P\\1&1&\cdots&1&1&B \end{bmatrix} = (x_1-1,x_2-1,\cdots,x_n-1,k-1,0)$ $x_{max} \le P^{\frac{1}{n+2}}$

5. $A_ix_i\equiv y_i \pmod{(P+s)}$ (对应扩展 wiener)

已知 $A_i, P$

先给定两组数据

$A_1x_1\equiv y_1 \pmod{(P+s)}$ $A_2x_2\equiv y_2 \pmod{(P+s)}$

拆开得

$A_1x_1+k_1P=y_1-k_1s \ \ \ ①$ $A_2x_2+k_2P=y_2-k_2s\ \ \ ②$

①*② 得

$(A_1x_1+k_1P)(A_2x_2+k_2P)=A_1A_2x_1x_2+A_1Px_1k_2+A_2Px_2k_1+P^2k_1k_2$

四个等式：

$k_1k_2 = k_1k_2$ $(A_1x_1+k_1P)k_2=(y_1-k_1s)k_2$ $A_1x_1k_2 - A_2x_2k_1 = y_1k_2-y_2k_1$ $(A_1x_1+k_1P)(A_2x_2+k_2P)=A_1A_2x_1x_2+A_1Px_1k_2+A_2Px_2k_1+P^2k_1k_2$

构造

$(k_1k_2,x_1k_2,x_2k_1,x_1x_2)\begin{bmatrix}1&P&0&P^2\\ 0&A_1&A_1&A_1P\\ 0&0&-A_2&A_2P\\ 0&0&0&A_1A_2\end{bmatrix} = (k_1k_2,(y_1-k_1s)k_2,y_1k_2-y_2k_1,(y_1-k_1s)(y_2-k_2s))$

配平

$x_i \le O(P^{\alpha}) \\ y_i \le O(P^{\beta}) \\ s \le O(P^{\gamma})$

在 $w$ 上的大小分别为$(P^{2\alpha},P^{2\alpha+\gamma},P^{\alpha+\beta},P^{2\alpha+2\gamma})$

所以构造对角矩阵 $D$

$D = \begin{bmatrix}P^{2\gamma}&0&0&0\\ 0&P^{\gamma}&0&0\\ 0&0&P^{\alpha-\beta+2\gamma}&0\\ 0&0&0&1\end{bmatrix}$

要满足 $7\alpha+\beta+3\gamma\le4$ ，前提 $\alpha+\gamma\ge \beta$

“Minkowski sum based lattice construction for multivariate simultaneous Coppersmith’s technique and applications to RSA” (Section 4)

这篇论文是打湾区杯的时候搜到的，具体算法的步骤为

算法步骤

可以将界进一步提升

6. $a_iX\equiv y_i \pmod{(P_i +s_i)}$

已知 $a_i,P_i$

$a_i \le O(P^{\alpha}) $
$ y_i \le O(P^{\beta}) $
$ s_i \le O(P^{\gamma})$

展开得到等式

$a_iX+k_iP_i=y_i-k_is_i$

注意到等式右边最大为 $\max(P^{\beta},P^{\alpha+\gamma})$

所以可认为是小量

构造

$(X, k_1,k_2,\cdots,k_n)*\begin{bmatrix}1&a_1&a_2&\cdots&a_n\\ 0&P_1&0&\cdots&0\\ 0&0&P_2&\cdots&0\\ \vdots&\vdots&\vdots&\ddots&\vdots\\ 0&0&0&\cdots&P_n\end{bmatrix} = (X,y_1-k_1s_1,y_2-k_2s_2,\cdots,y_n-k_ns_n)$

配平

以 $\beta \le \alpha+\gamma \le 1$ 为例

$D = \begin{bmatrix}1&0&\cdots&0 \\ 0 &P^{1-(\alpha+\gamma)}&\cdots&0 \\ \vdots&\vdots&\ddots&\vdots\\ 0&0&\cdots &P^{1-(\alpha+\gamma)}\end{bmatrix}$

满足

若 $\beta \le \alpha+\gamma \le 1$ ：$\alpha+\gamma\le1-\frac{1}{n}$
若 $ \alpha+\gamma \le \beta \le 1$ : $\beta \le1-\frac{1}{n}$

感觉这种情况很难构造一种测例

看一看另一种情况

X 是小量的情况

$X \le O(P^{\alpha}) $
$ y_i \le O(P^{\beta}) $
$ s_i \le O(P^{\gamma})$

这时候构造仍相同，只不过配平变了

$\beta \le \alpha+\gamma \le 1$ 的情况

$D = \begin{bmatrix}P^{\gamma}&0&\cdots&0 \\ 0 &1&\cdots&0 \\ \vdots&\vdots&\ddots&\vdots\\ 0&0&\cdots &1\end{bmatrix}$

满足 $\cfrac{n}{n+1}+\cfrac{\gamma}{n+1} \ge \alpha+\gamma$

有 $\alpha < \cfrac{n}{n+1}*(1-\gamma)$

另一种情况：

$\beta<\cfrac{n}{n+1}+\cfrac{\beta-\alpha}{n+1}$

The First Attack on k RSA Moduli (2014)

已知 $k \ge 2$ 个 moduli $N_i = p_iq_i$

等式：

$e_ix-y_i\phi{(N_i)} = z_i$

define $\delta = \cfrac{k}{2(k+1)}$

这个方法的界感觉差不多，但是玩不明白，只有特定的生成的公钥组才能打的出来

例子如下

论文例子

7. ACD 问题 $A_i = xy_i+z_i$

已知 $A_i$

$x \le O(2^{\alpha}) $
$ y_i \le O(2^{\beta}) $
$ z_i \le O(2^{\rho})$

一. 构造格

通过 $A_iy_0-A_0y_i$ 将规模从 $2^{\alpha+\beta}$ 降为 $2^{\beta+\rho}$

$(y_0, y_1,\cdots,y_n) * \begin{bmatrix}R&A_1&A_2&\cdots&A_n\\0&-A_0&0&\cdots&0\\0&0&-A_0&\cdots&0\\\vdots&\vdots&\vdots&\ddots&\vdots\\0&0&0&\cdots&-A_0\end{bmatrix} = (y_0R,y_0z_1-y_1z_0,\cdots,y_0z_n-y_nz_0)$

范围

满足

$\beta+\rho \le \cfrac{n(\alpha+\beta)+\rho}{n+1} $

得到

$\beta \le n(\alpha-\rho)$

二. 正交格

寻找一组向量 $a = (a_1,\cdots, a_n)$

构造等式

$(a_1,a_2,\cdots,a_n)*\begin{bmatrix}A_1&R&0&\cdots&0\\A_2&0&R&\cdots&0\\A_3&0&0&\cdots&0\\\vdots&\vdots&\vdots&\ddots&\vdots\\A_n&0&0&\cdots&R\end{bmatrix} = (\Sigma^{n}_{i=1}{a_iA_i},a_1R,\cdots,a_nR)$

其中

$\Sigma^{n}_{i=1}{a_iA_i} = x\Sigma^{n}_{i=1}{a_iy_i} +\Sigma^{n}_{i=1}{a_iz_i}$

因此，若找到的 $a$ 与 $y$ 正交，则 $w = (\Sigma^{n}_{i=1}{a_iz_i},a_1R,\cdots,a_nR)$ 极有可能是格上的最短向量

规约出来得到矩阵 $L$

可知 $L*y = 0$

于是通过求 $L$ 的右核选出合适的 $y$

经测试，以上两种方法的界差不多

三. coppersmith 求小根

前提已知 $N = x*y_0$

设 $z_i$ 为未知变量

可知 $A_i - z_i$ 均为 $x$ 的倍数

则有等式

$N \equiv 0 \pmod{x}$
$A_i-z_i \equiv 0 \pmod{x}$

利用 coppersmith 的扩大模数的方法（原理并没有太懂），把 $N$ 当作模数即可求小根

四. 使用 cuso 优化 coppersmith 进行求解

具体这里就不再阐述了

8. LWE

SLWE（求出私钥 $s$ )

1. 无模数的构造

$A*x+e = b$

已知 $A$

$e$ 很短

构造

$L = \begin{bmatrix}A&b\\0&\beta\end{bmatrix}$ $L = \begin{bmatrix}A&b\\0&\beta\end{bmatrix}*\begin{bmatrix}-x \\ 1\end{bmatrix} = \begin{bmatrix}e \\ \beta\end{bmatrix}$

可知最后的向量相当小

2. primal attack

$A_{m\times n}s_{n\times 1}+e_{m\times1} = b_{m\times1} \pmod{p}$

基础格

$(s_1, s_2,\cdots,s_n,1,k_1,k_2,\cdots,k_m)\begin{bmatrix}1&&&&a_{1,1}&a_{2,1}&\cdots&a_{m,1}\\&1&&&\vdots&\vdots&\ddots&\vdots\\&&\cdots&&a_{1,n}&a_{2,n}&\cdots&a_{m,n}\\&&&1&-b_1&-b_2&\cdots&-b_m\\&&&&p&&&\\&&&&&p&&\\&&&&&&\ddots&\\&&&&&&&p\end{bmatrix} = (s_1,s_2,\cdots,s_n,1,e_1,e_2,\cdots,e_m)$

共 $m+n+1$ 维

优化格

$As+e = b$
$s^TA^T+e^T=b^T $
$ K = [I_{n\times n},A^{‘}_{n\times(m-n)}] = PA^T_{m\times n} $
$ (s^TP^{-1})*(PA^T) +e^T=b^T $
$ s^{‘} = s^TP^{-1}$
$s^{‘}K+e^T = b^T$
$ \therefore s^{‘}K-b^T = e^T \pmod{p}$

因为 $K$ 的前 $n$ 维为单位阵，所以可以将格中的模数 $p$ 进行省略，因此可以达到降维的优化效果

$(s^{'}_1,s^{'}_2,\cdots,s^{'}_n,k_{m-n+1},k_{m-n+2},\cdots,k_m,1)*\begin{bmatrix}1&&&a^{'}_{1,1}&a^{'}_{1,2}&\cdots&a^{'}_{1,m-n}& \\ & \ddots&&\vdots&\vdots&\ddots&\vdots& \\ &&1&a^{'}_{n,1}&a^{'}_{n,2}&\cdots &a^{'}_{n,m-n}&\\&&& p&&&&\\&&&&p&&&\\&&&&&\ddots&&\\&&&&&&p&\\-b_1&-b_2&-b_3&\cdots&\cdots&\cdots&-b_m&1 \end{bmatrix} = (e_1,e_2,\cdots,e_m,1)$

DLWE（判断是不是 LWE 生成的参数）

基础版

原理

$As+e = b$

若能找到 $A$ 的左核里的一个短向量 $u$

即 $uA = 0$

则有 $uAs+ue = ub = ue \pmod{p}$

因为 $u,e$ 都是短的，其内积应是一个小的数字

而随机选取的就会大一些，从而进行区分

优化版

依旧降维

$P*kernel_{(m-n)\times m} = [I_{(m-n)\times(m-n)},kernel^{'}_{(m-n)\times n}]$

于是可以省下 $m-n$ 维

9. NTRU

加密过程

密钥生成

$f(x) \in \tau(d, d+1)\\ g(x) \in \tau(d,d)$

$R = \cfrac{\mathbb{Z}[x]}{x^N-1}\\R_p = \cfrac{(\mathbb{Z}/p\mathbb{Z})[x]}{x^N-1}\\R_q = \cfrac{(\mathbb{Z}/q\mathbb{Z})[x]}{x^N-1}$

$R,R_p,R_q$ 为三个卷积多项式环

多项式乘法相当于对系数进行了卷积操作

私钥为 $f、g$

公钥

$h(x) = f(x)^{-1}*g(x) \ \ in \ R_q$

center-lift

将 $R_p,R_q$ 上多项式转到 $R$ 上

即将 $(0,p)$ 范围内的系数转为 $(-\frac{p}{2},\frac{p}{2})$

加密

$e(x) = p \cdot h(x)r(x)+m(x) \pmod{q}$

解密过程

$a(x)\equiv f(x)*e(x) \pmod{q}$

$b(x)\equiv F_{p}(x)*a(x)\pmod{p}$

$b(x)$ 即为 $m(x)$

若要满足解密关系成立，需要满足以下条件（证明略）：

$(3d+\frac{1}{2})\cdot p < \frac{q}{2}$

即

$(6d+1)\cdot p <q$

攻击方法

小密钥空间

$N,d$ 过小直接枚举

格规约

$h(x)\equiv f(x)^{-1}\cdot g(x) \ in \ R_q$

可转化为 $f(x)\cdot h(x) = g(x) + u(x)\cdot p$

因为 $f(x),g(x)$ 均为小量，于是有等式

$(f(x),-u(x))\cdot \begin{bmatrix}1&h(x)\\0&q\end{bmatrix} = (f(x), g(x))$

将多项式乘法转换为矩阵乘法

$F,G,U$ 为三个多项式的系数向量

$H$ 为多项式乘法转换为卷积的矩阵

$f(x)\cdot1 \Rightarrow F_{1\times n}\cdot I_{n\times n}$

$f(x)\cdot h(x)-q\cdot u(x) \Rightarrow F_{1\times n}\cdot H_{n\times n} - q\cdot U_{1\times n}\cdot I_{n\times n} = G_{1\times n}$

因此格变为

$M = \left[ \begin{array}{c c c c | c c c c}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&0&q&\cdots&0 \\ \vdots&\vdots&\ddots&\vdots&\vdots&\vdots&\ddots&\vdots \\ 0&0&\cdots&0&0&0&\cdots&q\end{array} \right]$

让我们来看一下有解的界吧

$det(M) = q^N$

$\vert\vert(f,g)\vert\vert \approx \sqrt{4d}$

我觉得粗略的界是 $4d<q$ (有待确认)，而且 N 很大的时候，就算满足界也解不出来

维度比较大的时候要用 BKZ

但是我在 N = 160 时，用 flatter 也干出来了

10. HNP（隐藏数问题）

问题为给出 n 组方程，每组给出

$\beta_i \equiv \alpha_i * x_0 \pmod p$

$p$ 是 $m$ 位大小的数

其中给定 $p,\alpha_i$ 的全部和 $\beta_i$ 的一定位数

解出 $x_0$

假设 $\beta_i$ 已知 $s$ 位

则理论上的界: $s*(n+1)> m$

该问题可解

eg1(来自 tover 的 blog)

问题：

$n_{max} = 35,s = 8, m = 256,q = 2^{m}$ 泄漏 $\beta_i$ 的高 $s$ 位

设已知高位为 $B_i$ ,未知低位为 $b_i$

$A_ix_0 \equiv B_i + b_i \pmod q$

此时 $x_0,b_i$ 未知，且分别为 $m \ bit,(m-s) \ bit$

由于 $p$ 是 $m \ bit$ ，所以要想办法把 $x_0$ 转化为较小的未知数

任取一组数据有

$x_0 \equiv A_0^{-1}(B_0+b_0) \pmod q$

代入得

$A_{0}^{-1}(A_iB_0-A_0B_i)+A_{0}^{-1}A_ib_0 \equiv b_i \pmod q$

令 $D_i \equiv A_{0}^{-1}(A_iB_0-A_0B_i) \pmod q$, $E_i \equiv A_{0}^{-1}A_i \pmod q$, 展开得

$D_i+E_ib_0-k_iq = b_i$

此时几个未知数均为 $(m-s) \ bit$, 可以构造格进行求解

令常数 $R=2^{m-s}$ ，接下来构造格 $L(B)$

$B = \begin{bmatrix} -q & \\ &-q \\ & & \ddots \\ & & & -q \\ E_1 & E_2 & \cdots & E_{n-1} & 1 \\ D_1 & D_2 & \cdots & D_{n-1} & &R \end{bmatrix}_{(n+1)*(n+1)}$

有 $vB = (k_1,k_2,\cdots,k_{n-1},b_0,1)\cdot B=(b_1,b_2,\cdots,b_{n-1},b_0,R) = w$

可算

$||w|| \approx 2^{m-s}$ $\sigma(L(B)) \approx 2^{\frac{n*m-s}{n+1}}$

若 $||w|| \le \sigma(L(B))$ 的话有

$m-s \le \cfrac{n \cdot m - s}{n+1}$

化简得

$s \cdot n \ge m$

若满足此式则问题大概率可解

eg2 给低位

$n_{max} = 35,m =256,q$ 为 $256$ 位的素数，泄漏 $\beta_i$ 的低八位

$A_ix\equiv T*B_i+b_i \pmod{q}$

$x \equiv A_{0}^{-1}(T*B_0+b_0)$

$(TA_{0})^{-1}(A_ib_0-A_0b_i)+(A_0^{-1}A_i)B_0\equiv B_i\pmod{q}$

$D_i = (TA_{0})^{-1}(A_ib_0-A_0b_i)、E_i = (A_0^{-1}A_i)$

$D_i+E_i*B_0-k_iq=B_i$ $B = \begin{bmatrix} -q & \\ &-q \\ & & \ddots \\ & & & -q \\ E_1 & E_2 & \cdots & E_{n-1} & 1 \\ D_1 & D_2 & \cdots & D_{n-1} & &R \end{bmatrix}_{(n+1)*(n+1)}$

得到的结果与 eg1 的条件相似

总结

在很长一段摆烂的时间里终于更了一篇，还是太菜了，需要学习