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

原文链接：https://blog.csdn.net/qq_42667481/article/details/118344564