RSA题型汇总

RSA是每个新手都要跨越的第一道坎，相信你也经常遇见奇奇怪怪的RSA题型，这里记录了我遇见的各种题型，难度不分先后，随时更新。

dp泄露(dp=d mod p-1)

分析：
$\because dp\equiv d \mod p-1$
$\therefore edp\equiv ed\mod p-1$
$\because ed \equiv 1 \mod (p-1)(q-1)$
$\therefore edp+k_1(p-1) = 1+k_2(p-1)(q-1)$
$\therefore edp=(p-1)[k_1+k_2(q-1)]+1$
$\because dp<p-1$
$\therefore 令A=k_1+k_2(q-1)，有e>A$
$\therefore A\in (0,e)$
$\because 转换得p=\frac{edp-1}{A}+1$
$\therefore 遍历A（此时A不等于0）\in(1,e)，找到能整除的A，进而计算出p$
代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
from Crypto.Util.number import *
#已知量
dp= 
n = 
c = 
e = 

x = e*dp-1
for i in range(1,e):
    if x % i == 0:
        p_us = x//i +1
        if n % p_us == 0:
            p = p_us
            break

#print(p)
q=n//p
phi=(p-1)*(q-1)
d=inverse(e,phi)
m=pow(c,d,n)
ans=long_to_bytes(m)
print(ans)

明文爆破

已知： $n,e,c_list(每个明文字符单独加密的结果)$
分析： 使用string.printable来表示所有可打印字符，逐个加密每个字符来对照密文。
代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
from Crypto.Util.number import *
import string
#爆破

n = 
c_list = 
ans = ''
for i in range(len(c_list)):
    for j in string.printable:
        if pow(ord(j), e, n) == c_list[i]:
            print(f"Found char: {j}")
            ans += j
            break
print(ans)

共模攻击

介绍： 使用不同的e（如e1，e2）来加密同一段明文m，并且使用相同的模n。
分析：
此时已知两个不同的e1,e2，所以不需要再求d了，这里使用扩展欧几里得算法，求出$k_1e_1+k_2e_2 = 1$（若此时e1，e2不互素，也一般有较小的公因数，开小次方即可）。
所以$c_1^{k_1}c_2^{k_2} \equiv m^{k_1e_1+k_2e_2} \equiv m \mod n$
代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
#共模攻击（m相同，n相同，e不同）
from Crypto.Util.number import *
import gmpy2
c1= 
c2= 
e1= 
e2= 
n= 

_ , k1 , k2 = gmpy2.gcdext(e1,e2)
m = pow(c1,k1,n)*pow(c2,k2,n) % n
ans = long_to_bytes(m)
print(ans)

公共因子攻击

原本觉得太简单是不想放的，但是后来考虑到许多题都是使用了类似的思想，所以本题型的重点是学会利用 公因数 求解一系列问题。这里以最简单的RSA为例。
问题： 

1
2
3
4
5
6
#已知n1,n2,e,c求m
n1 = p*q1
n2 = p*q2
e = 
m = bytes_to_long(flag)
c = pow(m,e,n1)

分析：
可以看出$p$是$n_1,n_2$的公共因子，因此可以通过求两者的最大公因数来求$p$
$即p=gcd(n_1,n_2)$
代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#公共因子攻击
from Crypto.Util.number import *
#已知量
n1= 
n2=
c = 
e =

p=GCD(n1,n2)
q1=n1//p
phi=(p-1)*(q1-1)
d=inverse(e,phi)
m=pow(c,d,n1)
ans=long_to_bytes(m)
print(ans)

低加密指数攻击（e很小）

1.单组$（e，n，c）$

分析： 不用多说，这种题一般只需要直接开方或者小范围爆破

2.多组$（e，n_i，c_i）$（也叫做广播攻击）

分析：

  • 思路一： 可以先分析各个$n$之间是否有公共因子，如果有，可以使用上边的公共因子攻击。
  • 思路二： 使用中国剩余定理（CRT），通过中国剩余定理，可以更加逼近正确的$n$。中国剩余定理求出来一组$(n，c)$，此时攻击方法便和单组的一样了。
    代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#中国剩余定理
from Crypto.Util.number import *
import gmpy2

n_list=[...]
c_list=[...]
e = 

n = 1
n_list_2 = []
n_list_2_inv = []
for i in n_list:
    n *= i
  
for i in n_list:
    tmp = n // i
    tmp_inv = inverse(tmp,i)
    n_list_2.append(tmp)
    n_list_2_inv.append(tmp_inv)
  
c = 0
for i in range(len(c_list)):
    c += c_list[i]*n_list_2[i]*n_list_2_inv[i] % n
c = c % n

m = gmpy2.iroot(c,e)[0]
'''
for k in range(1000) #自定义爆破k的范围
	c = c + k*n
	t = gmpy2.iroot(c,e)
	if t[1]:
		m = t[0]
'''
ans = long_to_bytes(m)
print(ans)

p,q相近

已知： $n,c$，且p，q是十分接近的素数，或者是相邻的素数
解法：

  • 一、 factordb、yafu直接分解n
  • 二、 先对n开平方得到大概值，再使用gmpy2中的next_prime()来获取q，此时p=n//q
    代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
from Crypto.Util.number import *
import gmpy2

n = ...
c = ...
e = 65537

q = gmpy2.iroot(n,2)[0]
q = gmpy2.next_prime(q)
p = n // q
#print(p*q)
phi = (p-1)*(q-1)
d = gmpy2.invert(e, phi)
m = pow(c, d, n)
flag = long_to_bytes(ans)
print(flag)

Coppersmith攻击

介绍： Coppersmith方法基于LLL算法求多项式小根，求“已知某些二进制位，求剩余位”问题，
功能： 假如有一个$e$阶的多项式$f$，则有

  • 在模$n$下，可以用$O(\log n)$的算法求出$n^{\frac1e}$以内的根
  • 给定$\beta$，快速求出模$b$下的小根（其中$b\geq n^\beta$，且$b$是$n$的因数）

实现： 在$Sagemath$中使用small_roots()方法实现。

P高位泄露，求低位

分析： 利用Coppersmith，此时$p=pHigh+x$，则有$\frac 1e=1$ ,
令$p\equiv 0 \mod b$ ，其中$n^\beta \leq b \leq n$ ,
若想$b=p$，则需要$p\geq n^\beta$ ，由于RSA中$p,q$ 一般位数相近，都在$n^{0.5}$，所以一般取$\beta \in [0.1,0.4]$。

据说$p$的泄露位数$\frac{pHigh.nbits()}{p.nbits()}$要大于0.56左右才能解出，对512bits的$p$来说需要288位已知，对1024bits的$p$来说要576位左右。

代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
#sage
n=
p_high=
pbits=
kbits=pbits-p_high.nbits()  #小根位数

R.<x> = PolynomialRing(Zmod(n))
p_high <<= kbits
p = p_high + x 
roots = p.small_roots(X=2^kbits,beta=0.4)

p = p_high + int(roots[0])
q = n // p

例题

（鹤城杯 2021 babyrsa）
题目：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
from Crypto.Util.number import getPrime, bytes_to_long
from secret import flag

p = getPrime(1024)
q = getPrime(1024)
n = p * q
e = 65537
hint1 = p >> 724
hint2 = q % (2 ** 265)
ct = pow(bytes_to_long(flag), e, n)
print(hint1)
print(hint2)
print(n)
print(ct)

"""
1514296530850131082973956029074258536069144071110652176122006763622293335057110441067910479
40812438243894343296354573724131194431453023461572200856406939246297219541329623
21815431662065695412834116602474344081782093119269423403335882867255834302242945742413692949886248581138784199165404321893594820375775454774521554409598568793217997859258282700084148322905405227238617443766062207618899209593375881728671746850745598576485323702483634599597393910908142659231071532803602701147251570567032402848145462183405098097523810358199597631612616833723150146418889589492395974359466777040500971885443881359700735149623177757865032984744576285054725506299888069904106805731600019058631951255795316571242969336763938805465676269140733371287244624066632153110685509892188900004952700111937292221969
19073695285772829730103928222962723784199491145730661021332365516942301513989932980896145664842527253998170902799883262567366661277268801440634319694884564820420852947935710798269700777126717746701065483129644585829522353341718916661536894041337878440111845645200627940640539279744348235772441988748977191513786620459922039153862250137904894008551515928486867493608757307981955335488977402307933930592035163126858060189156114410872337004784951228340994743202032248681976932591575016798640429231399974090325134545852080425047146251781339862753527319093938929691759486362536986249207187765947926921267520150073408188188
"""

分析：
已知p的高1024-724 = 300位，以及q的低265位。已知的p的高300位远小于576位，因此不能直接用coppersmith定理，需要找到更多的已知位数。
由$n = pq$得，$n\equiv p_lq_l\mod 2^{265}$
所以得，$p_l \equiv nq_l^{-1} \mod 2^{265}$
求出了p的低265位，此时已知265+300 = 565，很接近576位，但是还是有些距离，进行几位爆破。
代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#sage
from Crypto.Util.number import *
n = 21815431662065695412834116602474344081782093119269423403335882867255834302242945742413692949886248581138784199165404321893594820375775454774521554409598568793217997859258282700084148322905405227238617443766062207618899209593375881728671746850745598576485323702483634599597393910908142659231071532803602701147251570567032402848145462183405098097523810358199597631612616833723150146418889589492395974359466777040500971885443881359700735149623177757865032984744576285054725506299888069904106805731600019058631951255795316571242969336763938805465676269140733371287244624066632153110685509892188900004952700111937292221969
p_high = 1514296530850131082973956029074258536069144071110652176122006763622293335057110441067910479
q_low = 40812438243894343296354573724131194431453023461572200856406939246297219541329623
c = 19073695285772829730103928222962723784199491145730661021332365516942301513989932980896145664842527253998170902799883262567366661277268801440634319694884564820420852947935710798269700777126717746701065483129644585829522353341718916661536894041337878440111845645200627940640539279744348235772441988748977191513786620459922039153862250137904894008551515928486867493608757307981955335488977402307933930592035163126858060189156114410872337004784951228340994743202032248681976932591575016798640429231399974090325134545852080425047146251781339862753527319093938929691759486362536986249207187765947926921267520150073408188188
e = 65537
mod_num = 2^265

p_low = inverse(q_low,mod_num)*n % mod_num

pbits = 1024
R.<x> = PolynomialRing(Zmod(n))

for i in range(2^6):
	#这里对p_high往低几位进行爆破，当然也可以对p_low往高几位进行爆破，注意kbits的变化即可。
    p_high1 = p_high << 6
    p_high1 = p_high1 + i
    kbits = pbits - p_high1.nbits()
    p_high1 <<= kbits
    p_bar = p_high1 + p_low
    kbits = kbits - p_low.nbits()

    p = p_bar + x*mod_num  #因为低位以及知道，x是中间的数，因此向左移265位
    p = p.monic()          #转换成首一多项式，small_roots只能处理首一多项式
    print(i)
    roots = p.small_roots(X = 2^kbits,beta = 0.4)
    if roots:
        p = p_bar + int(roots[0])*mod_num
        print(p)
        if n%p == 0:
            q = n // p
            phi = (p-1)*(q-1)
            d = inverse(e,phi)
            m = pow(c,d,n)
            ans = long_to_bytes(m)
            print(ans)

m高位泄露，求低位

分析： 利用coppersmith方法，可以构造$(m_{high}+x)^e-c\equiv 0 \mod n$ ，此时有$b \geq n^{\beta}$ ，因此取$\beta = 1$ 。
代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#sage
c = 
e = 
m_high =
mbits =

kbits = mbits - m_high.nbits()
m_high <<= kbits
R.<x> = PolynomialRing(Zmod(n))
f = (m_high + x)^e - c
f=f.monic()
roots = f.small_roots(X = 2 ^ kbits,beta = 1)
m = m_high + roots[0]
print(m)

dp高位泄露

已知： $d_{ph},e,n,c$，求$dp$，从而求明文
分析：
这里分情况讨论，分别记为 $e$较大的情况 和 $e$较小的情况。

  • 1.$e$较大：使用二元coppersmith求解，可以求出$d_p$，之后就利用费马小定理，得到$a^{e\cdot d_p}\equiv a\mod p$，所以$p=gcd(a^{e\cdot d_p}-a,n)$
  • 2.$e$较小： 因为$e\cdot d_p\equiv 1\mod (p-1)$，所以有$ed_p=k(p-1)+1$，即$ed_p+k-1\equiv 0\mod p(由d_p<p-1可得k\in(1,e))$。令$tmp = e^{-1}\mod n$，则$tmp\cdot ed_p+tmp(k-1)\equiv 0\mod p$，即$d_p+tmp(k-1)\equiv 0 \mod n$。对$k$进行爆破，利用coppersmith定理求$d_p$低位
    代码：
    1.$e$较大：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
from Crypto.Util.number import *
import gmpy2
import itertools

def small_roots(f, bounds, m=1, d=None):
    if not d:
        d = f.degree()
        print(d)
    R = f.base_ring()
    N = R.cardinality()
    f /= f.coefficients().pop(0)
    f = f.change_ring(ZZ)
    G = Sequence([], f.parent())
    for i in range(m + 1):
        base = N ^ (m - i) * f ^ i
        for shifts in itertools.product(range(d), repeat=f.nvariables()):
            g = base * prod(map(power, f.variables(), shifts))
            G.append(g)
    B, monomials = G.coefficient_matrix()
    monomials = vector(monomials)
    factors = [monomial(*bounds) for monomial in monomials]
    for i, factor in enumerate(factors):
        B.rescale_col(i, factor)
    B = B.dense_matrix().LLL()
    B = B.change_ring(QQ)
    for i, factor in enumerate(factors):
        B.rescale_col(i, 1 / factor)
    H = Sequence([], f.parent().change_ring(QQ))
    for h in filter(None, B * monomials):
        H.append(h)
        I = H.ideal()
        if I.dimension() == -1:
            H.pop()
        elif I.dimension() == 0:
            roots = []
            for root in I.variety(ring=ZZ):
                root = tuple(R(root[var]) for var in f.variables())
                roots.append(root)
            return roots
    return []

n = 
c = 
e = 
#hint=dp >> kbits
hint = 
kbits = 
leak = hint << kbits

R.<x,y> = PolynomialRing(Zmod(n))
f = e * (leak + x) + (y - 1)
res = small_roots(f,(2^kbits,2^kbits),m=1,d=4)   #求不出时调整m，d的参数值
for root in res:
    print(root)
    dp_low = root[0]
    dp = leak + dp_low
    tmp = pow(2,e*dp,n) - 2
    p = gmpy2.gcd(tmp,n)
    q = n // p
    d = inverse(e,(p-1)*(q-1))
    m = pow(c,d,n)
    print(long_to_bytes(m))

2.$e$较小

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#sage
from Crypto.Util.number import *
dp0 = 
e = 
n = 
kbits = 

P.<x> = PolynoimalRing(Zmod(n))
tmp = inverse(e,n)
for k in range(1,e):
	f = dp0 << kbits + x + tmp * (k - 1)
	root = small_roots(X = 2^kbits,beta = 0.4)[0]
	if root:
		dp = dp0 << kbits + root
		x = e*dp - 1
		for i in range(1,e):
			if x % i == 0:
		        p_us = x//i +1
		        if n % p_us == 0:
		            p = p_us
		            break
		if p<0:
			continue
		else:
			#print(p)
			q=n//p
			phi=(p-1)*(q-1)
			d=inverse(e,phi)
			m=pow(c,d,n)
			ans=long_to_bytes(m)
			print(ans)
			break

参考： RSA | Lazzaro

Study
#CTF
RSA题型汇总
http://ramoor.github.io/2025/04/07/RSA题型汇总/
作者
Ramoor
发布于
2025年4月7日
许可协议