基于格的通用私钥攻击（RSA用了同一个d）

假设现在有r组n,e，他们的私钥均为d，则有：

e₁*d = k₁*phi(N₁) + 1

e₂*d = k₂*phi(N₂) + 1

​ . . .

*e_rd = k_r*phi(N₃) + 1

此处默认（N₁ < N₂ < … < N_r < 2N_r ）

令 M = [N_r^1/2 ]

phi(N_r )= N_i - s_i 且k_i < d (i = 1,2,…,r)

则有：e_i*d - N_i*k_i = 1 - k_i*s_i

可以列出下列等式：

​ dM = dM

e₁*d - N₁*k₁ = 1 - k₁*s₁

e₂*d - N₂*k₂ = 1 - k₂*s₂

​ . . .

e_r*d - N_r*k_r = 1 - k_r*s_r

可以构造
$$
x_r*B_r = v_r\
x_r = (d,k_1,k_2,…,k_r)
$$

$$
B_r =
\begin{bmatrix}
{M}&{e_1}&{\cdots}&{e_r}\
{0}&{-N_1}&{\cdots}&{0}\
{\vdots}&{\vdots}&{\ddots}&{\vdots}\
{0}&{0}&{\cdots}&{-N_r}\
\end{bmatrix}\
vr = (dM,1-k_1s_1,…,1-k_rs_r)
$$
而后对B_r 使用LLL算法得到向量b,最后
$$
d = \frac{|b|}{M}
$$