2. RSA算法原理

RSA算法是1977年由Ron Rivest、Adi Shamir和Leonard Adleman共同提出的非对称加密算法，其安全性基于大整数因子分解的数学困难问题。RSA是当前应用最广泛的公钥密码体制之一，被用于SSL/TLS、数字签名、安全电子邮件等场景。

2.1 RSA密钥生成

RSA密钥生成的核心步骤包括大素数选取、模数计算、公私钥指数确定。以下为完整流程：

2.2 大素数选取与素性测试

大素数选取是RSA密钥生成的第一步，也是最耗时的步骤。实际工程中采用随机生成+概率素性测试的策略：

• 随机生成候选数：使用密码学安全随机数生成器（CSPRNG）生成长度为 k 位的奇数
• 小素数筛除：用前几百个小素数（如3,5,7,11,...）快速筛除合数，减少后续计算量
• Miller-Rabin素性测试：对通过筛除的候选数进行多次测试，错误概率 ≤ 4^-t（t为测试轮数）

2.3 加密与解密过程

RSA加密和解密基于模幂运算，将明文/密文视为整数，在模 n 下进行指数运算。消息 m 必须满足 0 ≤ m < n。

解密正确性由欧拉定理保证：若 c ≡ m^e (mod n)，则 c^d ≡ m^ed ≡ m^1+kφ(n) ≡ m (mod n)。

2.4 RSA的安全性分析

RSA的安全性建立在以下数学难题之上，同时需防范多种攻击向量：

2.4.1 安全基础

• 大整数因子分解问题（IFP）：给定 n = p×q，求 p 和 q。目前没有多项式时间算法，2048位RSA在可预见的未来被认为是安全的
• RSA问题（RSAP）：给定 (n, e, c)，求 m 使得 c ≡ m^e mod n。若IFP可解，则RSAP可解；反之不一定成立

2.4.2 主要攻击类型与防御

2.4.3 密钥长度安全等级

2.5 RSA算法代码示例

以下为Python实现的RSA密钥生成、加密与解密核心逻辑（仅用于教学演示，实际生产环境应使用cryptography库）：

import random
from math import gcd

def generate_prime(bits):
    """生成指定位数的素数（简化版）"""
    while True:
        # 生成随机奇数
        candidate = random.getrandbits(bits) | (1 << (bits-1)) | 1
        # Miller-Rabin素性测试（简化：5轮）
        if is_probable_prime(candidate, 5):
            return candidate

def is_probable_prime(n, k):
    """Miller-Rabin素性测试"""
    if n < 2: return False
    if n == 2 or n == 3: return True
    if n % 2 == 0: return False
    
    r, d = 0, n - 1
    while d % 2 == 0:
        r += 1
        d //= 2
    
    for _ in range(k):
        a = random.randrange(2, n - 2)
        x = pow(a, d, n)
        if x == 1 or x == n - 1:
            continue
        for _ in range(r - 1):
            x = pow(x, 2, n)
            if x == n - 1:
                break
        else:
            return False
    return True

def rsa_keygen(bits=2048):
    """RSA密钥生成"""
    # 选取两个大素数
    p = generate_prime(bits // 2)
    q = generate_prime(bits // 2)
    
    # 计算模数
    n = p * q
    phi = (p - 1) * (q - 1)
    
    # 公钥指数（常用65537）
    e = 65537
    # 确保互素
    while gcd(e, phi) != 1:
        e = random.randrange(3, phi, 2)
    
    # 私钥指数（扩展欧几里得算法）
    d = pow(e, -1, phi)
    
    return (n, e), (n, d)

def rsa_encrypt(m, pub_key):
    """RSA加密"""
    n, e = pub_key
    return pow(m, e, n)

def rsa_decrypt(c, priv_key):
    """RSA解密"""
    n, d = priv_key
    return pow(c, d, n)

# 使用示例
pub_key, priv_key = rsa_keygen(2048)
message = 123456789  # 实际应使用填充后的消息
ciphertext = rsa_encrypt(message, pub_key)
plaintext = rsa_decrypt(ciphertext, priv_key)
print(f"原始消息: {message}")
print(f"解密结果: {plaintext}")
print(f"加解密正确: {message == plaintext}")