RSA加解密以及攻击方法

from Crypto.Util.number import getPrime, bytes_to_long, long_to_bytes		# 将string转换成大整数
from math import gcd

def modinv(e, phi):
    # 扩展欧几里得算法计算模逆
    def extended_gcd(a, b):
        if b == 0:
            return (1, 0)
        else:
            x1, y1 = extended_gcd(b, a % b)
            x, y = y1, x1 - (a // b) * y1
            return (x, y)
    x, _ = extended_gcd(e, phi)
    return x % phi


p = getPrime(512)		# 512位的素数
q = getPrime(512)		# 512位的素数

n = p * q
phi = (p - 1) * (q - 1)

e = 65537				# 大部分默认使用这个e的值
assert gcd(e, phi) == 1

d = modinv(e, phi)

# 加密
def encrypt(message, e, n):
    m = bytes_to_long(message.encode())
    c = pow(m, e, n)
    return c

# 解密
def decrypt(cipher_int, d, n):
    m = pow(cipher_int, d, n)
    message = long_to_bytes(m).decode()
    return message

msg = "Hello World!"
cipher = encrypt(msg, e, n)
decrypted = decrypt(cipher, d, n)

from cryptography.hazmat.primitives.asymmetric import rsa
from cryptography.hazmat.primitives import serialization
from Crypto.Util.number import getPrime

e = 65537
p = getPrime(512)		# 512位的素数
q = getPrime(512)		# 512位的素数
n = p * q
phi = (p - 1) * (q - 1)
d = pow(e, -1, phi)

# 计算 CRT 参数
# 这些参数必须传（库要求的）
dmp1 = d % (p - 1)
dmq1 = d % (q - 1)
iqmp = pow(q, -1, p)

# 构造私钥对象
private_numbers = rsa.RSAPrivateNumbers(
    p=p,
    q=q,
    d=d,
    dmp1=dmp1,
    dmq1=dmq1,
    iqmp=iqmp,
    public_numbers=rsa.RSAPublicNumbers(e=e, n=n)
)

private_key = private_numbers.private_key()

# 导出为 PEM 格式（PKCS#8）
pem = private_key.private_bytes(
    encoding=serialization.Encoding.PEM,
    format=serialization.PrivateFormat.PKCS8,
    encryption_algorithm=serialization.NoEncryption()
)

# 打印 PEM 私钥
print(pem.decode())

public_key = private_key.public_key()
pem_pub = public_key.public_bytes(
    encoding=serialization.Encoding.PEM,
    format=serialization.PublicFormat.SubjectPublicKeyInfo
)
print(pem_pub.decode())

from cryptography.hazmat.primitives import serialization

pem_data = b"""-----BEGIN PRIVATE KEY-----
......
-----END PRIVATE KEY-----"""

# 解析 PEM 私钥对象
private_key = serialization.load_pem_private_key(
    pem_data,
    password=None  # 如果加密了，需要提供密码（bytes）
)

# 提取私钥参数（适用于 RSA 密钥）
numbers = private_key.private_numbers()

# 打印出 RSA 私钥参数
print(f"Modulus (n): {numbers.public_numbers.n}")
print(f"Public Exponent (e): {numbers.public_numbers.e}")
print(f"Private Exponent (d): {numbers.d}")
print(f"Prime 1 (p): {numbers.p}")
print(f"Prime 2 (q): {numbers.q}")
print(f"d mod (p-1): {numbers.dmp1}")
print(f"d mod (q-1): {numbers.dmq1}")
print(f"q^-1 mod p: {numbers.iqmp}")	# 用于CRT的

from cryptography.hazmat.primitives import serialization

pem_data = b"""-----BEGIN PUBLIC KEY-----
......
-----END PUBLIC KEY-----"""

key = serialization.load_pem_public_key(pem_data)

# 提取公钥的详细信息
numbers = key.public_numbers()
print(f"Modulus (n): {numbers.n}")
print(f"Exponent (e): {numbers.e}")

import math

def fermat_factor(n, max_iter=1000000):
    a = math.isqrt(n)
    if a * a < n:
        a += 1
    for _ in range(max_iter):
        b2 = a*a - n
        b = math.isqrt(b2)
        if b*b == b2:
            return a - b, a + b
        a += 1
    return None

n = 
result = fermat_factor(n)
if result:
	print("p =", result[0], "q =", result[1])
else:
	print("未成功")

import math

def pollard_p1(n, B=1000000):
    a = 2
    for j in range(2, B):
        a = pow(a, j, n)
    g = math.gcd(a-1, n)
    if 1 < g < n:
        return g, n // g
    return None

n = 
result = pollard_p1(n)
if result:
    print("p =", result[0], "q =", result[1])
else:
    print("未成功")

from sage.all import *
n = 
factors = ecm.factor(n)
phi = prod([f - 1 for f in factors])

from gmpy2 import iroot
from Crypto.Util.number import long_to_bytes

e = 
n = 
c = 

# 可以根据条件以及测试结果调整max的大小
max = 10000
for i in range(1, max):
    modified_c = c + i * n
    m_root, exact = iroot(modified_c, e)
    if exact:
        print(f"找到解: i = {i}")
        print("明文:", long_to_bytes(m_root))
        break
else:
    print("尝试范围内未找到可解的 m")

import math
from Crypto.Util.number import long_to_bytes

def continued_fraction(numerator, denominator):
    """生成分数 numerator/denominator 的连分数表示"""
    cf = []
    while denominator:
        a = numerator // denominator
        cf.append(a)
        numerator, denominator = denominator, numerator - a * denominator
    return cf


def convergents_from_cf(cf):
    """根据连分数序列 cf 生成收敛分数 (k, d)"""
    n0, d0 = cf[0], 1
    yield (n0, 1)
    if len(cf) == 1:
        return
    n1 = cf[1] * cf[0] + 1
    d1 = cf[1]
    yield (n1, d1)
    for i in range(2, len(cf)):
        ni = cf[i] * n1 + n0
        di = cf[i] * d1 + d0
        yield (ni, di)
        n0, d0, n1, d1 = n1, d1, ni, di


def is_perfect_square(x):
    """判断 x 是否为完全平方数"""
    if x < 0:
        return False
    s = math.isqrt(x)
    return s * s == x


def wiener_attack(e, n):
    """
    使用 Wiener 攻击尝试恢复 RSA 私钥 d。
    参数:
        e: 公钥指数
        n: 模数
    返回:
        若成功，返回私钥指数 d；否则返回 None。
    """
    cf = continued_fraction(e, n)
    for k, d in convergents_from_cf(cf):
        if k == 0:
            continue
        # 检查 (e*d - 1) 是否被 k 整除，以得到 phi
        if (e * d - 1) % k != 0:
            continue
        phi = (e * d - 1) // k
        # 计算方程 x^2 - (n - phi + 1)x + n = 0 的判别式
        s = n - phi + 1
        discr = s * s - 4 * n
        if discr >= 0 and is_perfect_square(discr):
            t = math.isqrt(discr)
            # 计算 p, q
            p = (s + t) // 2
            q = (s - t) // 2
            if p * q == n:
                return d
    return None


n = 
e = 
c = 

d = wiener_attack(e, n)
if d:
    print(f"得到d: {d}")
    m = pow(c, d, n)
    message = long_to_bytes(m).decode()
    print(f"明文内容为：{message}")
else:
    print("Wiener 攻击未能恢复 d")

from Crypto.Util.number import inverse, long_to_bytes
from math import gcd

n = 
e1 = 
e2 = 
c1 = 
c2 = 

# 使用扩展欧几里得算法求出 x 和 y
def extended_gcd(a, b):
    if b == 0:
        return (1, 0)
    else:
        x1, y1 = extended_gcd(b, a % b)
        x = y1
        y = x1 - (a // b) * y1
        return (x, y)

x, y = extended_gcd(e1, e2)

# 处理负指数（计算逆元）
if x < 0:
    c1 = inverse(c1, n)
    x = -x
if y < 0:
    c2 = inverse(c2, n)
    y = -y

m = (pow(c1, x, n) * pow(c2, y, n)) % n

# 解密后的明文
print(long_to_bytes(m))