# 从欧拉定理到指尖的密码：用Python亲手构建RSA加密系统 你是否曾好奇，当你在浏览器地址栏看到那个小小的锁形图标，背后究竟是怎样一套精妙的数学魔法在守护着你的每一次登录、每一笔交易？我们每天都在使用HTTPS、SSH、PGP，却很少有机会亲手揭开其核心——RSA非对称加密算法的神秘面纱。今天，我们不满足于仅仅理解概念，而是要挽起袖子，用Python代码，从最基础的数学定理出发，一步步搭建起一个可以实际运行的RSA加密系统。这不仅仅是一次编程练习，更是一场深入密码学心脏的探险，让你真正理解那些看似抽象的公式，是如何转化为保护数字世界安全的坚实壁垒的。 ## 1. 基石：理解驱动RSA的数学引擎 在动手写代码之前，我们必须先搞清楚RSA赖以生存的数学土壤。很多人一上来就死记硬背“选两个大质数p和q”，却对背后的“为什么”一头雾水，导致后续的密钥生成、加解密过程都成了机械的步骤模仿。让我们先抛开复杂的术语，从一个核心关系入手。 想象一个时钟，不过这个时钟的表盘刻度不是12，而是一个任意的数字n。欧拉函数 `φ(n)` 描述的是，在1到n-1这些数字里，有多少个与n“互质”（即最大公约数为1）。例如，`φ(8) = 4`（与8互质的数有1,3,5,7）。欧拉定理则告诉我们一个关于这个时钟的奇妙性质：如果整数a与n互质，那么 `a^φ(n)` 在这个n刻度的时钟上，指针总会指回1。用数学语言写就是： ``` a^φ(n) ≡ 1 (mod n) ``` 这个“≡”和“(mod n)”表示我们只关心除以n后的余数，这就是**模运算**的世界，也是整个RSA算法的舞台。 RSA的巧妙之处在于，它构造了一对特殊的数字e（公钥指数）和d（私钥指数），使得对于任何信息m（转换成数字后），满足： ``` (m^e)^d ≡ m (mod n) ``` 也就是说，用e加密一次，再用d解密一次，就能变回原信息。如何找到这样的e和d呢？关键等式就藏在这里： ``` e * d ≡ 1 (mod φ(n)) ``` 这个等式的意思是，`e*d` 除以 `φ(n)` 的余数是1。一旦我们构造出满足这个等式的e和d，欧拉定理就能保证加解密过程的正确性。而`φ(n)`的计算，当n是两个质数p和q的乘积时，变得极其简单：`φ(n) = (p-1)*(q-1)`。这就是为什么RSA需要两个大质数的根本原因——它们让核心参数`φ(n)`的计算既安全又方便。 > 注意：这里的“安全”是相对的。`φ(n)`的计算之所以方便，是因为我们知道p和q。而对于外部攻击者，他们只知道巨大的合数n，想要从n倒推出`φ(n)`，其难度等同于分解n为p和q，这在计算上是极其困难的。 为了直观对比理解这几个核心概念，我们用一个表格来梳理： | 概念 | 数学定义/描述 | 在RSA中的作用与意义 | | :--- | :--- | :--- | | **模运算 (mod)** | 只关心除法后的余数，如 `13 mod 5 = 3`。 | 构建有限的数学循环系统，是加解密运算的数学空间。 | | **最大公约数 (gcd)** | 能同时整除两个数的最大正整数。 | 判断两个数是否互质，是欧拉函数和定理应用的前提。 | | **欧拉函数 φ(n)** | 小于n的正整数中与n互质的数的个数。 | 其值`φ(n)`定义了RSA算法中密钥对的数学关系（`e*d ≡ 1 mod φ(n)`）。 | | **欧拉定理** | 若a与n互质，则 `a^φ(n) ≡ 1 (mod n)`。 | 确保RSA加解密过程数学正确性的核心理论基石。 | | **模逆元** | 对于整数a和模数m，若存在整数b使得 `a*b ≡ 1 (mod m)`，则b是a的模逆元。 | 私钥指数d本质上是公钥指数e关于模`φ(n)`的模逆元。 | 理解了这些，你就掌握了RSA的“设计图纸”。接下来，我们将进入车间，开始用Python锻造我们的加密工具。 ## 2. 工坊：构建RSA密钥生成器 理论很美妙，但密码学是实践的科学。我们现在就开始编写第一个核心函数：RSA密钥生成器。这个过程就像打造一把独一无二的锁和钥匙。锁（公钥）可以公开给任何人，让他们把信息锁进去；而钥匙（私钥）必须由你自己严密保管，用于开锁读取信息。 密钥生成的核心步骤可以清晰地分解如下： 1. **选择两个大质数 p 和 q**：这是安全的基础。质数要足够大、随机，并且不能靠得太近。 2. **计算模数 n 和欧拉函数 φ(n)**：`n = p * q`，`φ(n) = (p-1) * (q-1)`。 3. **选择公钥指数 e**：选择一个整数 e，满足 `1 < e < φ(n)`，且 e 与 φ(n) 互质。通常使用 65537 (0x10001)，因为它二进制表示中1很少，能优化加密运算速度，且安全性高。 4. **计算私钥指数 d**：计算 e 关于模 φ(n) 的模逆元 d。即求解满足 `e*d ≡ 1 (mod φ(n))` 的 d。 让我们用Python一步步实现。首先，我们需要一个生成大质数的函数。在实际工业级应用中，会使用更复杂的概率性测试（如米勒-拉宾测试），这里为了教学清晰，我们使用一个简单的质数检查方法，并借助Python的`secrets`模块确保随机性。 ```python import secrets import math def is_prime(num: int, k=5) -> bool: """一个简单的概率性质数测试（费马小定理基础版），k为测试次数。""" if num < 2: return False # 处理一些小质数 small_primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29] if num in small_primes: return True for prime in small_primes: if num % prime == 0: return False # 费马小定理测试 for _ in range(k): a = secrets.randbelow(num - 3) + 2 # 随机选择 2 <= a <= num-2 if pow(a, num - 1, num) != 1: return False return True def generate_large_prime(bit_length=512) -> int: """生成一个指定位数的大（概然）质数。""" while True: # 使用secrets生成密码学安全的随机数，确保高位为1使其达到指定位数 candidate = secrets.randbits(bit_length) | (1 << (bit_length - 1)) | 1 if is_prime(candidate): return candidate ``` 有了质数生成器，我们就可以组装密钥生成函数了。计算模逆元d是这里的一个小难点，我们可以使用**扩展欧几里得算法**。这个算法不仅能求出两个数的最大公约数，还能找到满足 `e*d + φ(n)*k = 1` 的系数d和k，其中的d模φ(n)后就是我们需要的私钥指数。 ```python def extended_gcd(a, b): """扩展欧几里得算法，返回 (gcd, x, y) 使得 a*x + b*y = gcd(a, b)。""" if b == 0: return a, 1, 0 else: gcd, x1, y1 = extended_gcd(b, a % b) x = y1 y = x1 - (a // b) * y1 return gcd, x, y def mod_inverse(e, phi): """计算 e 模 phi 的乘法逆元 d，即 e*d ≡ 1 (mod phi)。""" gcd, x, _ = extended_gcd(e, phi) if gcd != 1: raise ValueError(f"e ({e}) 和 φ(n) ({phi}) 不互质，无法计算模逆元。") # x 可能是负数，需要调整到正数范围 [0, phi-1] return x % phi def generate_rsa_keys(bit_length=1024): """生成RSA公钥和私钥对。""" # 1. 生成两个大质数 p = generate_large_prime(bit_length // 2) q = generate_large_prime(bit_length // 2) # 确保p和q不相等 while p == q: q = generate_large_prime(bit_length // 2) # 2. 计算 n 和 φ(n) n = p * q phi_n = (p - 1) * (q - 1) # 3. 选择公钥指数 e e = 65537 # 行业标准，一个优秀的默认值 # 确保 e 与 φ(n) 互质 while math.gcd(e, phi_n) != 1: # 理论上65537几乎总是互质，这里以防万一 e = secrets.randbelow(phi_n - 3) + 2 # 4. 计算私钥指数 d d = mod_inverse(e, phi_n) # 公钥: (e, n), 私钥: (d, n) public_key = (e, n) private_key = (d, n, p, q) # 有时会保存p和q以加速解密（使用中国剩余定理） return public_key, private_key ``` 运行 `generate_rsa_keys()`，你就得到了一对属于你自己的RSA密钥。公钥 `(e, n)` 可以放心地交给任何人，而私钥 `(d, n)` 则需要像保护银行密码一样保护起来。在真实场景中，私钥通常会经过加密后存储在本地。 ## 3. 实战：实现信息的加密与解密 有了密钥，我们就可以进行最激动人心的部分了：加密和解密。RSA算法本身是定义在整数上的，所以我们需要先把任何形式的信息（文本、文件）转换成一个或一系列的大整数。 **加密过程**非常简单：对于明文数字 `m`（必须满足 `0 <= m < n`），计算密文 `c = m^e mod n`。 **解密过程**同样直接：对于密文数字 `c`，计算明文 `m = c^d mod n`。 这里的关键是计算大整数的幂模运算 `pow(a, b, m)`，即 `a^b mod m`。幸运的是，Python内置的 `pow` 函数支持三个参数，它使用了高效的模幂算法（如快速幂），能够处理天文数字般的指数运算，而不会导致内存溢出或计算时间过长。 让我们编写加解密函数，并处理文本到整数的转换： ```python def rsa_encrypt(plaintext_int: int, public_key): """使用公钥加密一个整数。""" e, n = public_key if plaintext_int < 0 or plaintext_int >= n: raise ValueError("明文整数必须满足 0 <= m < n") ciphertext_int = pow(plaintext_int, e, n) return ciphertext_int def rsa_decrypt(ciphertext_int: int, private_key): """使用私钥解密一个整数。""" d, n, *_ = private_key # 解包，忽略可能存在的p, q plaintext_int = pow(ciphertext_int, d, n) return plaintext_int def text_to_int(text: str) -> int: """将文本字符串编码为一个大整数。""" # 使用UTF-8编码将文本转换为字节，然后将字节视为一个大整数 byte_data = text.encode('utf-8') return int.from_bytes(byte_data, 'big') def int_to_text(number: int) -> str: """将一个大整数解码为文本字符串。""" # 计算表示这个整数所需的字节长度 byte_length = (number.bit_length() + 7) // 8 byte_data = number.to_bytes(byte_length, 'big') return byte_data.decode('utf-8') ``` 但是，这里有一个重要的限制：由于 `m < n` 的要求，我们能加密的明文整数大小受限于模数n。对于长文本，我们需要采用**分块加密**的策略。同时，直接使用RSA加密小整数或具有固定模式的明文是不安全的，在实际应用中（如PKCS#1标准）会先对明文进行**填充**，增加随机性和抵抗某些攻击的能力。为了教学完整，我们实现一个简单的分块加密示例： ```python def rsa_encrypt_text(text: str, public_key, block_size_bytes=None): """加密文本，自动分块。block_size_bytes建议为 (n的字节长度 - 11) 用于PKCS#1 v1.5填充，此处简化。""" e, n = public_key n_byte_len = (n.bit_length() + 7) // 8 # 简化处理：每个块能容纳的明文字节数。实际应更小以预留填充空间。 if block_size_bytes is None: block_size_bytes = n_byte_len - 1 # 非常保守的估计 encrypted_blocks = [] # 将文本转换为字节 data_bytes = text.encode('utf-8') for i in range(0, len(data_bytes), block_size_bytes): block = data_bytes[i:i+block_size_bytes] m_int = int.from_bytes(block, 'big') # 确保 m_int < n if m_int >= n: # 如果块太大，需要减小block_size_bytes并重新设计逻辑 raise ValueError(f"明文块过大，请减小 block_size_bytes。当前块值: {m_int}, n: {n}") c_int = pow(m_int, e, n) encrypted_blocks.append(c_int) return encrypted_blocks def rsa_decrypt_text(encrypted_blocks, private_key, block_size_bytes=None): """解密分块加密的整数列表，还原为文本。""" d, n, *_ = private_key n_byte_len = (n.bit_length() + 7) // 8 if block_size_bytes is None: block_size_bytes = n_byte_len - 1 decrypted_bytes = bytearray() for c_int in encrypted_blocks: m_int = pow(c_int, d, n) # 将解密后的整数转换回字节块 block_bytes = m_int.to_bytes(block_size_bytes, 'big') # 去除可能因to_bytes固定长度而产生的头部零字节（需根据具体填充方案调整） # 这里简单去除开头的零字节，直到遇到非零字节（这不是标准做法，仅用于演示） start = 0 while start < len(block_bytes) and block_bytes[start] == 0: start += 1 decrypted_bytes.extend(block_bytes[start:]) return decrypted_bytes.decode('utf-8', errors='ignore') ``` 现在，让我们进行一次完整的流程演示： ```python # 1. 生成密钥 print("正在生成1024位RSA密钥对...") public_key, private_key = generate_rsa_keys(1024) print(f"公钥 (e, n): ({public_key[0]}, ...{str(public_key[1])[-20:]})") print(f"私钥 (d, n): ({private_key[0]}, ...{str(private_key[1])[-20:]})") # 2. 准备明文 secret_message = "Hello, RSA! 这是一条秘密信息。" print(f"\n原始明文: {secret_message}") # 3. 加密 print("\n正在加密...") cipher_blocks = rsa_encrypt_text(secret_message, public_key, block_size_bytes=100) # 使用较小的块 print(f"生成密文块列表，共 {len(cipher_blocks)} 个块。") # 4. 解密 print("\n正在解密...") decrypted_message = rsa_decrypt_text(cipher_blocks, private_key, block_size_bytes=100) print(f"解密结果: {decrypted_message}") # 5. 验证 if decrypted_message == secret_message: print("\n✅ 加解密成功！信息完整还原。") else: print("\n❌ 解密失败，信息不匹配。") ``` 运行这段代码，你将亲眼看到信息如何从可读的文本，经过公钥加密变成一堆无法理解的巨大整数，再通过私钥魔法般地恢复原貌。这种“单向”和“可逆”的特性，正是非对称加密的精髓。 ## 4. 进阶：签名、验证与性能考量 RSA的能力远不止于加密。另一个至关重要的应用是**数字签名**。它的逻辑与加密相反：发送者用自己的**私钥**对信息的摘要（如SHA-256哈希值）进行“签名”（即加密操作），生成签名值。接收者用发送者的**公钥**对签名值进行“验证”（即解密操作），得到摘要，再与自己计算的摘要对比。如果一致，就证明信息确实来自该发送者且未被篡改。 ```python import hashlib def rsa_sign(message: str, private_key): """使用私钥对消息进行签名。""" # 1. 计算消息的哈希值 hash_obj = hashlib.sha256(message.encode('utf-8')) hash_digest = hash_obj.digest() # 字节串 hash_int = int.from_bytes(hash_digest, 'big') # 2. 使用私钥对哈希值进行“加密”（即签名） d, n, *_ = private_key # 注意：哈希值可能 >= n，需要处理。通常签名标准（如PKCS#1）会先对哈希值进行编码和填充。 # 此处简化，假设哈希值 < n。对于SHA-256，哈希值是256位（32字节），而1024位的n是128字节，通常满足。 if hash_int >= n: raise ValueError("哈希值过大，无法直接签名。需使用PSS或PKCS#1 v1.5等填充方案。") signature_int = pow(hash_int, d, n) return signature_int def rsa_verify(message: str, signature_int: int, public_key) -> bool: """使用公钥验证消息的签名。""" # 1. 计算消息的哈希值 hash_obj = hashlib.sha256(message.encode('utf-8')) hash_digest = hash_obj.digest() hash_int = int.from_bytes(hash_digest, 'big') # 2. 使用公钥对签名进行“解密”（即验证） e, n = public_key decrypted_hash_int = pow(signature_int, e, n) # 3. 比较解密得到的哈希值与计算出的哈希值 return decrypted_hash_int == hash_int ``` 在实际项目中，直接对哈希值进行幂模运算存在安全风险（如可伪造签名）。因此，工业标准如 **RSA-PSS**（概率签名方案）或 **RSA-PKCS#1 v1.5** 会定义复杂的填充流程，将哈希值编码成一个与模数n长度相近、结构特定的“消息代表”，然后再进行签名运算。Python的`cryptography`库提供了这些标准的安全实现。 最后，我们必须正视RSA的局限性。正如原始资料提到的，它的主要缺点是**慢**。一次1024位或2048位的幂模运算开销很大。因此，在实际系统中（如TLS/SSL），RSA通常不用于加密整个通信内容，而是用于解决一个核心问题：**安全地交换一个对称加密的密钥**（如AES密钥）。这个过程称为**密钥交换**。通信双方使用RSA加密来传递一个随机生成的会话密钥，后续所有大量的数据加密解密都使用更快的对称加密算法（如AES）来完成。这种结合了非对称加密安全性和对称加密效率的**混合加密系统**，才是当今互联网安全的基石。 > 提示：如果你在自己的项目中使用密码学，一个最重要的原则是**不要自己发明加密算法或协议**。始终使用经过广泛审查和测试的成熟库，如Python的 `cryptography`。本文的手工实现旨在教育理解，而非用于生产环境。 从欧拉定理的一个优雅等式，到屏幕上成功解密的“Hello, RSA!”，我们完成了一次完整的密码学构建之旅。我最初学习RSA时，总觉得那些数学公式离编程很远，直到自己把`pow(m, e, n)`这行代码跑通，看到数字按照数百年前的数学定理精确地转换，那种连接理论与实践的震撼感，是单纯阅读教科书无法比拟的。理解RSA，就像是获得了一把理解现代数字安全世界的钥匙，它让你明白，那些看似无形的“安全锁”，背后矗立着的是何等坚固而美丽的数学支柱。