RSA加密算法及攻击方法全面解析

一、RSA基础理论

1. 模运算规则

• 基本运算：
  • (a + b) % p = (a % p + b % p) % p
  • (a - b) % p = (a % p - b % p) % p
  • (a * b) % p = (a % p * b % p) % p
  • (a ^ b) % p = ((a % p)^b) % p
• 结合律、交换律、分配律同样适用模运算

2. 重要数论定理

• 欧几里得算法：计算最大公因子的有效方法
• 欧几里得扩展算法：找到x,y使得c = ax + by
• 费马小定理：若p是素数且a不是p的倍数，则a^(p-1) ≡ 1 mod p
• 欧拉定理：若n,a互素，则a^φ(n) ≡ 1 mod n
• 中国剩余定理：解决同余方程组问题的重要工具

3. RSA原理

基于大整数因数分解难题，核心参数：

• 选择两个大素数p和q
• 计算n = p*q
• 计算φ(n) = (p-1)*(q-1)
• 选择e满足1 < e < φ(n)且gcd(e, φ(n)) = 1
• 计算d ≡ e⁻¹ mod φ(n)
• 公钥：(n, e)，私钥：(n, d)

二、RSA基础攻击方法

1. 暴力分解N

适用条件：N的比特位数小于512位

攻击方法：

• 使用在线数据库(http://factordb.com/)
• 使用yafu工具分解

例题：JarvisOJ - Easy RSA

from Crypto.Util.number import long_to_bytes
import gmpy2

p,q = 13574881, 23781539
n = q*p
e = 23
c = 0xdc2eeeb2782c
phi = (q-1) * (p-1)
d = gmpy2.invert(e,phi)
m = gmpy2.powmod(c,d,n)
print(long_to_bytes(m))

2. 多因子分解

适用条件：N可分解为多个素数因子

原理：
φ(n) = (p1-1)(p2-1)(p3-1)...，加解密过程与常规RSA相同

例题：2018 picoctf: Super Safe RSA 3

from Crypto.Util.number import *
import gmpy2

factors = [2209835647, 3279221983, ..., 2574736709] # 32个素数因子
phi = 1
for x in factors:
    phi *= (x-1)
d = gmpy2.invert(e, phi)
print(long_to_bytes(pow(c, d, n)))

3. 模不互素攻击

适用条件：存在两个公钥的N不互素

原理：计算gcd(n1, n2)可直接获得公共因子

例题：SCTF-RSA2

import gmpy2
from Crypto.Util.number import long_to_bytes

n1 = 20823369114556260762913588844471869725762985812215987993867783630051420241057912385055482788016327978468318067078233844052599750813155644341123314882762057524098732961382833215291266591824632392867716174967906544356144072051132659339140155889569810885013851467056048003672165059640408394953573072431523556848077958005971533618912219793914524077919058591586451716113637770245067687598931071827344740936982776112986104051191922613616045102859044234789636058568396611030966639561922036712001911238552391625658741659644888069244729729297927279384318252191421446283531524990762609975988147922688946591302181753813360518031
n2 = 19083821613736429958432024980074405375408953269276839696319265596855426189256865650651460460079819368923576109723079906759410116999053050999183058013281152153221170931725172009360565530214701693693990313074253430870625982998637645030077199119183041314493288940590060575521928665131467548955951797198132001987298869492894105525970519287000775477095816742582753228905458466705932162641076343490086247969277673809512472546919489077884464190676638450684714880196854445469562733561723325588433285405495368807600668761929378526978417102735864613562148766250350460118131749533517869691858933617013731291337496943174343464943

p1 = gmpy2.gcd(n1, n2)
q1 = n1 // p1
# 后续计算d和解密...

三、公钥指数e相关攻击

1. 小公钥指数攻击

适用条件：e特别小(如e=3)

原理：m = ³√(c + k×N)，通过枚举k寻找整数解

例题：JarvisOJ-Extremely hard RSA

from multiprocessing import Pool
pool = Pool(4)

def calc(j):
    a, b = gmpy2.iroot(cipher + j * N, 3)
    if b == 1:
        print(long_to_bytes(a))
        pool.terminate()

2. Rabin算法攻击(e=2)

例题：

p = 275127860351348928173285174381581152299
q = 319576316814478949870590164193048041239
e = 2

# 计算yp和yq
inv_p = gmpy2.invert(p, q)
inv_q = gmpy2.invert(q, p)

# 计算mp和mq
mp = pow(cipher, (p + 1) // 4, p)
mq = pow(cipher, (q + 1) // 4, q)

# 计算四种可能的解
a = (inv_p * p * mq + inv_q * q * mp) % N
b = N - int(a)
c = (inv_p * p * mq - inv_q * q * mp) % N
d = N - int(c)

四、私钥指数d相关攻击

1. Wiener's Attack

适用条件：d < (1/3)N^(1/4)

原理：利用连分数逼近找到d

例题：2016 HCTF RSA1

def wiener_hack(e, n):
    frac = ContinuedFractions.rational_to_contfrac(e, n)
    convergents = ContinuedFractions.convergents_from_contfrac(frac)
    for (k, d) in convergents:
        if k != 0 and (e * d - 1) % k == 0:
            phi = (e * d - 1) // k
            s = n - phi + 1
            discr = s * s - 4 * n
            if (discr >= 0):
                t = Arithmetic.is_perfect_square(discr)
                if t != -1 and (s + t) % 2 == 0:
                    return d
    return False

2. Boneh and Durfee attack

适用条件：d < N^0.292，比Wiener攻击更强

五、Coppersmith相关攻击

1. Stereotyped Messages Attack

适用条件：e较小且已知m的高位部分

例题：2019强网杯copperstudy-level1

load("coppersmith_py3.sage")

N = 0xa1888c641a05aeb81b3d1686317a86f104791fe1d570a5b11209f45d09ea401d255a70744e7a2d39520e359c23a9f1209ee47f496dbd279e62ee1648b3a277ced8825298274322e0a7a86deea282676310a73b6bb946fc924c34ac6c8784ff559bf9a004c03fb167ef54aaea90ce587f2f3074b40d7f632022ec8fb12e659953
e = 3
m = 0x9e67d3a220a3dcf6fc4742052621f543b8c78d5d9813e69272e65ac676672446e5c88887e8bfdfc92ec87ec74c16350e6b539e3bd910b000000000000000000
c = 0x93145ece45f416a11e5e9475518f165365456183c361500c2f78aff263028c90f20b7d97205f54e21f3bcc8a556b457889fde3719d0a0f9c9646f3f0d0a1e4bee0f259f023168fe8cc0511848c1635022fcc20b6088084585e2f8055a9d1b1d6bdb228087900bf7c6d42298f8e45c451562c816e2303990834c94e580bf0cbd1

ZmodN = Zmod(N)
P.<x> = PolynomialRing(ZmodN)
f = (m + x)^e - c
roots = f.small_roots(X=2^kbits, beta=0.4)

2. Factoring with High Bits Known

适用条件：已知p或q的高位部分

例题：2019强网杯copperstudy-level2

n = 0x241ac918f708fff645d3d6e24315e5bb045c02e788c2b7f74b2b83484ce9c0285b6c54d99e2a601a386237d666db2805175e7cc86a733a97aeaab63486133103e30c1dca09741819026bd3ea8d08746d1d38df63c025c1793bdc7e38d194a30b492aadf9e31a6c1240a65db49e061b48f1f2ae949ac9e7e0992ed24f9c01578d
p_fake = 0x2c1e75652df018588875c7ab60472abf26a234bc1bfc1b685888fb5ded29ab5b93f5105c1e9b46912368e626777a873200000000000000000000000000000000

pbits = 1024
kbits = 130
pbar = p_fake & (2^pbits-2^kbits)
PR.<x> = PolynomialRing(Zmod(n))
f = x + pbar
x0 = f.small_roots(X=2^kbits, beta=0.4)[0]
print(hex(int(x0 + pbar)))

六、选择明文/密文攻击

1. Padding Attack

适用条件：加密的Padding可控

例题：

def getM2(a,b,c1,c2,n,e):
    a3 = pow(a,e,n)
    b3 = pow(b,e,n)
    first = c1-a3*c2+2*b3
    second = e*b*(a3*c2-b3)
    third = second*gmpy2.invert(first,n)
    fourth = (third+b)*gmpy2.invert(a,n)
    return fourth % n

e=0x3
a=1
b=-1
c1=0x3aa5058306947ff46b0107b062d75cf9e497cdb1f120d02eaeca30f76492c550
c2=0x6a645739f25380a5e5b263ff5e5b4b9324381f6408a11fdaab0488209145fb3e
n=0xb33aebb1834845f959e05da639776d08a344abf098080dc5de04f4cbf4a1001d
m = getM2(a,b,c1,c2,n,e)-padding2

2. RSA LSB Oracle Attack

适用条件：可以选择密文并泄露最低位

攻击脚本：

def brute_flag(encrypted_flag, n, e):
    # 二分逼近算法实现
    while flag_upper_bound > flag_lower_bound + 1:
        ciphertext = (ciphertext * pow(2, e, n)) % n
        # 根据返回的奇偶性调整边界
        # ...
    return flag_upper_bound

七、实用工具集

1. OpenSSL命令

• 生成私钥：openssl genrsa -out prikey.pem
• 查看私钥：openssl rsa -in prikey.pem -text -modulus
• 提取公钥：openssl rsa -in prikey.pem -pubout -out pubkey.pem
• 加密：openssl rsautl -encrypt -in file.plain -inkey pubkey.pem -pubin -out file.enc
• 解密：openssl rsautl -decrypt -inkey prikey.pem -in file.enc

2. 其他工具

• RsaCtfTool：多功能RSA攻击工具

  ./RsaCtfTool.py --publickey ./key.pub --private
  ./RsaCtfTool.py --publickey ./key.pub --uncipherfile filename
  

• yafu：强大的因数分解工具
• sage数学工具：实现各种高级攻击算法

八、综合防御建议

1. 使用足够大的密钥长度(至少2048位)
2. 选择适当的e值(通常65537)
3. 确保随机数生成器的质量
4. 实现正确的填充方案(如OAEP)
5. 防止侧信道攻击
6. 定期更新密钥

通过全面理解这些攻击方法和防御措施，可以更好地评估RSA实现的安全性并有效应对各种威胁。