多素数RSA加密原理

• 接下来介绍一下多素数RSA，多素数RSA与正常RSA相比，多素数RSA的模数$N$是由三个或者更多个不同的素数相乘的。这个变体就被称为多素数RSAmulti-prime RSA，与传统RSA相比，它在密钥生成和CRT解密方面具有更高的速度。

多素数RSA

• 多素数RSA是一个RSA的简单拓展，其中多素数RSA模数$N$是由3个素数或者多个素数相乘。然而，其实我们其实将RSA视为特殊的多素数RSA，因为正常的RSA加密只有两个素数。
• 模数$N$使用多余两个素数的优势是在密钥生成以及用中国剩余定理解密的时候比标准RSA更有效率，这两种操作的开销随着模数中质数的数量增加而减少。
• 下面使用的大部分符号和假设都是对RSA中符号和假设的直接扩展。模数中有两个质数时，恢复与RSA相同的定义与性质。为了方便起见，在提到模数中有$r$个质数的多质数RSA时，我们通常使用r-prime RSA这一名称。
• 对于r个素数的多素数RSA，模数$N=p_1···p_r$仅仅是r个不同的素数相乘。对于RSA加密，我们仅仅考虑平衡素数。为了方便，我们设多素数$p_1···p_r$的值不断自增，满足$p_i<p_{i+1}$其中$i=1,...,r-1$，我们假设：

$$4<\frac{1}{2}N^{\frac{1}{r}}<p_1<N^{\frac{1}{r}}<p_r<2N^{\frac{1}{r}}$$

• 多素数RSA的密钥生成算法本质上与传统RSA相同，不同之处在于模数需要r个随机且互不相同的平衡素数，而不是两个。公钥指数$e$和私钥指数$d$定义为模$\phi(N)$的乘法逆元，即满足：$ed\equiv 1~mod~(\phi(N))$，或者说$ed= 1+k\phi(N)$我们之前就已经说了，这个是密钥等式。

• 其中$k$是某个正整数，与正常RSA加密相同，我们可以用$N-s$来替代$\phi(N)$，对于$\phi(N)$，它使得$s$能被写成如下形式：

  $$\begin{array}{l} s&=N-\phi(N)\\ &=N-\Pi^{r}_{i=1}(p_i-1)\\ &=\sum^{r}_{i=1}\frac{N}{p_i}-\sum^{r}_{i,j=1 ,i<j}\frac{N}{p_ip_j}+\sum^{r}_{i,j,k=1,i<j<k}\frac{N}{p_ip_jp_k}+···+(-1)^{r} \end{array}$$

  • 上述式子，再结合平衡素数的假设，我们就可以推出$s$的一个上界，其上界如下：

  $$|s|=(2r-1)N^{1-\frac{1}{r}}$$

  • 因此$\phi(N)$和$N$有大约$\frac{r-1}{r}$的最高有效位MSB相同，因此$N$可以非常好的近似于$\phi(N)$。
  • 然而，随着模数中素数数量的增加，$N$和$\phi(N)$之间共有的比特比例会逐渐降低，大多数针对RSA的攻击，都可以推广到多素数RSA的情形，只需在模数包含r个素数时使用上述关于$|s|$的界即可。需要注意的是，当取$r=2$时，就恢复了传统RSA的相应界限。

• 多素数RSA的加密算法与正常RSA完全相同，对于任意明文消息$m$，密文为$c=m^{e}~mod(~N)$，公钥指数通常记作$e=N^\alpha$，其中$0<\alpha<1$

• 与传统RSA一样，多素数RSA也有两种解密算法：

  • 标准解密方法与RSA完全相同：
    • 给定密文$c$，明文通过$m=c^{d}~mod(~N)$，计算得到，其中$d$是私钥指数。
    • 私钥指数通常记作$d=N^{\beta}$或$d=N^{\delta}$，其中$0<\beta,\delta≤1$。
    • 在部分密钥泄露攻击的情形下，我们设$d=N^{\beta}$，并用$\delta$表示$d$的未知部分的数量级。例如，$\hat{d}$是$d$的一个已知近似值，则假设未知部分满足$|d-\hat{d}|≤N^{\delta}$，在其他所有情形中，我们直接记$d=N^{\delta}$
  • 另一种解密方法就是CRT-RSA体制的解密方法，是对CRT-RSA解密算法的自然推广。
    • 具体而言，我们分别计算$r$个部分解密结果，然后使用Garner算法将它们合并。
    • 在这种情况下，私钥指数记为：$d=N^{\beta}$，而CRT指数$d_i=d~mod(~p_i-1)$，满足$0＜\delta≤\frac{1}{r}$
    • 我们将使用中国剩余定理进行解密的多素数RSA称为CRT multi-prime RSA，或简称为采用CRT解密的多素数RSA。

• 多素数RSA的公钥为$(e,N)$，私钥为$(d,p_1,...,p_r)$，为了加速解密算法，私钥中还可以包含其他信息，例如PKCS#1 v2.1标准在私钥中包含了如下等逆元信息，这样在使用CRT进行解密时，就不需要再重新计算这些逆元：

$$p_1^{-1}~mod~p_2\\ p_1p_2^{-1}~mod~p_3\\ ...\\ p_1...p_{r-1}^{-1}~mod~p_r$$

多素数RSA的效率

• 多素数RSA密钥生成算法需要生成r个尺寸相同的随机素数。对于一个模数$N$，每个素数需要约等于$N^{\frac{1}{r}}$。对于RSA来说，需要生成两个大小相同的随机素数其大小为$N^{\frac{1}{2}}$。对于一个n比特位的模数，每个素数所需的随机比特是相同的。然而由于素数测试的复杂度随着素数位数呈超线性增长，生成多素数RSA的所有$\frac{n}{r}$位素数的总体复杂度要低于生成传统RSA的两个$n/2$位质数的复杂度。
• 密钥生成时间的具体差异取决于实现算术运算所使用的具体算法。总体来说，多素数RSA的密钥生成时间会随着模数中素数数量的增加而减少。
• 多素数RSA的加密与传统RSA相同，因此加密开销也相同。当使用标准解密时， 解密开销同样与RSA一致。因此，使用多素数RSA并采用标准解密的唯一好处是降低了密钥生成的开销。
• 然而，当解密使用CRT时，多素数RSA的解密开销低于CRT-RSA的解密开销，解密算法中的主要开销是$r$次部分解密，这些部分解密本质上就是模幂运算。
  • 根据正常解密的效率可以得到解密的期望开销为：$r·\frac{3}{2}\delta nM(\frac{n}{r})$，其中$M(\frac{n}{r})$表示长度为$\frac{n}{r}$的模幂运算的复杂度。
  • 当CRT指数的大小为$N^{\delta}$且模数为$n$位时，我们假设CRT指数的二进制表示1和0的数量大致相同，与CRT-RSA的解密开销$2·\frac{3}{2}\delta n M(\frac{n}{2})$相比，可以看出，多素数RSA的解密开销始终低于CRT-RSA，接下来，我们将更详细地讨论多素数RSA的两种情形。
    • 当使用较小的公钥指数时，CRT指数通常会满长度的。因此，在这种情况下，我们可以将多素数RSA中的$\delta$取为$\frac{1}{r}$，而$CRT-RSA$中取位$\frac{1}{2}$。在这种情况下，CRT-RSA与多素数RSA的解密开销比为：$\frac{M(\frac{n}{2})}{M(\frac{n}{r})}$，其中$M(·)$表示对应位数的模幂运算复杂度。
    • 由于$M(n)$的复杂度可能介于近线性到二次方之间，因此该比值的范围为$(\frac{r}{2},\frac{r^{2}}{4}]$，因此预计至少能获得$\frac{r}{2}$倍的加速。当$M(n)$关于$n$是二次时，加速可达到$\frac{r^{2}}{4}$倍
    • 在Boneh和Shacham的实现中，使用GMP打整数库，对1024位模数的3-prime RSA与CRT=RSA相比，当$r=3$时，观察到约1.73倍的加速。注意，这个实际观察到的加速落在预测范围$(\frac{r}{2},\frac{r^2}{4}]=(1.5,2.25]$内。
    • 当使用较小的CRT指数时，CRT-RSA的解密开销与多素数RSA解密开销的比值为：$\frac{2M(\frac{n}{2})}{rM(\frac{n}{r})}$，由于$M(n)$的复杂度可能介于近线性到二次方之间，因此该比值范围为$(1,\frac{r}{2})$。在实际情况中，$M(n)$的复杂度通常不会非常接近线性，因此可以预期多素数RSA的解密开销仍然更低。使用较小的CRT指数来加速多素数RSA的想法最早由Paixão提出。
• 随着模数中质数数量的增加，密钥生成和CRT解密的效率都会提高。虽然这似乎鼓励使用更多素数，但是必须在安全上做出权衡。随着质数数量增加，在固定模数大小下，每个素数因子变小，这会使得使用ECM（椭圆曲线法）进行分解会变得更容易。

破解多素数RSA

• 当模数的分解已知时，我们就认为一个多素数RSA实例被破解了。对于传统RSA，恢复私钥指数d或计算$\phi(N)$就足够了，因为存在确定性（多项式时间）算法可以在已知其中之一的情况下分解模数。

• 对于多素数RSA，目前没有已知的等价结果。也就是说，没有已知的确定性算法可以在已知私钥指数或$\phi(N)$的情况下分解模数。然而，一旦已知$\phi(N)$的某个倍数，就可以利用Miller的结果以概率方式分解模数。由于$ed-1=k\phi(N)$，因此，只要获得私钥指数$d$，就足以以概率方式分解模数。