RSA的共解密指数攻击

本文总结了一个基于格的攻击，该攻击针对的是多个共用同一个私钥的RSA实例。当私钥$\,d\,$满足一定条件时，即可根据这些RSA实例的公钥求出$\,d\,$，从而将这些RSA实例全部破解。

理解本文所需的前置背景：

格论，可以先看看格基规约算法：数学基础
格基规约算法的用途，见格基规约算法：算法详解

攻击描述

符号约定和假设

首先我们给出攻击中的假设条件和符号约定。设同一个RSA加密系统中有$\,r\,$个RSA实例共用同一个私钥$\,d\,$，这些实例的公钥分别为$\, \left(e_1,\ N_1\right),\ldots,\left(e_r,\ N_r\right)\,$ 。不妨设$\,N_1,\ldots,\ N_r\,$依次增大，并且由于是同一个系统中的实例，故认为$\, N_1,\ldots,\ N_r\,$具有相同的比特长度，于是有$\,N_1<N_2<\cdots<N_r<2N_1\,$。

由RSA加密的原理可以得到如下$\,r\,$个方程：

$\begin{array}{c} e_{1} d=1+k_{1} \varphi\left(N_{1}\right) \\ e_{2} d=1+k_{2} \varphi\left(N_{2}\right) \\ \vdots \\ e_{r} d=1+k_{r} \varphi\left(N_{r}\right) \end{array}$

对任意的$\,i\,$，设$\, e_i<\varphi\left(N_i\right)\ ,\ \ \varphi\left(N_r\right)=N_i-s_i\,$.我们假定生成$\, N_1,\ldots,\ N_r\,$ 的素数具有相同的比特长度，则${\, s}_{i\ }<3N_1^{1/2}\,$ 。并且最关键的，假设以下命题成立：若$\, v\,$是格$\, \mathcal{L}\,$中满足Minkowski’s bound的一个向量，则$\, \pm v\,$为格中所有的非零最短向量，除此以外没有其他向量范数为$\,\lambda_{1}\!\left(\mathcal{L}\right)\,$ 。

攻击原理和方法

设$\, M=\left\lfloor N_r^{1/2}\right\rfloor\,$ ，由之前假设中的等式可得方程组

$\begin{array}{c} d M=d M \\ e_{1} d-N_{1} k_{1}=1-k_{1} s_{1} \\ e_{2} d-N_{2} k_{2}=1-k_{2} s_{2} \\ \vdots \\ e_{r}-N_{r} k_{r}=1-k_{r} s_{r} \end{array}$

下面将方程组写为矩阵形式。记

$\, x_r=\left(d,k_1,k_2,\cdots,k_r\right)\ ,v_r=\left(dM,1-k_1s_1,\cdots,1-k_rs_r\right)$ $\mathcal{B}_{r}=\left[\begin{array}{ccccc} M & e_{1} & e_{2} & \cdots & e_{r} \\ 0 & -N_{1} & 0 & \cdots & 0 \\ 0 & 0 & -N_{2} & \cdots & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & 0 & \cdots & -N_{r} \end{array}\right]$

则有$\, x_r\mathcal{B}_r=v_r\,$。注意到$\, \mathcal{B}_r\,$的行向量组生成了一个$\, r+1\,$维的格$\, \mathcal{L}\,$，而$\, v_r\in\mathcal{L}\,$。那么由假设可知，当不等式$\left|v_{r}\right| < \sqrt{r+1} \det(\mathcal{L})^{1 /(r+1)}$ 成立时（即满足Minkowski’s bound时），攻击者只要解出格$\, \mathcal{L}\,$上的SVP问题即可解出$\, v_r\,$，从而得到$\, v_r\,$第一个分量$\, dM\,$。$\,M\,$已知，因此攻击者可求出$\, d\,$，从而攻破这些共解密指数实例。

攻击条件

经过一些简单的不等式推导可得，当$\, d<N_r^{\delta_r}\,$且$\, \delta_r<\frac{1}{2}-\frac{1}{2(r+2)}-\log_{N_r}6\,$时，不等式$\,\left|v_{r}\right| < \sqrt{r+1} \det(\mathcal{L})^{1 /(r+1)}\,$ 一定能成立。因此$\, d<N_r^{\delta_r}\,$且$\, \delta_r<\frac{1}{2}-\frac{1}{2(r+2)}-\log_{N_r}6\,$就是在先前提出的假设成立时，攻击一定能成功的条件（具体推导请查阅参考资料，查找关键词common private）。

攻击的提出者Hinek在对RSA-2048/4096进行实验时发现要想保证攻击一定成功，实际的$\,\delta_r\,$要比满足前面这个不等式的$\,\delta_r\,$最大值小一点（大概小0.005左右）。

共用私钥的RSA实例个数$\,r\,$越大，攻击效果越好。Hinek进行了全面的攻击实验，当设定$\,r=35\,$，当$\, d<N^{0.485}\,$，数万次攻击基本全部成功。更详细的实验结果请查阅文末的参考资料。

攻击代码

以下代码在sagemath 9.1上运行。

攻击算法

当攻击成功时会计算并打印出正确的私钥$\,d\,$，当攻击失败时计算出的$\,d\,$是错误的。

"""
	instance: 共私钥的RSA实例，为一个列表。该列表的每一项都是字典，instance[i]['e']为第i个RSA实例的e，instance[i]['n']为第i个RSA实例的n。
"""
def common_private_attack(instance, debug=False, algo="LLL"):
    r = len(instance)
    instance.sort(key=lambda x: x['n'])
    M = isqrt(instance[r-1]['n'])  
    
    # Build up Lattice basis B
    B = zero_matrix(r+1)
    B[0,0] = isqrt(instance[r-1]['n'])
    for i in range(1, r+1):
        B[0,i] = instance[i-1]['e']
        B[i,i] = - instance[i-1]['n']
    if debug:
        print("The basis of the lattice we build is:"); print(B)
    
    if algo == "LLL":
        print("Performing LLL reduction..."); B = B.LLL(); print("Done.")
    elif algo == "BKZ":
        print("Performing BKZ reduction..."); B = B.BKZ(block_size=len(instance)); print("Done.")
    
    dM = B[0,0]; d = dM // M;
    # 有时会算出负数
    d = abs(d)
    print(" dM = {} \n d = {}".format(dM, d))

    if dM % d != 0:
        print("Fail to attack these instances.")

测试代码

调用以下方法即可生成满足攻击条件的RSA实例。

from Crypto.Util.number import getStrongPrime, getPrime, getRandomNBitInteger
from gmpy2 import gcd, invert
from math import floor, log

# Generate r instances of RSA with the same d.
def gen_instance(r=2, bit_len=2048, delta_r=None,delta=0, debug=False):
    
    if delta_r is None:
        delta_r = 0.5 -  0.5 / (r+1) - log(6, 2^bit_len) + delta
    #     d = getRandomNBitInteger(int(2 * bit_len * delta_r))
    d = getPrime(floor(bit_len * delta_r))

    if d & 1 == 0:
        d += 1
    print("The d we choose is: {}".format(d))
    print("d satisfy the condition: d < Nr^{}".format(delta_r))
    print("\n")
    
    print("Generating instances ...")
    instance = []
    
    for i in range(r):
        while True:
            p = getStrongPrime(bit_len//2)
            q = getStrongPrime(bit_len//2)
#             p = getPrime(bit_len)
#             q = getPrime(bit_len)
            n = p * q
            phi = (p-1)*(q-1)
            if gcd(d, phi) == 1:
                e = invert(d, phi)
                this = {'n':n, 'e':e, 'd':d}
                instance.append(this)
            
                break
  
    print("Done.")
    
    if debug:
        print("The RSA Instances we choose is below:")
        for i in range(r):
            print("instance {}: {}".format(i, instance[i]))
    return instance

参考资料

M. Jason Hinek. On the Security of Some Variants of RSA. 2007.
M. Jason Hinek. Cryptanalysis of RSA and Its Variants. 2009