• RSA加密对私钥的攻击比对公钥的攻击难多了，这篇博客主要讲解的就是RSA小私钥攻击，主要讲解如下内容，可能会分成两三篇博客进行记录，也可能只用一篇博客进行记录。

image-20260128223929733

  • 使用小私钥指数的RSA具有一定的风险。尽管在某些场景下，尽可能降低解密成本可能是比较有吸引力的，但如果私钥指数选择得过小，就会存在非常现实且有效的攻击，使得整个密码系统完全不安全。
  • 在任何密码系统中，如果私钥（或秘密密钥）是从一个较小的集合中选取的，那么总是可以通过简单的穷举法搜索出来密钥从而破坏该系统。对RSA而言所有满足d<2ld<2^{l}的私钥指数dd都可以直接通过猜测得到，其中ll取决于当前技术的发展水平。例如，在目前的计算能力下，恢复所有满足d≤260d≤2^{60}的私钥指数是可行的，而对所有满足d≤280d≤2^{80}的私钥指数则是不可行的。
  • 然而，接下来介绍的攻击方法，都能够恢复原大于简单穷举搜索所能覆盖范围的私钥指数。事实上，所有这些攻击都可以有效地攻破私钥指数大小达到NδN^{\delta}（其中δ≥14\delta ≥\frac{1}{4}）的RSA实例。对于一个1024比特的模数，即便是这些攻击中最弱的一种，也已经可以破解私钥指数满足d≤2256d≤2^{256}的RSA实例。
  • 与前面几个攻击不太相同的是，那些攻击通常是在给定公钥以及一个或多个密文的情况下恢复一个或多个明文，然而针对小私钥指数RSA的所有攻击，都是利用密钥等式，仅凭借公钥就通过分解模数来彻底攻破RSA实例。
  • 在以下攻击中，除非另有说明，我们将假设公钥指数和私钥指数都是在模λ(N)\lambda(N)意义下定义的，并且二者都小于λ(N)\lambda(N)。
  • 由如下密钥等式：

ed=1+kλ(N)ed=1+k\lambda(N)

  • 我们可以推出如下一个不等式关系：

0<k=ed−1λ(N)<edλ(N)<min{e,d}0<k=\frac{ed-1}{\lambda(N)}<\frac{ed}{\lambda(N)}<min\{e,d\}

  • 特别地，由于本章关注的是小私钥指数RSA，因此有k<dk<d。当指数是模ϕ(N)\phi(N)定义时，同样的论证也依然成立。

维纳连分数攻击

  • 第一个具有重大意义的RSA小私钥指数攻击就是维纳连分数攻击。仅仅只有公钥(e,N)(e,N)，这个攻击可以使用eN\frac{e}{N}的连分数展开某个渐进分数所活动信息来分解模数。
  • 下面的定理最一般的形式重新描述了维纳连分数攻击，记该定理为定理5.2，定理内容如下：
    • 设N=pqN=pq是一个RSA的模数，设ee是一个有效的公钥指数，并且dd是定义在模λ(N)\lambda(N)下与之对应的私钥指数。
    • 设kk是一个满足密钥等式ed=1+kλ(N)ed=1+k\lambda(N)的整数，g=gcd(p−1,q−1)g=gcd(p-1,q-1)，g0=ggcd(g,k)g_0=\frac{g}{gcd(g,k)}，以及k0=kgcd(k,g)k_0=\frac{k}{gcd(k,g)}
    • 如果私钥指数满足d<pq2(p+q−1)g0k0=N2sg0k0d<\frac{pq}{2(p+q-1)g_0k_0}=\frac{N}{2sg_0k_0}，那么NN能在关于log(N)log(N)和gk\frac{g}{k}的多项式时间内被分解。
    • 证明如下：

题型1 维纳攻击

维纳攻击 题目1

  • 题目来源：

维纳攻击 题目2

  • 题目来源：XYCTF2024
  • 题目附件如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
import gmpy2
import hashlib
from Crypto.Util.number import *

p = getPrime(512)
q = getPrime(512)
d = getPrime(512)
e = gmpy2.invert(d, (p**3 - 1) * (q**3 - 1))
flag = "XYCTF{" + hashlib.md5(str(p + q).encode()).hexdigest() + "}"
print(e)
print(p * q)
# 172005065945326769176157335849432320425605083524943730546805772515111751580759726759492349719668775270727323745284785341119685198468883978645793770975366048506237371435027612758232099414404389043740306443065413069994232238075194102578269859784981454218948784071599231415554297361219709787507633404217550013282713899284609273532223781487419770338416653260109238572639243087280632577902857385265070736208291583497988891353312351322545840742380550393294960815728021248513046077985900158814037534487146730483099151396746751774427787635287611736111679074330407715700153025952858666841328055071403960165321273972935204988906850585454805923440635864200149694398767776539993952528995717480620593326867245714074205285828967234591508039849777840636255379730281105670496110061909219669860172557450779495125345533232776767292561378244884362014224844319802810586344516400297830227894063759083198761120293919537342405893653545157892446163
# 99075185389443078008327214328328747792385153883836599753096971412377366865826254033534293886034828804219037466246175526347014045811852531994537520303063113985486063022444972761276531422538694915030159420989401280012025249129111871649831185047820236417385693285461420040134313833571949090757635806658958193793

拓展维纳攻击

Boneh and Durfee攻击

共模攻击

共私钥攻击