基于参数优化拟合和二分搜索的CRT-RSA小d_q实际攻击方法

Practical Attack Method on Small{\mathit{d}}_{\mathit{q}}CRT-RSA Based on Parameter Optimization, Fitting and Binary Search

摘要

针对当前缺乏系统的方法来有效指导CRT-RSA小d_q实际攻击的问题，提出一种基于参数优化拟合和二分搜索的CRT-RSA小d_q实际攻击方法。首先对小d_q攻击参数{\tau }_p\mathrm{、}{\tau }_q进行优化，基于优化的{\tau }_p\mathrm{、}{\tau }_q值和约化格基长度的实验统计，给出一种基于参数拟合的可攻击上界的估计方法，其估计结果与实验结果吻合；在该方法的指导下，对给定参数条件下的小d_q实际攻击上界进行探索；随后加入之前RSA小解密指数实际攻击探索时所提的模数素因子的高比特猜测策略，基于实验中的“多值现象”，提出适合并行实现的二分搜索攻击方法，该方法能有效提升给定参数下小d_q实际可攻击的上界。此外，对Takayasu等的格进行优化，并对其提出的helpful多项式在实际攻击中的效果进行探索，可为后续CRT-RSA的小d_q攻击研究带来启发和帮助。

Abstract

To address the absence of a systematic method for effectively guiding practical attacks on small d_q CRT-RSA, a practical attack method based on parameter optimization, fitting and binary search is proposed. Initially, the parameters {\tau }_p and {\tau }_q in the small d_q attack are optimized. Subsequently, guided by the optimized values of {\tau }_p and {\tau }_q, along with experimental statistics on the length of the reduced lattice basis, an estimation method for an attackable upper bound is proposed through parameter fitting, which aligns with experimental results. Guided by the method, the attackable upper bound of small d_q given the parameters is explored. Furthermore, the most significant bits (MSBs) guess strategy for the prime factor of the modulus, which is proposed in previous explorations of practical attacks on small RSA decryption exponents, is introduced. Based on the “multivalued phenomenon” observed in experiments, a binary search attack method suitable for parallel implementation is proposed, effectively enhancing the upper bound of practical attacks on small d_q under the given parameters. Additionally, the lattice proposed by Takayasu et al. is optimized, and the performance of helpful polynomials in practical attacks is explored. The practical attack exploration presented here can offer inspiration and assistance for the future research on small d_q attacks against CRT-RSA.

关键词

CRT-RSA体制 / 小

d_q

攻击 / 高比特猜测 / 多值现象 / 二分搜索

Key words

CRT-RSA / small

d_q

attack / MSBs guess / multivalued phenomenon / binary search

RSA^[1]是Rivest等基于大整数分解困难问题设计的公钥密码算法，也是首个实用的公钥密码算法，广泛应用于网络通信和数据加密中。自提出以来，有关RSA的密码分析一直是密码学领域研究的热点。RSA通过公钥和私钥分别实现数据的加密和解密，其中的加解密运算均由模指数运算来实现。当解密指数d适当大时（如d\approx N，其中N为RSA模数），该运算即使使用快速算法（如蒙哥马利模乘算法）仍然不够高效。与AES（Advanced Encryption Standard）等对称密码相比，其实现的效率远远落后。

为了提高解密效率，人们曾提出使用小的解密指数d。然而，研究人员很快发现，当d很小时，RSA是不安全的。Wiener^[2]利用连分数方法指出，当时，RSA可被完全攻破（即求出解密指数d或给出N的分解，二者被证明是等价的^[3-5]）。Boneh等^[6]利用CopperSmith格方法^[7]将Wiener的结果改进为，这也是当前RSA小解密指数攻击的最好结果。这一结果意味着，通过选择小的d（）来加速解密是不可行的。

在上述背景下，CRT-RSA（Chinese Remainder Theorem RSA）^[8]迅速成为RSA研究的焦点。CRT-RSA是RSA的一类变种，它不再直接使用RSA私钥d进行解密，而是利用CRT-指数d_p\equiv d\mathrm{m}\mathrm{o}\mathrm{d}\left(p-\mathrm{1}\right)和d_q\equiv d\mathrm{m}\mathrm{o}\mathrm{d}\left(q-\mathrm{1}\right)，分别计算模p和模q下的解密结果（其中N=pq），再通过中国剩余定理（CRT）得到明文。当d_p\mathrm{、}{d}_q很小时，通过中国剩余定理得到的d一般很大（d的规模接近于N）。因此，CRT-RSA可以在提高解密效率的同时，还能有效规避RSA的小解密指数攻击，能够很好地平衡效率和安全性。

然而，在发现针对小d的攻击方法不适用于CRT-RSA后，研究人员把目光聚焦到CRT-指数d_p和d_q，先后提出了CRT-RSA的小d_q攻击和小d_p\mathrm{、}{d}_q攻击。本文主要关注CRT-RSA的小d_q攻击。有关小d_p\mathrm{、}{d}_q攻击的研究成果，见文献[9-18]。

May^[16]首次给出CRT-RSA的小d_q攻击方法，先给出一种模q的CopperSmith格攻击方法，该方法能够在的条件下完全攻破CRT-RSA，其中。随后，他又给出了一种模e（e为加密指数）的攻击方法，该方法在时能够攻破CRT-RSA。尽管后一种方法只在时才有效，但在时，后者能够攻击更大的d_q。Bleichenbacher等^[10]在May的模e攻击基础上，通过引入新变量进行优化，将可攻击的条件提升至。文献[19]和文献[10]的攻击都只能在N的素因子不平衡的情况下实施。Takayasu等^[14]在文献[10]基础上提出了一种改进的小d_q攻击，该攻击能够在\frac{\left(\mathrm{1}-\beta \right)\left(\mathrm{3}+\mathrm{2}\beta \right)-\mathrm{2}\sqrt[]{\beta \left(\mathrm{1}-\beta \right)\left(\alpha \beta +\mathrm{3}\alpha +\beta \right)}}{\mathrm{3}+\beta }的情况下完全攻破CRT-RSA，其中e=N^{\alpha }且满足\alpha >\beta /(\mathrm{1}-\beta )。该攻击在时有效，攻击范围可覆盖到平衡情形。

需要注意的是，上述的结论都是理论结果，即CopperSmith参数m趋于无穷时得到的渐近结果，此时格的维数为无穷大。在实际攻击中，随着格的维数增加，格基约化算法如LLL算法^[20]的约化效率和质量都不断下降，因此，实际攻击中往往很难达到理论攻击界。实际攻击中，对于小d_q攻击的现状文献[10]展示了大量实验，其结果显示，对模数为1 000 bit，\beta分别取\mathrm{0.305}、\mathrm{0.355}、\mathrm{0.405}、\mathrm{0.440}的CRT-RSA，当参数m=\mathrm{6}时，实际攻击中能够成功攻击的\delta值分别为\mathrm{0.016}、\mathrm{0.100}、\mathrm{0.050}、\mathrm{0.010}。针对同样的模数规模和\beta，文献[14]中给出了更好的结果：相比文献[10]，其在格维数相当的情况下，可成功攻击到的\delta值更大（对应分别为\mathrm{0.170}、\mathrm{0.100}、\mathrm{0.054}、\mathrm{0.012}）。注意到，文献[10]和文献[14]中的实验均考虑e\approx N（即\alpha =\mathrm{1}）的情形。为了更好的对比，本文后续章节的讨论同样考虑\alpha =\mathrm{1}的情形。

本文对CRT-RSA的小d_q实际攻击进行探索。从前文介绍可知，尽管有多名学者已经给出了小d_q攻击的多个实验结果，但这些结果与理论界仍有很大的差距。在实际攻击中，需要确定合适的参数，如何给出一个与实验结果适配度高的可攻击上界估计。同时，由于约化算法的效率和质量会随着格的维数增加不断下降，如何在格的维数不明显增加的情况下，给出更好的实际攻击结果，也是非常值得探索的问题。具体地，本文工作如下。1）文献[14]中所给出的参数{\tau }_p\mathrm{、}{\tau }_q的优化值{\tau }_p=(\mathrm{1}-\mathrm{2}\beta -\delta )/(\mathrm{2}\beta )\mathrm{、}{\tau }_q=(\mathrm{1}-\beta -\delta )/(\mathrm{1}-\beta )是在参数m趋于无穷时的理论最优值，而实际攻击中往往不够优化。基于此，在给定参数m和模数规模的条件下，对文献[14]中小d_q攻击的参数{\tau }_p\mathrm{、}{\tau }_q进行优化并给出相应的优化值。2）针对当前缺乏关于文献[14]中小d_q可攻击上界的有效估计方法，结合{\tau }_p\mathrm{、}{\tau }_q的优化值，利用实验统计和参数拟合，在给定参数条件下，给出了一种小d_q实际可攻击上界的估计方法，实验验证了该估计的有效性。3）基于文献[14]中的小d_q攻击方法，探索给定参数下小d_q实际可攻击的上界，并且通过加入猜测p的高比特的策略，利用“多值现象”设计了适合并行实现的二分搜索算法，从而能够有效实现d_q更大时的小d_q攻击。4）先利用helpful多项式理论对文献[14]中的格进行优化；随后，实验发现helpful多项式理论尽管在理论分析中有很好的指导作用，但在实际攻击中并不完全适用；最后通过理论分析和实验给出实际攻击中格构造的优化方法。

1 预备知识

1.1 CRT-RSA

在RSA中，加密指数e和解密指数d满足ed\equiv \mathrm{1}\mathrm{m}\mathrm{o}\mathrm{d}\phi (N)，其中\phi (N)为模数N的欧拉函数。记m\mathrm{、}c分别为明文和密文，加密和解密运算为c=m^e\mathrm{m}\mathrm{o}\mathrm{d}N和m=c^d\mathrm{m}\mathrm{o}\mathrm{d}N。当d适当大时，解密运算效率很低。利用中国剩余定理，CRT-RSA能够快速计算c^d\mathrm{m}\mathrm{o}\mathrm{d}N。在解密时，CRT-RSA不再直接使用d，而是使用CRT指数d_p\mathrm{、}{d}_q，其中d_p\mathrm{、}{d}_q满足e{d}_p\equiv \mathrm{1}\mathrm{m}\mathrm{o}\mathrm{d}\left(p-\mathrm{1}\right),e{d}_q\equiv \mathrm{1}\mathrm{m}\mathrm{o}\mathrm{d}\left(q-\mathrm{1}\right)。

具体解密过程如下：1）预计算T=p^{-\mathrm{1}}\mathrm{m}\mathrm{o}\mathrm{d}q；2）计算m_p=c^{d_p}\mathrm{m}\mathrm{o}\mathrm{d}p,m_q=c^{d_q}\mathrm{m}\mathrm{o}\mathrm{d}q；3）计算明文：m=p{\left[\left(m_q-m_p\right)T\right]}_{\mathrm{m}\mathrm{o}\mathrm{d}q}+m_p，其中{\left[A\right]}_{\mathrm{m}\mathrm{o}\mathrm{d}q}表示A模q的非负最小剩余。

利用上述计算，CRT-RSA的解密运算效率约为普通RSA的4倍^{[4, 21]}。考虑到在CRT-RSA的设计中，d_p和d_q可以适当选择较小的值，解密效率的提升将更加显著。高效的解密使得CRT-RSA 成为当前最实用的RSA变种。

1.2 格理论与LLL算法

设{\mathit{u}}_{\mathrm{1}},\dots ,{\mathit{u}}_w\in {\mathbf{ℝ}}^n是w个线性无关的向量，其中w\le n。由{\mathit{u}}_{\mathrm{1}},\dots ,{\mathit{u}}_w的所有整系数线性组合构成的集合称为由{\mathit{u}}_{\mathrm{1}},\dots ,{\mathit{u}}_w张成的n维格，即：

\mathit{L}=\left\{{\displaystyle \sum _{i=\mathrm{1}}^w}{k}_i{\mathit{u}}_{\mathit{i}}|k_{\mathrm{1}},\dots ,k_w\in \mathbb{Z}\right\}\mathrm{。}

向量组{\mathit{u}}_{\mathrm{1}},\dots ,{\mathit{u}}_w称为格\mathit{L}的一组基，w和n分别称为格\mathit{L}的秩和维数。格\mathit{L}称为满秩的，当且仅当w=n。设\mathit{U}为由行向量{\mathit{u}}_{\mathrm{1}},\dots ,{\mathit{u}}_w构成的w\times n阶矩阵，则\mathrm{d}\mathrm{e}\mathrm{t}\mathit{L}=\sqrt[]{\mathrm{d}\mathrm{e}\mathrm{t}(\mathit{U}{\mathit{U}}^{\mathbf{T}})}称为格L的行列式，其中{\mathit{U}}^{\mathbf{T}}表示矩阵\mathit{U}的转置。格中最受关注的困难问题之一是最短向量问题（Shortest Vector Problem, SVP），即给定格\mathit{L}，寻找一个非零格向量\mathit{v}，满足对任意非零格向量\mathit{u}\in \mathit{L}, 都有‖\mathit{v}‖\le ‖\mathit{u}‖，其中 ‖\cdot ‖表示欧几里得范数。求解SVP是困难的，但在许多密码分析中，往往相对较短的非零格向量即可满足需求。著名的格基约化算法LLL^[20]可以在多项式时间内有效找到一组相对较短且接近垂直的格基。其输出格基质量可由下面的引理保证。

引理1^[20] 设\mathit{L}是一个w维的满秩格，{\tilde{\mathit{v}}}_{\mathrm{1}},\dots ,{\tilde{\mathit{v}}}_w为LLL算法约化输出的\mathit{L}的一组格基，则：

‖{\tilde{\mathit{v}}}_{\mathit{i}}‖\le {\mathrm{2}}^{\frac{w\left(w-\mathrm{1}\right)}{\mathrm{4}\left(w+\mathrm{1}-i\right)}}{\left(\mathrm{d}\mathrm{e}\mathrm{t}\mathit{L}\right)}^{\frac{\mathrm{1}}{w+\mathrm{1}-i}},\mathrm{1}\le i\le w\mathrm{。}

由引理1给出的约化输出格基长度的上界比较粗糙。为了给出更精确的估计，基于实验方法，Nguyen等^[22]给出了LLL输出格基中第一个向量长度的近似值\mathrm{1}.{\mathrm{02}}^w{\left(\mathrm{d}\mathrm{e}\mathrm{t}\mathit{L}\right)}^{\frac{\mathrm{1}}{w}}，其中w为格\mathit{L}的维数。在中等维数的随机格中，该值一般能很好地近似格中最短向量。但该值在非随机格中并不具有普适性。本文尝试基于该值给出小d_q实际攻击上界的估计，但与实验结果偏差较大。在第3.2节本文重新考量文献[14]中所给格的输出格基质量。

1.3 CopperSmith方法

设‖h(x_{\mathrm{1}},\dots ,x_r)‖表示多项式h(x_{\mathrm{1}},\dots ,x_r)的系数向量的欧几里得范数。考虑模方程h\left(x_{\mathrm{1}},\dots ,x_r\right)\equiv

\mathrm{0}(\mathrm{m}\mathrm{o}\mathrm{d}M)，其目标解{\tilde{x}}_{\mathrm{1}},\dots ,{\tilde{x}}_r满足

\left|{\tilde{x}}_i\right|\le X_i,i=\mathrm{1},\dots ,r（1）

CopperSmith^[7]提出了一种求上述模方程小根的算法，只要{\displaystyle \prod _{i=\mathrm{1}}^r}{X}_i\le M，该算法可在多项式时间内找到所有满足式（1）的解。随后，Howgrave-Graham^[23]给出了一种更容易理解的表述方式，具体如下。

引理2^[23] 设m,M,X₁,…，X_r 为正整数，g\left(x_{\mathrm{1}},\dots ,x_r\right)\in

\mathbb{Z}，[x_{\mathrm{1}},\dots ,x_r]是一个至多n项的多项式，其范数为‖g\left(x_{\mathrm{1}},\dots ,x_r\right)‖。若：1）g\left({\tilde{x}}_{\mathrm{1}},\dots ,{\tilde{x}}_r\right)\equiv \mathrm{0}\left(\mathrm{m}\mathrm{o}\mathrm{d}{M}^m\right)，其中，2）‖g\sqrt[]{n}，则g\left({\tilde{x}}_{\mathrm{1}},\dots ,{\tilde{x}}_r\right)=\mathrm{0}在\mathbb{Z}上成立。

从引理2的条件2）可以看出，为了实现脱模，需要找到范数较小的多项式。由于多项式与其系数向量存在一一对应关系，寻找范数较小的多项式就转化为寻找格中长度较短的非零向量，该目标可由LLL算法实现。找到符合引理2条件的多项式，即可求得多项式的公共根。而求解多项式公共根，需要这些多项式代数独立。这里，称多项式f_{\mathrm{1}},f_{\mathrm{2}},\dots ,f_m\in k[x_{\mathrm{1}},x_{\mathrm{2}},\dots ,x_n]在域k上代数独立，如果不存在域k上m元多项式\Phi \in k\left[y_{\mathrm{1}},y_{\mathrm{2}},\dots ,y_m\right]，使得\Phi (f_{\mathrm{1}},f_{\mathrm{2}},\dots ,f_m)=\mathrm{0}。利用CopperSmith方法得到的多项式是否代数独立，目前仍是一个公开的问题，使用时一般认可并采用下面的假设。

假设1 通过LLL算法得到的多项式是代数独立的，其公共根可通过计算结式或求Gröbner基得到。CopperSmith方法在RSA的分析中有着广泛的应用，并已取得丰硕的成果。该方法构造格的优化原则之一就是尽可能多地使用helpful多项式，尽可能少地使用unhelpful多项式。helpful多项式的概念是文献[24]在文献[25]的helpful向量概念基础上提出的：设f、M为CopperSmith方法构造格使用的多项式和模数，格对角线上与f对应的元素为a。如果，则f称为helpful多项式；反之，则称为unhelpful多项式。

helpful多项式的最大化使用和unhelpful多项式的最小化使用，是基于CopperSmith方法的格密码分析和优化的核心。本文将在第3.4节探讨该定义在实际攻击中的适用性。

2 文献[14]的小d_q攻击

由e{d}_q\equiv \mathrm{1}\mathrm{m}\mathrm{o}\mathrm{d}\left(q–\mathrm{1}\right)知，存在整数k，使得：

e{d}_q=\mathrm{1}+k_q\left(q-\mathrm{1}\right)（2）

式（2）两边乘以p可得：

e{d}_{q}p=p+k_q\left(N-p\right)=\left(k_q-\mathrm{1}\right)\left(N-p\right)+N（3）

设e=N^{\alpha },p=N^{\beta },d_q\le N^{\delta }，则：

k_q=\frac{e{d}_q-\mathrm{1}}{q-\mathrm{1}}\approx N^{\alpha +\delta +\beta -\mathrm{1}}=N^{\delta +\beta }\mathrm{。}

CRT-RSA的小d_q攻击以式（2）和式（3）为基础展开。如无特别说明，本文后续章节中的符号均与本节相同。

令f_p\left(x_p,y_p\right)=x_p\left(N-y_p\right)+N。由式（3）知，\left(x_p,y_p\right)=(k_q-\mathrm{1},p)是模方程f_p\left(x_p,y_p\right)=x_p\left(N-y_p\right)+N\equiv \mathrm{0}\mathrm{m}\mathrm{o}\mathrm{d}e的一个解，其中。以f_p(x_p,y_p)为基础，May^[19]基于CopperSmith方法使用如下的shift多项式构造格：

\left\{\begin{array}{c}{g}_{i,k}\left(x_p,y_p\right):=x_p^i{f}_p^k(x_p,y_p)e^{m-k};\\ h_{j,k}(x_p,y_p):=y_p^j{f}_p^k(x_p,y_p)e^{m-k}\mathrm{。}\end{array}\right.

其中：t是一个待优化的参数；\mathrm{0}\le k\le m,\mathrm{1}\le j\le t；\mathrm{0}\le i+k\le m。

文献[10]发现文献[19]攻击所构造的格中对角线上出现大量的Y，这意味着很多出现在格对角线上的项中含有y_p（即p），利用这一发现，他们引入了一个代表q的新变量y_q，利用如下的shift多项式构造格：

\left\{\begin{array}{c}{g}_{i,k}\left(x_p,y_p,y_q\right):=x_p^i{y}_q^s{f}_p^k\left(x_p,y_p\right)e^{m-k},\mathrm{0}\le k\le m,\mathrm{0}\le i\le m-k;\\ h_{j,k}\left(x_p,y_p,y_q\right):=y_p^j{y}_q^s{f}_p^k\left(x_p,y_p\right)e^{m-k},\mathrm{0}\le k\le m,\mathrm{1}\le j\le t\mathrm{。}\end{array}\right.

其中，s和t是待优化的参数。

利用关系式y_p{y}_q=N，对角线上的y_p与y_q结合为N，使得出现在对角线上的y_p数量大大减少，而增加的N可以通过在相应行乘以N^{-\mathrm{1}}\mathrm{m}\mathrm{o}\mathrm{d}e消去。这样的改动使得在维数不变的情况下，格的行列式绝对值明显减小。

Takayasu等对比分析了文献[10]和文献[19]构造的格，发现文献[10]使用的shift多项式可以进一步简化：令f_q\left(x_q,y_q\right)=\mathrm{1}+x_q\left(y_q-\mathrm{1}\right)，则由式（2）可知，\left(x_q,y_q\right)=\left(k_q,q\right)是f_q\left(x_q,y_q\right)\equiv \mathrm{0}\mathrm{m}\mathrm{o}\mathrm{d}e的一个解。此时，文献[10]中的一些多项式可以由f_q\left(x_q,y_q\right)更简洁地表示。例如，N^{-\mathrm{1}}{y}_q{f}_p\left(x_p,y_p\right)就是f_q\left(x_q,y_q\right)。基于此，他们构造如下的shift多项式：

\left\{\begin{array}{c}{g}_{i,k}\left(x_p,y_p\right)=x_p^i{f}_p^k\left(x_p,y_p\right)e^{m-k};\\ g_{i,k}^{\text{'}}\left(x_p,y_p\right)=y_p^i{f}_p^k\left(x_p,y_p\right)e^{m-k};\\ g_{i,k}^{″}\left(x_p,y_p,x_q,y_q\right)=f_p^{k-i}\left(x_p,y_p\right)f_q^i\left(x_p,y_p\right)e^{m-k}\mathrm{。}\end{array}\right.

其对应的指标集分别为

\left\{\begin{array}{c}{I}_x=\left\{k=\mathrm{0},\dots ,m;i=\mathrm{0},\dots ,m-k\right\};\\ I_{y,p}=\left\{k=\mathrm{0},\dots ,m;i=\mathrm{1},\dots ,⌈{\tau }_{p}m⌉\right\};\\ I_{y,q}=\left\{k=\mathrm{1},\dots ,m;i=\mathrm{1},\dots ,⌈{\tau }_{q}k⌉\right\}\mathrm{。}\end{array}\right.

其中，{\tau }_p\ge \mathrm{0}、\mathrm{0}\le {\tau }_q\le \mathrm{1}是两个待优化的参数。

由于\left(x_p,x_q,y_p,y_q\right)=\left(k_q-\mathrm{1},k_q,p,q\right)是f_q\left(x_q,y_q\right)\equiv

\mathrm{0}\mathrm{m}\mathrm{o}\mathrm{d}e,f_p\left(x_p,y_p\right)\equiv \mathrm{0}\mathrm{m}\mathrm{o}\mathrm{d}e的目标解，因此有：

x_q=x_p+\mathrm{1},y_p{y}_q=N（4）

利用式（4）进行变量替换，使得g_{i,k}\left(x_p,y_p\right),g_{i,k}^{\text{'}}

\left(x_p,y_p\right)和g_{i,k}^{″}\left(x_p,y_p,x_q,y_q\right)的展开式中仅含有形如x_p^{i_{px}}{y}_p^{i_{py}}和x_q^{i_{qx}}{y}_q^{i_{qy}}的项，其中，i_{px}、i_{py}、i_{qx}、i_{qy}是非负整数。上述替换既能有效降低格的维数，又能通过乘以N^{-\mathrm{1}}\mathrm{m}\mathrm{o}\mathrm{d}e来降低格的行列式，提升攻击效果。具体地，根据引理2，结合x_p,x_q\le X=N^{\beta +\delta },y_p\le Y_p=N^{\beta },y_q\le Y_q=N^{\mathrm{1}-\beta }可以得到：

要满足{\tau }_p\ge \mathrm{0}，则须\alpha >\beta /(\mathrm{1}-\beta )，见文献[14]。

3 所提小d_q实际攻击

文献[14]的小d_q攻击是在文献[10]和文献[19]的基础上改进得到的，攻击的理论效果最好，因此本文的实际攻击以Takayasu等的攻击为基础展开。为了更好地与文献[14]作对比，本文将对同样的情形（\beta =\mathrm{0.305},\mathrm{0.355},\mathrm{0.405},\mathrm{0.440}）实施小d_q攻击。本文中的小d_q攻击以第2节攻击算法为基础开展探索，设n_N表示N的比特数，并取\alpha =\mathrm{1}。

3.1 {\tau }_p\mathrm{、}{\tau }_q的优化

为了更好地探索小d_q攻击的攻击上界，寻找实际攻击中{\tau }_p、{\tau }_q的最优值至关重要。文献[14]中给出的{\tau }_p、{\tau }_q优化值是在粗略估计理论上界时获得的，在实际攻击中未必最优。因此，在实施实际攻击前先对{\tau }_p\mathrm{、}{\tau }_q进行优化。设\mathrm{d}\mathrm{e}\mathrm{t}\mathit{L}=X^{s_X}{Y}_p^{s_{Y_p}}{Y}_q^{s_{Y_q}}{e}^{s_e}，依据引理2简化形式可以得到：

（5）

这里，s_X\mathrm{、}{s}_{Y_p}\mathrm{、}{s}_{Y_q}\mathrm{、}{s}_e\mathrm{、}\mathrm{d}\mathrm{i}\mathrm{m}\mathit{L}近似值如下：

\left\{\begin{array}{c}{s}_X\approx \frac{\mathrm{1}}{\mathrm{6}}m\left(m+\mathrm{1}\right)\left(\mathrm{2}m+\mathrm{4}+\mathrm{3}{\tau }_{p}m+{\tau }_q\left(\mathrm{2}m+\mathrm{1}\right)\right);\\ s_{Y_p}\approx \frac{\mathrm{1}}{\mathrm{6}}m\left(m+\mathrm{1}\right)\left(m+\mathrm{2}+\mathrm{3}{\tau }_p\left(m+{\tau }_{p}m+\mathrm{1}\right)\right);\\ s_{Y_q}\approx \frac{\mathrm{1}}{\mathrm{12}}{\tau }_q^{\mathrm{2}}m\left(m+\mathrm{1}\right)\left(\mathrm{2}m+\mathrm{1}\right)+\frac{\mathrm{1}}{\mathrm{4}}{\tau }_{q}m\left(m+\mathrm{1}\right);\\ s_e\approx \frac{\mathrm{1}}{\mathrm{6}}m\left(m+\mathrm{1}\right)\left(\mathrm{2}m+\mathrm{4}+\mathrm{3}{\tau }_{p}m+{\tau }_q\left(m-\mathrm{1}\right)\right);\\ \mathrm{d}\mathrm{i}\mathrm{m}\mathit{L}\approx \frac{\mathrm{1}}{\mathrm{2}}({\tau }_q+\mathrm{2}{\tau }_p+\mathrm{1})m\left(m+\mathrm{1}\right)+m+\mathrm{1}\mathrm{。}\end{array}\right.

尽管上述结果仍不是精确值，但计算结果保留了所有m的低次项，与真实值的近似程度大大提升。由式（5）可得：

记：f\left({\tau }_p,{\tau }_q\right)=\left(m\mathrm{d}\mathrm{i}\mathrm{m}\mathit{L}-\beta s_X-\beta s_{Y_p}-\left(\mathrm{1}-\beta \right)s_{Y_q}-s_e\right)/s_X，

则通过求解\left\{\begin{array}{c}{f}_{{\tau }_p}\left({\tau }_p,{\tau }_q\right)=\mathrm{0}\\ f_{{\tau }_q}\left({\tau }_p,{\tau }_q\right)=\mathrm{0}\end{array}\right.即可得到{\tau }_p、{\tau }_q的优化值，其中f_{{\tau }_p}、f_{{\tau }_q}表示f对{\tau }_p、{\tau }_q的偏导。不难看出，{\tau }_p、{\tau }_q的优化值与\beta和m有关，且获取{\tau }_p和{\tau }_q最优值与m的解析关系式比较困难，因此本文给出最优值与\beta、m之间的离散对应表，并以\beta =\mathrm{0.305}为例展示，如表1所示。

注意到，表1中的{\tau }_p、{\tau }_q最优值与文献[14]中有着不小的偏差。以m=\mathrm{6}为例：当m=\mathrm{6}、攻击目标为\delta =\mathrm{0.176}时，文献[14]中得到结果为{\tau }_p=\mathrm{0.351},{\tau }_q=\mathrm{0.747}，与表1中{\tau }_p=\mathrm{0.264}、{\tau }_q=\mathrm{0.629}差距较大。实验也验证了表1中参数在实验中的显著效果，部分结果见第4节。

表1对后续的实验探索具有重要的指导意义。在实施实际攻击时，先根据需要选择合适的参数m，之后即可根据表1选择与之对应的{\tau }_p\mathrm{、}{\tau }_q的优化值，从而高效地实施小d_q实际攻击实验。

3.2 给定参数下小d_q实际可攻击上界估计

在实际攻击探索中，首先需要探索给定m和模数时小d_q的实际可攻击上界。如果有一个可靠的估计作为指导，在探索过程中只需要在\delta上界估计值附近上下浮动，即可快速通过实验找到特定参数下的实际可攻击上界，大大避免了穷举式搜索带来的盲目和低效。因此，为了指导实验的参数设置，优化实验的探索过程，需要有一个实际可攻击上界的可靠估计。鉴于未发现已有的关于文献[14]小d_q攻击的估计方法，本文尝试给出一个有效的可攻击上界估计方法。

由于引理1中对LLL算法输出向量长度上界的估计较为粗糙，本文尝试利用文献[22]的实验结果，即\frac{{\lambda }_{\mathrm{1}}\left(\mathit{L}\right)}{{\left(\mathrm{d}\mathrm{e}\mathrm{t}\mathit{L}\right)}^{\frac{\mathrm{1}}{w}}}\approx {\left(\mathrm{1.02}\right)}^w，这里{\lambda }_{\mathrm{1}}(\mathit{L})为格\mathit{L}最短非零向量的长度。为满足引理2的条件2），只需满足：

两边关于N取对数，得：

记N的规模为n_N。利用\mathrm{l}\mathrm{o}{\mathrm{g}}_N\mathrm{1.02}\approx \mathrm{l}\mathrm{o}{\mathrm{g}}_{\mathrm{2}}\mathrm{1.02}/n_N、 \mathrm{l}\mathrm{o}{\mathrm{g}}_{N}w\approx \mathrm{l}\mathrm{o}{\mathrm{g}}_{\mathrm{2}}w/n_N、\mathrm{l}\mathrm{o}{\mathrm{g}}_{N}e\approx\mathrm{1}、\mathrm{l}\mathrm{o}{\mathrm{g}}_N\mathrm{d}\mathrm{e}\mathrm{t}L\approx \left(\delta +\beta \right)s_X+\beta s_{Y_p}+\left(\mathrm{1}-\beta \right)s_{Y_q}+s_e,可得：

（6）

然而，同基于引理1的估计一样，式（6）给出的实际可攻击上界估计与实验偏差仍然很大。例如，当\beta =\mathrm{0.305}、n_N=\mathrm{1}\mathrm{000}、m=\mathrm{5}、{\tau }_p=\mathrm{0.26}、{\tau }_q=\mathrm{0.62}时，基于引理1和式（6）得到的实际可攻击上界估计分别为0.157和0.160，都与实验探索到的实际攻击上界0.167相差很大，其他参数情形类似。这意味着，上述两种估计方法都不适合用来估计文献[14]小d_q攻击的实际可攻击上界。

为了给出与实验结果更吻合的估计，考虑对文献[14]中格的约化输出格基进行分析。由第2节知，尽管该攻击多项式中含4个变量，但变量满足式（4），因此实际求解结式时只需要2个多项式即可。

为便于叙述，称{\left(‖{\tilde{\mathit{v}}}_{\mathrm{2}}‖/{\left(\mathrm{d}\mathrm{e}\mathrm{t}\mathit{L}\right)}^{\frac{\mathrm{1}}{w}}\right)}^{\frac{\mathrm{1}}{w}}为LLL算法约化输出格基中第2个向量{\tilde{\mathit{v}}}_{\mathrm{2}}的长度度量（简称为目标度量）。当m=\mathrm{6}、n_N=\mathrm{1}\mathrm{000}时，目标度量如表2所示，格的维数w=\mathrm{58}。从表2可以看到，目标度量平均值在\mu =\mathrm{0.85}附近，而\mathrm{0}.{\mathrm{85}}^{\mathrm{58}}远远小于\mathrm{1}.{\mathrm{02}}^{\mathrm{58}},导致前述估计与实验结果偏差很大。

由上可知，基于文献[22]给的估计对文献[14]的小d_q攻击并不适用，本文尝试用目标度量来给出可靠的估计。下面以\beta =\mathrm{0.305}、n_N=\mathrm{1}\mathrm{000}、m=\mathrm{6}的参数设定为例给出基于参数拟合的估计方法。

从表2可知，目标度量的平均值是一个与\delta相关的函数。本文考虑对表2中目标度量均值和\delta进行二次多项式拟合，得到拟合关系y=f(x)。用实验拟合函数y代替目标度量，可得：

‖{\tilde{\mathit{v}}}_{\mathrm{2}}‖/{\left(\mathrm{d}\mathrm{e}\mathrm{t}\mathit{L}\right)}^{\frac{\mathrm{1}}{w}}\approx y^w\mathrm{。}

若使约化输出的第2个向量满足引理2的条件2），只需y^w{\left(\mathrm{d}\mathrm{e}\mathrm{t}\mathit{L}\right)}^{\frac{\mathrm{1}}{w}}\le e^m/\sqrt[]{w}。对其两边关于N取对数，得到：

（7）

为了便于估计\delta的上界，需要对\mathrm{l}\mathrm{o}{\mathrm{g}}_{N}y进行近似处理：\mathrm{l}\mathrm{o}{\mathrm{g}}_{N}y\approx \frac{\mathrm{l}\mathrm{o}{\mathrm{g}}_{\mathrm{2}}y}{n_N}=\frac{\mathrm{l}\mathrm{n}y}{n_N\mathrm{l}\mathrm{n}\mathrm{2}}\mathrm{。}

进一步地，取\mathrm{l}\mathrm{n}y在x=\mu处的近似值，得到：

\mathrm{l}\mathrm{o}{\mathrm{g}}_{N}y\approx \frac{\mathrm{l}\mathrm{n}\mu +\left(\frac{y}{\mu }-\mathrm{1}\right)-\frac{\mathrm{1}}{\mathrm{2}}{\left(\frac{y}{\mu }-\mathrm{1}\right)}^{\mathrm{2}}}{n_N\mathrm{l}\mathrm{n}\mathrm{2}}\mathrm{。}

将\mathrm{l}\mathrm{o}{\mathrm{g}}_{N}y以及\mathrm{l}\mathrm{o}{\mathrm{g}}_{N}w\approx \mathrm{l}\mathrm{o}{\mathrm{g}}_{\mathrm{2}}\left(w/n_N\right),\mathrm{l}\mathrm{o}{\mathrm{g}}_{N}e=\mathrm{1},

\mathrm{l}\mathrm{o}{\mathrm{g}}_N\mathrm{d}\mathrm{e}\mathrm{t}\mathit{L}\approx \left(\delta +\beta \right)s_X+\beta s_{Y_p}+\left(\mathrm{1}-\beta \right)s_{Y_q}+s_e代入式（7），可以得到：

\frac{w\mathrm{l}\mathrm{o}{\mathrm{g}}_{\mathrm{2}}w}{\mathrm{2}{n}_N}-\beta s_{Y_p}-\left(\mathrm{1}-\beta \right)s_{Y_q}-s_e)/s_X-\beta \mathrm{。}

注意到，拟合函数中的x即为\delta。

令y=f(x)，则：

(w^{\mathrm{2}}\frac{\mathrm{l}\mathrm{n}\mu +\left(\frac{f\left(x\right)}{\mu }-\mathrm{1}\right)-\frac{\mathrm{1}}{\mathrm{2}}{\left(\frac{f\left(x\right)}{\mu }-\mathrm{1}\right)}^{\mathrm{2}}}{n_N\mathrm{l}\mathrm{n}\mathrm{2}}+\frac{w\mathrm{l}\mathrm{o}{\mathrm{g}}_{\mathrm{2}}w}{\mathrm{2}{n}_N}

（8）

记式（8）左侧为g\left(x\right)，则的解为，即该方法得到的小d_q可攻击上界估计为x_{\mathrm{0}}。具体地，将f\left(x\right)=-\mathrm{17.945}{x}^{\mathrm{2}}+\mathrm{8.015}\mathrm{8}x+\mathrm{0.017}\mathrm{8}、\mu =\mathrm{0.85}、n_N=\mathrm{1}\mathrm{000}代入式（8），即可得到此时的可攻击上界估计。

实验发现，当m值和N的规模不同时，目标度量值差别很大，很难给出一个涵盖各种参数的统一的估计表达式，因此，本文给出不同参数条件下的数值估计，如表3所示。

从表3中可以看出，拟合优度都在0.99以上，拟合曲线的拟合效果很好。这里，拟合优度指拟合曲线对样本值的拟合程度，其值越接近1表示拟合效果越好。本文对估计结果进行了验证，例如m=\mathrm{8}、n_N=\mathrm{1}\mathrm{000}时，估计值为0.188 0；实验中\delta =\mathrm{0.188}的成功率高达90%，而\delta =\mathrm{0.189}的成功率仅为2%。各个参数情形估计与实验验证的详细展示，见第4节表8。

利用同样的方法，给出\beta =\mathrm{0.355}、\mathrm{0.400}、\mathrm{0.440}时的可估计上界估计，如表4所示。

表4中拟合的二次曲线效果同样很好（拟合优度均在0.99以上）。这也意味着，以此为基础进行的实际可攻击上界的估计相当可靠。事实上，当\beta =\mathrm{0.355}、m=\mathrm{6}、n_N=\mathrm{1}\mathrm{000}时，估计值为，而实验中\delta =\mathrm{0.110}的成功率为92%，的成功率仅为9%。这充分验证了本文估计的可靠性。详细结果见第4节表8。

3.3 给定参数下小d_q实际攻击上界探索与改进

根据文献[14]的小d_q攻击方法，结合第3.1节给出的{\tau }_p\mathrm{、}{\tau }_q优化值，本文对模数为1 000 bit和m=\mathrm{6}和m=\mathrm{8}时小d_q可攻击上界进行了探索，结果如表5所示。

从表5可以看到，当\beta =\mathrm{0.305}、n_N=\mathrm{1}\mathrm{000}和\beta =\mathrm{0.355}、n_N=\mathrm{1}\mathrm{000}时，本文中格的维数分别为58、60，与文献[14]中表3中相同参数对应的格维数56、58基本相当，但在优化参数的帮助下，本文得到了比文献[14]中表3更高的攻击上界：本文得到的\delta上界为0.176和0.110，而文献[14]给出的界为0.170和0.100。这一对比体现了本文优化参数的有效性。

为了进一步提升特定参数m下的可攻击上界，与在文献[26]中的RSA小解密指数实际攻击的改进一样，本文尝试加入p的高比特穷举的策略。在给出具体攻击之前，首先给出p、q高比特互推的引理。

引理3^[26] 设N=pq，其中p和q分别为是{\eta }_{\mathrm{1}}、{\eta }_{\mathrm{2}}比特的素数。记p_m、q_m分别为p、q的高s比特对应数值，p_l、q_l分别为p、q的低\left({\eta }_{\mathrm{1}}-s\right)、\left({\eta }_{\mathrm{2}}-s\right)比特对应数值，则有：

\left\{\begin{array}{c}{q}_m=⌊⌊\frac{N}{p_m·{\mathrm{2}}^{{\eta }_{\mathrm{1}}-s}+{\mathrm{2}}^{{\eta }_{\mathrm{1}}-s-\mathrm{1}}}⌋/{\mathrm{2}}^{{\eta }_{\mathrm{1}}-s}⌋+\theta ,\theta \in \{-\mathrm{1},\mathrm{0},\mathrm{1}\};\\ p_m=⌊⌊\frac{N}{q_m·{\mathrm{2}}^{{\eta }_{\mathrm{2}}-s}+{\mathrm{2}}^{{\eta }_{\mathrm{2}}-s-\mathrm{1}}}⌋/{\mathrm{2}}^{{\eta }_{\mathrm{2}}-s}⌋+{\theta }^{\text{'}},\theta \text{'}\in \{-\mathrm{1},\mathrm{0},\mathrm{1}\}\mathrm{。}\end{array}\right.

引理3中p、q的规模不同，使得p_m、q_m计算结果与文献[26]中略有差异，但推导过程与之完全类似，本文不再证明。同文献[26]一样，由于多值现象的存在，p_m、q_m的近似值足以帮助完成攻击。因此，在不影响攻击实验的情况下，本文取\theta ={\theta }^{\text{'}}=\mathrm{0}。下面以p的高比特穷举来展开分析（q的高比特情形类似）。

当p的高s比特已知时，f_p,f_q分别变化为

\left\{\begin{array}{c}{f}_p\left(x_p,y_p^{\text{'}}\right)=N+x_p\left(N-p_m\cdot {\mathrm{2}}^{{\eta }_{\mathrm{1}}-s}-y_p^{\text{'}}\right)=\mathrm{0};\\ f_q\left(x_q,y_q^{\text{'}}\right)=\mathrm{1}+x_q\left(q_m\cdot {\mathrm{2}}^{{\eta }_{\mathrm{2}}-s}+y_q^{\text{'}}-\mathrm{1}\right)=\mathrm{0}\mathrm{。}\end{array}\right.

同样地，多项式g_{i,k}、g_{i,k}^{\text{'}}、g_{i,k}^{″}以及代换方程y_p{y}_q=N都应该随着y_p=p_m\cdot {\mathrm{2}}^{{\eta }_{\mathrm{1}}-s}+y_p^{\text{'}}和y_q=q_m\cdot {\mathrm{2}}^{{\eta }_{\mathrm{2}}-s}+y_q^{\text{'}}进行变化。同时，新变量的上界变为

与之前相比，x_p、x_q的界不变，而y_p^{\text{'}}、y_q^{\text{'}}的界比y_p、y_q更小，不难推出可求解的\delta的上界会得到一定程度的提升。p的高比特穷举能够在不改变格的维数的条件下，在文献[14]基础上进一步提升小d_q攻击的可攻击上界。但改进策略在实际攻击中究竟是否可行，还要取决于效率。一般而言，频繁地穷举会带来巨大的计算代价，极大地制约算法的效率。幸运的是，实验中发现了与文献[26]类似的多值现象，即在p、q真实高比特值p_m、q_m附近，存在着大量其他的穷举值，能够帮助完成有效的小d_q攻击。这类穷举值{\tilde{p}}_m称为有效猜测值，对应的({\tilde{p}}_m,{\tilde{q}}_m)称为有效猜测对，部分多值现象如表6所示。

从表6可以看出，对不同的参数设定，实验中都出现了多值现象。尽管这里的有效猜测值并不像文献[26]一样多，但利用二分搜索仍然能起到很可观的加速效果。利用二分法搜索有效猜测值来实施攻击，大大减少一般穷举带来的巨大计算代价，有效提升了CRT-RSA小d_q攻击的实际可攻击上界。例如，对\beta =\mathrm{0.305}、n_N=\mathrm{1}\mathrm{000}的CRT-RSA，给定参数m=\mathrm{6}时，使用文献[14]中的攻击方法能够达到的攻击上界为\delta \le \mathrm{0.176}，而基于二分搜索的攻击方法能够达到的攻击界为\delta \le \mathrm{0.182}。详细实验结果，见第4节。

3.4 文献[14]中格的优化探索

尽管文献[14]中的格在文献[10]和文献[19]所给格的基础上进行了优化，效果也比二者要好，但在编程实验中发现，依据helpful多项式的定义，该格仍然可以进一步优化。下面以\beta =\mathrm{0.305}、n_N=\mathrm{1}\mathrm{000}、m=\mathrm{6}为例探讨。注意到，格对角线上对应于g_{i,k}\left(x_p,y_p\right)、 g_{i,k}^{\text{'}}\left(x_p,y_p\right)和g_{i,k}^{″}\left(x_p,y_p,x_q,y_q\right)的元素为X_p^{k+i}{Y}_p^k{e}^{m-k}、X_p^k{Y}_p^{k+i}{e}^{m-k}、X_q^k{Y}_q^i{e}^{m-k}^[14]。在上述参数条件下，{\tau }_p和{\tau }_q的优化值分别为0.264和0.629。对g_{i,k}^{″}\left(x_p,y_p,\right.x_q,\left.y_q\right)，有：\mathrm{1}\le k\le m,\mathrm{1}\le i\le ⌈{\tau }_{q}k⌉。

由此可知，在选择优化参数时，e^{m-\mathrm{1}}{f}_q(x_q,y_q)和e^{m-\mathrm{2}}{f}_q^{\mathrm{2}}(x_q,y_q)显然出现在shift多项式中，且与其对应出现在对角线上的元素为X_q{Y}_q{e}^{m-\mathrm{1}}和X_q^{\mathrm{2}}{Y}_q^{\mathrm{2}}{e}^{m-\mathrm{2}}。由X_q=N^{\delta +\beta },Y_q=N^{\mathrm{1}-\beta }知：X_q{Y}_q{e}^{m-\mathrm{1}}\approx N^{\delta },X_q^{\mathrm{2}}{Y}_q^{\mathrm{2}}{e}^{m-\mathrm{2}}\approx N^{\mathrm{2}\delta }。

显然上述两个多项式都是unhelpful多项式。需注意以下事实：在下三角CopperSmith格中，如果一个多项式对应出现在对角线上的项不在之后多项式中出现（这里先后顺序依照事先定义的序），则去掉该多项式后剩下的多项式构成的格仍为下三角方阵。因此，如果上面两个多项式对应在对角线上的项x_q{y}_q和x_q^{\mathrm{2}}{y}_q^{\mathrm{2}}不在之后的多项式出现，那么这两个多项式就可以从格中剔除，得到优化的格。

事实上，形如x_q^t{y}_q^t（t为正整数）的项只出现在形式为f_p^{k-i}\left(x_p,y_p\right)f_q^i\left(x_p,y_p\right)e^{m-k}的shift多项式中，其中：f_p\left(x_p,y_p\right)=N+x_p\left(N-y_p\right)，f_q\left(x_q,y_q\right)=\mathrm{1}+x_q\left(y_q-\mathrm{1}\right)。将f_p^{k-i}\left(x_p,y_p\right)f_q^i\left(x_p,y_p\right)e^{m-k}展开并忽略系数，得到：{\displaystyle \sum _{i_p=\mathrm{0}}^{k-i}}{\displaystyle \sum _{i_q=\mathrm{0}}^i}{x}_p^{i+i_p-i_q}{x}_q^{k-i-i_p+i_q}{y}_p^{i_p}{y}_q^{i_q}。

再利用y_p{y}_q=N和x_q=x_p+\mathrm{1}替换，确保只含有x_p^{i_{px}}{y}_p^{i_{py}}和x_q^{i_{qx}}{y}_q^{i_{qy}}，最终得到含x_q^{i_{qx}}{y}_q^{i_{qy}}的项为{\displaystyle \sum _{i_q=\mathrm{0}}^i}{\displaystyle \sum _{i_p=\mathrm{0}}^{\mathrm{m}\mathrm{i}\mathrm{n}\{k-i,i_q-\mathrm{1}\}}}{\displaystyle \sum _{k_q=\mathrm{0}}^{i-i_q+i_p}}{x}_q^{k-k_q}{y}_q^{i_q-i_p}。

如果某个shift多项式中含x_q^t{y}_q^t，则有：i_q-i_p=t,k-k_q=t。又因为：k_q\le i-i_q+i_p,i\le ⌈{\tau }_{q}k⌉，则有：k=k_q+t\le i-i_q+i_p+t=i\le ⌈{\tau }_{q}k⌉。

注意到{\tau }_q=\mathrm{0.629}，因此满足k\le i\le ⌈{\tau }_{q}k⌉的只有k=\mathrm{1}和k=\mathrm{2}，此时k=i，即会出现x_q{y}_q和x_q^{\mathrm{2}}{y}_q^{\mathrm{2}}的shift多项式只有e^{m-\mathrm{1}}{f}_q(x_q,y_q)和e^{m-\mathrm{2}}{f}_q^{\mathrm{2}}(x_q,y_q)，不会有其他shift多项式。因此e^{m-\mathrm{1}}{f}_q(x_q,y_q)和e^{m-\mathrm{2}}{f}_q^{\mathrm{2}}(x_q,y_q)可从原格中剔除，达到优化格效果。

从表5可以看到，本节参数设定下，可以攻击到的\delta上界为0.176。对\delta =\mathrm{0.176}的CRT-RSA实施攻击时，shift多项式中又有另外两个多项式可以剔除（推导证明过程同上），即：e^{\mathrm{2}}{f}_p\left(x_p,y_p\right)f_q^{\mathrm{3}}\left(x_p,y_p\right),e{f}_p\left(x_p,y_p\right)

f_q^{\mathrm{4}}\left(x_p,y_p\right)\mathrm{。}

需要注意的是，这两个多项式对应出现在对角线上的系数为e^{\mathrm{2}}{X}^{\mathrm{4}}{Y}_q^{\mathrm{3}}和e{X}^{\mathrm{5}}{Y}_q^{\mathrm{4}}，这两个系数的规模为

\left\{\begin{array}{c}{e}^{\mathrm{2}}{X}^{\mathrm{4}}{Y}_q^{\mathrm{3}}=e^{\mathrm{2}}{N}^{\mathrm{4}\left(\beta +\delta \right)}{N}^{\mathrm{3}\left(\mathrm{1}-\beta \right)}=e^{\mathrm{2}}{N}^{\mathrm{3}+\mathrm{4}\delta +\beta };\\ e{X}^{\mathrm{5}}{Y}_q^{\mathrm{4}}=e^{\mathrm{2}}{N}^{\mathrm{5}\left(\beta +\delta \right)}{N}^{\mathrm{4}\left(\mathrm{1}-\beta \right)}=e{N}^{\mathrm{4}+\mathrm{5}\delta +\beta }\mathrm{。}\end{array}\right.

显然，当\delta =\mathrm{0.176}、\beta =\mathrm{0.305}时，上面两个系数都比模数e^{\mathrm{6}}大。然而，实验效果与上述优化结果并不完全相符。实验发现，剔除前两个多项式后，利用新的格来攻击\delta =\mathrm{0.176}的CRT-RSA成功率与原格基本相同，而剔除上述4个多项式后，得到的攻击成功率反而不如原格。这是因为剔除的标准依赖于helpful多项式的定义，而其定义是从理论攻击中给出的。

设原格\mathit{L}的基矩阵为\mathit{A}，新添加的多项式对应到对角线处元素为b，由于新添加的多项式不影响原格，不妨设其添加在最后，即新格为{\mathit{L}}^{\mathit{\text{'}}}=\left(\begin{array}{cc}\mathit{A}& \mathrm{0}\\ *& b\end{array}\right)。

基于CopperSmith格方法的RSA攻击的理论分析，通常采用引理2简化形式，对应于新格\mathit{L}\mathit{\text{'}}判断条件即：。因此若使新格的效果不亚于原格，则应有。然而，引理2的简化形式不适合作为实际攻击的判断条件，第3.2节给出实际可攻击上界估计时要保留所有低次项和系数，并且要借助实验中统计的目标度量，正是出于这一考虑。事实上，计算发现e^{\mathrm{2}}{N}^{\mathrm{3}+\mathrm{4}\delta +\beta }\approx e^{\mathrm{6.09}}，这一规模仅仅略大于e^{\mathrm{6}}，因而一旦加入系数和具体的目标度量，很可能多项式e^{\mathrm{2}}{f}_p\left(x_p,y_p\right)f_q^{\mathrm{3}}\left(x_p,y_p\right)并不是实际攻击中的unhelpful多项式，因此剔除后反而影响攻击效果。

综合上述讨论，在不影响格满秩特性的条件下，可通过剔除一些unhelpful多项式来优化格。该方法可在保持攻击界不下降的前提下降低格的维数，从而提升攻击效率。但优化的过程需要谨慎，考虑到helpful多项式理论在实际攻击中未必完全适用，要剔除的多项式究竟是有益的还是无益的，最终还应该以实验效果为准。

在对格进行优化时，可以实施下面步骤：1）先对利用定义，筛选出unhelpful多项式；2）将剔除后不改变格满秩特性的unhelpful多项式作为剔除备选；3）根据实验效果，确定可以剔除的多项式，得到最终的优化格。

4 实验

本文中的实验在PC机（Intel（R）Core（TM）i7-9700 CPU @3.00 GHz）上用SageMath 9.3完成。首先实施了大量实验来检验{\tau }_p、{\tau }_q优化值的效果，其中部分效果对比展示如表7所示。

在表7中，每一组参数\beta中，粗体部分是本文给出的优化值及其对应格的效果，另一行的{\tau }_p,{\tau }_q是根据文献[14]中的理论最优值计算得到的。从表7可以看到，第1组和第3组实验中，优化值对应格实施的攻击成功率都高于理论最优值对应的格，同时优化值对应的格的维数更低；第2组优化值对应的攻击成功率虽与理论最优值下的成功率相同，但格维数更低；第4组虽然格维数相同，但本文优化值对应的格实施的攻击成功率要高出10%以上。这几组数据的对比说明了参数优化值的有效性。

为了验证表3和表4中给出的各个参数情形下可攻击上界估计的有效性，本文实施了大量的实验，其结果如表8所示。

从表8可以看到，各个参数情形给出的估计结果与检验结果匹配良好。如\beta =\mathrm{0.305}、m=\mathrm{6}、n_N=\mathrm{1}\mathrm{000}时，\delta =\mathrm{0.188}、\mathrm{0.189}的攻击成功率分别为90%和2%。表8显示，最接近估计值的检验点（对应第1组的0.188、第2组的0.110、第3组的0.060、第4组的0.008）的攻击成功率都达到了80%以上，与之对应的，而下一个检验点的攻击成功率均不到40%，并且同一参数情形中，前后成功率差距达到60%以上。这充分验证了本文基于实验和参数拟合的估计方法的有效性和准确性。

为了探索本文的小d_q实际攻击的效果，本文针对不同的参数实施了大量的实验。先在p的高s比特已知的条件下，探索文献[14]中的小d_q攻击方法实际能够达到的上界，结果如表9所示。

在表9中，s=\mathrm{0}表示p的高比特未知。从表9数据对比可以看到，4组参数设定中，s=\mathrm{10}时可成功攻击的\delta上界相比s=\mathrm{0}时都有提升，提升程度约为5~6比特。这说明，当p高s比特已知时，\delta的实际可攻击上界确实会有一定的提升。

在确认已知p的部分高比特能够给\delta的实际可攻击上界带来提升后，本文在文献[14]的攻击基础上，实施了基于二分搜索的CRT-RSA小d_q实际攻击，其结果如表10所示。

利用二分法在穷举空间搜索有效猜测对时，可以将穷举空间适当分割，进而实施并行策略加速攻击。表10中的总运行时间是指：对p的高s比特进行二分搜索，每搜索1个值随即实施一次文献[14]的小d_q攻击，直到搜索到第1个有效猜测值并完成攻击，这一过程消耗的总时间。具体地，在实例1中，当\beta =\mathrm{0.305}、n_N=\mathrm{1}\mathrm{000}、m=\mathrm{6}时，对p的高10比特进行搜索，基于二分搜索的CRT-RSA小d_q实际攻击方法可以在1 h左右实现\delta \le \mathrm{0.182}条件下的实际攻击（如表10中，实例1只需要约27 min）；类似地，对比表5中文献[14]中的攻击方法得到的结果，在相同参数下的实例2、实例3、实例4中，基于二分搜索的小d_q实际攻击方法高效地攻击到比前者高5~6比特的d_q。从表10可以看到，该攻击方法最先搜索到的有效猜测值大多不是真实的p_m或q_m。一般情况下，利用二分搜索寻找到真实高比特值仍然需要很长的时间：以实例4为例，二分法搜索到第一个有效猜测值920仅仅需要3次循环，而搜索到真实值918需要14次循环，这充分体现了多值现象的加速效果。将本文的实际攻击结果与文献[14]中的结果进行对比，如表11所示。

从表11可以看出，对前两行参数，在格维数相当的情况下，本文的实际攻击方法能够攻击到的\delta远远高于文献[14]；对于后两行参数，在格维数低于文献[14]的条件下，得到了不低于他们的攻击上界。这一对比充分说明了本文实际攻击方法的优势和显著效果。

5 结束语

对CRT-RSA的小d_q实际攻击进行探索研究。首先对文献[14]中的小d_q攻击的参数{\tau }_p、{\tau }_q进行优化，得到不同参数设定下的最优参数值。为指导攻击实验，在基于LLL输出格基的长度上界和Nguyen等实验结果的估计存在偏差的情况下，基于实验统计的目标度量和参数拟合，给出小d_q实际可攻击上界估计，由此得到的上界估计与实验结果匹配转好，体现该方法的有效性。在优化参数和估计基础上，对给定参数下小d_q实际可攻击上界进行探索。先利用文献[14]中的小d_q攻击进行探索，随后采用猜测p的高比特的方法进行尝试。实验中发现的“多值现象”使得给定参数下的实际可攻击上界得到进一步提升。最后，尝试对文献[14]中的格进行优化，理论分析和实验结果显示，helpful多项式的理论在实际攻击中并不完全适用，在此基础上给出格在实际攻击中的优化方法。

尽管本文在实际攻击探索中得到了很多有价值的信息和结论，但仍有很多问题值得进一步探索。1）本文给出的参数{\tau }_p、{\tau }_q的优化值也未必是最优的。实际上，引理2中完整的条件含有指数函数和对数函数等复杂的小项，为便于求极值和求根，本文同样去掉了这些小项。给出实际攻击中真正最优的参数值是非常有价值的工作。2）目前实际可攻击上界估计值吻合度虽然很好，但估计值依赖于参数m、 \beta，如果能给出一个有效又能涵盖各个参数的统一的估计表达式，对实际攻击的指导效果将会更好。3）基于二分搜索的实际攻击方法确实能够提升实际可攻击上界，但其中有效猜测值的数量远远少于文献[26]中RSA小解密指数攻击的情形。其他参数的比特穷举探索或许能带来新的视野。最后，对文献[14]中的格进行进一步优化，使之更契合实际攻击、更便于实施，同样非常值得探索。尽管还有很多值得深度探索的问题，但本文的实验探索、优化与估计，仍能对CRT-RSA的小d_q实际攻击研究提供重要的参考。

参考文献

[1] RIVEST R L， SHAMIR A， ADLEMAN L. A method for obtaining digital signatures and public-key cryptosystems［J］. Communications of the ACM， 1978，21（2）：120-126.

[2] WIENER M J. Cryptanalysis of short RSA secret exponents［C］∥Proceedings of the Advances in Cryptology- EUROCRYPT ’89. Berlin， Germany： Springer， 1990：372.

[3] STINSON D R. Cryptography：theory and practice［M］. 2nd ed. Florida，USA： CRC Press， 2002.

[4] MAY A. Computing the RSA secret key is deterministic polynomial time equivalent to factoring［C］∥Proceedings of the Advances in Cryptology-CRYPTO 2004. Berlin， Germany： Springer， 2004：213-219.

[5] CORON J S， MAY A. Deterministic polynomial-time equivalence of computing the RSA secret key and factoring［J］. Journal of Cryptology， 2007，20（1）：39-50.

[6] BONEH D， DURFEE G. Cryptanalysis of RSA with private key d less than N0.292［C］∥Proceedings of the Advances in Cryptology-EUROCRYPT’99. Berlin， Germany： Springer， 1999：1-11.

[7] DON C. Finding a small root of a univariate modular equation［C］∥Proceedings of the Advances in Cryptology-EUROCRYPT’96. Berlin， Germany： Springer， 1996：155-165.

[8] QUISQUATER J J， COUVREUR C.Fast decipherment algorithm for RSA public-key cryptosystem［J］. Electronics Letters，1982，18（21）：905-907.

[9] GALBRAITH S D， HENEGHAN C， MCKEE J F. Tunable balancing of RSA［M］∥Information security and privacy. Berlin， Germany： Springer， 2005：280-292.

[10] BLEICHENBACHER D， MAY A. New attacks on RSA with small secret CRT-exponents［C］∥Proceedings of the Public Key Cryptography-PKC 2006. Berlin， Germany： Springer， 2006：1-13.

[11] 韩立东， 王小云， 许光午. RSA密码系统小CRT解密指数的攻击分析［J］. 中国科学： 信息科学， 2011，41（2）：173-180.

[12] JOCHEMSZ E， MAY A. A polynomial time attack on RSA with private CRT-exponents smaller than N0.073［C］∥Proceedings of the Advances in Cryptology-CRYPTO 2007. Berlin， Germany： Springer， 2007：395-411.

[13] TAKAYASU A， LU Y， PENG L Q. Small CRT-exponent RSA revisited［M］∥Advances in Cryptology-EUROCRYPT 2017. Cham， Switzerland： Springer， 2017：130-159.

[14] TAKAYASU A， LU Y， PENG L Q. Small CRT-exponent RSA revisited［J］. Journal of Cryptology， 2019，32（4）：1337-1382.

[15] PENG L Q， TAKAYASU A. Generalized cryptanalysis of small CRT-exponent RSA［J］. Theoretical Computer Science， 2019，795：432-458.

[16] MAY A， NOWAKOWSKI J， SARKAR S. Partial key exposure attack on short secret exponent CRT-RSA［M］∥Advances in Cryptology-ASIACRYPT 2021. Cham， Switzerland： Springer， 2021： 99-129.

[17] ZHOU Y Y， VAN DE POL J， YU Y， et al. A third is all you need： extended partial key exposure attack on CRT-RSA with additive exponent blinding［M］∥Advances in cryptology-ASIACRYPT 2022. Cham， Switzerland： Springer， 2022：508-536.

[18] MAY A， NOWAKOWSKI J， SARKAR S. Approximate divisor multiples-factoring with only a third of the secret CRT-exponents［M］∥Advances in Cryptology-EUROCRYPT 2022. Cham， Switzerland： Springer， 2022：147-167.

[19] MAY A. Cryptanalysis of unbalanced RSA with small CRT-exponent［C］∥Proceedings of the Advances in Cryptology-CRYPTO 2002. Berlin， Germany： Springer， 2002：242-256.

[20] LENSTRA A K， LENSTRA H W， LOVÁSZ L. Factoring polynomials with rational coefficients［J］. Mathematische Annalen， 1982，261（4）：515-534.

[21] HERRMANN M， MAY A. Maximizing small root bounds by linearization and applications to small secret exponent RSA［C］∥/Proceedings of the Public Key Cryptography-PKC 2010. Berlin， Germany： Springer， 2010：53-69.

[22] NGUYEN P Q， STEHLÉ D. LLL on the average［C］∥Proceedings of the Algorithmic Number Theory. Berlin， Germany： Springer，2006：238-256.

[23] HOWGRAVE-GRAHAM N. Finding small roots of univariate modular equations revisited［C］∥Proceedings of the Crytography and Coding. Berlin， Germany： Springer， 1997：131-142.

[24] TAKAYASU A， KUNIHIRO N. Better lattice constructions for solving multivariate linear equations modulo unknown divisors［C］∥Proceedings of the Information Security and Privacy. Berlin， Germany： Springer， 2013：118-135.

[25] MAY A. Using LLL-reduction for solving RSA and factorization problems［M］∥The LLL algorithm. Berlin， Germany： Springer， 2009：315-348.

[26] LI Q， ZHENG Q X， QI W F. Practical attacks on small private exponent RSA： new records and new insights［J］. Designs， Codes and Cryptography， 2023，91（12）：4107-4142.

基金资助

国家自然科学基金面上项目(12371526)