1. 项目概述为什么我们要亲手实现RSA如果你看过《模仿游戏》或者《谍影重重》这类电影一定对“加密”这个词不陌生。电影里特工们用一串串看似毫无规律的字符传递绝密信息敌方截获后却束手无策那种紧张感和智力上的博弈正是密码学的魅力所在。RSA这个以三位发明者姓氏首字母命名的算法就是现代密码学皇冠上的一颗明珠。它不仅是电影情节的常客更是我们每天网上购物、登录银行、收发加密邮件时背后默默无闻的守护神。你可能用过各种加密库一行import rsa调用几个函数加密解密就完成了。这很方便但就像开车不需要懂发动机原理一样你可能会错过最精彩的部分。这个项目的核心就是带你从“会用”到“懂原理”亲手用Python从零开始一步步推导并实现RSA加密的全过程特别是那个最核心也最容易被当成黑盒的密钥生成步骤。我们将不依赖任何现成的RSA库只用Python标准库中的基础数学工具把电影里的概念变成屏幕上可运行的代码。这不仅能让你彻底理解非对称加密的基石更能让你在面试或解决复杂安全架构问题时拥有知其所以然的底气。2. RSA加密的核心原理单向陷阱门函数在动手写代码之前我们必须先搞清楚RSA赖以生存的数学基础。它之所以安全核心在于一个被称为“单向陷阱门函数”的概念。想象一下我给你两个很大的质数比如61和53让你把它们相乘得到3233这非常容易小学生心算可能费点劲但计算机瞬间完成。现在我反过来只给你3233这个结果让你找出它是由哪两个质数相乘得来的即质因数分解。你会发现这件事变得极其困难尤其是当数字大到有几百位的时候即使用最强大的超级计算机也需要耗费以年甚至世纪计的时间。这种“正向计算简单逆向求解极其困难”的特性就是“单向函数”。而“陷阱门”的意思是如果你掌握一些特定的、秘密的信息比如其中一个质数那么逆向求解就会变得非常简单。在RSA中这对大质数就是“陷阱门”的关键。2.1 关键数学概念与公式RSA整个体系建立在几个数学公式之上我们一步步拆解选择两个大质数p和q。这是所有运算的起点也是秘密的核心。计算模数 nn p * q。这个n是公开的长度比特数决定了密钥的强度。常见的RSA-2048就是指n有2048比特。计算欧拉函数 φ(n)φ(n) (p-1) * (q-1)。这个值必须保密。欧拉函数计算的是小于n且与n互质的正整数的个数。对于两个质数相乘的情况公式就是上面这样。选择公钥指数 e选择一个整数e满足1 e φ(n)且e与φ(n)互质即最大公约数gcd(e, φ(n)) 1。通常选择65537 (0x10001)因为它二进制表示中只有两个1计算效率高且足够大安全性好。计算私钥指数 d计算e关于φ(n)的模逆元d。即满足(d * e) % φ(n) 1。d是私钥的核心必须严格保密。加密过程对于明文消息m需要先将其转换为小于n的整数计算密文c (m ^ e) % n。这里^表示幂运算。解密过程用私钥解密密文c恢复明文m (c ^ d) % n。这个过程的正确性由欧拉定理保证。简单理解因为d是e的模逆元所以(m ^ e) ^ d m ^ (e*d) m ^ (k*φ(n)1)。根据欧拉定理当m与n互质时m ^ φ(n) % n 1因此上式结果等于m % n。即使m与n不互质通过中国剩余定理也能证明解密依然正确。注意这里的m在实际应用中通常不是直接加密的原始数据如字符串而是经过填充如OAEP后的数据。填充是为了防止特定的攻击如明文猜测攻击。我们为了聚焦核心原理先实现“教科书式RSA”但你必须知道生产环境绝对不要使用无填充的RSA。2.2 为什么RSA是安全的安全性的根在于大整数质因数分解的困难性。公钥是(n, e)谁都能看到。私钥是(n, d)但计算d需要φ(n)计算φ(n)需要p和q。攻击者只知道公开的n想从n倒推出p和q目前没有高效算法。只要p和q足够大比如1024位以上现有的计算能力就无法在可接受的时间内完成分解。所以整个RSA大厦的地基就是“生成两个足够大、足够随机的质数p和q”。接下来我们就重点攻克这个问题。3. 核心实战手写RSA密钥生成器理解了原理我们开始用Python实现。我们将分模块构建一个完整的RSA密钥生成器。3.1 环境准备与基础工具函数我们只需要Python标准库。核心是random模块用于生成随机数以及自带的整数运算和math库。首先实现一些基础数学工具函数这些是构建RSA的砖瓦。import random import math def gcd(a, b): 使用欧几里得算法计算最大公约数。 while b ! 0: a, b b, a % b return a def extended_gcd(a, b): 扩展欧几里得算法。返回 (gcd, x, y)使得 a*x b*y gcd(a, b)。 这个函数用于后续计算模逆元。 if a 0: return b, 0, 1 gcd, x1, y1 extended_gcd(b % a, a) x y1 - (b // a) * x1 y x1 return gcd, x, y def modinv(a, m): 计算 a 关于模 m 的模逆元。即找到 x 使得 (a * x) % m 1。 基于扩展欧几里得算法实现。 g, x, y extended_gcd(a, m) if g ! 1: raise Exception(模逆元不存在) return x % m def is_prime_miller_rabin(n, k5): 使用米勒-拉宾素性测试判断一个数是否为质数。 k 是测试次数次数越多准确率越高但耗时也越长。 if n 2: return False # 处理小质数 small_primes [2, 3, 5, 7, 11, 13, 17, 19, 23, 29] if n in small_primes: return True for p in small_primes: if n % p 0: return False # 将 n-1 写成 d * 2^r 的形式 r, d 0, n - 1 while d % 2 0: r 1 d // 2 # 进行 k 轮测试 for _ in range(k): a random.randrange(2, n - 1) x pow(a, d, n) # 使用内置pow进行模幂运算效率极高 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 # 本轮测试未通过n是合数 return True # 通过所有测试n极有可能是质数实操心得pow(a, b, c)是Python的内置函数直接计算(a**b) % c并且使用了高效的模幂算法如快速幂比自己写循环快无数倍在处理大整数时至关重要。米勒-拉宾测试是一个概率性测试但k取5时误判将一个合数判为质数的概率已经低于1 / 4^k即低于千万分之一在实际应用中完全可靠。OpenSSL等工业级库也使用它。3.2 生成大质数RSA的基石这是最关键的一步。我们不能简单地在一个范围内随机取数然后测试那样效率太低。标准做法是随机生成一个指定位数的奇数然后不断递增直到通过素性测试。def generate_large_prime(bit_length): 生成一个指定位数的大质数。 if bit_length 2: raise ValueError(质数位数至少为2) while True: # 1. 生成一个随机奇数。确保最高位和最低位都是1以保证位数准确且是奇数。 candidate random.getrandbits(bit_length) candidate | (1 (bit_length - 1)) | 1 # 设置最高位和最低位为1 # 2. 使用米勒-拉宾测试 if is_prime_miller_rabin(candidate): return candidate # 如果不通过candidate 2继续测试下一个奇数 # 在实际更健壮的实现中这里可以加一个上限避免在极端情况下死循环。注意事项random.getrandbits()是生成密码学安全随机数的关键。对于生产环境应使用secrets.randbits()它提供了密码学安全的随机源。设置最高位为1是为了确保生成的数确实达到了指定的比特长度例如1024位的数其二进制形式第一位必须是1。这是一个“猜-测”循环。虽然平均需要尝试很多次根据素数定理但对于计算机来说生成一个1024位的质数通常在秒级完成。3.3 完整的RSA密钥对生成函数现在我们可以将以上部分组合起来生成完整的RSA密钥对。def generate_rsa_keys(bit_length1024): 生成RSA公钥和私钥。 参数 bit_length: 模数 n 的目标比特长度例如1024, 2048。 返回: (public_key, private_key)其中公钥为(e, n)私钥为(d, n)。 if bit_length % 2 ! 0: raise ValueError(比特长度最好是偶数以便生成两个长度相近的质数。) p_bit_length bit_length // 2 q_bit_length bit_length - p_bit_length # 允许长度略有差异更随机 print(f正在生成 {p_bit_length} 位左右的质数 p...) p generate_large_prime(p_bit_length) print(fp 生成完毕。) print(f正在生成 {q_bit_length} 位左右的质数 q...) while True: q generate_large_prime(q_bit_length) if q ! p: # 确保p和q不相等虽然概率极低 break print(fq 生成完毕。) # 计算 n 和 φ(n) n p * q phi_n (p - 1) * (q - 1) # 选择公钥指数 e e 65537 # 行业标准一个优秀的默认值 # 检查 e 是否与 φ(n) 互质对于65537和大的φ(n)几乎总是互质 if gcd(e, phi_n) ! 1: # 如果不互质需要重新选择e或者极罕见情况重新生成密钥 raise Exception(e 与 φ(n) 不互质请尝试重新生成密钥。) # 计算私钥指数 d d modinv(e, phi_n) public_key (e, n) private_key (d, n) # 保存质数 p 和 q用于加速解密中国剩余定理。实际存储私钥时有时会包含。 private_key_with_crt (d, n, p, q) print(f\n密钥生成成功) print(f模数 n (公开) 的长度: {n.bit_length()} 比特) print(f公钥 e (公开): {e}) print(f私钥 d (保密): [已隐藏]) print(f质数 p (绝密): [已隐藏]) print(f质数 q (绝密): [已隐藏]) return public_key, private_key, private_key_with_crt核心环节解析质数长度通常让p和q长度大致相等。如果两者大小过于悬殊可能会降低安全性。所以我们将目标长度平分。公钥指数 e直接固定为65537。这是一个绝佳选择因为它是一个费马数2^161二进制只有两个1使得模幂运算pow(m, e, n)非常快。同时它足够大避免了某些小指数攻击。模逆元计算我们之前实现的modinv函数在这里派上用场它高效地计算出了私钥d。中国剩余定理(CRT)加速返回的private_key_with_crt包含了p和q。在解密时利用CRT可以将计算c^d mod n分解为计算模p和模q下的两个更小规模的运算速度能提升3-4倍。这是所有工业级RSA实现的标准优化。3.4 加密与解密函数的实现有了密钥加密和解密函数就非常直观了。def rsa_encrypt(public_key, plaintext_int): 使用公钥加密一个整数。 参数 public_key: 元组 (e, n) 参数 plaintext_int: 需要加密的整数必须满足 0 plaintext_int n 返回: 密文整数 e, n public_key if not (0 plaintext_int n): raise ValueError(明文整数必须在 [0, n) 范围内。) ciphertext_int pow(plaintext_int, e, n) return ciphertext_int def rsa_decrypt(private_key, ciphertext_int): 使用私钥解密密文整数。 参数 private_key: 元组 (d, n) 或 (d, n, p, q) 参数 ciphertext_int: 密文整数 返回: 解密后的明文整数 if len(private_key) 4: # 使用CRT加速解密 d, n, p, q private_key # 计算 m_p c^(d mod (p-1)) mod p dp d % (p - 1) m_p pow(ciphertext_int, dp, p) # 计算 m_q c^(d mod (q-1)) mod q dq d % (q - 1) m_q pow(ciphertext_int, dq, q) # 使用扩展欧几里得求 q 关于 p 的逆元 _, q_inv_p, _ extended_gcd(q, p) # CRT合成 h (q_inv_p * (m_p - m_q)) % p plaintext_int m_q h * q else: # 标准解密 d, n private_key plaintext_int pow(ciphertext_int, d, n) return plaintext_int实操要点加密和解密的核心就是一行pow函数调用这再次体现了Python大整数运算和内置算法的强大。CRT加速的实现看起来步骤多了但每一步的模数p或q都只有n的一半大小pow运算的代价远小于直接对n运算。这是必学的优化技巧。再次强调这里的plaintext_int是整数。真实世界的文本或数据需要先通过编码如PKCS#1 OAEP填充转换为整数。4. 从字符串到加密完整的应用演示为了看到一个完整流程我们实现一个简单的演示加密一个短字符串。def bytes_to_int(b): 将字节串转换为大整数。 return int.from_bytes(b, byteorderbig, signedFalse) def int_to_bytes(i, lengthNone): 将大整数转换回字节串。 length 参数可以指定输出字节长度用于填充对齐。 b i.to_bytes((i.bit_length() 7) // 8, byteorderbig) if length is not None: if len(b) length: raise ValueError(整数太大无法放入指定长度。) b b.rjust(length, b\x00) # 左侧填充零字节 return b def demo_rsa_string(messageHello, RSA!): print(*50) print(演示使用手写RSA加密字符串) print(*50) # 1. 生成密钥 print(\n1. 生成RSA密钥对 (1024位)...) public_key, _, private_key_crt generate_rsa_keys(bit_length1024) e, n public_key # 2. 准备明文 print(f\n2. 原始消息: {message}) message_bytes message.encode(utf-8) # 注意无填充的RSA能加密的数据大小受限于n。对于1024位n最多加密117字节。 # 这里我们消息很短所以直接转换。 m_int bytes_to_int(message_bytes) print(f 转换为整数: {m_int}) print(f 整数比特长度: {m_int.bit_length()} (必须 {n.bit_length()})) if m_int n: print(错误明文整数 n无法加密) return # 3. 加密 print(\n3. 使用公钥 (e, n) 加密...) c_int rsa_encrypt(public_key, m_int) print(f 得到密文整数: {c_int}) # 4. 解密 print(\n4. 使用私钥 (含CRT参数) 解密...) decrypted_int rsa_decrypt(private_key_crt, c_int) print(f 解密得到整数: {decrypted_int}) # 5. 恢复字符串 decrypted_bytes int_to_bytes(decrypted_int) recovered_message decrypted_bytes.decode(utf-8) print(f\n5. 解密后的消息: {recovered_message}) # 验证 if message recovered_message: print(\n✅ 演示成功加密解密结果一致。) else: print(\n❌ 演示失败) return public_key, private_key_crt, c_int运行这个demo_rsa_string()函数你将在控制台看到一个完整的加密解密流程。从生成两个大质数开始到最终还原出“Hello, RSA!”字符串每一步的计算结果都清晰可见。5. 常见问题、陷阱与进阶指南自己实现一遍后你会对RSA有更深的理解也会遇到一些“坑”。这里总结几个关键点。5.1 为什么不能直接加密长文本或文件这就是著名的“RSA加密数据大小限制”问题。由于RSA加密本质上是模n的幂运算明文m必须是一个小于n的整数。对于1024位的n其最大值约等于2^1024转换成字节是128字节。但这128字节并非全部可用于数据因为还需要填充结构来保证安全。无填充时最多加密floor(log2(n))比特的数据即略小于128字节。解决方案实际应用中RSA不直接加密数据本身而是采用“混合加密”体系。随机生成一个对称密钥如AES-256密钥。用这个对称密钥加密实际的大数据文件、长文本。用RSA公钥加密这个对称密钥。将RSA加密后的对称密钥和AES加密后的数据一起发送。 接收方则先用RSA私钥解密出对称密钥再用对称密钥解密数据。这样既利用了RSA的非对称特性进行密钥交换又利用了对称加密的高效性。5.2 “教科书式RSA”有哪些安全隐患我们实现的RSA是教科书式的存在多种攻击风险明文猜测攻击如果明文空间很小比如只有“是”或“否”攻击者可以直接用公钥加密所有可能明文与截获的密文对比。共模攻击如果同一份明文用不同的公钥相同的n不同的e加密可能被破解。低指数攻击如果e很小比如3并且明文也很小加密后的c m^e可能小于n那么直接对c开e次方就能得到m。解决方案使用标准的填充方案如PKCS#1 v1.5或更优的OAEP (Optimal Asymmetric Encryption Padding)。填充会在明文前面和后面加入特定的、随机的结构使得加密前的整数“随机化”并且具有可验证的结构从而抵御上述攻击。Python的cryptography库中的RSA实现就默认使用OAEP填充。5.3 如何选择密钥长度密钥长度直接关系到安全性。随着计算能力的提升被推荐的RSA密钥长度也在增加。1024位已不再被推荐用于新的系统。NIST建议在2030年后停止使用。2048位当前2023-2024年的标准选择被认为在可预见的未来是安全的。3072位或4096位用于需要长期安全如CA根证书或更高安全级别的场景。在我们的generate_rsa_keys函数中可以通过bit_length参数指定。生成2048位密钥的时间大约是1024位的数倍因为生成大质数更困难且后续运算量也更大。5.4 性能优化与生产环境建议我们的实现是教学性质的。生产环境中你需要使用权威库如Python的cryptography。这些库经过了无数专家的审计和优化实现了正确的填充、高效的底层运算可能用C语言实现、以及防侧信道攻击等措施。密钥存储私钥必须妥善保管通常加密后存储在文件或硬件安全模块HSM中。公钥可以公开分发。随机数源使用secrets模块替代random模块来生成质数候选数确保密码学安全性。不要自己造轮子用于安全系统这是最重要的建议。密码学非常精妙一个微小的实现失误如随机性不足、时序攻击都可能导致整个系统被攻破。学习实现是为了理解实际应用请务必使用久经考验的库。5.5 调试与问题排查如果你在实现过程中遇到问题可以按以下步骤排查检查质数生成打印出生成的p和q用is_prime_miller_rabin多测试几次确保它们真的是质数。验证数学关系生成密钥后手动验证(e * d) % φ(n)是否等于1。这是最根本的校验。检查数据范围加密时确保明文整数m严格小于n。使用小参数测试先用很小的、可手算的质数如p61, q53进行测试验证整个加密解密流程。确保基础逻辑正确后再换用大质数。对比标准库用cryptography库生成一个密钥对加密一个数字然后用你自己的解密函数去解密看是否能成功。这是一个非常好的集成测试方法。亲手实现一遍RSA就像亲手拆解并组装了一台精密的钟表。你看到了每一个齿轮质数生成、模逆元计算、模幂运算是如何咬合最终让加密和解密这两个反向过程完美运转的。这种理解是单纯调用API无法获得的。它让你在面对“为什么RSA是安全的”、“2048位密钥到底有多强”这类问题时能给出从数学根基出发的自信回答。虽然最终在真实项目中我们还是会信赖cryptography这样的工业级库但此刻你代码编辑器里这个能自己生成密钥、加密解密的小程序无疑是你技术理解力的一次扎实的飞跃。下次再看密码学相关的电影你嘴角或许会浮现出一丝会心的微笑——因为你知道那炫酷画面背后的数学之美你已经亲手触碰过了。
