关于微信公众号

前言

由于最近的比赛中各类参考 paper 的与RSA相关的题目层出不穷。但每次做题的时候，即使搜索到了paper，由于比赛时间关系，自己也是囫囵吞枣似的赶紧照着 paper 实现完成解题，但并没有真正消化其背后的知识原理。于是想借此重新学习一下比赛中题目所涉及的知识，沉一沉浮躁的心。

题目

今天学习的paper是《Generalization of Some Attacks on RSA with Small Prime Combination and Small Private Exponent》，出自山东大学密码技术与信息安全实验室。

可以用于解决下面这道CTF题目

from Crypto.Util.number import *
from secret import p,q,e,flag

i = 11
j = 2
n = p * q
phi = (p-1)*(q-1)
d = inverse(e, phi)

assert i*p - j*q < n ** 0.342

m = bytes_to_long(flag)
c = pow(m,e,n)

0.摘要

​ de weger 在 2002 年发表了一篇论文：Cryptanalysis of RSA with Small Prime Difference，是针对具有小私钥 $d$，并且素数差 $|p-q|$ 很小的 RSA 公钥加密系统。其相对于 Wiener 攻击 和 Boneh-Durfee 攻击，加上了 $|p-q|$ 的约束，但是也相应的放开了对 $d$ 的约束。随后，Maitra 和 Sarkar 发现了当 $|2q-p|$ 较小时，系统也是脆弱的。而在这片论文中，将 $|p-q|,|2q-p|$ 和小私钥 $d$ 的场景进行了推广：对于某些整数 $i,j$，当 $|ip-jq|$ 较小且具有小私钥 $d$ 时，仅利用 $e,n$ 我们就可以恢复私钥 $d$。

1.引言

​ 由 Rivest，Shamir, Adleman 于 1978 年提出的 RSA 时当今较为流行的公钥加密方案。RSA 系统由 公钥 $(N,e)$ ，私钥 $d$，和由两个大素数 $p,q$ 乘积而来的 $N$ 组成。其中， $ed \equiv 1 \pmod {\varphi(N)}$，$\varphi(N) = (p-1)\cdot (q-1)$。加密消息 $m \in \mathbb{Z}_N^*$，我们用公钥 $(N,e)$ 计算 $c\equiv m^e \pmod N$, 解密消息我们用私钥 $d$ 计算 $c^d \equiv m \pmod N$。

​ 对于RSA的安全性，有很多研究都是针对 $e$ 或 $d$ 较小的情况进行的。比较著名的基于连分数的 Wiener 攻击在 $d \lt \frac{1}{3} N^{\frac{1}{4}}$ 时有很好的实用性。这个后来被 Boneh 和 Durfee 优化，引入了 LLL 算法，将 $d$ 的界提升了到了 $N^{0.292}$。

​ de weger提出了另一种攻击，当 $\Lambda=|p-q|$ 较小时，RSA 密码系统也是不安全的。 事实上，当 $\Lambda \lt N^{\frac{1}{4}}$ 时，我们可以直接通过费马分解算法将 $N$ 分解。而 de Weger 提出了一种当 $d,\Lambda$ 均较小时的攻击手法：当 $\delta \lt \frac{3}{4}-\beta$ 时，$d = N^{\delta},\Lambda = N^\beta$。其证明主要内容是 $\frac{e}{N-2\sqrt{N}+1}$ 的连分数收敛性计算。即将 Wiener 的研究结果进行了拓展。随后 Maitra 和 Sarkar 提出了一种，$\Lambda$ 很大，但是 $|2p-q|$ 较小的场景。他们证明当 $\delta \lt \frac{3}{4}-\beta-\tau,2p-q=N^{\beta}$，其中 $\tau$ 是一个较小的数时，攻击奏效。

​ 而这篇论文的目的是进一步扩展这些结果，对于某些正整数 $i,j$，我们考虑素数的组合 $|ip-jq|$。我们将费马分解法推广到 $|ip-jq|=N^\beta$ 较小的场景，并证明，当 $\beta \lt \frac{1}{4}$ 时，费马分解可以用于求 $N$ 的分解。对于 Wiener 攻击结论的拓展，我们考虑 $|ip-jq|=N^\beta$ 较小，而不是 $q-p, 2p-q$ 较小。我们将说明当 $\delta \lt \frac{3}{4}-\beta -\tau$ 时通过连分数我们能够快速恢复私钥 $d$。（$d$ 也需要满足一些条件）

de weger 将 Boneh 和 Durfee 的攻击中的条件拓展为 $\delta \lt \frac{1}{6}(4\beta+5)-\frac{1}{3}\sqrt{(4\beta+5)(4\beta-1)}$。那么我们考虑 $ip-jq=N^\beta$，得到新的条件 $\delta \lt \frac{1}{6}(4\beta+5+2\theta)-\frac{1}{3}\sqrt{(4\beta+5+2\theta)(4\beta-1+2\theta)}$，其中 $\theta$ 由 $i,j$ 决定。

​ 以前文献中的结果只考虑了 $p$ 和 $q$ 大小相同的情况。这篇论文的方法消除了这个限制。因此可以识别出更多不安全的密钥。

​ 在一些实际场景中（例如智能卡），人们通常根据一些指定的比特模式生成素数 $p$ 和 $q$。因此，用户在选择 RSA 参数时应格外小心，以避免出现以下情况：$p − q$很小，或$2p− q$很小，或者更一般的是 $ip− jq$ 很小。因此，这项工作也具有一定的实践意义。

2.差值较小时费马分解

这一部分我们将讨论在 $|ip-jq|$ 的情况下分解 RSA 的模数 $N$，从一个引理开始

引理 1 设整数 $i,j$，如果 $N=pq$，且 $N^\beta = |ip-jq|$，那么有
$$
ip+jq-2(ijN)^{1/2} \le \frac{N^{2\beta}}{4(ijN)^{1/2}} \tag{1}
$$
证明：

由于 $\sqrt{ip}-\sqrt{jq} = \frac{ip-jq}{\sqrt{ip}+\sqrt{jq}}$，两边平方得到
$$
ip+jq-2(ijN)^{1/2} = (\sqrt{ip}-\sqrt{jq})^2 =\frac{N^{2\beta}}{(\sqrt{ip}+\sqrt{iq})^2} \le \frac{N^{2\beta}}{4(ijN)^{1/2}}
$$
那么基于这个引理，我们得到

定理 1 设 $i,j \in \mathbb{Z}$，与 $N$ 无关的 $u \in \mathbb{N}$，$N^\beta = |ip-jq|$，如果 $N^{\beta} \le (logN)^u(|ij|N)^{1/4}$，那么 $N$ 可以在 $O((logN)^{2u})$ 内被分解。

证明：

根据 引理 1 我们有
$$
0 \le |i|p+|j|q - 2(|ij|N)^{1/2} \le \frac{N^{2\beta}}{4(ijN)^{1/2}} \le \frac{(logN)^{2u}}{4}
$$
或者
$$
-2 \le |i|p+|j|q - 2\lceil(|ij|N)\rceil^{1/2} \le \frac{(logN)^{2u}}{4}
$$
注意到 $2\lceil(|ij|N)\rceil^{1/2}$ 是我们已知的一个整数。

与传统费马分解方法略有不同，分解 $N$ 过程如下：

遍历每一个 $s=-2,-1,0,1,\cdots,2\lceil(logN)^{2u}/4\rceil$，我们解如下方程组
$$
\left{\begin{align}
|i|x+|j|y = s+2\lceil(|ij|N)^{1/2} \rceil \
xy=N

\end{align}\right.
$$
如果对于某个 $s$，我们得到整数解 $(x0,y0)$，那么就意味着我们成功分解了 $N$。而我们的定理则保证了整数解的存在性。

3.对连分数方法的应用

在上个部分我们得知，如果 $|ip-jq|=N^\beta \lt (logN)^u (|ij|N)^{1/4}$，也就是说，如果 $\beta \lt \frac{1}{4}$，那么费马分解方法就能够很快的分解 $N$。而这一章，我们同样考虑里两个大素数 $p,q$，他们不必是相同尺寸的，只需要满足 $|ip-jq|=N^{\beta}, \frac{1}{4} \lt \beta \le \frac{1}{2}$。方便起见，论文余下部分我们均默认 $|ip-jq|=N^\beta$ ，$\beta$ 的区间也是 $(\frac{1}{4},\frac{1}{2}]$。

对连分数的应用我们还是基于 de weger 的研究成果（$q-p = N^\beta,d = N^{\delta}$），其证明了，如果 $\delta \lt \frac{3}{4}-\beta$，那么 $d$ 将在 $\frac{e}{N-2\sqrt{N}+1 }$ 的连分数展开收敛中。在《Revisiting Wiener’s attack–new weak keys in RSA》中，Maitra 和 Sarkar 将这一结论拓展到 $2p-q$ 较小的场景，并给出了一个新得界。

而 Blomer 和 May 在 《A generalized Wiener attack on RSA》中，引入 $xe+y \equiv 0 \pmod {\varphi(N)}$ 已经较小的 $|p-q|$ 来拓展了 Wiener 攻击。这也在 《Revisiting Wiener’s attack–new weak keys in RSA》被拓展到了 $2p-q$ 较小的场景。那么在这一章中，我们应该介绍如何通过较小的 $ip-jq$ 来求出脆弱的私钥。同样，我们从如下引理出发：

引理 2

设有正整数 $i,j$，如果 $0 \lt ip-jq\ = N^\beta$，那么有
$$
\left| \sqrt{\frac{i}{j}N} + \sqrt{\frac{j}{i}N} - (p+q)\right | \lt \frac{lN^{2\beta}}{(\sqrt{i}+\sqrt{j})^2\sqrt{ijN}}
$$
其中 $l$ 为正整数满足 $p \gt \frac{lj+i}{li+j}q$ 或者 $q \gt \frac{-li+j}{-lj+i}p$。

证明：我们将从 $p \gt q$ 和 $q \gt p $ 两个情况进行严格证明。

如果 $q \gt p$，那么由 $0 \lt ip-jq=N^\beta$ 我们可知 $i \gt j$，因此 $iq-jp \gt0$，那么至少存在一个正整数 $l_1$ 使得 $l_1(ip-jq) \gt iq-jp \gt 0$

如果 $p \gt q$，那么由 $0 \lt ip-jq=N^\beta$ 我们可知 $i \lt j$，因此 $iq-jp \lt0$，那么至少存在一个负整数 $l_2$ 使得 $l_2(jq-ip) \gt jp-iq \gt 0$

我们设 $l \ge l_0 = max{l_1,|l_2|}$，就有 $|iq-jp| \lt l(ip-jq)$

于是，魔法开始：
$$
\left| \sqrt{\frac{i}{j}N} + \sqrt{\frac{j}{i}N} - (p+q)\right |=\frac{|(iq-jp)(ip-jq)|}{ij(\sqrt{\frac{i}{j}N}+\sqrt{\frac{j}{i}N}+(p+q))}
$$

$$
\lt \frac{l(ip-jq)^2}{ij(\sqrt{\frac{i}{j}N}+\sqrt{\frac{j}{i}N}+(p+q))}
$$

$$
= \frac{lN^{2\beta}}{ij(\sqrt{\frac{i}{j}N}+\sqrt{\frac{j}{i}N}+(p+q))}
$$
由于 $p+q \gt 2\sqrt{N}$，所以有
$$
\left| \sqrt{\frac{i}{j}N} + \sqrt{\frac{j}{i}N} - (p+q)\right | \lt\frac{lN^{2\beta}}{ij(\sqrt{\frac{i}{j}N}+\sqrt{\frac{j}{i}N}+2\sqrt{N})} = \frac{lN^{2\beta}}{(\sqrt{i}+\sqrt{j})^2\sqrt{ijN}}
$$
上述引理使得我们在 $ip-jq=N^\beta$ 较小时能够找到 $p+q$ 的一个近似，这将在我们后面的内容中发挥非常大的作用。

3.1 恢复小私钥 $d$

基于引理2，如果 $d$ 和 $\beta$ 较小，我们使用连分数将可以快速的恢复私钥。

定理 2 设有正整数 $i,j$，且 $ip-jq = N^\beta,d = N^\delta$，并使用引理 2 中定义的 $l$。如果 $\delta \lt \frac{3}{4} - \beta - \tau,2\tau \ge \frac{log(4l)-log((\sqrt{i}+\sqrt{j})^2\sqrt{ij})}{logN}$，那么存在一个多项式算法（$logN$）恢复私钥 $d。$

证明：我们设有整数 $k$ 满足 $ed = k\varphi(N) + 1$，根据 引理 2 ，我们有 $\left| \sqrt{\frac{i}{j}N} + \sqrt{\frac{j}{i}N} - (p+q)\right | \lt \frac{lN^{2\beta}}{(\sqrt{i}+\sqrt{j})^2\sqrt{ijN}}$，即
$$
\left| \sqrt{\frac{i}{j}N} + \sqrt{\frac{j}{i}N} + \varphi(N)-N-1\right | \lt \frac{lN^{2\beta}}{(\sqrt{i}+\sqrt{j})^2\sqrt{ijN}}
$$
那么现在，魔法开始
$$
\left |\frac{e}{N-\sqrt{\frac{i}{j}N}-\sqrt{\frac{j}{i}N}+1} - \frac{k}{d} \right |
$$

$$
\le \left |\frac{e}{N-\sqrt{\frac{i}{j}N}-\sqrt{\frac{j}{i}N}+1} - \frac{e}{\varphi(N)} \right | + \left |\frac{e}{\varphi(N)} -\frac{k}{d} \right |,基本不等式
$$

$$
=\frac{e\left| \sqrt{\frac{i}{j}N}-\sqrt{\frac{j}{i}N} -p -q\right |}{\varphi(N)(N-\sqrt{\frac{i}{j}N}-\sqrt{\frac{j}{i}N}+1)}+\frac{1}{d\varphi(N)}，通分
$$

$$
\lt \frac{e\frac{lN^{2\beta}}{(\sqrt{i}+\sqrt{j})^2\sqrt{ijN}}}{\varphi(N)(N-\sqrt{\frac{i}{j}N}-\sqrt{\frac{j}{i}N}+1)}+\frac{1}{d\varphi(N)}，根据引理 2 推出的不等式
$$

$$
\lt \frac{lN^{2\beta}}{((\sqrt{i}+\sqrt{j})^2\sqrt{ijN}(N-\sqrt{\frac{i}{j}N}-\sqrt{\frac{j}{i}N}+1)}+\frac{1}{d\varphi(N)},\because \frac{e}{\varphi(N) }\lt 1
$$

假设（一般情况下满足） $\varphi(N) \gt \frac{3}{4}N$，$N-\sqrt{\frac{i}{j}N}-\sqrt{\frac{j}{i}N}+1 \gt \frac{3}{4}N,N \gt 8d$

那么我们有
$$
\left |\frac{e}{N-\sqrt{\frac{i}{j}N}-\sqrt{\frac{j}{i}N}+1} - \frac{k}{d} \right | \lt \frac{lN^{2\beta}}{((\sqrt{i}+\sqrt{j})^2\sqrt{ijN}\frac{3}{4}N}+\frac{4}{3Nd}，代入上述条件
$$

$$
=\frac{4lN^{2\beta-\frac{3}{2}}}{3(\sqrt{i}+\sqrt{j})^2\sqrt{ij}}+\frac{1}{6N^{2\delta}},整理一下，代入d
$$

根据 $\tau$ 的定义，我们有
$$
\frac{4lN^{2\beta-\frac{3}{2}}}{3(\sqrt{i}+\sqrt{j})^2\sqrt{ij}} \lt \frac{1}{3} N^{2\beta-\frac{3}{2}+2\tau}
$$
所以如果 $\delta \lt \frac{3}{4}-\beta - \tau$，那么
$$
\frac{1}{3} N^{2\beta-\frac{3}{2}+2\tau} \gt \frac{1}{3} N^{-2\delta},\delta \lt 1
$$
所以
$$
\left |\frac{e}{N-\sqrt{\frac{i}{j}N}-\sqrt{\frac{j}{i}N}+1} - \frac{k}{d} \right | \lt \frac{1}{3} N^{-2\delta} + \frac{1}{6N^{2\delta}} = \frac{1}{2d^2}
$$
因此，根据 Legendre theorem，$\frac{k}{d}$ 收敛于 $\frac{e}{N-\sqrt{\frac{i}{j}N}-\sqrt{\frac{j}{i}N}+1} $ 的连分数展开上。

下面给出一个例子

例 1 在这个样例中，我们 $p$ 为500比特，$q$ 为 503比特，条件是 $11p-2q \lt N^{0.342}$

选取的 $ p,q$ 为

p=2880794542322299126706444345451054566788591299326109649598593295363377126011666800246753142436062672739058788177830266655144151568857625404801769045849(500 bits)

q=15844369982772645196885443899980800117337252146288269651197838948986507046422836536143684559825456026982099871598507492783605579115924091397626830393181(503 bit)

取 $l=2^{164}$，我们有 $p \gt \frac{2l+11}{11l+2}q$，于是我们选到 $\tau = 0.0797$，因为 $\beta = 0.342,\frac{3}{4}-\beta - \tau = 0.3283$，所以根据定理2，满足 $d \lt N^{0.3823}$ 的私钥都能够被有效恢复。

经过实验发现，如果 $d$ 略微大于 $N^{0.3823}$，也能够有较大概率被回复，比如，当 $d$ 为 332 比特，334 比特，336比特时，恢复 $d$ 的概率分别为 $0.679,0.197,0.048$。

3.2 根据 $ex+y \equiv 0 \pmod {\varphi(N)}$ 分解 $N$

这一节，我们仍然设定 $ip-jq$ 较小，设 $|a|$ 为 $a$ 的比特数，并定义 $|p|=l_p,|q|=l_q$。

定理 3 设 $ip-jq=N^{\beta},\frac{1}{4}\lt\beta\le \frac{1}{2},\Delta = (\sqrt{i}+\sqrt{j})^2\sqrt{ij}$，其中 $i,j$ 是较小的正整数。$l$ 继续沿用 引理 2 的定义，$\epsilon \gt \frac{4}{3} lN^{\beta-\frac{5}{4}} + \Delta N^{\frac{1}{4}-\beta}$，假设 $l_q-l_p$ 较小，并且存在正整数 $k$ 使得 $e$ 满足 $ex+y=k\varphi(N)$，那么当 $0\lt x\lt \sqrt{\frac{3\Delta}{8(1+\epsilon)l}}\sqrt{\frac{\varphi(N)}{e}}\frac{N^{\frac{3}{4}}}{ip-jq}$ 并且 $|y| \lt \frac{l(ip-jq)}{\varphi(N)N^{\frac{1}{4}}}ex$ ，那么$N$ 可以在多项式时间（$logN$）内被分解。

证明：首先，我们考虑 $k$ 的界。

因为 $ex+y=k\varphi(N)$，所以 $k = \frac{ex+y}{\varphi(N)} \le \frac{ex}{\varphi(N)}(1+\frac{l(ip-jq)}{\varphi(N)N^{\frac{1}{4}}})$

令 $\lambda = \sqrt{\frac{i}{j}N} +\sqrt{\frac{j}{i}N}$，因为 $ip-jq=N^\beta$，并且 $|y| \lt \frac{l(ip-jq)}{\varphi(N)N^{\frac{1}{4}}}ex$

所以
$$
\left | \frac{e}{N-\lambda+1} - \frac{k}{x}\right | = \frac{k(\lambda -p -q)-y}{x(N-\lambda+1)} \le \frac{|k(\lambda-p-q)|+|y|}{x(N-\lambda+1)}
$$

根据引理 2，并结合上述不等关系有我们得到
$$
\lt \frac{\frac{ex}{\varphi(N)}(1+\frac{lN^\beta}{\varphi(N)N^{\frac{1}{4}}})\frac{lN^{2\beta}}{\Delta\sqrt{N}}+\frac{l(ip-jq)}{\varphi(N)N^{\frac{1}{4}}}ex}{x(N-\lambda + 1)}
$$

$$
=\frac{\frac{e}{\varphi(N)}(1+\frac{lN^\beta}{\varphi(N)N^{\frac{1}{4}}}+\frac{\Delta N^{\frac{1}{4}}}{N^\beta})\frac{lN^{2\beta}}{\Delta\sqrt{N}}}{(N-\lambda + 1)}
$$

因为 $\epsilon \gt \frac{4}{3} lN^{\beta-\frac{5}{4}} + \Delta N^{\frac{1}{4}-\beta}$，并且 $N-\lambda+1 \gt \frac{3}{4}N$，所以我们与
$$
\left | \frac{e}{N-\lambda+1} - \frac{k}{x}\right | \lt \frac{\frac{e}{\varphi(N)}(1+\epsilon)\frac{lN^{2\beta}}{\Delta\sqrt{N}}}{(N-\lambda + 1)}
$$

$$
\lt (1+\epsilon)\frac{4el}{3\varphi(N)\Delta}N^{2\beta-\frac{3}{2}}
$$

如果 $0\lt x\lt \sqrt{\frac{3\Delta}{8(1+\epsilon)l}}\sqrt{\frac{\varphi(N)}{e}}N^{\frac{3}{4}-\beta}$，那么就有 $\left | \frac{e}{N-\lambda+1} - \frac{k}{x}\right | \lt \frac{1}{2x^2}$。

因此，$\frac{k}{x}$ 会出现在 $\frac{e}{N-\lambda+1}$ 的连分数展开上。然后由 $N+1-\frac{ex}{k}=p+q+\frac{y}{k}$，我们可以计算出 $p+q$ 的一个大约值。而误差项 $|\frac{y}{k}| \le \frac{4l(ip-jq)}{3N^{1/4}}$。因为 $i,j,lq-lp$ 较小，所以 $\frac{y}{k} \le c N^{1/4}$，其中 $c$ 是某个常数。通过枚举几个比特，我们可以恢复大部分的 $p+q$ 的高位值，随后利用 Coppersmith 方法即可在多项式时间内分解 $N$。

4. Weger 对 Boneh Durfee 攻击的拓展

针对 RSA 小私钥的 Boneh Durfee attack，在素数差较小的时候，Weger将 $d$ 的界提升到了 $N^{1/2}$。这一章，我们将证明这对小的 $|ip-jq|$ 也同样成立。

假设公钥指数 $e$ 和 $N$ 比特数相同，设 $ed = 1+k\varphi(N)$，记 $x=k,y=-(p+q-\sqrt{\frac{i}{j}N}-\sqrt{\frac{j}{i}N})$，且 $A=N+1-\sqrt{\frac{i}{j}N}-\sqrt{\frac{j}{i}N}$。于是我们有 $ed=1+x(A+y)$ 。注意到我们假设 $e \approx N$，从而 $x \lt e^\delta$。再设 $\frac{l}{(\sqrt{i}+\sqrt{j})^2\sqrt{ij}}=N^\theta$。根据第三节的计算，我们有
$$
|y| \lt \frac{l(ip-jq)^2}{(\sqrt{i}+\sqrt{j})^2\sqrt{ijN}} \le e^{2\beta + \theta-\frac{1}{2}}
$$
我们的目标是找到二元多项式 $x_0 (A+y_0) \equiv 0 \pmod e$ 的解，其中 $|x_0| \lt X =e^\delta$，并且 $|y_0| \lt Y = e^{2\beta + \theta =\frac{1}{2}}$

在 Boneh 和 Durfee 的 《 Cryptanalysis of RSA with private key d less than N^0.292》中提到 $X^{2+3\eta}Y^{1+3\eta+3\eta^2} \lt N^{1+3\eta-\epsilon}$，其中 $\eta$ 是固定 $X,Y,N$ 后需要进以步优化的参数。并且其他与 $N$ 无关的数都整合到误差项 $\epsilon $ 中了。

我们注意到我们攻击的渐进边界为，
$$
\delta(2+3\eta)+(2\beta+\theta-\frac{1}{2})(1+3\eta+3\eta^2) \lt 1\cdot (1+3\eta)
$$
等效形式为
$$
3(2\beta+\theta-\frac{1}{2})\tau^2+3(2\beta+\theta+\delta-\frac{3}{2})\tau + (2\beta+\theta+2\delta-\frac{3}{2}) \lt 0
$$
取 $\eta = -\frac{2\beta+\theta+2\delta-\frac{3}{2}}{4\beta+2\theta-1}$，则条件变为
$$
\delta \lt \frac{1}{6}(4\beta+2\theta+5)-\frac{1}{3}\sqrt{(4\beta+2\theta+5)(4\beta+2\theta-1)}
$$
根据 《 Cryptanalysis of RSA with private key d less than N^0.292》，如果 LLL 算法求出的规约基的前两个元素是线性独立的，则我们可以解出 $x_0,y_0$，此时

$(x_0,-y_0+\sqrt{\frac{i}{j}N}+\sqrt{\frac{j}{i}N})$ 就是 $(k,p+q)$，那么 $N$ 就可以分解了。

注意到这里 $\delta$ 的上界大于我们定理 2 中提到的：当 $\frac{1}{4}\lt \beta \le \frac{1}{2}$，$\delta \lt \frac{3}{4}-\beta-\tau$。

注 1. 《 Cryptanalysis of RSA with private key d less than N^0.292》 中使用了子群技术的第二个结果也可以被拓展

2. 《Revisiting Wiener’s attack–new weak keys in RSA》 中的 2.1和3中提到，$l$ 需要很小 $(l \le 4)$，但是我们注意到这样并不能保证条件 $p \gt \frac{2l+2}{4l+1}$ 成立。在我们早些的示例中，$l$ 是 164比特的数，比起 $N$ 其并不能被忽略。事实上，设 $l = N^\iota$ ，则根据 $l$ 的定义我们有 $\iota + \beta \gt \frac{1}{2}$。

5. 总结

这篇论文中，我们讨论了 RSA 中与参数相关的安全问题，我们指数，当 $|ip-jq|=N^\beta \le N^{1/4}$ 时 $N$ 可以被高效的分解。并且我们还考虑了一般情况 $ip−jq$ 以获得其他结果。此外，我们研究了基于 Coppersmith 方法的 Boneh 和 Durfee 攻击，并修正了 Cryptanalysis of RSA with private key d less than N^0.292》 中的界。因此，我们建议，在选择 RSA 密码系统的素因子时，必须保证 $|ip− jq |$ 对于 RSA 密码系统安全性来说不是很小。

---

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可联系QQ 643713081，也可以邮件至 643713081@qq.com