从零实现RSA算法：深入理解非对称加密原理与Python实践

1. 项目缘起为什么我们要亲手实现RSA如果你是一名计算机科学、信息安全或者密码学方向的学生或开发者那么“RSA”这个名字对你来说一定不陌生。它几乎成了非对称加密的代名词出现在无数教科书、面试题和技术博客里。你可能已经无数次地调用过类似crypto.publicEncrypt()这样的API看着加密后的密文感觉一切理所当然。但不知道你有没有过这样的疑问这个算法内部到底是怎么运转的那些巨大的质数、欧拉函数、模逆运算是如何组合在一起最终实现“公钥加密私钥解密”这个神奇过程的这就是我们这次任务的核心抛开所有现成的密码学库从零开始用代码实现RSA算法。这不仅仅是一个编程练习更是一次对密码学核心思想的深度探索。当你亲手用代码计算出公钥和私钥并成功加密解密一段信息时你对RSA的理解将不再停留在概念层面。你会明白为什么它安全也会直观地感受到它的计算开销甚至能体会到在参数选择不当时可能出现的“坑”。网络上搜索“RSA代码实现”的热度一直很高这恰恰说明了大家对这个“黑盒”内部的好奇与求知欲。从“dangerous rsa”这样的关键词也能看出理解其原理对于避免错误使用至关重要。所以这篇博文就是一份“硬核”的实操指南。我将以一个从业者的角度带你一步步推导RSA的数学原理并将其转化为清晰、可运行的代码我们将使用Python因为它足够表达思想且易于理解。我们不止步于“能跑通”更要深究“为什么这么做”。我会分享在实现过程中容易忽略的细节、性能优化的思路以及如何验证你的实现是否正确。无论你是为了巩固基础知识、完成课程作业还是为更复杂的密码学应用打基础这篇内容都将提供一条从理论到实践的完整路径。2. RSA的数学心脏从质数到密钥对在动手写代码之前我们必须先吃透RSA赖以生存的数学基础。如果你觉得公式枯燥不妨把它们想象成一套精密的乐高搭建说明书每一步都不可或缺。2.1 核心步骤拆解RSA密钥生成可以分解为五个清晰的步骤第一步选择两个大质数p和q这是所有安全性的起点。p和q必须足够大、并且是随机生成的质数。为什么必须是质数因为RSA的安全性基于“大整数质因数分解的困难性”。如果p和q不是质数那么分解n p * q可能会变得容易得多。在教学中我们为了演示会用小质数如61和53但在实际应用中p和q通常是1024位或2048位的巨大整数。第二步计算模数n计算n p * q。这个n就是模数它既是公钥的一部分也是私钥的一部分。它的二进制长度就是所谓的“密钥长度”例如n是2048位长我们就说这是RSA-2048。第三步计算欧拉函数φ(n)对于两个质数p和q其欧拉函数的值非常简单φ(n) (p-1) * (q-1)。这个φ(n)在后续计算中至关重要但它必须被严格保密绝不能和公钥一起泄露。你可以把它理解为密钥生成过程中的一个“中间秘密”。第四步选择公钥指数e公钥由(n, e)组成。e的选择需要满足两个条件1 e φ(n)e与φ(n)互质即最大公约数 gcd(e, φ(n)) 1。 通常为了计算效率我们会选择一个较小的、且二进制表示中1的位数较少的质数。最常用、最标准的选择是 65537 (0x10001)。为什么是65537因为它足够大大于许多简单攻击的范围又是质数并且其二进制形式10000000000000001只有两个1这使得基于它的模幂运算速度非常快。第五步计算私钥指数d私钥由(n, d)组成。d是e对于模φ(n)的模逆元。也就是说d需要满足(e * d) % φ(n) 1。 这个d就是那个能解开用e加密的信息的“魔法数字”。计算d需要用到扩展欧几里得算法这是实现中的一个小难点我们后面会详细讲。至此公钥(n, e)和私钥(n, d)都已生成。公钥可以公开给任何人私钥则必须由所有者严密保管。2.2 加密与解密的数学表达有了密钥对加密和解密过程在数学上非常优雅加密用公钥对于明文消息m需要是一个小于n的整数计算密文c m^e mod n。解密用私钥对于密文c计算明文m c^d mod n。这里的关键是m^e mod n和c^d mod n这两个模幂运算。直接先计算幂再取模是不可行的因为m^e会是一个天文数字。我们必须使用高效的算法如快速模幂算法。注意这里的m代表一个整数。在实际应用中我们需要先将文本如字符串通过某种编码方式如PKCS#1 OAEP转换为整数并确保这个整数小于n。直接对字符的ASCII码进行加密是不安全也不标准的做法我们会在后续部分讨论这个重要的“填充”问题。3. 核心算法实现扩展欧几里得与快速模幂理论清晰后我们进入编码实战。我们将首先实现两个最核心的辅助函数它们是RSA的“发动机”。3.1 扩展欧几里得算法求解模逆元计算私钥指数d即求解方程e * d ≡ 1 (mod φ(n))本质上是求e在模φ(n)下的乘法逆元。扩展欧几里得算法不仅能求出两个数的最大公约数gcd还能找到满足贝祖等式ax by gcd(a, b)的整数x和y。当a和b互质时gcd(a, b) 1贝祖等式变为ax by 1。对等式两边同时取模b我们得到ax ≡ 1 (mod b)。看这里的x可能需要对b取模调整到正数范围就是a模b的逆元下面是它的递归实现非常精妙def extended_gcd(a, b): 扩展欧几里得算法。 返回一个三元组 (gcd, x, y)使得 a*x b*y gcd(a, b)。 当 gcd(a, b) 1 时x 即为 a 模 b 的逆元。 if b 0: return a, 1, 0 else: gcd, x1, y1 extended_gcd(b, a % b) # 根据递归结果回溯计算当前层的 x, y x y1 y x1 - (a // b) * y1 return gcd, x, y def mod_inverse(e, phi): 计算 e 在模 phi 下的乘法逆元 d。 即寻找 d 使得 (e * d) % phi 1。 gcd, x, _ extended_gcd(e, phi) if gcd ! 1: # 如果 e 和 phi 不互质则逆元不存在这对于RSA密钥生成意味着参数选择错误。 raise ValueError(fe ({e}) 和 φ(n) ({phi}) 不互质无法计算逆元。请重新选择 e。) else: # x 可能为负数需要将其调整到 [0, phi) 的正数范围内。 return x % phi实操心得在调试时务必验证(e * d) % phi 1。另外extended_gcd函数中的回溯公式是理解的关键点建议用一个小例子如 a17, b3120在纸上手动演算一遍你会对算法的美感有更深体会。3.2 快速模幂算法处理天文数字的运算无论是加密的m^e mod n还是解密的c^d mod n指数e或d都可能非常大比如2048位密钥的d。直接计算幂再取模你的计算机内存会瞬间被撑爆。快速模幂算法Exponentiation by Squaring通过将指数二进制分解将计算复杂度从 O(n) 降低到 O(log n)。其核心思想是a^b mod m可以通过以下方式计算如果b是偶数a^b mod m (a^(b/2) mod m)^2 mod m如果b是奇数a^b mod m (a * a^(b-1)) mod m (a * (a^((b-1)/2) mod m)^2) mod m迭代实现通常更高效def fast_modular_exponentiation(base, exponent, modulus): 快速模幂运算计算 (base ^ exponent) % modulus 的高效方法。 if modulus 1: return 0 result 1 base base % modulus # 确保 base 小于 modulus while exponent 0: # 如果当前指数位为1则将当前的 base 乘入结果 if exponent % 2 1: # 或者使用位操作 (exponent 1) result (result * base) % modulus # 将 base 平方并将指数右移一位除以2 base (base * base) % modulus exponent exponent // 2 # 或者使用位操作 exponent 1 return result为什么这样快假设指数是13二进制1101。算法过程是result 1exp13(1101), bit1: result (1*a) % m aexp6(110), bit0: 只平方 a - a^2exp3(11), bit1: result (a * a^2) % m a^3exp1(1), bit1: result (a^3 * a^4) % m a^7exp0: 结束实际上我们只进行了几次乘法和取模运算而不是13次。对于大指数这种效率提升是指数级的。4. 从零构建RSA类密钥生成与加解密有了核心算法支撑我们可以搭建一个完整的、用于演示的RSA类。请注意这个实现是教育性质的侧重于清晰易懂并未包含工业级的随机数生成、填充方案等切勿直接用于生产环境。4.1 密钥生成将理论转化为代码import random from math import gcd class SimpleRSA: def __init__(self, key_size1024): 初始化RSA实例。 key_size: 期望的密钥模数 n 的比特长度。实际 n 的长度可能略小于 key_size*2。 self.key_size key_size self.p self.q self.n self.phi self.e self.d None def generate_keypair(self): 生成RSA公钥和私钥对。 # 1. 选择两个大质数 p 和 q (这里为演示使用小质数实际应用必须用密码学安全的随机大质数) # 警告以下方法不适用于真实加密仅用于教学演示。 # 真实环境应使用 secrets 模块和质数测试如Miller-Rabin。 print(正在生成质数 p 和 q...) # 为了演示稳定我们暂时固定两个质数。实际应替换为随机生成。 self.p 61 # 应替换为 generate_large_prime(self.key_size//2) self.q 53 # 应替换为 generate_large_prime(self.key_size//2) print(fp {self.p}, q {self.q}) # 2. 计算模数 n self.n self.p * self.q print(fn p * q {self.n}) # 3. 计算欧拉函数 φ(n) self.phi (self.p - 1) * (self.q - 1) print(fφ(n) (p-1)*(q-1) {self.phi}) # 4. 选择公钥指数 e # 通常使用 65537它是一个质数且与绝大多数 φ(n) 互质。 self.e 65537 # 检查 e 是否与 φ(n) 互质 if gcd(self.e, self.phi) ! 1: # 如果 65537 不互质极其罕见则尝试另一个小质数如 3。 self.e 3 while gcd(self.e, self.phi) ! 1: self.e 2 # 尝试下一个奇数 print(f公钥指数 e {self.e}) # 5. 计算私钥指数 d (e 模 φ(n) 的逆元) self.d mod_inverse(self.e, self.phi) print(f私钥指数 d {self.d}) # 返回公钥和私钥 public_key (self.n, self.e) private_key (self.n, self.d) print(f生成完毕公钥 (n, e): {public_key}) print(f 私钥 (n, d): {private_key}) return public_key, private_key踩坑提醒上面的代码中质数生成部分被简化了。在真实项目中这是最需要小心的地方。你必须使用密码学安全的随机数生成器如Python的secrets模块来生成候选大数并经过多次米勒-拉宾素性测试才能确认其为质数。使用小质数或非安全的随机数你的RSA将毫无安全性可言。4.2 基础加解密整数消息的传输现在我们实现最基础的、对整数进行加解密的函数。def encrypt_int(self, m, public_key): 使用公钥加密一个整数消息 m。 public_key: 元组 (n, e) 返回密文整数 c。 n, e public_key if m 0 or m n: raise ValueError(f明文 m ({m}) 必须在区间 [0, n-1] 内。当前 n{n}) # 使用快速模幂运算进行加密 c fast_modular_exponentiation(m, e, n) return c def decrypt_int(self, c, private_key): 使用私钥解密密文整数 c。 private_key: 元组 (n, d) 返回解密后的明文整数 m。 n, d private_key if c 0 or c n: raise ValueError(f密文 c ({c}) 必须在区间 [0, n-1] 内。当前 n{n}) # 使用快速模幂运算进行解密 m fast_modular_exponentiation(c, d, n) return m让我们写一个简单的测试来验证整个流程# 测试代码 if __name__ __main__: rsa SimpleRSA(key_size512) # 使用小密钥方便演示 public_key, private_key rsa.generate_keypair() # 测试一个整数消息 original_message 42 print(f\n原始消息 (整数): {original_message}) # 加密 ciphertext rsa.encrypt_int(original_message, public_key) print(f加密后的密文 (整数): {ciphertext}) # 解密 decrypted_message rsa.decrypt_int(ciphertext, private_key) print(f解密后的消息 (整数): {decrypted_message}) # 验证 if original_message decrypted_message: print(✅ 加解密测试成功) else: print(❌ 加解密失败)运行这段代码你会看到类似以下的输出直观地展示了RSA如何对一个数字进行变换和恢复正在生成质数 p 和 q... p 61, q 53 n p * q 3233 φ(n) (p-1)*(q-1) 3120 公钥指数 e 17 私钥指数 d 2753 生成完毕公钥 (n, e): (3233, 17) 私钥 (n, d): (3233, 2753) 原始消息 (整数): 42 加密后的密文 (整数): 2557 解密后的消息 (整数): 42 ✅ 加解密测试成功5. 处理文本消息编码、填充与分块恭喜你我们已经实现了一个能对整数进行加解密的RSA但现实世界中我们需要加密的是文本、文件等数据。这就引出了三个关键问题编码、填充和分块。5.1 为什么不能直接加密字符串计算机中字符串由字节构成。简单的想法是将每个字符的ASCII码或Unicode当作整数加密。但这存在严重问题效率极低RSA运算非常慢逐个字符加密不可行。不安全它等同于一种简单的替换密码容易受到频率分析等攻击。大小限制明文整数m必须小于模数n。对于长文本单个字符的编码值虽然小但如果我们想把多个字符组合成一个整数这个整数很容易超过n。因此标准做法是将文本字符串转换为字节序列。将这些字节序列解释为一个大的整数int.from_bytes。确保这个整数小于n。如果不满足就需要将字节序列分块。在将字节转换为整数之前先进行填充。填充方案如PKCS#1 v1.5或OAEP不仅解决了分块对齐问题更重要的是增加了随机性防止多种攻击如确定性加密导致相同明文产生相同密文。5.2 实现一个简单的分块加密示例为了理解过程我们先实现一个不包含标准填充、仅进行分块的简单文本加解密。再次强调这种简单分块缺乏填充是不安全的仅用于教学演示。假设我们的模数n是2048位256字节。一个UTF-8编码的字符通常占1-4字节。我们可以设定一个块大小比如block_size n_byte_length - 11为什么减11这是PKCS#1 v1.5填充的预留空间我们先借用这个概念。def encrypt_text(self, plaintext, public_key): 一个简化的、不安全的文本加密演示。 将字符串分块每块转换为整数后加密。 警告此方法未使用标准填充仅用于演示原理切勿用于实际加密 n, e public_key # 计算n的字节长度并确定每块明文的最大字节数预留空间模拟填充 n_byte_len (n.bit_length() 7) // 8 max_block_bytes n_byte_len - 11 # 模拟PKCS#1 v1.5的预留 # 将字符串编码为字节 plaintext_bytes plaintext.encode(utf-8) ciphertext_blocks [] # 分块处理 for i in range(0, len(plaintext_bytes), max_block_bytes): block plaintext_bytes[i:imax_block_bytes] # 将字节块转换为整数 m_int int.from_bytes(block, byteorderbig, signedFalse) # 加密该整数块 c_int self.encrypt_int(m_int, public_key) # 将加密后的整数转换为字节并填充到固定长度n_byte_len c_bytes c_int.to_bytes(n_byte_len, byteorderbig) ciphertext_blocks.append(c_bytes) # 将所有密文块连接起来。在实际中可能需要额外的格式来标记块边界。 # 一种简单方法是使用固定长度或者用分隔符。这里我们返回字节列表。 return ciphertext_blocks def decrypt_text(self, ciphertext_blocks, private_key): 解密上面 encrypt_text 方法生成的密文块列表。 n, d private_key n_byte_len (n.bit_length() 7) // 8 plaintext_bytes_list [] for c_bytes in ciphertext_blocks: # 将密文字节转换回整数 c_int int.from_bytes(c_bytes, byteorderbig) # 解密 m_int self.decrypt_int(c_int, private_key) # 将解密后的整数转换回字节 # 注意我们需要知道原始明文块的长度。在无填充的情况下这很困难。 # 这里我们假设解密出的整数转换成的字节长度 原始块的最大长度。 # 这是一个脆弱的假设再次说明无填充的不实用性。 max_block_bytes n_byte_len - 11 m_bytes m_int.to_bytes(max_block_bytes, byteorderbig) # 去除可能存在的尾部零因为to_bytes会填充到指定长度 # 这种方法非常不稳健仅用于演示 m_bytes m_bytes.rstrip(b\x00) plaintext_bytes_list.append(m_bytes) # 拼接所有字节块并解码为字符串 decrypted_bytes b.join(plaintext_bytes_list) return decrypted_bytes.decode(utf-8, errorsignore)重要警告上述decrypt_text中去除尾部零 (rstrip(b\x00)) 的方法极其不可靠。如果原始明文中就包含零字节解密就会出错。这正体现了标准填充方案的绝对必要性。填充方案会在加密前向明文添加特定结构的、包含随机数的数据解密后可以明确地移除这些填充数据从而准确恢复原始明文。5.3 迈向标准PKCS#1 OAEP填充简介在实际应用中如TLS、PGPRSA从不直接加密原始数据。而是使用一个称为“RSAES-OAEP”或“RSAES-PKCS1-v1_5”的填充方案。OAEPOptimal Asymmetric Encryption Padding是目前推荐的标准它通过随机化和哈希函数提供了更强的安全性抵抗选择密文攻击等。简单来说OAEP的过程是对待加密的消息M先使用一个哈希函数和随机数r通过一种称为“掩码生成函数”的流程将M编码成一个长度恰好等于模数字节长度k的“数据块”DB。然后对这个数据块DB进行RSA加密。解密时先RSA解密得到DB再通过反向的OAEP解码过程验证填充格式并恢复出原始消息M。实现OAEP需要编码哈希函数如SHA-256、MGF1掩码生成函数等代码较为复杂。Python的cryptography库中的rsa模块就内置了OAEP的实现。对于我们这个教学项目理解其存在和重要性远比手动实现一个不完整的版本更有价值。核心教训是在生产环境中永远不要自己实现加密原语使用经过严格审计的库如cryptography。6. 验证、调试与常见陷阱自己实现算法调试是必不可少的环节。以下是一些验证方法和常见问题。6.1 如何验证你的RSA实现是正确的基础数学验证检查p和q是否为质数。验证n p * q。验证φ(n) (p-1)*(q-1)。验证gcd(e, φ(n)) 1。验证(e * d) % φ(n) 1。加解密循环测试随机生成多个小于n的整数m。计算c encrypt_int(m, public_key)。计算m2 decrypt_int(c, private_key)。断言m m2。与标准库交叉验证 这是最可靠的方法。用你的代码生成密钥对然后用一个成熟的密码学库如Python的cryptography加载这些密钥进行加密和解密看结果是否一致。from cryptography.hazmat.primitives.asymmetric import rsa, padding from cryptography.hazmat.primitives import hashes import cryptography.hazmat.primitives.serialization as serialization # 假设你用我们的SimpleRSA生成了 (n, e, d) # 1. 用 cryptography 构建公钥和私钥对象 public_numbers rsa.RSAPublicNumbers(e, n) private_numbers rsa.RSAPrivateNumbers(p, q, d, d, d, d, public_numbers) # 这里简化了实际需要所有参数 # ... 加载密钥 ... # 2. 用 cryptography 加密一段数据 # 3. 用我们的 SimpleRSA.decrypt 解密看是否能得到原文 # 4. 反之亦然这个过程能帮你发现密钥格式、填充方式等方面的细微差别。6.2 实现中常见的“坑”整数溢出与字节序 Python的整数是任意精度的所以没有溢出问题。但在将整数与字节串相互转换时int.to_bytes和int.from_bytes字节序byteorder必须一致通常使用big。指定signedFalse也很重要确保处理的是无符号整数。密钥生成中的随机性 教学代码中我们用了固定质数。真实场景下质数生成必须是密码学安全的随机过程。使用random模块是不安全的应该使用secrets模块生成随机种子并结合米勒-拉宾素性测试进行多次检验。性能问题 RSA的模幂运算很慢。密钥越长越安全但也越慢。通常RSA用于加密对称密钥如AES密钥而不是直接加密大量数据。这就是“混合加密系统”的概念。侧信道攻击 即使是正确的算法实现方式也可能泄露信息。例如快速模幂运算中根据指数位的0或1执行result (result * base) % modulus的次数不同。通过精确测量运算时间攻击者可能推测出指数d私钥的位模式。工业级实现会使用“蒙哥马利模乘”和“常数时间”编程等技术来抵御此类攻击。我们的简单实现不具备这种防护。填充预言攻击 这就是为什么必须使用OAEP等填充方案的原因。如果解密方在收到错误填充的密文时返回不同的错误信息如“填充错误” vs “解密失败”攻击者可能利用这些信息逐步破解密文。OAEP填充提供了“所有或无”的安全性即填充错误会导致整个解密失败不泄露任何信息。7. 从教学实现到工业应用鸿沟与桥梁通过上面的步骤我们已经完成了一个功能完整的RSA教学实现。但必须清醒认识到这个实现和可以投入使用的工业级密码库之间存在着巨大的鸿沟。理解这些差距正是这个项目的深层价值所在。工业级实现需要考虑的额外因素密码学安全随机数生成器random模块是伪随机不适合密码学。必须使用操作系统提供的密码学安全随机源如secrets模块、os.urandom()或专门的硬件随机数生成器。大质数生成与测试生成一个1024位的质数并非易事。需要生成一个随机的、适当大小的奇数。进行初步筛选如排除小质数的倍数。进行多次米勒-拉宾素性测试。测试次数取决于所需的安全级别。例如对于1024位密钥进行40-50次测试可以将误判合数被误认为质数的概率降到极低。标准与兼容性你的密钥和密文需要能被其他系统识别。这意味着你需要遵循标准格式如PEM格式将密钥编码为Base64并加上-----BEGIN RSA PRIVATE KEY-----这样的头尾标记。DER格式二进制的ASN.1编码。PKCS#1, PKCS#8标准定义了密钥信息的结构。 实现这些编码/解码本身就是一个复杂的任务。性能优化中国剩余定理在解密时利用私钥的p和q可以分别计算m_p c^d mod p和m_q c^d mod q然后通过CRT组合得到最终的m。这可以将解密速度提升约4倍。窗口算法对快速模幂运算的进一步优化。蒙哥马利约简一种高效的模乘算法。抵抗侧信道攻击常数时间实现确保算法的执行时间与秘密数据如私钥d无关。盲化在解密操作前先用一个随机数对密文进行盲化处理以隐藏真实的运算路径。那么我们亲手实现的意义是什么深刻理解你不再把RSA当作一个黑盒API。你知道了密钥从哪里来加解密如何运转以及为什么某些操作如填充至关重要。调试能力当你在使用高级库遇到问题时比如“RSA公钥未找到”这类错误你对其背后的数据结构有概念能更有效地排查。安全直觉你会本能地对“自己写加密代码”保持警惕并理解为什么安全专家总是强调“不要自己造轮子”。学习其他算法的基础RSA涉及的数论知识模运算、欧拉定理、模逆元是理解许多其他密码学协议如Diffie-Hellman密钥交换、椭圆曲线密码学的基石。所以下次当你在代码中轻松地调用RSA.import_key()或cipher.encrypt()时你会对幕后发生的复杂而精妙的过程怀有一份敬意。这份从零实现的经历让你从一个API调用者变成了一个原理的洞察者。这才是动手实现核心算法最大的收获。