针对含小CRT私钥不平衡RSA的攻击

发表于 更新于 分类于

不平衡RSA指的是p,q的大小相差很大，并且将假定q<p，q的大小为 \(N^\beta\)，\(d_p=d\ mod\ p-1\) ，\(d_p\) 的大小为 \(N^\delta\)

本文将按顺序介绍几种方法来分解满足条件的 \(N\)，随着p,q相差越大，即 \(\beta\) 越小，可以利用的 \(d_p\) 的上界也将提高

  1. \(3\beta + 2\delta ≤ 1 − log_N (4).\)
  2. \(3\beta − \beta^2 + 2\delta ≤ 1 − \epsilon.\)
  3. \(\frac{5}{3}\beta +\frac{2}{3}\sqrt{3\beta − 5\beta^2} + \delta ≤ 1 − \epsilon\)

1红色 2蓝色 3绿色

不平衡RSA的生成方法

生成p,q 满足 \(q<N^\beta,\ p>N^{1-\beta},\ gcd(p-1,\frac{q-1}{2})=1\) \[ \begin{cases} d\equiv d_p\ mod\ p-1\\ d\equiv d_q\ mod\ \frac{p-1}{2} \end{cases}\\ e\equiv d^{-1}\ mod\ \frac{\phi(N)}{2} \]

方法介绍

方法1

该方法的时间复杂度为\(O(log^2(N))\)

设 \(ed_p+k(p-1)=1\)，则 \(ed_p-(k+1)\equiv 0\ mod\ p\)

设 \(f_p(x,y)=ex-y\) ，则在模p下有解 \((d_p,k+1)\)

因为 \(e<\frac{(p-1)(q-1)}{2}\) \[ d_p<N^\delta,\ |k+1|<2|k|=2|\frac{ed_p-1}{p-1}|<2\frac{ed_p}{p-1}=(q-1)d_p<N^{\beta+\delta} \] 造格子\(L_p,\ B_p\)为\(L_p\)上的一组基，\(X=N^\delta,\ Y=N^{\beta+\delta}\) \[ B_p= \begin{pmatrix} NX\\ eX&-Y \end{pmatrix} \] 见我之前写的文章Coppersmith算法及其应用

运用Minkowski定理和Howgrave-Graham定理，得到 \[ ||v||\le \sqrt{2det(B_p)}<\frac{N^{1-\beta}}{\sqrt{2}}<\frac{p}{\sqrt{2}} \] 计算得 \[ 3\beta + 2\delta ≤ 1 − log_N (4) \] 假设 \(||v||=(c_0,c_1)·B_p\) 是 \(L_p\) 上满足 \(||v||<\frac{p}{\sqrt{2}}\) 的最短向量，那么 \(|c_0|=k,\ |c_1|=qd_p\)

这是因为 \[ f(x_0,y_0)=c_0Nx_0+c_1(ex_0-y_0)=0\Rightarrow c_0qd_p=c_1k \] 又因为我们假设 \(q\nmid k\) ，所以 \(gcd(qd_p,k)=gcd(d_p,k)\). 由 \(ed_p+k(p-1)=1\) 得，\(gcd(d_p,k)=1\)，所以 \[ c_0=ak\ \ and\ \ c_1=aqd_p \] 因为 \(v\) 是最小向量，所以 \(gcd(c_0,c_1)=1\ \Rightarrow |a|=1\)

所以q可以由 \(gcd(c_1,N)=q\) 得到，从而分解 \(N\) ，而 \(d_p\) 和 \(k+1\) 也可以根据 \(c_0,c_1\) 计算得出从而得到 \(f_p(x,y)\) 的解 \((d_p,k+1)\)

例子

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
from Crypto.Util.number import *
import gmpy2
from random import getrandbits,randrange

while True:
    p=getPrime(int(2048-512))
    q=getPrime(int(512))
    if gmpy2.gcd(p-1,(q-1)//2)==1:
        break
n=p*q

while True:
    d_p=getrandbits(int(200))
    d_q=randrange(0,(q-1)//2)
    d=d_p*inverse((q-1)//2,p-1)*(q-1)//2+d_q*inverse(p-1,(q-1)//2)*(p-1)
    if GCD(d,(p-1)*(q-1)//2)==1:
        break

e=inverse(d,(p-1)*(q-1)//2)

X=2**200
Y=2**712

L=matrix([[n*X,0],[e*X,-Y]])
c1=abs(L.LLL()[0][1])//Y
q=int(GCD(c1,n))

print(1<q<n,n%q==0)

方法2

在方法1的基础上使用x-shift多项式

设 \(X=\frac{n+1}{2}N^\delta\ and\ Y=\frac{n+1}{2}N^{\beta+\delta}\)

设多项式 \(g_{m,i,j}(x,y) = N^{max(0,m−j)}x^if_p(x,y)^j\)对于$ 0 ≤ j < n，i=n-j-1$

则 \(g_{m,i,j}\) 有非零解 \((x_0,y_0)=(d_p,k+1)\ mod\ p^m\)

m是n的函数，需要进行优化，后面会讲

例如，取n=4和m=2，得到一个4维格子 \(L_p(4)\) \[ B_p(4)= \begin{pmatrix} N^2X^3\\ eNX^3&-NX^2Y\\ e^2X^3&-2eX^2Y&XY^2\\ e^3X^3&-3e^2X^2Y&3eXY^2&-Y^3 \end{pmatrix} \] 方法1就是m=1，n=2时的特例，即 \(B_p(2)\)

计算得到 \[ det(B_p(n))=N^{\frac{m(m+1)}{2}}(XY)^{\frac{n(n-1)}{2}}=(\frac{n+1}{2})^{n(n-1)}N^{\frac{m(m+1)}{2}+(2\delta+\beta)\frac{n(n-1)}{2}} \] 结合LLL算法和Howgrave-Graham定理得 \[ 2^{\frac{n-1}{4}}det(B_p(n))^{\frac{1}{n}}\le \frac{N^{(1-\beta)m}}{\sqrt{n}} \]

\[ \Rightarrow N^{\frac{m(m+1)}{2}+(2\delta+\beta)\frac{n(n-1)}{2}}\le cN^{(1-\beta)mn},\ c=((2^{-\frac{3}{4}}(n+1))^{n-1}\sqrt{n})^{-n} \]

让下面式子左边最小， \[ \frac{m(m+1)}{2}+(2\delta+\beta)\frac{n(n-1)}{2}-(1-\beta)mn\le0 \] 当 \(n\rightarrow \infin\) 可以得到 \(m=(1-\beta)n\)，代入再计算得 \(3\beta-\beta^2+2\delta\le 1\)

在方法1中，我们通过 \(k\mid c_1，d_p\mid c_2\) 求出根。但方法2增加了系数的个数，所以需要使用另一种方法求根

假设点 \((x_0,y_0)\) 是 \(f_p\) 的根，对任意的整数 \(a\) ，点 \((ax_0,ay_0)\) 也是 \(f_p\) 的根。每一个根 \((ax_0,ay_0)\) 对于 \(|a|\le \frac{n+1}{2}\) ，都满足条件 \(|ax_0|\le X,\ |ay_0|\le Y\)。存在至少 \(n+1\) 个根（论文说的，没弄懂），根据Howgrave-Graham定理，\(f\) 在 \(Z\) 上包含了这些根

显然这些根也是多项式 \(p(x,y)=y_0x-x_0y\ \in\ Z[x,y]\) 的根，因为这些根在直线 \(y=\frac{y_0}{x_0}x\) 上。多项式 \(p,\ f\) 分别是1阶和n阶的，因为这两个多项式有至少 \(n+1\) 个公共点，而 \(p\) 是不可约多项式，所以 \(p|f\)

通过分解 \(f\) 寻找多项式 \(p'=(by_0)x-(bx_0)y\) 。因为 \(ed_p-(k+1)=-kp\) ，所以 \(gcd(d_p,k+1)|kp\)。但 \(gcd(d_p,kp)=gcd(d_p,k)=1\)，所以 \(gcd(x_0,y_0)=gcd(d_p,k+1)=1\)

所以 \(p=\frac{p'}{b}=\frac{p'}{gcd(by_0,bx_0)}\)

方法3

我们假定 e 拥有与 N 一样的数量级，因为 e 是由 \(d^{-1}\ mod\ \frac{\phi(N)}{2}\) 生成的

回顾式子 \[ ed_p+k(p-1)=1\\ \Rightarrow (k+1)(p-1)-p=-ed_p\\ \Rightarrow (k+1)(N-q)-N=-ed_pq \] 这给出多项式 \(f_e(y,z)=y(N-z)-N\)，在模e下有根 \((y_0,z_0)=(k+1,q)\)

定义 \(Y=N^{\beta+\delta},\ Z=N^\beta\)，有 \(|y_0|\le Y,\ |z_0|\le Z\) 。

类似之前的思路，我们可以定义3维格 \(L_e\) \[ B_e= \begin{pmatrix} e\\ &eY\\ -N&NY&-YZ \end{pmatrix} \] 运用Howgrave-Graham定理，找到 \(v\in L_e,\ |v|<\frac{e}{\sqrt{3}}\)，可以得到 \(3\beta+2\delta\le 1-\epsilon\) 和方法1类似的结果

在方法1中，我们使用 \(x\)-shifted 多项式来提高 \(\beta\) 的上界。类似的，现在我们使用 \(z\)-shifted 多项式来提高 \(\delta\) 的上界

定义 \(y\)-shifted 多项式和 \(z\)-shifted 多项式 \[ \begin{cases} g_{i,j}(y,z)=e^{m-i}y^jf_e^i(y,z)\\ h_{i,j}(y,z)=e^{m-i}z^jf_e^i(y,z) \end{cases} \] 这些多项式在模 \(e^m\) 都有相同的根 \((y_0,z_0)\)。利用这些多项式 \(g_{i,j}(yY,zZ)\) 和 \(h_{i,j}(yY,zZ)\) 的的系数向量构造格 \(L_e(m)\)对于 \(g\) 我们取所有满足 \(i+j\le m\) 的i,j，但对于 \(h\) 我们取 \(i=0...m,\ j=1...t\) ，这里t是依据m优化的函数决定的

例如，取 \(m=2,\ t=1\)，得到一个格子 \(L_e(2)\) \[ B_e(2)= \begin{pmatrix} g_{0,0}\\ g_{0,1}\\ g_{1,0}\\ g_{0,2}\\ g_{1,1}\\ g_{2,0}\\\hline h_{0,1}\\ h_{1,1}\\ h_{2,1} \end{pmatrix}= \begin{pmatrix} e^2\\ &e^2Y\\ -eN&eNY&-eYZ\\ &&&e^2Y^2\\ &-eNY&&eN^2Y^2&-eY^2Z\\ N^2&-2N^2Y&2NYZ&N^2Y^2&-2NY^2Z&Y^2Z^2\\\hline &&&&&&e^2Z\\ &&eNYZ&&&&-eNZ&-eYZ^2\\ &&-2N^2YZ&&N^2Y^2Z&-2NY^2Z^2&N^2Z&2NYZ^2&Y^2Z^3 \end{pmatrix} \] 运用Howgrave-Graham定理，有 \(|v|<\frac{e^m}{\sqrt{dim\ L_e(m)}}\)

设 \(t=\tau m,\ e=N^{1-o(1)}\)，通过计算得到 \[ \begin{array}\\ det\ L_e(m)&=(eY)^{\frac{1}{6}(2m^3+(6+3t)m^2+(4+3t)m)}Z^{\frac{1}{6}(m^3+(3+6t)m^2+(2+9t+3t^2)m+3t+3t^2)}\\ &=N^{\frac{1}{6}m^3((1+\beta+\delta)(2+3\tau)+\beta(1+6\tau+3\tau^2)+o(1))} \end{array} \]

\[ |v|\le 2^{\frac{dim\ L_e(m)-1}{4}}det(L_e(m))^\frac{1}{dim\ L_e(m)}<\frac{e^m}{\sqrt{dim\ L_e(m)}}\\ \Rightarrow det\ L_e(m)<cN^{(1-o(1))m\ dim\ L_e(m)} \]

这里的c与N无关，贡献用 \(\epsilon\) 表示。计算可得 \(dim(L)=\frac{(m+1)(m+2)}{2}+t(m+1)\)

结合上式，忽略 \(m\rightarrow \infin\) 时的低阶项，得 \(3\beta(\tau^2+3\tau+1)+\delta(3\tau+2)-3\tau-1<0\)

让左边最小得到，\(\tau=\frac{1-3\beta-\delta}{2\beta}\)，代入再计算得 \(\frac{5}{3}\beta +\frac{2}{3}\sqrt{3\beta − 5\beta^2} + \delta ≤ 1\)

扩展

在上面的方法中，我们都假定了 \(q\nmid k\) 。但当 \(q\mid k\) 时，条件会更加宽松

设 \(k=qr\) ，有 \(ed_p-(k+1)=-kp=-rN\) 。所以在方法1的基础上，\(f_p=0\) 不仅在模p下有解，也在模N下有解

因此有 \(\sqrt{2det(Bp)}<\frac{N}{\sqrt{2}}\)，计算得 \(\beta+2\delta\le1-log_N(4)\)

参考

  • May A . Cryptanalysis of Unbalanced RSA with Small CRT-Exponent[C]// Advances in Cryptology - CRYPTO 2002, 22nd Annual International Cryptology Conference, Santa Barbara, California, USA, August 18-22, 2002, Proceedings. Springer-Verlag, 2002.