The Rsa in Lattice. This article draws lessons from many masters' blogs

# 一.维纳攻击 Plus++

# Abstract:

我们已知的维纳攻击是需要私钥 $d<N^\frac1}{4} $ 以及 e 和 N 差不多大,于是 d 就可以在 e/N 的连分数中找 d 和 phi。这里扩展了这个攻击使得当给定 多个 $e_i$ 对于 $N_i$ 的时候 d 只需要更小就能解。对于这种情况的两个 $e_i$ ,$d_i<N({5/14)$ 仍可解密。同时随着解密指数的增多 能够使得他更有效的解密,可以增加到 N1ϵN^{1-\epsilon} 但是越来越慢。然而,这种方法的复杂性指数是指存在的指数的数量

# Wiener‘s Approach :

已知 edkλ(N)=1ed-k\lambda(N)=1λ(N)=(p1)(q1)/g\lambda(N)=(p-1)(q-1)/g 其中 g=gcd(p1,q1)g=gcd(p-1,q-1) ,设 s=1pqs=1-p-q .

于是可以推出 $$edg-kN=g+ks$$​​ => eNkdg=g+ksdgN=(kdg)(sN)+1dN\frac{e}{N}-\frac{k}{dg}=\frac{g+ks}{dgN}=(\frac{k}{dg})(\frac{s}{N})+\frac{1}{dN}​​ , 已知 e 和 N 差不多大,s 和 N0.5N^{0.5}​ 差不多大,即 k/dg 和 1 差不多大

# Guo’s Approach :

针对 2 或 3 个方程式,其中 eie_i 较大, did_i 相近且较小

e1d1gk1(p1)(q1)=g(1)e_1d_1g-k_1(p-1)(q-1)=g\ \ (1)

e2d2gk2(p1)(q1)=g(2)e_2d_2g-k_2(p-1)(q-1)=g\ \ (2)

于是 (1)×k2(2)×k1=k2d1e1k1d2e2=k2k1modn(1)×k_2-(2)×k_1=k_2d_1e_1-k_1d_2e_2=k_2-k_1\mod n ,两边同除 k2d1e2k_2d_1e_2 得到 e1e2k1d2k2d1={e_1\over e_2} - {k_1d_2\over k_2d_1} =

假设 eie_i 极大 ,和 N 很接近,那么我们就可以得知 did_i , kik_i 小而且接近,上限设为 NαN^α 那么右侧的大小接近于 N(1+α)N^{-(1+\alpha)} .

在根据 Poincare 定理可知:当 $$2 (k_2 d_1)^2}<N({1+α)$ $$

即可以由 e1e2\frac{e_1}{e_2}​​ 的连分数可以求得 k1d2k2d1\frac{k_1d_2}{k_2d_1}​​​​ (即 $$α=\frac {1}{3}-\epsilon,(\epsilon>0)$$​​ )

注意:

  • 只知道 kjdjk_jd_j 并不能求得 kjk_jdjd_j
  • gcd(k_id_j,k_jd_i)>1$$​

# Extension Approach

理论上仍欠缺

得到解的指数范围为

αn={(2n+1)2n(2n+1)(n/2n)(2n2)2n+(4n+2)(n/2n)ifniseven(2n+1)2n4n((n1)/2n1)(2n2)2n+8n((n1)/2n1)ifnisodd.\alpha_n=\begin{cases} \frac{(2n+1)2^n-(2n+1)(^n_{n/2})}{(2n-2)2^n+(4n+2)(^n_{n/2})}\ \ \ \ if \ n\ is\ even\\\\ \frac{(2n+1)2^n-4n(^{n-1}_{(n-1)/2})}{(2n-2)2^n+8n(^{n-1}_{(n-1)/2})}\ \ \ \ \ if\ n\ is\ odd. \end{cases}

可知当 n 慢慢变大的 时候 α 的变化为 14,514,25,...,1ϵ\frac{1}{4},\frac{5}{14},\frac{2}{5},...,1-\epsilon

LLL 格基规约的时候可知,时间复杂度最大为 O(26nn3log3N)O(2^{6n}n^3log^3N) 所以该方法仅对少部分有效

方法:

  • 设维纳攻击中的方程式为 WiW_idigeikiN=g+kisd_ige_i-k_iN=g+k_is

  • 设 Guo‘s Approach 的方程式为 Gi,jG_{i,j}kidjejkjdiei=kikjk_id_je_j-k_jd_ie_i=k_ik_j

  • 假设 di,kid_i,k_i 上限为 dαnd^{\alpha_n} ,g 很小, s 约为N^

  • 已知两个公钥为例:

    • 列出三条方程式,即 Wi,G1,2,W1W2W_i,G_{1,2},W_1W_2:

      • $d_1ge_1-k_1N=g+k_1s $ (1)
      • $ k_1d_2e_2-k_2d_1e_1=k_1-k_2$ (2)
      • d1d2g2e1e2d1gk2ed_1d_2g^2e_1e_2-d_1gk_2e (3)
    • (1)=(1)×k2,(2)=(2)×g(1)=(1)×k_2,(2)=(2)×g 之后构造以下 Vector 和 Lattice

      (k1k2,d1gk2,d2gk1,d1d2g2)[1N0N2e1e1e1Ne2e2Ne1e2]=(k1k2,k2(g+k1s),g(k1k2),(g+k1s)(g+k2s))(k_1k_2,d_1gk_2,d_2gk_1,d_1d_2g^2)\left[\begin{matrix}1&-N&0&N^2\\\\&e_1&-e_1&-e_1N\\\\&&e_2&-e_2N\\\\&&&e_1e_2\end{matrix}\right]=(k_1k_2,k_2(g+k_1s),g(k_1-k_2),(g+k_1s)(g+k_2s))

  • 根据 闵可夫斯基 定理,我们可以得知,要使得 TV 是该格的一个 SVP 那么需要去满足TVndet(L)1n||TV'||≤\sqrt{n}\det(L)^{\frac{1}{n}}

    已知

    {eiNdiNαkidiNαg1s=1pqN0.5\begin{cases}e_i≈N\\\\d_i≈N^α\\\\k_i≈d_i≈N^α\\\\g≈1\\\\s=1-p-q≈N^{0.5}\end{cases}

    • 但是右边算出来为 2N2N 而结果定然满足 TV>2N||TV'||>2N 因此不可以这么做,所以我们去重新构造一个格子,设M1=N12,M2=N1+αM_1=N^{\frac{1}{2}},M_2=N^{1+\alpha} ,将 M1 和 M2 分别乘到第二列和第三列 ,N 乘到第一列,得到新格子

      L2=[NM1NN2M1e1M2e1e1NM2e2e2Ne1e2]L_2=\left[\begin{matrix}N&-M_1N&&N^2\\\\&M_1e_1&-M_2e_1&-e_1N\\\\&&M_2e_2&-e_2N\\\\&&&e_1e_2\end{matrix}\right]

      格基规约之后得到的新向量 TV=(k1k2N,k2(g+k1s)M1,g(k1k2)M2,(g+ks)(g+k2s))TV'=(k_1k_2N,k_2(g+k_1s)M_1,g(k_1-k_2)M_2,(g+k_s)(g+k_2s))​​​ 同时也满足 $$||TV'||≤2N^1+2α}$$​​​ 同时带入({\frac{1) $$||TV'||≤\sqrt{n}\det(L)n}}=2N({\frac{13)+\frac {\alpha}{4}};$$​​​​ 得到 $$α≤\frac {5}{14}$$

再提一下三个公钥的矩阵构造:

L3=[1NN2N3e1e1e1Ne1e1Ne1N2e2e2Ne2Ne2N2e1e2e1e2e1e2e1e2Ne3e3Ne3Ne3N2e1e3e1e3Ne2e3e2e3Ne1e2e3]×DL_3=\left[\begin{matrix}1&-N&&N^2&&&&-N^3\\\\ &e_1&-e_1&-e_1N&-e_1&&e_1N&e_1N^2\\\\ &&e_2&-e_2N&&e_2N&&e_2N^2\\\\ &&&e_1e_2&&-e_1e_2&-e_1e_2&-e_1e_2N\\\\ &&&&e_3&-e_3N&-e_3N&e_3N^2\\\\ &&&&&e_1e_3&&-e_1e_3N\\\\ &&&&&&e_2e_3&-e_2e_3N\\\\ &&&&&&&e_1e_2e_3\end{matrix} \right]\times D

格基规划得到:

TV=(k1k2k3,d1gkVk3,k1d2gk3,d1d2g2k3,k1k2d3g,k1d3g,k2d3g,d1d2d3g3)TV'=(k_1k_2k_3,d_1gk_Vk_3,k_1d_2gk_3,d_1d_2g^2k_3,k_1k_2d_3g,k_1d_3g,k_2d_3g,d_1d_2d_3g^3)

请我喝[茶]~( ̄▽ ̄)~*

De3B4to 微信支付

微信支付

De3B4to 支付宝

支付宝