RSA 攻击脚本使用手册

环境依赖

pip install gmpy2 pycryptodome libnum rsa

库	用途
gmpy2	高精度运算、模逆 invert、开根 iroot、GCD
Crypto.Util.number	long_to_bytes / bytes_to_long
libnum	n2s / s2n 数字与字符串互转
rsa	PEM 密钥文件的直接解密

---

RSA 基础回顾

n = p * q
φ = (p-1) * (q-1)
e * d ≡ 1 (mod φ)
c ≡ m^e (mod n)
m ≡ c^d (mod n)

dp ≡ d (mod p-1)
dq ≡ d (mod q-1)

---

攻击场景速查表

已知条件	对应攻击类型	核心公式
p, q, e, c	标准解密	d = invert(e, (p-1)*(q-1))
e, n, dp, c	dp 泄露	p = (dp*e-1)/k + 1, 遍历 k
p, q, dp, dq, c	CRT 解密	m = ((mp-mq)*I%p)*q + mq
同 n, 两组 (e1,c1) (e2,c2)	共模攻击	e1s1+e2s2=1
e 极小, m^e < n	低加密指数	m = iroot(c, e)
多个 n 不互素	公因数碰撞	p = gcd(n_i, n_j)
n, c 已知, e 未知	e 爆破	遍历 e

---

场景一：已知 p, q, e, c（标准解密）

原理：

φ = (p-1) * (q-1)
d = invert(e, φ)
m = pow(c, d, n)

代码：

from gmpy2 import *
from Crypto.Util.number import *

e = 65537
p = 11104861498641160020551133747582851050482827883841239117180799157472078278661946047575808556331157873693827396366774529894387508349540416345196575506278923
q = 11679509046055093484387585536769973960915016129595089156764897709796981174994469835617477280580153684696296947700908005372625963068761884667061288424062299
n = p * q
phi = (p - 1) * (q - 1)

c = 107231634326770221094746500662759833069538826889622113541963502019198110108069323378894690079642183610095239954706951543119631076510963730112159650609957643624113005383712711607499848326073565499855248813568303969304750726010325092933463405916555840861079556487402413769882136752563441454755381891094020751935

d = invert(e, phi)
M = pow(c, d, n)
print(long_to_bytes(M))

---

场景二：已知 e, n, dp, c（dp 泄露攻击）

原理：

dp ≡ d (mod p-1)
dp * e = 1 + k * (p-1)
遍历 k ∈ [1, e)，当 (dp*e-1) % k == 0 时：
  p = (dp*e-1) // k + 1
验证 n % p == 0 即得 p

代码：

e = 65537
n = 248254007851526241177721526698901802985832766176221609612258877371620580060433101538328030305219918697643619814200930679612109885533801335348445023751670478437073055544724280684733298051599167660303645183146161497485358633681492129668802402065797789905550489547645118787266601929429724133167768465309665906113
dp = 905074498052346904643025132879518330691925174573054004621877253318682675055421970943552016695528560364834446303196939207056642927148093290374440210503657
c = 140423670976252696807533673586209400575664282100684119784203527124521188996403826597436883766041879067494280957410201958935737360380801845453829293997433414188838725751796261702622028587211560353362847191060306578510511380965162133472698713063592621028959167072781482562673683090590521214218071160287665180751

import gmpy2
for i in range(1, e):
    if (dp * e - 1) % i == 0:
        p = (dp * e - 1) // i + 1
        if n % p == 0:
            q = n // p
            phi = (p - 1) * (q - 1)
            d = gmpy2.invert(e, phi)
            M = pow(c, d, n)
            print(bytes.fromhex(hex(M)[2:]))

---

场景三：已知 p, q, dp, dq, c（CRT 快速解密）

原理（中国剩余定理加速）：

mp = c^dp mod p
mq = c^dq mod q
I = invert(q, p)
m = ((mp - mq) * I mod p) * q + mq

CRT 公式使解密速度比直接 pow(c, d, n) 快约 4 倍（模数更小）。

代码：

p = 8637633767257008567099653486541091171320491509433615447539162437911244175885667806398411790524083553445158113502227745206205327690939504032994699902053229
q = 12640674973996472769176047937170883420927050821480010581593137135372473880595613737337630629752577346147039284030082593490776630572584959954205336880228469
dp = 6500795702216834621109042351193261530650043841056252930930949663358625016881832840728066026150264693076109354874099841380454881716097778307268116910582929
dq = 783472263673553449019532580386470672380574033551303889137911760438881683674556098098256795673512201963002175438762767516968043599582527539160811120550041
c = 24722305403887382073567316467649080662631552905960229399079107995602154418176056335800638887527614164073530437657085079676157350205351945222989351316076486573599576041978339872265925062764318536089007310270278526159678937431903862892400747915525118983959970607934142974736675784325993445942031372107342103852

import gmpy2
I = gmpy2.invert(q, p)
mp = pow(c, dp, p)
mq = pow(c, dq, q)

m = (((mp - mq) * I) % p) * q + mq

import binascii
from Crypto.Util.number import long_to_bytes
print(long_to_bytes(m))
print(binascii.unhexlify(hex(m)[2:]))
print(hex(m))

---

场景四：共模攻击 (Common Modulus Attack)

适用条件：

• 两组公钥 (e1, n) 和 (e2, n) 共享同一个 n
• gcd(e1, e2) = 1
• 明文 m 相同

原理：

e1 * s1 + e2 * s2 = gcd(e1, e2) = 1（扩展欧几里得）
m = c1^s1 * c2^s2 mod n

若 s1 为负，使用 c1^(-s1) = invert(c1, n)^(-s1) 替代。

步骤一：从 PEM 公钥文件中提取 n 和 e：

from Crypto.PublicKey import RSA
from Crypto.Util.number import *

f1 = open("publickey1.pem", "rb").read()
f2 = open("publickey2.pem", "rb").read()
c1 = open("cipher1.txt", "rb").read()
c2 = open("cipher2.txt", "rb").read()

pub1 = RSA.importKey(f1)
pub2 = RSA.importKey(f2)
n1 = pub1.n
e1 = pub1.e
n2 = pub2.n
e2 = pub2.e
c1 = bytes_to_long(c1)
c2 = bytes_to_long(c2)

print("n1 =", n1)
print("e1 =", e1)
print("c1 =", c1)
print("n2 =", n2)
print("e2 =", e2)
print("c2 =", c2)

步骤二：执行共模攻击：

import libnum
from gmpy2 import invert

def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = egcd(b % a, a)
        return (g, x - (b // a) * y, y)

def main():
    n = 103606706829811720151309965777670519601112877713318435398103278099344725459597221064867089950867125892545997503531556048610968847926307322033117328614701432100084574953706259773711412853364463950703468142791390129671097834871371125741564434710151190962389213898270025272913761067078391308880995594218009110313
    c1 = 100156221476910922393504870369139942732039899485715044553913743347065883159136513788649486841774544271396690778274591792200052614669235485675534653358596366535073802301361391007325520975043321423979924560272762579823233787671688669418622502663507796640233829689484044539829008058686075845762979657345727814280
    c2 = 86203582128388484129915298832227259690596162850520078142152482846864345432564143608324463705492416009896246993950991615005717737886323630334871790740288140033046061512799892371429864110237909925611745163785768204802056985016447086450491884472899152778839120484475953828199840871689380584162839244393022471075
    e1 = 3247473589
    e2 = 3698409173

    s = egcd(e1, e2)
    s1 = s[1]
    s2 = s[2]

    if s1 < 0:
        s1 = -s1
        c1 = invert(c1, n)
    elif s2 < 0:
        s2 = -s2
        c2 = invert(c2, n)

    m = pow(c1, s1, n) * pow(c2, s2, n) % n
    m_int = int(m)
    print(libnum.n2s(m_int))

if __name__ == '__main__':
    main()

---

场景五：低加密指数攻击 (Low Exponent)

适用条件：

• e 很小（如 3, 17, 65537）
• m^e < n（模运算实际未生效）
• 可能给多组密文而未给 n

原理：

当 m^e < n 时，c = m^e（无模约简），直接：

m = iroot(c, e)

代码：

n = 26287684934288536371438030224508784042871268975402791015134838900290249602701092702492594931306572692868654436714501196060619149020850402317982203575250568283872182497606239389480186694649979877566740647822434500023605871516831662099415987589808614777313595453727243531121031390104059097782466650186291076316486240197369759537327997880644540629964227584070506981319936888159712058406052247256554081989035415864476278146328967410452695134756792942103209740186339835071828587981271027235499355298543650516643100665039796305276163706693873611519506528344413021878980171629732211592839945004800782325172828561339662590291
c_list = [220679552464923590542169148982631...]

from Crypto.Util.number import *
from gmpy2 import *
for e in range(1000, 2001):
    for c in c_list:
        print(long_to_bytes(iroot(c, e)[0]), end='')

注意：iroot(c, e) 返回 (根, 是否精确) 元组，[0] 取结果。

---

场景六：多 n 不互素攻击（公因数碰撞）

虽然脚本名叫“低加密指数广播攻击”，但实际是通过 GCD 找不互素的 n。

适用条件：

• 多组 (n, c) 对
• 某两个 n 共享素数因子 p（gcd(n_i, n_j) ≠ 1）

原理：

p = gcd(n_i, n_j)
q = n_i // p
d = invert(e, (p-1)*(q-1))
m = pow(c_i, d, n_i)

代码：

import gmpy2
import libnum

e = 65537

n0 = int('63306931765261881888912008095340470978772999620205174857271016152744820165330787864800482852578992473814976781143226630412780924144266471891939661312715157811674817013479316983665960087664430205713509995750877665395721635625035356901765881750073584848176491668327836527294900831898083545883834181689919776769', 5)
c0 = int('11273036722994861938281568979042367628277071611591846129102291159440871997302324919023708593105900105417528793646809809850626919594099479505740175853342947734943586940152981298688146019253712344529086852083823837309492466840942593843720630113494974454498664328412122979195932862028821524725158358036734514252', 5)
n1 = int('63306931765261881888912008095340470978772999620205174857271016152744820165330787864800482852578992473814976781143226630412780924144266471891939661312715157811674817013479316983665960087664430205713509995750877665395721635625035356901765881750073584848176491668327836527294900831898083545883834181689919776769', 5)
c1 = int('42478690444030101869094906005321968598060849172551382502632480617775125215522908666432583017311390935937075283150967678500354031213909256982757457592610576392121713817693171520657833496635639026791597219755461854281419207606460025156812307819350960182028395013278964809309982264879773316952047848608898562420', 5)

n = [n0, n1]
c = [c0, c1]

for i in range(len(n)):
    for j in range(len(n)):
        if i != j:
            if gmpy2.gcd(n[i], n[j]) != 1:
                print(i, j)
                p = gmpy2.gcd(n[i], n[j])
                print("p = ", p)
                q = n[i] // p
                print("q = ", q)
                d = gmpy2.invert(e, (p - 1) * (q - 1))
                print("d = ", d)
                m = pow(c[i], d, n[i])
                print("m = ", m)

print(libnum.n2s(int(m)))

注意：输入中的 int('xxxx', 5) 表示 n 和 c 是以五进制字符串形式给出的，需要转换为十进制。

---

场景七：e 未知爆破

适用条件：

• 已知 n, c, p, q（或能分解 n）
• e 未知但范围可控

原理：

已知 p, q 可算出 φ，遍历 e 使 gcd(e, φ) == 1，解密后检查是否含 flag 特征。

代码：

from base64 import b64encode as b32encode
from gmpy2 import invert, gcd, iroot
from Crypto.Util.number import *
from binascii import a2b_hex, b2a_hex
import random

e = 65537
p = 99855353761764939308265951492116976798674681282941462516956577712943717850048051273358745095906207085170915794187749954588685850452162165059831749303473106541930948723000882713453679904525655327168665295207423257922666721077747911860159181041422993030618385436504858943615630219459262419715816361781062898911
q = 135283423427545651023916134156519717109709399113553907832988770259402226695880524199087896377303631866790192008529658716376684328032075836094156150811025163336681163420875451747389868549203081743561907379260240665153166927504059379076555558704275659133135906827306189040804323574468819553401905127999523676067
n = p * q
phi = (p - 1) * (q - 1)

c = 12641635617803746150332232646354596292707861480200207537199141183624438303757120570096741248020236666965755798009656547738616399025300123043766255518596149348930444599820675230046423373053051631932557230849083426859490183732303751744004874183062594856870318614289991675980063548316499486908923209627563871554875612702079100567018698992935818206109087568166097392314105717555482926141030505639571708876213167112187962584484065321545727594135175369233925922507794999607323536976824183162923385005669930403448853465141405846835919842908469787547341752365471892495204307644586161393228776042015534147913888338316244169120

for e in range(100000):
    if gcd(e, phi) == 1:
        d = invert(e, phi)
        M = pow(c, d, n)
        if b'CTF' in long_to_bytes(M):
            print(long_to_bytes(M))
print('down')

CTF 可根据实际 flag 格式替换为 flag、moectf 等。

---

辅助脚本

计算私钥 d

import gmpy2

q = 1325465431
p = 152317153
e = 65537

d = gmpy2.invert(e, (p - 1) * (q - 1))
print(d)

十六进制大数转十进制

k = 0x2227e398fc6ffcf5159863a345df85ba50d6845f8c06747769fee78f598e7cb1bcf875fb9e5a69ddd39da950f21cb49581c3487c29b7c61da0f584c32ea21ce1edda7f09a6e4c3ae3b4c8c12002bb2dfd0951037d3773a216e209900e51c7d78a0066aa9a387b068acbd4fb3168e915f306ba40

k_str = hex(k)
k10 = int(k_str, 16)
print(k10)

long_to_bytes 正反向遍历

当只拿到一个大整数，需要在正负方向搜索含 flag 的值：

from math import sqrt
from Crypto.Util.number import long_to_bytes

x = 2949512038986137685036398826630440282631884919219498674716380193882113

# 递增查找
for i in range(9999999999999999999999999999999999):
    x = x + i
    if b'ctf{' in long_to_bytes(x):
        print(long_to_bytes(x))

from Crypto.Util.number import long_to_bytes

x = 2949512038986137685036398826630440282631884919219498674716380193882113

# 递减查找
for i in range(9999999999999999999999999999999999):
    x = x - i
    if b'ctf{' in long_to_bytes(x):
        print(long_to_bytes(x))

---

PEM 公钥解析与 rsa 库解密

从 PEM 文件提取参数

from Crypto.PublicKey import RSA
from Crypto.Util.number import *

f1 = open("publickey1.pem", "rb").read()
f2 = open("publickey2.pem", "rb").read()
c1 = open("cipher1.txt", "rb").read()
c2 = open("cipher2.txt", "rb").read()

pub1 = RSA.importKey(f1)
pub2 = RSA.importKey(f2)
n1 = pub1.n
e1 = pub1.e
n2 = pub2.n
e2 = pub2.e
c1 = bytes_to_long(c1)
c2 = bytes_to_long(c2)

print("n1 =", n1)
print("e1 =", e1)
print("c1 =", c1)
print("n2 =", n2)
print("e2 =", e2)
print("c2 =", c2)

完整私钥解密

当已拥有完整私钥参数 (n, e, d, p, q) 且密文是二进制格式时：

import rsa
import gmpy2

e = 65537
n = 86934482296048119190666062003494800588905656017203025617216654058378322103517
p = 285960468890451637935629440372639283459
q = 304008741604601924494328155975272418463
phi = (p - 1) * (q - 1)
d = gmpy2.invert(e, phi)

key = rsa.PrivateKey(n, e, d, q, p)

with open("flagenc.txt", "rb") as f:
    f = f.read()
    print(rsa.decrypt(f, key))

---

相关工具

本目录旁边的 工具/ 目录内有：

工具	用途
RSATool2	Windows 图形化 RSA 攻击辅助工具
yafu	大整数分解，yafu "factor(@)" -batchfile n.txt
jwt_GUI	JWT 相关工具

yafu 用法示例：

# 将 n 写入文件
echo "n=你的n值" > n.txt
# 运行分解
yafu "factor(@)" -batchfile n.txt

---

快速决策流程

收到 RSA 题目
│
├─ 有 .pem 文件？
│   └─ 先用 PEM 公钥解析代码提取 n, e
│
├─ 已知 p, q？
│   ├─ 只有 p, q, e, c → 场景一（标准解密）
│   ├─ 还有 dp, dq → 场景三（CRT 解密）
│   └─ 缺 e → 场景七（e 爆破）
│
├─ 已知 n, dp, c？
│   └─ 场景二（dp 泄露）
│
├─ 同一 n 有两组 (e, c)？
│   └─ 场景四（共模攻击）
│
├─ 多个 (n, c) 对？
│   ├─ e 相同且很小 → 场景五（低加密指数）
│   └─ n 可能不互素 → 场景六（公因数碰撞）
│
├─ 只有 n 和 c，e=65537？
│   └─ 尝试用 yafu 分解 n
│
└─ 无头绪？
    └─ 查 factorDB，或用 sage 尝试维纳攻击