大二下学期有学信息安全数学基础课程，分数考的好低(心痛😭

要学密码学吗，没想好，或许先试试吧

加密原理

生成密钥：

选择两个大素数p和q(通常1024位或更长)，计算它们的乘积n=p*q，n称为模数，是公钥和私钥共有的部分

计算n的欧拉函数值 ϕ(n)=(p-1)(q-1)

选择公钥指数e,满足1<e<ϕ(n)且e 与 ϕ(n)互质

计算私钥指数d，d是e关于模 ϕ(n)的乘法逆元，d≡e−1(modϕ(n))

密钥对：公钥(e,n) 私钥(d,n)

加密 (用公钥 (e,n))：
对明文m（需转换为整数且 m<n），计算密文 c：c≡m**e(modn)

解密 (用私钥 (d,n))：
对密文 c，计算明文 m：m≡c**d(modn)

RSA的安全性依赖于大数分解的困难性，是现代网络安全（如HTTPS、数字签名）的基石之一

怎么求逆元🤔
1.扩展欧几里得算法

ouji

2.欧拉定理

费马小定理：若p为素数，则有a^{p-1}≡1(mod p)
a^{p-2}*a≡1(mod p)
p−2就是a在mod p意义下的逆元

欧拉定理：若a、p互素，则有a^{φ(p)}≡1(mod p)(费马小定理的一般形式)
a^{φ(p)-1}*a≡1(mod p)
a^{φ(p)−1}就是a在mod p意义下的逆元

RSA的正确性证明需要中国剩余定理

加密脚本

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
# 导入 Crypto.Util.number 模块中的所有函数
from Crypto.Util.number import *
# 导入 gmpy2 模块，用于高性能的数学运算
import gmpy2
# 从 secret 模块导入 flag，通常用于表示隐藏信息
# from secret import flag

# 这是给出了 flag 的样式，并不是真正的 flag，但已经提供了一些提示，有些题目会根据 flag 头来破解
flag = b"this_is_a_secret"

# 生成两个 1024 位的质数 p 和 q
p = getPrime(1024)
q = getPrime(1024)

# 计算 n，即 p 和 q 的乘积，用于 RSA 算法的模数
n = p * q
# 定义公钥指数 e，通常为 65537
e = 65537
# 将 flag 转换为长整数
m = bytes_to_long(flag)

# 使用 gmpy2 模块的 powmod 函数进行模幂运算，加密消息得到密文 c
c = gmpy2.powmod(m, e, n)

# 打印模数 n
print(f'n = {n}')
# 打印公钥指数 e
print(f'e = {e}')
# 打印加密后的密文 c
print(f'c = {c}')
# 打印质数 p（通常在 CTF 中不会直接给出）
print(f'p = {p}')
# 打印质数 q（通常在 CTF 中不会直接给出）
print(f'q = {q}')

解密脚本

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
# 导入 Crypto.Util.number 模块中的所有函数，用于处理数字和字节之间的转换等
from Crypto.Util.number import *


"""输入部分"""
# 已知的模数 n，用于 RSA 加密和解密
n = 4024941574680124502316363981547051098032677531528457166859670261861728313081282635664023890534034586556845494323497683923813915739234466472396261320600483
# 已知的公钥指数 e，通常为 65537
e = 65537
# 已知的密文 c，需要被解密
c = 226967182640114431119923862488626190608050511354278604627242247124377735518111678279381846350389469161980779137969837090666693533616114290831130137310320
# 已知的质数 p，用于计算私钥
p = 62658315832909660478685872111870233686035497063073558738980225214351386198939
# 已知的质数 q，用于计算私钥
q = 64236351092062515945998729497153532140067861836088195242257976217499252460697


"""处理部分"""
# 计算欧拉函数 phi(n)，用于RSA算法中的私钥计算
phi = (p-1)*(q-1)
# 计算私钥指数 d ，即 e 在模 phi(n) 的逆元
d = inverse(e,phi)
# 使用私钥指数 d 解密密文 c，得到明文 m，具体就是 m = c ** d (modn)
m = pow(c, d, n)
# 将解密后的长整数 m 转换回字符串，得到原始的 flag 信息
flag = long_to_bytes(m)


"""输出部分"""
# 打印解密后的 flag 信息
print(flag)

yafu用于自动整数因式分解，在RSA中，当p、q的取值差异过大或过于相近的时候，使用yafu可以快速的把n值分解出p、q值

  1. 假如要分解因数 6 ，输入命令：.\yafu-x64.exe "factor(6)"。

  2. 如果因数过长，将 因数 用文本文件存放在 yafu 目录下，例如：data.txt 。文件最后一行一定要换行，否则eof; done processing batchfile

    命令：.\yafu-x64.exe “factor(@)” -batchfile data.txt

CTF题目

签到题

给出n,e和c的十进制数值，直接用yafu或factordb分解n恢复密钥解密

给出公钥文件（如.pem或.pub）和密文文件（如flag.enc），要求通过分析公钥提取模数n和指数e，分解n得到p和q，进而计算私钥d并解密密文

openssl rsa -pubin -in pubkey.pem -text -modulus 获取e和n,c是flag.enc这个文件的16进制打开，然后转成10进制

RSA解密

共模攻击

明文m被不同的e1,e2和相同的n加密，生成不同的密文c1,c2，gcd(e1,e2)=1

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
from Crypto.Util.number import *
from math import gcd

def common_modulus_attack(n, e1, e2, c1, c2):
    # 扩展欧几里得算法，求解 a * e1 + b * e2 = 1
    def egcd(a, b):
        if b == 0:
            return (a, 1, 0)
        else:
            g, y, x = egcd(b, a % b)
            return (g, x, y - (a // b) * x)

    g, a, b = egcd(e1, e2)
    if g != 1:
        raise Exception("e1 and e2 are not coprime!")

    # 若 a < 0，则计算 c1^{-a} mod n，即模逆+幂
    if a < 0:
        c1 = inverse(c1, n)
        a = -a
    if b < 0:
        c2 = inverse(c2, n)
        b = -b

    m = (pow(c1, a, n) * pow(c2, b, n)) % n
    return m

# 示例数据（演示用，请替换为真实数据）
n = 18962682884029916758266148712505745769930251807486581175852746411420202928241516937832183978007221718832524708070926778926047462679852701680119573672086987102806746013917856291115241315396097056547791102379598520572653521839151746091770505325576025506216040948960407634360766413917009528663176592446406188935607285249768406522483451323332869038201690761692396934508701198776039170160825932569854510890717698839864324907395534236377475429151260126650206505223888915546928897884818098697371381102013517518088143512010341618604013730873811895372101358873053673492497993058229695619855124625929422288077109937999813125009
e1 = 17
e2 = 13
m = b"attack at dawn"
m_int = bytes_to_long(m)

# 模拟加密得到 c1, c2
c1 = pow(m_int, e1, n)
c2 = pow(m_int, e2, n)

# 执行共模攻击还原明文
recovered_m = common_modulus_attack(n, e1, e2, c1, c2)
print("Recovered message:", long_to_bytes(recovered_m))

低指数攻击

RSA 低指数攻击通常指 当使用较小的公钥指数（如 e=3）且没有足够的填充即明文过小导致m^e < n）时，可以直接通过取 e 次根得到明文

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

def low_exponent_attack(c, e):
    # 直接计算整数的e次根
    m_root, exact = gmpy2.iroot(c, e)
    if not exact:
        raise ValueError("The root is not exact; m^e >= n, attack failed.")
    return int(m_root)

# 示例明文
plaintext = b"attack at dawn"
m = bytes_to_long(plaintext)

# 参数设置（低指数 e=3）
n = 17207813408827103864232834453718240404256207776473195603833883222550085713263312178061956051570981138304553424351533759341843886988037589996836800172080989247901092860675283917792376508142626356947018854628009464434064348703066932998068320382047678068831988903330670000137190543367195121038536391898033648631182445857699244565169300742700970528157714029607334860854474360615932123721060603038551920908076990199310564184431371353455563870497874701913547639261995158683757252811208140013377653322801908827687229389173989691699203062882442083075199375009430197914167802307859798384351637765054362302474384036006738670083
e = 3
c = pow(m, e, n)

# 执行攻击
recovered = low_exponent_attack(c, e)
print("Recovered message:", long_to_bytes(recovered))

低加密指数广播攻击

多个不同模n(互素），相同明文m，使用相同的小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
import gmpy2
from functools import reduce
from Crypto.Util.number import long_to_bytes

def CRT(items):
    N = reduce(lambda x, y: x * y, (i[1] for i in items))
    result = 0
    for a, n in items:
        m = N // n
        d, r, s = gmpy2.gcdext(n, m)
        if d != 1:
            raise Exception("Input not pairwise co-prime")
        result += a * s * m
    return result % N, N

# 示例数据（需至少2组n和c）
e = 3
n = [
3733764742621371987947351902968312868056845889086054346406914908377408144612536549613883596047991001782736997571483548656987227352705958618056056807752367,
5975714612645545165217802713165264900295593190225535517994609218472455963199049168546710002169642814118703212038789758731340259084486414821051036778066333
]
c = [
7722709502790459166639993213708833737796147876436427049309008419119949153843426449996193173565875000,
7722709502790459166639993213708833737796147876436427049309008419119949153843426449996193173565875000
]

# 检查数据是否有效
if len(n) < 2 or len(c) < 2:
    raise ValueError("需要至少2组 (n, c) 数据")

data = list(zip(c, n))
x, N = CRT(data)

# 开立方恢复m
m = gmpy2.iroot(x, e)
if not m[1]:
    raise ValueError("无法开立方，可能 m^3 >= N 或数据无效")

m_int = int(m[0])
print('m is:', long_to_bytes(m_int))

低解密指数攻击

d也称为解密指数，当d比较小的时候，e也就特别大，所以发现e特别大的时候考虑低解密指数攻击,核心思想是利用 连分数逼近从公钥 (e,n)中恢复出私钥 d

Wiener 攻击成立的条件是：d<1/3n^{1/4}

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
import gmpy2
from Crypto.Util.number import long_to_bytes
import hashlib

def continuedFra(x, y):
    cF = []
    while y:
        cF.append(x // y)
        x, y = y, x % y
    return cF

def Simplify(ctnf):
    numerator = 0
    denominator = 1
    for x in reversed(ctnf):
        numerator, denominator = denominator, x * denominator + numerator
    return (numerator, denominator)

def calculateFrac(x, y):
    cF = continuedFra(x, y)
    cF = [Simplify(cF[:i]) for i in range(1, len(cF)+1)]
    return cF

def solve_pq(a, b, c):
    par = gmpy2.isqrt(b * b - 4 * a * c)
    return (-b + par) // (2 * a), (-b - par) // (2 * a)

def wienerAttack(e, n):
    for (d, k) in calculateFrac(e, n):
        if k == 0:
            continue
        if (e * d - 1) % k != 0:
            continue
        phi = (e * d - 1) // k
        p, q = solve_pq(1, n - phi + 1, n)
        if p * q == n:
            return abs(int(p)), abs(int(q))
    print('[!]not find!')
    return None, None

n = 101991809777553253470276751399264740131157682329252673501792154507006158434432009141995367241962525705950046253400188884658262496534706438791515071885860897552736656899566915731297225817250639873643376310103992170646906557242832893914902053581087502512787303322747780420210884852166586717636559058152544979471
e = 46731919563265721307105180410302518676676135509737992912625092976849075262192092549323082367518264378630543338219025744820916471913696072050291990620486581719410354385121760761374229374847695148230596005409978383369740305816082770283909611956355972181848077519920922059268376958811713365106925235218265173085

p, q = wienerAttack(e, n)
if p and q:
    print('[+]Found!')
    print('[-]p =', p)
    print('[-]q =', q)
    d = gmpy2.invert(e, (p-1)*(q-1))
    d_int = int(d)
    flag = "flag{" + hashlib.md5(hex(d_int).encode()).hexdigest() + "}"
    print(flag)
else:
    print("Failed to factorize n")

Boneh-Durfee 攻击

条件 d<n^{0.292}

太复杂了先放这里😨

公因子攻击

如果两个不同的 RSA 公钥 n1=p*q1，n2=p*q2共用了一个素因子 p，我们可以通过求 GCD恢复 p，然后分解两个模数，从而恢复私钥

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
from Crypto.Util.number import getPrime, inverse, bytes_to_long, long_to_bytes
from math import gcd

# 模拟两个共用素因子的 RSA 公钥
p = getPrime(128)
q1 = getPrime(128)
q2 = getPrime(128)

n1 = p * q1
n2 = p * q2

e = 65537

# 分别计算 c1 和 c2（加密相同明文也可以）
m = b"hello"
m_int = bytes_to_long(m)
c1 = pow(m_int, e, n1)
c2 = pow(m_int, e, n2)

# 执行攻击：找出公共素因子
shared_p = gcd(n1, n2)
assert shared_p == p

# 分解两个模数
retrieved_q1 = n1 // shared_p
retrieved_q2 = n2 // shared_p

# 还原私钥 d1 和 d2
phi1 = (shared_p - 1) * (retrieved_q1 - 1)
phi2 = (shared_p - 1) * (retrieved_q2 - 1)
d1 = inverse(e, phi1)
d2 = inverse(e, phi2)

# 解密
recovered_m1 = pow(c1, d1, n1)
recovered_m2 = pow(c2, d2, n2)

print("Recovered from n1:", long_to_bytes(recovered_m1))
print("Recovered from n2:", long_to_bytes(recovered_m2))

RSA Padding Oracle 攻击

Padding Oracle 攻击是一种针对 RSA 使用 PKCS#1 v1.5 填充模式的侧信道攻击,在不获取私钥的情况下，通过服务端的错误反馈（如 “填充无效” 或 “解密失败”）逐步解密 RSA 密文或伪造签名

PKCS#1 v1.5 的加密填充格式如下

1
00 02 [至少 8 字节随机非零填充] 00 [明文数据]

给定密文 c，攻击者构造新密文c′=(s**{e}*c)modn，其中 s 是缩放因子。

解密后得到 m′=s⋅m mod  n。

通过查询 Oracle 判断 m′ 的填充是否合法，可推断 m 的范围。

并没懂😶）

私钥部分信息泄露攻击

在 RSA 的 CRT（中国剩余定理）优化模式中，私钥通常存储以下参数：

  • p,q大素数，n=p*q
  • dp=d mod (p-1)
  • dq=d mod (q-1)
  • qinv=q^{-1} mod p（用于快速解密）

已知dp和n，可以恢复p

image-20250716223820730

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
import gmpy2

def recover_p_from_dp(e, n, dp):
    m = 2  # 任意数（通常选小整数）
    c = pow(m, e, n)
    m_p = pow(c, dp, n)
    p = gmpy2.gcd(m_p - m, n)
    if p != 1 and p != n:
        return p
    return None

e = 65537
n = 123...  # 模数
dp = 456...  # 泄露的dp
p = recover_p_from_dp(e, n, dp)
if p:
    q = n // p
    print("Found p:", p)
    print("Found q:", q)

工具

RsaCtfTool RSA自动化解密工具

参考 https://www.freebuf.com/articles/web/287854.html

总结了一些rsa的攻击方式，题目好多，以后存一些板子