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

# Ⅲ . 漫步铜匠的世界.

Coppersmith tnl ! 对于 CopperSmith 当中的多项式一直很不解是啥娃意....

# Abstract:

问题就是 在我们假设的最高次数为 n 次的 首一 多项式 F(x)=xn+an1xn1+...+a1x+a0F(x)=x^n+a_{n-1}x^{n-1}+...+a_1x+a_0​ 找到所有的 $$|x_0|<M^{\frac {1}{n}}$$​ 满足 F(x0)0modMF(x_0)\equiv0\mod M​ ;

首一 的原因:

  • 非首一多项式的化 但 gcd(ad,M)=1gcd(a_d,M)=1 可以 使用逆元来使得他首一
  • gcd(a_d,M)>1$$​ ,就可以把 $F(x)\mod M$​ 分解成两个同余式来解决

Coppersmith 就是 以 F(x)F(x) 为根源,利用多个 Gi(x)G_i(x) 构造一个系数足够小的 G(x)G(x) , 来得到 x0x_0 。比如我们可以考虑 n+1n+1Gi(x)=Mxifori[0,d)G_i(x)=Mx^i\ for\ i\in[0,d)F(x)F(x) , 那么我们可以构造格子,且 det(L)=MnXd(d+1)2det(L)=M^nX^{\frac{d(d+1)}{2}} :

B=[M......MX..................MXn1a0a1X...an1Xn1Xn]B=\left[\begin{matrix}M&&...&&...\\\\ &MX&...&...\\\\ ...&&...&...\\\\ &&...&MX^{n-1}&\\\\ a_0&a_1X&...&a_{n-1}X^{n-1}&X^{n}\end{matrix}\right]

所要 构造的多项式 G(x)G(x) 就应该可能是 格基规约后的 SVP 的各项系数

# Theorem:

  • # 0x01 Howgrave-Graham's Theorem:

    我们把 F(x)F(x) 用向量表示,那么 bF=(a0,a1X,a2X2...adXd)b_F=(a_0,a_1X,a_2X^2...a_dX^d) , 用 M 表示模数,设 X 是x0|x_0| 的上限 ,其中 F(x0)0modMF(x_0)\equiv 0\mod M

    若 $$||b_F||<\frac {M}{\sqrt {d+1}}$$​ ,那么 F(x0)=0F(x_0)=0

    Proof :

    ​ 由柯西不等式,$$(\Sigman_{i=1}x_iy_i)^2≤(\Sigma^n_{i=1}x_i2)(\Sigma^n_i=1}y_i(2)$$​​​​​ ,于是我们假设 $$x_i≥0,y_i=1$$​​​​​,则可以得知 $$\Sigma^n_{i=1)x_i≤\sqrtn\Sigma(n_{i=1)x_i^2}$$​​​​ , 那么

    F(x0)=Σi=0naix0iΣi=0naix0iΣi=0naiXid+1bFd+1Md+1=M|F(x_0)|=|\Sigma^n_{i=0}a_ix_0^i|\newline ≤\Sigma^n_{i=0}|a_i||x_0|^i\newline ≤\Sigma^n_{i=0}|a_i|X^i≤\sqrt{d+1}||b_F||\newline <\sqrt{d+1}\frac{M}{\sqrt{d+1}}=M

    又由于 F(x0)0modMF(x_0)\equiv 0\mod M ,故此 F(x0)=0F(x_0)=0

  • # 0x02 Theorem 2

    c1(d)=212(d+1)1dc_1(d)=2^{-\frac{1}{2}}(d+1)^{-\frac{1}{d}}​​​ ,如果 $$X<c_1 (d) M^{\frac {2}{d (d+1)}}$$​​​ ,那么所有满足 $$|x_0|≤X$$​​​ 的 x0x_0​​​ 都能够满足 G(x0)=0G(x_0)=0​​​ 在整数域上

    Proof:

    我们已知 $$||SVP_1||≤2^\frac{n-1}{4}}det(L)({\frac{1)n}}=2({\frac{d)4}}M({\frac{d)d+1}}X({\frac{d)2}}$$ ,({\f) Theorem 1 可知(ra) 只需要(c{d) $$24}}M({\frac{d)d+1}}X({\frac{d)2}} <\frac{M}{\sqrt{d+1}}$ , ({\frac{d) $\sqrt{d+1}\ 24}}X({\frac{d)2}}<M(\frac{1)$$​​ , 那么 Theorem 2 就成立。也即是 定理中的条件

  • # 0x03 Theorem 3(Coppersmith)

    对于上述定理, Coppersmith 对其扩展了他的范围。观察 Theorem 2 中的限制条件,容易得知要使得 式子 的 X 范围更大 我们有两种方法:

    • 增加矩阵中行数,以至于 ** 增加维度 n ** (这些行数 对于 det(L)\det(L) 的贡献需要小于 M)
    • 通过 “ x-shift ” 多项式使得 xF(x),x2F(x)...xkF(x)xF(x),x^2F(x)...x^kF(x) 增大右侧 的 M

    令 ϵ(0,min(0.18,1d))\epsilon \in (0,min(0.18,\frac{1}{d}))​ ;F(x)F(x)​ 是度为 d , 并且存在F(x0)=0modMF(x_0)=0\mod M​,$$|x_0|<\frac1}{2}M({\frac{1)-\epsilon}$$​的多项式,那么 x0x_0​ 可以在关于 d,1ϵ,log(M)d,\frac{1}{\epsilon},log(M)​ 的多项式时间复杂度 O((1ϵ)9log3M)O((\frac{1}{\epsilon})^9\log ^3M)​内被找到

    Proof :

    h>1h>1​ 是取决于 dd​ 和 ϵ\epsilon​ 的一个整数,决定式为 h=d1dϵ+1d1dϵh=\frac{\frac{d-1}{d\epsilon}+1}{d}≈\frac{1}{d\epsilon}​ ,考虑多项式 $$G_i,j}(x)=M({h-1-j)F(x)jxi,0≤i<d,0≤j<h$$​ (注意到 Gi,j(x0)0modMh1G_{i,j}(x_0)\equiv0\mod M^{h-1}​),那么格基维数为 dhdh

    det(L)=M(h1)hd2X(dh1)dh2\det(L)=M^{\frac{(h-1)hd}{2}}X^{\frac{(dh-1)dh}{2}}​ , 规约之后就可以得到 $$||SVP||<2^\frac{dh-1}{4}}\det(L)({\frac{1)dh}}=2({\frac{dh-1)4}}M({\frac{h-1)2}}X({\frac{dh-1){2}}$$​ ,

    该向量对应一个度数为 dh-1 的多项式G(x)G(x)​​ , 且G(x0)0modMh1G(x_0)\equiv 0\mod M^{h-1}​​ , 若其范数小于 Mh1dh\frac{M^{h-1}}{\sqrt{dh}}​​ 则有 G(x0)=0G(x_0)=0​​ 在 整数域上 ,即 $$\sqrtdh}2({\frac{dh-1)4}}M({\frac{h-1)2}}X({\frac{dh-1)2}}<M({h-1)$$​​ ,整理一下 得到 $$\sqrtdh} 2({\frac{dh-1)4}}X({\frac{dh-1)2}}<M({\frac{h-1){2}}$$​​ ,

    在整理一下 得到 $$c (d,h) X<M^\frac{h-1}{dh-1}}$$​​ ($$c(d,h)=\sqrt2(dh)({\frac{1){dh-1}}$$​​) 由 M 的幂次 h1dh1=1dd1d(dh1)\frac{h-1}{dh-1}=\frac{1}{d}-\frac{d-1}{d(dh-1)}​​ ,由设定条件, ϵ=d1d(dh1)\epsilon=\frac{d-1}{d(dh-1)}​​ 于是就得到了 h=d1dϵ+1d1dϵh=\frac{\frac{d-1}{d\epsilon}+1}{d}≈\frac{1}{d\epsilon}​​

    注:dh=1+d1dϵdh=1+\frac{d-1}{d\epsilon}​ , 所以 c(d,h)=2(1+d1dϵ)dϵd1c(d,h)=\sqrt{2}(1+\frac{d-1}{d\epsilon})^{\frac{d\epsilon}{d-1}}​ ,当 ε 趋向于 0 的时候 c(d,h)c(d,h)​ 收敛于 2\sqrt{2}​ ; 当 ε 趋向于 0.18 时, c(d,h)c(d,h)​ 仍小于 2,故满足 $$c (d,h) X<M^{\frac {h-1}{dh-1}}$$​ 也即设定条件

  • # 条件:

    Alice 使用同一公钥对两个具有某种线性关系的消息 M<sub>1</sub > 和 M<sub>2</sub > 进行加密,并将加密后的消息 C<sub>1</sub>,C<sub>2</sub > 这里假设模数为 N 可以得到两者线性关系用以下表示:M1f(M2)modNM_1≡f (M_2) mod N 其中 f 表示一个线性变化过程,例如 f=ax+bf=ax+b

  • # 原理:

    我们已知C1M1emodNC_1≡M_1^e \mod N, 并且 M1f(M2)modNM_1≡f (M_2) \mod N, 因此可以得出 M<sub>2</sub> 是f(x)eC1modNf(x)^e≡C_1 \mod N 的一个解,即它是方程 f(x)eC1f(x)^e-C_1 在模 N 意义下的一个根 并且 也是xeC2x^e-C_2 模 N 下的一个根。所以 xM2x - M_2 同时整除以上两个多项式的时候,就可以寻找他们的最大公因子,如果这个最大公因子恰好线性,就是想要求得的 M<sub>2</sub>。

  • # 例子:

    • 对于 e = 3 , f(x)=ax+bf(x) = ax + b 情况下:

      • 我们有 $$C_1≡ M_1^3 \mod N , M_1 ≡ a M_2 +b mod N => C_1 ≡ (aM_2 +b)^3 \mod N,C_2 ≡ M_2^3 \mod N$$​

      • 于是 可以得出 式 1 和 式 2

        (aM2+b)3=a3M23+3a2M22b+3aM2b2+b3a3M23b3(aM2b)(a2M22+aM2b+b2)modN(aM_2+b)^3=a^3M_2^3+3a^2M_2^2b+3aM_2b^2+b^3\newline a^3M_2^3-b^3\equiv (aM_2-b)(a^2M_2^2+aM_2b+b^2)\mod N

      • 接着 继续推出a3M232b3+3b(a2M22+aM2b+b2)C1modNa^3M_2^3-2b^3+3b(a^2M_2^2+aM_2b+b^2)\equiv C_1\mod N

      • 得到式 3 3b(a2M22+aM2b+b2)C1a3C2+2b3modN3b(a^2M_2^2+aM_2b+b^2)\equiv C_1-a^3C_2+2b^3\mod N

      • 式 2 和 式 3 得到 (a3C2b3)3b(aM2b)(C1a3C2+2b3)modN(a^3C_2-b^3)*3b\equiv (aM_2-b)(C_1-a^3C_2+2b^3)\mod N

      • 于是 直接得到M_2\equiv \frac{bC_1+2a^3C_2-b^3}

        就得到了 M<sub>2</sub>,因此就可以找到 M<sub>2</sub> 就得到了明文 M

    • Example:

      import gmpy2
      id1 = 
      id2 = 
      c1 = 
      c2 = 
      n = 
      a = 1
      b = id1 - id2
      def getmessage(a, b, c1, c2, n):
          b3 = gmpy2.powmod(b, 3, n)
          part1 = b * (c1 + 2 * c2 - b3) % n
          part2 = a * (c1 - c2 + 2 * b3) % n
          part2 = gmpy2.invert(part2, n)
          return part1 * part2 % n
      message = getmessage(a, b, c1, c2, n) - id2
      message = hex(message)[2:]
      if len(message) % 2 != 0:
          message = '0' + message
      print message.decode('hex')

      Exp:

      def attack(c1, c2, b, e, n):
          PR.<x>=PolynomialRing(Zmod(n))
          g1 = x^e - c1
          g2 = (x+b)^e - c2
          def gcd(g1, g2):
              while g2:
                  g1, g2 = g2, g1 % g2
              return g1.monic()
          return -gcd(g1, g2)[0]
      c1 = 
      c2 = 
      n = 
      e=
      a = 
      id1 = 
      id2 = 
      b = id2 - id1
      m1 = attack(c1,c2, b,e,n)

# Coppersmith's short-pad Attack

  • # 条件:

    大部分明文在加密过程中需要去 padding,但 padding 短的话,有可能就可以去容易攻击了,对应多项式根会变小

  • # 原理:

    Alice 给 Bob 发消息,Alice 需要去对 明文 随机 padding, 加密得到密文C1C_1 发送给 Bob。而 Peter 中间截获了密文。如果 Alice 继续发送 明文 随机 padding, 又被 Peter 截获,就有可能会被 Peter 解密得到明文

    假设模数 N 长度为 k , 同时 padding 长度为 m=k/e2m=⌊k/e^2⌋​. 假设 明文 长度最多为 k-m bits. 则 padding 方式为 $$M_1=2mM+r_1,0≤r_1≤2m$$​ M2M_2​也是如此去加密

    因此就可以使用下面的方式去解密:
    g1(x,y)=xeC1g2(x,y)=(x+y)eC2g_1(x,y)=x^e-C_1g_2(x,y)=(x+y)^e-C_2
    其中 y=r<sub>2</sub>-r<sub>1</sub> 显然有两个相同的 根 M<sub>1</sub>

  • # 定理:

    如果 (x<sub>0</sub>,y<sub>0</sub>) 是方程

    \begin{cases} f(x,y)=0\newline g(x,y)=0 \end{cases}$$ 的解 则 $y_0$ 是 $Res_x(f,g)$的一个根 可以在sage里面使用resultant 来实现结式计算,$g_1 · resultant( g_2 )$ 默认将结式以第二个变量来表示,也可以指定$g_1 · resultant( g_2 , y )$ 来将结式以x表示,求出y后,采用Related Message Attack,即求解gcd ( g1 , g2 ),如果结果是线性的,就攻击成功了 x = -gcd( g1 , g2 )[0]
    def short_pad_attack(c1, c2, e, n):
        PRxy.<x,y> = PolynomialRing(Zmod(n))
        PRx.<xn> = PolynomialRing(Zmod(n))
        PRZZ.<xz,yz> = PolynomialRing(Zmod(n))
        g1 = x^e - c1
        g2 = (x+y)^e - c2
        q1 = g1.change_ring(PRZZ)
        q2 = g2.change_ring(PRZZ)
        h = q2.resultant(q1)
        h = h.univariate_polynomial()
        h = h.change_ring(PRx).subs(y=xn)
        h = h.monic()
        kbits = n.nbits()//(2*e*e)
        diff = h.small_roots(X=2^kbits, beta=0.4)[0]  # find root < 2^kbits with factor >= n^0.4
        return diff
    def related_message_attack(c1, c2, diff, e, n):
        PRx.<x> = PolynomialRing(Zmod(n))
        g1 = x^e - c1
        g2 = (x+diff)^e - c2
        def gcd(g1, g2):
            while g2:
                g1, g2 = g2, g1 % g2
            return g1.monic()
        return -gcd(g1, g2)[0]
    if __name__ == '__main__':
        n = 
        e = 
        c1 =
        c2 = 
        diff = short_pad_attack(c1, c2, e, n)
        print("difference of two messages is %d" % diff)
        m1 = related_message_attack(c1, c2, diff, e, n)
        print("m1:", m1)
        print("m2:", m1 + diff)

# Part of m Leaking Attack

  • # 条件:

    我们加密消息 m , CmdmodNC ≡ m^d \mod N. 我们假设已知部分m0m_0 , 就是m=m0+xm=m_0 + x 。同时我们不知道 的 x 就是多项式的根 ,满足 Coppersmith 的约束

  • # 攻击原理:

    给定一个合数 N,同时合数 b 是 N 的一个因子,且 对于 一个已知的 β(0<β<1), 满足 b ≥ Nβ。给定一个度数为 δ ,首项 是 1 的单变量多项式 f<sub>b</sub>(x) ∈ Z [X], 在 δ 和 N 的比特长都的多项式函数的时间之内去得到所有 b|f<sub>b</sub>(x) 的满足 |x<sub>0</sub>|≤ X 的根 x<sub>0</sub> ∈ Z,X 是 x<sub>0</sub> 的上界。目标是通过这个更宽松的一个界去获得更大的可能性解出 x

    • 定理 1: Coppersmith 96: 已知 N , b , β , f , δ 。我们可以在 O(cδ5log9N)O(cδ^5log^9N)​​内得到满足条件:

      x012Nβ2δϵ|x_0|≤\frac{1}{2}N^{\frac{β^2}{δ}-\epsilon}

      的一员同余方程 f (x)=0 mod b 的解 (ε 多取 β/7)

    • 定理 2: Coppersmith 96 [2]: 当 N=b 时,就可以在 ( log N,δ ) 的多项式时间内所有满足

      |x_0|≤N^{\frac{1}{δ}}$$​ 的模等式 fN(x) = 0 mod N的解。因此只需要 e足够小,且得到了部分明文,就可以在log N和e的多项式内求出x
    n = 
    e = 
    c = 
    mbar = 
    kbits = 
    beta = 1
    nbits = n.nbits()
    print("upper {} bits of {} bits is given".format(nbits - kbits, nbits))
    PR.<x> = PolynomialRing(Zmod(n))
    f = (mbar + x)^e - c
    x0 = f.small_roots(X=2^kbits, beta=1)[0]  # find root < 2^kbits with factor = n
    print("m:", mbar + x0)
  • # NOte:

    m 高位泄露是 coppersmith 原版结论,可以扩展到 高位 / 低位 / 高低位泄露的一般情况

    m=M + x<sub>0</sub> · 2k + M' ;f<sub>n</sub>(x) = (M + x<sub>0</sub> · 2k + M' )e - c

    即可用 sage 求解 (只要位置明文 |x<sub>0</sub>| ≤ N1/e)

# Part of p Leaking Attack:

  • # 条件:

    知道公钥中模数 N 中的一个因子的较高位

  • # 原理:

    kp 高位比特泄露: p > q ,k ∈ N*,q 不整除 k , 如果对于 kp 的一个估计值 p~ 满足 | kp-p~|≤ 2 N1/4 就可以在多项式时间内得到 N 的分解

    Proof:

    fp(x)=x+pf_p(x)=x+p​ 的一个解为 x0=kppmodpx_0=kp-p\mod p​满足 $$x_0≤2N^{\frac {1}{4}}$$​ , 该多项式是首一多项式,有定理 1 可知他有解。

    推广到 p 的低位泄露也可以使用 coppersmith 方法攻击 ,只需要化为首一多项式即可

  • # exp:

    n = 
    e = 
    c = 
    pbar = 
    kbits = 
    print("upper %d bits (of %d bits) is given" % (pbar.nbits()-kbits, pbar.nbits()))
    PR.<x> = PolynomialRing(Zmod(n))
    f = x + pbar
    x0 = f.small_roots(X=2^kbits, beta=0.4)[0]  # find root < 2^kbits with factor >= n^0.4
    p = x0 + pbar
    print("p:", p)
    q = n // int(p)
    d = inverse_mod(e, (p-1)*(q-1))
    print("m:", pow(c, d, n))
  • # Note:

    sagemath 当中 small_root 参数不能太大,因此要自行判断阀值取调整 (若 x 过大,即使存在 X 内的解,也无法解

    比如 p 的低位泄露时,因不确定高位到底缺失多少 bit, 所以要在 2n.nbits()/2kbits2^{n.nbits()/2-kbits} 附近做 X 的阀值估计,无法确定 p 是否大于 q 所以对 β=0.5 改为 0.4

# Part of d Leaking Attack:

  • # 条件:

    给出 n.nbits ()/4 , 泄露了 d 的低位,我们可以通过 n 和 e 计算 d 在一个多项式的时间里

    Proof :

    s=p+qs=p+q , ed=1+kϕ(n)=1+k(ns+1)ed=1+k\phi(n)=1+k(n-s+1)

    ed01+k(ns+1)mod2n4(1)ed_0\equiv1+k(n-s+1)\mod 2^{\frac{n}{4}}(1)

    p2sp+n0mod2n4(2)p^2-sp+n\equiv 0\mod 2^{\frac{n}{4}}\ (2)

    p×(1)k×(2)=ed0p+kpnkp2kn+kpmod2n4p×(1)-k×(2)=ed_0\equiv p+kpn-kp^2-kn+kp\mod2^{\frac{n}{4}}

    解一元同余方程 ed0xkx(nx+1)+knxmod2d0.nbits()ed_0x-kx(n-x+1)+kn\equiv x\mod2^{d_0.nbits()} 就得到了 p 的低位 p0p_0

  • # EXP:

    def partial_p(p0, kbits, n):
        PR.<x> = PolynomialRing(Zmod(n))
        nbits = n.nbits()
        f = 2^kbits*x + p0
        f = f.monic()
        roots = f.small_roots(X=2^(nbits//2-kbits), beta=0.4)  # find root < 2^(nbits//2-kbits) with factor >= n^0.4
        if roots:
            x0 = roots[0]
            p = gcd(2^kbits*x0 + p0, n)
            return ZZ(p)
    def find_p(d0, kbits, e, n):
        X = var('X')
        for k in range(1, e+1):
            results = solve_mod([e*d0*X - k*X*(n-X+1) + k*n == X], 2^kbits)
            for x in results:
                p0 = ZZ(x[0])
                p = partial_p(p0, kbits, n)
                if p and p != 1:
                    return p
    if __name__ == '__main__':
        n = 
        e = 
        c = 
        d0 = 
        beta = 0.5
        nbits = n.nbits()
        kbits = d0.nbits()
        print("lower %d bits (of %d bits) is given" % (kbits, nbits))
        p = int(find_p(d0, kbits, e, n))
        print("found p: %d" % p)
        q = n//int(p)
        print("d:", inverse_mod(e, (p-1)*(q-1)))

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

De3B4to 微信支付

微信支付

De3B4to 支付宝

支付宝