什么是 RSA 加密？它的工作原理是什么？

RSA 是一种非对称加密算法，由 Rivest、Shamir 和 Adleman 于 1977 年提出，广泛应用于数字签名、安全通信和身份验证中。其核心原理基于大整数因数分解的数学难题，通过一对密钥（公钥和私钥）实现安全数据传输。

工作原理

1. 密钥生成：
   • 选择两个大质数 p 和 q，计算其乘积 n = p × q（模数）。
   • 计算欧拉函数 φ(n) = (p-1) × (q-1)。
   • 选择一个与 φ(n) 互质的整数 e（通常为 65537），作为公钥指数。
   • 计算私钥指数 d，满足 d × e ≡ 1 mod φ(n)。
   • 公钥为 (e, n)，私钥为 (d, n)。
2. 加密过程：
   • 将明文 M（需转换为数字且小于 n）通过公钥加密：

     C ≡ M^e \mod n  
     

     生成密文 C。

3. 解密过程：
   • 使用私钥解密密文 C：

     M' ≡ C^d \mod n  
     

     恢复出明文 M' = M。

安全基础

• 加密过程依赖公钥 (e, n)，攻击者即使截获密文 C 也无法推导出私钥 d。
• 破解难度在于从 n 分解出质数 p 和 q（大整数分解在计算上不可行）。

实际应用

• 数字签名：用私钥加密消息哈希值，接收方以公钥验证。
• TLS/SSL 协议：用于安全交换对称密钥（如 AES 密钥）。

# 示例（简化版）

import math  

def generate_rsa_keys(p: int, q: int):  
    n = p * q  
    phi_n = (p - 1) * (q - 1)  
    e = 65537  # 公钥指数  
    d = pow(e, -1, phi_n)  # 私钥指数  
    return (e, n), (d, n)  

def encrypt(message: int, pub_key):  
    e, n = pub_key  
    return pow(message, e, n)  # M^e mod n  

def decrypt(ciphertext: int, priv_key):  
    d, n = priv_key  
    return pow(ciphertext, d, n)  # C^d mod n  

# 测试

pub_key, priv_key = generate_rsa_keys(61, 53)  
cipher = encrypt(123, pub_key)  
message = decrypt(cipher, priv_key)  # 输出 123