• CRT-RSA是由Quisquater和Couvreur推广，CRT-RSA目前是实际中实现RSA的标准方法。

CRT-RSA加密原理

• 通过利用模数的分解，可以降低RSA解密的计算成本。

• 设$(e,N)$是一个有效的公钥，$(d,p,q)$为其对应的私钥，其中指数是模数$\lambda(N)$定义的。

  • 对于给定的密文$c=m^e~mod(~N)$，RSA的标准解密是通过计算$m=c^d~mod(~N)$恢复明文，即对一个n位数进行一次模幂运算。
  • 由于解密方已知模数中的质数，因此明文也可以通过密文分别取模$p$和$q$进行部分解密，然后再利用中国剩余定理将这些结果结合起来计算出明文。
  • 首先我们先能计算：

  $$m_p = c^{d}~mod~p\\ m_q = c^{d}~mod~q$$

  • 由于这两个质数互素，可以利用中国剩余定理将它们组合以得到明文。例如，使用Garner算法，明文计算公式为：

  $$m=m_p+p·((m_q-m_p)·p^{-1}~mod~q)$$

  • 因此，我们将对一个n位整数的单次模幂运算替换为两个$\frac{n}{2}$位整数的模幂运算，外加若干其他操作。如下面所述，标准解密中的单次模幂运算在计算上比备用方法所需的所有计算都更昂贵。

• 我们将把任何使用中国剩余定理进行解密、以类似上述方法实现的RSA称为CRT-RSA。

• 此外，我们将把CRT-RSA的解密方法称为CRT解密，就像我们把标准RSA的解密称为标准解密一样。由于RSA的素数是保密的，这种解密方法当然不能用于加密。CRT-RSA的加密方法和标准RSA相同。

  • 当私钥指数大于$N^{\frac{1}{2}}$时，可以在每个部分解密中使用一个缩减后的指数。

  $$d_p=d~mod(~p-1)\\ d_q=d~mod(~q-1)$$

  • 根据费马小定理，$d_p$和$d_q$可以在部分解密中替代$d$的使用，下面的$d_p$和$d_q$我们称之为CRT指数。

  $$m_p=c^{d_p}~mod~p\\ m_q=c^{d_q}~mod~q$$

  • 由它们的定义以及RSA密钥等式可知，它们还满足：

  $$ed_p\equiv 1~mod(~p-1)\\ ed_q\equiv 1~mod(~q-1)$$

  • 因此存在整数$k_p$和$k_q$使得，我们将这些称为CRT方程

  $$ed_p=1+k_p(p-1)\\ ed_q=1+k_q(q-1)$$

  • 当私钥指数比每一个素数都小的，这就满足$d=d_p=d_q$

• 对于CRT-RSA，我们假设公钥由$(e,N)$给出，私钥由$(d_p,d_q,p,q)$给出。在实际中，私钥可能还包含$p$模$q$的逆元即：$p^{-1}~mod~q$，这样使用Garner算法合并部分解密结果时就不需要再计算这个逆元了。（例如，参考PKCS#1 v2.1标准）

CRT-RSA的变种

• CRT-RSA的指数选择有多种方式，取决于是否需要快速加密或解密。与标准RSA类似，使用较小的指数可以降低计算成本。
• 在实际中，几乎总是固定的小公钥指数，例如$e=2^{16}+1$或$e=3$。此时，有极高的概率私钥指数$d$以及两个CRT指数通常都是满尺寸的。当素数是平衡素数的时候，我们可以预计$d\approx N$，那么$d_p,d_q\approx N^{\frac{1}{2}}$
• 使用这样的CRT-RSA小公钥指数意味着以最大化解密开销代价来最小化加密开销。
• 在某些情况下，可能希望尽量降低解密开销。可以通过使用较小的私钥指数来减少解密开销，但由于私钥指数过小的情形是可以被破解的，所以私钥指数至少应大于$N^{0.2929}$，或者比这个界限更大。然而，使用CRT解密时，Wiener观察到可以使用远小于$N^{\frac{1}{4}}$的CRT指数仍然可以保持加密安全。
  • 具体来说，在密钥生成算法中，选择不同的小CRT指数$d_p$和$d_q$，然后通过中国剩余定理计算公钥指数$e$，这样高概率下而定的公钥指数仍然是满尺寸的。
  • 此外，私钥指数$d$也很可能是满尺寸的。因此，所有针对小私钥攻击都不适用。当然，CRT指数也不能选得过小，之后会学习相关攻击。
  • 以这种方式生成的CRT-RSA通常称为Rebalanced RSA。有关Rebalanced RSA的密钥生成算法的详细细节，可参见Boneh和Shacham。在Rebalanced RSA中，CRT解密开销被最小化，但代价是加密（以及标准加密）开销被最大化。
  • 注：Rebalanced RSA其实是先生成较小的CRT指数$d_p,d_q$，而私钥指数$d$以及公钥指数$e$都是满尺寸的，并且$p,q$也都是平衡的。这就使得加密开销非常大，解密开销非常小。
• 典型的CRT-RSA（使用小公钥指数）和Rebalanced RSA分别代表了在CRT-RSA中最小化（或最大化）加密或解密开销的两种极端情况。也可以生成CRT-RSA实例，使用加密和解密开销更加平衡。例如，可能希望加密和解密的计算量大致相等。Galbraith、Heneghan和McKee，Sun和Wu以及Jochemsz和May提出了几种用于生成任意大小公钥和CRT指数的CRT-RSA密钥生成算法。

CRT-RSA的效率

• 每种RSA变体的效率都高于使用标准解密的RSA。按照前面的定义，设$M(n)$表示对两个$n$位数在另一个$n$位数模下相乘的复杂度。考虑一个模数为$n$位、私钥指数为$d=N^{\delta}$的RSA系统。
• 假设私钥指数在二进制表示中1和0的数量大致相等，则解密的复杂度预计为：$\frac{3}{2}\delta nM(n)$。对于CRT解密，复杂度主要由对部分解密$m_p$和$m_q$的两次模幂运算决定。这里假设在使用Garner算法时，已预先计算好$p^{-1}~mod~q$的逆元。
• 设两个CRT指数大约为$N^{\delta_p}$，其中$0<\delta_p≤\frac{1}{2}$。假设每个CRT指数在二进制中0和1的数量大致相等，则CRT解密的复杂度预计为：$2·\frac{3}{2}·\delta_p nM(\frac{n}{2})$，也就是说两次$\frac{n}{2}$位数的模幂运算是CRT解密主要计算量。
• 因此，CRT解密预计必标准解密快的倍数为：$\frac{1}{2}·\frac{\delta}{\delta_p}·\frac{M(n)}{M(\frac{n}{2})}$。由于$M(n)$的复杂度可以在接近线性到二次之间变化，因此这种加速比大约在区间$(\frac{\delta}{\delta_p},\frac{2\delta}{\delta_p}]$内，。如果CRT解密的部分可以并行完成，那么加速比还可以再增加一倍。
• 下面我们来考虑这种加速在不同CRT-RSA变体中的表现。当公钥指数较小且私钥指数与CRT指数均为满尺寸时，如果素数平衡，我们有$\delta\approx1$且$\delta_p\approx \frac{1}{2}$。这对应的加速比大约在区间$(2,4]$内。因此，使用CRT解密的速度至少比标准解密快一倍。
• 当使用Rebalanced RSA时，CRT指数较小，但私钥指数仍为满尺寸。因此，我们有$\delta\approx 1$且$\delta_p \ll \frac{1}{2}$。这对应的加速比大约在取决$(\frac{1}{\delta_p},\frac{2}{\delta_p}]$。例如，考虑一个模数为1024位、CRT指数为160位的实例，这对应的加速比大约在$(6.4,12.8)$之间。
• 将Rebalanced RSA与典型CRT-RSA实例进行比较，解密开销预计快约$\frac{1}{\delta_p}$倍。在这里，乘法开销相同，唯一不同的是指数的大小。以前面提到的1024位模数和160位CRT指数为例，相比典型的1024位私钥指数实例，加速比约为3.2。在Boneh和Shacham的实现中，使用这些参数，实际中实现的加速约为3.06倍。
• 对于指数平衡的CRT-RSAS，由于公钥指数小于$\phi(N)$，私钥指数预计仍为全尺寸。因此，解密加速预计与Rebalancd RSA相等。如果两个CRT指数大约为$N^{\delta_p}$，则加速比预计在区间$(\frac{1}{\delta_p},\frac{2}{\delta_p}]$之间。实际加速值将取决于模乘运算的具体实现。同样，如果允许部分解密并行进行，这个加速比还会再增加一倍。

破解CRT-RSA

• 我们认为，当CRT-RSA的模数分解已知时，这个实例（实际上也是一个普通的RSA实例）就被破解了。由于CRT-RSA也是RSA的一个实例，因此所有针对RSA的攻击同样适用于CRT-RSA。特别地，只要计算出私钥指数$d$就足以破解CRT-RSA，因此此时模数可以在多项式时间内被确定分解。

• 计算出CRT指数同样足以破解CRT-RSA：

  • 利用CRT指数$d_p,d_q$，注意将CRT方程(CRT等式)

  $$ed_p-1=k_p(p-1)\\ ed_q-1=k_q(q-1)$$

  • 将上面两个式子相乘得到，其中左边的所有量都是已知的

  $$e(ed_pd_q-d_p-d_q)+1=k_pk_q(p-1)(q-1)$$

  • 因此我们能计算出$\phi(N)$的一个倍数，从而利用Miller的结果分解模数。
  • 此外，由上述方程可知：$D=-ed_pd_q+d_p+d_q$，是一个有效的标准解密私钥指数，之后可以用它来解密任何密文。或者可以使用一种确定性的基于格的方法，其思路类似于May和Coron与May的结果，由Maitra和Sarkar提出，可在多项式时间内分解模数。

• 即使只知道一个CRT指数，模数仍然预计可以被轻松分解。假设我们已知$d_p$。

  • 如果私钥指数$d$小于每个素数，使得$d=d_p=d_q$，那么$ed_p-1$是$\lambda(N)$的倍数，此时可以利用$Miller$的结果以概率性方法分解模数。
  • 如果私钥指数$d$，大于每个素数，注意到由于$ed_p=1+k_p(p-1)$因此对于任意明文$m\in \Z^{*}_p$，都有$m^{ed_p}\equiv m~mod(~p)$
  • 因此，就有$m^{ed_p}-m=cp$，其中$c$是某个整数，设$M=(m^{ed_p}-m)~mod(~N)$，当$c$不是素数$q$的倍数时，通过计算$gcd(M,N)=p$
  • 当$c$是$q$的倍数时，则有$m^{ed_p}\equiv m~mod(~N)$，如果这对所有$m\in \Z^{*}_p$都成立，那么模数可以被分解，因此$d_p$只是明文$m$的一个恢复指数，目前尚不清楚这些信息能否用于分解模数。