Python实现RSA加密：从数学原理到工程实践

1. 项目概述从零到一用Python亲手实现RSA如果你正在学习密码学或者需要在项目中集成非对称加密功能那么“用Python实现RSA”绝对是一个绕不开的经典练手项目。RSA算法这个以三位发明者姓氏首字母命名的非对称加密体系自1977年诞生以来就成为了现代信息安全特别是网络通信、数字签名、证书体系的基石。我们每天使用的HTTPS、SSH登录、软件更新验证背后都有它的身影。然而仅仅调用cryptography或PyCryptodome库中的RSA.encrypt()和RSA.decrypt()函数总感觉隔着一层纱知其然而不知其所以然。这个项目的核心价值就在于亲手实现——从生成一对大素数开始一步步推导出公钥和私钥然后基于数论原理完成加密、解密、签名和验签的全过程。这不仅能让你深刻理解“为什么非对称加密是安全的”更能让你在遇到诸如“密钥格式错误”、“填充模式异常”等问题时拥有从底层排查和解决的能力。无论你是密码学的初学者还是希望夯实基础的开发者这个项目都将是一次极具价值的实践。2. 核心原理与数学基础拆解在动手写代码之前我们必须先吃透RSA背后的数学原理。这就像盖房子要先打地基理解了这些后续的代码实现才会清晰明了。2.1 密钥生成的数学核心欧拉函数与模逆元RSA的安全性建立在“大数分解难题”之上。简单说给你两个非常大的质数p和q你能轻松算出它们的乘积N但反过来给你一个非常大的N你想找出它是由哪两个质数相乘得到的以目前计算机的计算能力需要极其漫长的时间可能数百年甚至更久。密钥生成过程就是围绕这个难题来构造的选择两个大质数随机选择两个足够大的、不相等的质数p和q。这里“足够大”是关键通常建议在1024位约308位十进制数以上才具备基本安全性。计算模数NN p * q。这个N就是公钥的一部分也是加解密运算的模数。它会公开。计算欧拉函数φ(N)φ(N) (p-1) * (q-1)。欧拉函数φ(n)表示小于n的正整数中与n互质的数的个数。对于两个质数乘积这个公式成立。这个φ(N)的值必须绝对保密它是私钥安全性的核心。选择公钥指数e选择一个整数e满足1 e φ(N)且e与φ(N)互质即最大公约数gcd(e, φ(N)) 1。通常为了计算效率会直接选用素数655370x10001因为它二进制表示中只有两个1便于快速模幂运算且安全性经过充分验证。计算私钥指数d计算d使得(d * e) mod φ(N) 1。也就是说d是e在模φ(N)下的模逆元。这个d就是私钥的核心部分必须严格保密。至此你的公钥就是(e, N)私钥就是(d, N)。可以看到知道N和e无法推导出d因为需要知道φ(N)而要知道φ(N)就必须分解N得到p和q——这正是大数分解难题。2.2 加解密与签名验签的运算本质有了密钥对加解密和签名验签就变成了模幂运算。加密公钥操作对于明文消息m需要先转换为一个小于N的整数计算密文c m^e mod N。解密私钥操作对于密文c计算明文m c^d mod N。根据欧拉定理可以证明(m^e)^d mod N m。签名和验签的过程与加解密类似但目的和密钥使用顺序相反签名私钥操作对消息的摘要如SHA-256哈希值H计算签名s H^d mod N。这里是用私钥对“消息指纹”进行加密。验签公钥操作收到消息和签名s后重新计算消息摘要H然后计算H s^e mod N。如果H等于H则证明签名有效因为只有持有私钥的一方才能生成这样的s使得用公钥e解密后能得到正确的摘要。注意在实际应用中直接对原始消息进行m^e mod N运算是不安全的被称为“教科书式RSA”或“裸RSA”容易受到多种攻击。必须引入填充方案如PKCS#1 v1.5或OAEP将消息填充后再加密。我们的实现会先演示原理再强调并引入填充的必要性。3. 核心模块实现与代码解析我们将把整个项目拆分成几个核心函数模块并逐一实现。我们会使用Python内置的random,math库以及强大的pycryptodome库来辅助生成大素数和处理大数运算虽然最终目标是理解原理但完全从零实现大素数生成和Miller-Rabin素性测试代码量过大我们聚焦于RSA算法本身。3.1 环境准备与依赖安装首先确保你的Python环境建议3.6以上并安装必要库。我们将主要使用pycryptodome它是一个功能强大且流行的密码学库我们用它来获取安全随机数和进行大数运算。pip install pycryptodome如果安装pycryptodome遇到问题也可以尝试其前身pycrypto的替代品之一但pycryptodome维护更活跃。我们的代码会基于pycryptodome的Crypto.Util.number模块。3.2 密钥生成模块实现这是整个项目的起点。我们将实现一个generate_rsa_keys函数。from Crypto.Util.number import getPrime, GCD, inverse import random def generate_rsa_keys(bit_length1024): 生成RSA公钥和私钥。 参数: bit_length: 密钥模数N的位长度例如1024, 2048。 返回: (public_key, private_key) 其中公钥为(e, n)私钥为(d, n)。 # 1. 生成两个大素数p和q # 使用getPrime函数它内部使用安全随机数生成并经过素性测试 p getPrime(bit_length // 2) q getPrime(bit_length // 2) # 确保p和q不相等虽然概率极低但加上检查更稳妥 while p q: q getPrime(bit_length // 2) # 2. 计算模数n n p * q # 3. 计算欧拉函数φ(n) phi_n (p - 1) * (q - 1) # 4. 选择公钥指数e常用65537 e 65537 # 检查e是否与φ(n)互质如果不几乎不可能则需要重新选择e if GCD(e, phi_n) ! 1: # 理论上65537与一个偶数互质的概率很高这里为演示完整性做检查 e 65537 while GCD(e, phi_n) ! 1: e random.randrange(3, phi_n, 2) # 选择一个奇数 # 5. 计算私钥指数d即e模φ(n)的模逆元 d inverse(e, phi_n) # inverse函数使用扩展欧几里得算法高效计算模逆元 # 返回密钥对 public_key (e, n) private_key (d, n) # 注意实际应用中私钥通常包含(p, q, d, e, n)等更多信息以便优化运算。 # 这里我们只返回核心参数。 return public_key, private_key, p, q, phi_n # 返回p,q,phi_n用于演示和验证代码解析与注意事项getPrime函数这是pycryptodome提供的函数用于生成一个指定位数的“很可能”是素数的随机数。它内部使用了Miller-Rabin素性测试等算法在密码学上是安全的。自己实现一个可靠的素性测试生成器需要更多代码这里我们借助库以保证正确性和安全性。inverse函数同样来自pycryptodome用于计算模逆元实现了扩展欧几里得算法比自己手写更高效且无bug。关键点我们返回了p, q, phi_n这仅用于教学演示和验证。在真正的密钥生成函数中绝对不可以将这些敏感信息返回或存储。生成密钥后应立即安全地丢弃p,q,phi_n只保留(e, n)和(d, n)。密钥长度bit_length1024在现代已不被认为足够安全建议用于学习。生产环境应使用2048位或3072位。3.3 核心运算模幂运算的实现加解密和签名验签都涉及base^exponent mod modulus的计算。直接计算base^exponent再取模在指数很大时比如一个1024位的d是完全不可能的结果会是一个天文数字。我们必须使用快速模幂算法也称为平方-乘算法。def fast_modular_exponentiation(base, exponent, modulus): 使用平方-乘算法实现快速模幂运算 (base^exponent mod modulus)。 这是RSA运算的核心能高效处理大指数。 if modulus 1: return 0 result 1 base base % modulus # 先取模减少后续计算量 while exponent 0: # 如果当前指数位是1则将当前的base乘入结果 if exponent % 2 1: # 等价于 exponent 1 result (result * base) % modulus # 将base平方并为处理下一位指数做准备 base (base * base) % modulus # 右移指数相当于除以2取下整 exponent exponent // 2 # 等价于 exponent 1 return result为什么必须用快速模幂假设私钥d是一个1024位的数其值大约在2^1023数量级。直接计算c^d会产生一个拥有天文数字位数的中间结果任何计算机的内存都无法容纳。快速模幂算法通过边乘边取模确保所有中间结果都不会超过modulus的大小从而使得计算成为可能。其时间复杂度约为 O(log exponent)非常高效。3.4 加解密与签名验签功能实现现在我们可以组合上述模块实现完整的加解密和签名验签函数。我们先实现“教科书式RSA”无填充然后再讨论并引入填充。def rsa_encrypt(plaintext_int, public_key): 教科书式RSA加密无填充不安全仅用于演示原理 e, n public_key # 确保明文整数小于n if plaintext_int n: raise ValueError(Plaintext must be less than modulus n.) ciphertext_int fast_modular_exponentiation(plaintext_int, e, n) return ciphertext_int def rsa_decrypt(ciphertext_int, private_key): 教科书式RSA解密无填充 d, n private_key plaintext_int fast_modular_exponentiation(ciphertext_int, d, n) return plaintext_int def rsa_sign(message_hash_int, private_key): 教科书式RSA签名对哈希值直接加密 d, n private_key if message_hash_int n: # 实际上哈希输出长度如SHA-256是256位远小于通常的n至少1024位所以一般不会触发。 # 但为严谨起见可以在这里对哈希值进行填充如PKCS#1 v1.5签名填充。 raise ValueError(Hash value too large for modulus.) signature_int fast_modular_exponentiation(message_hash_int, d, n) return signature_int def rsa_verify(message_hash_int, signature_int, public_key): 教科书式RSA验签对签名解密并对比哈希值 e, n public_key decrypted_hash_int fast_modular_exponentiation(signature_int, e, n) return decrypted_hash_int message_hash_int从原理到实践的关键一跃引入填充上面的代码清晰地展示了RSA的数学原理但正如之前警告的它是极不安全的。主要问题有确定性加密同样的明文同样的公钥永远产生同样的密文。这容易受到已知明文攻击。小明文攻击如果明文m很小导致m^e n那么加密就变成了c m^e因为没超过模数攻击者可以直接对c开e次方根得到m。共模攻击、选择密文攻击等。因此所有实际的RSA应用都必须使用填充方案。最常用的是加密填充OAEP (Optimal Asymmetric Encryption Padding)这是现代标准。签名填充PSS (Probabilistic Signature Scheme) 或 PKCS#1 v1.5 填充后者虽旧但仍广泛使用但PSS更安全。由于填充方案的实现较为复杂且pycryptodome库提供了完善、安全的实现我们接下来的“实战应用”部分将转向使用库函数并解释如何正确使用它们。理解原理后安全地使用经过审计的库才是工程实践的正确选择。4. 完整流程实战与库的安全应用理解了手搓RSA的原理后我们来看看如何在实际项目中使用标准库安全地进行RSA操作。4.1 使用cryptography库生成密钥与加解密cryptography是另一个非常流行且符合现代密码学最佳实践的Python库。from cryptography.hazmat.primitives.asymmetric import rsa, padding from cryptography.hazmat.primitives import hashes, serialization from cryptography.hazmat.backends import default_backend import os # 1. 生成密钥对 private_key rsa.generate_private_key( public_exponent65537, key_size2048, # 生产环境使用2048或以上 backenddefault_backend() ) public_key private_key.public_key() # 2. 序列化密钥保存到文件或传输 # 序列化私钥PKCS#8格式PEM编码 pem_private private_key.private_bytes( encodingserialization.Encoding.PEM, formatserialization.PrivateFormat.PKCS8, encryption_algorithmserialization.NoEncryption() # 或使用BestAvailableEncryption来加密私钥文件 ) with open(private_key.pem, wb) as f: f.write(pem_private) # 序列化公钥SubjectPublicKeyInfo格式PEM编码 pem_public public_key.public_bytes( encodingserialization.Encoding.PEM, formatserialization.PublicFormat.SubjectPublicKeyInfo ) with open(public_key.pem, wb) as f: f.write(pem_public) # 3. 加密使用公钥OAEP填充 message bThis is a secret message that needs to be encrypted. # 注意RSA加密有长度限制对于长消息应使用“混合加密”用RSA加密一个对称密钥再用该对称密钥加密消息。 ciphertext public_key.encrypt( message, padding.OAEP( mgfpadding.MGF1(algorithmhashes.SHA256()), algorithmhashes.SHA256(), labelNone ) ) print(Ciphertext (hex):, ciphertext.hex()) # 4. 解密使用私钥对应OAEP填充 decrypted_message private_key.decrypt( ciphertext, padding.OAEP( mgfpadding.MGF1(algorithmhashes.SHA256()), algorithmhashes.SHA256(), labelNone ) ) print(Decrypted message:, decrypted_message.decode())4.2 使用cryptography库进行签名与验签# 1. 签名使用私钥 message_to_sign bImportant contract data. # 先对消息进行哈希 hasher hashes.Hash(hashes.SHA256(), backenddefault_backend()) hasher.update(message_to_sign) message_digest hasher.finalize() signature private_key.sign( message_digest, # 通常是对原始消息签名库内部会处理填充。这里演示对摘要签名需指定特定填充。 # 更常见的用法是直接对原始消息签名库会自动哈希并填充。 # padding.PSS( # mgfpadding.MGF1(hashes.SHA256()), # salt_lengthpadding.PSS.MAX_LENGTH # ), # hashes.SHA256() # 但cryptography的sign方法通常要求提供padding和hash算法对摘要签名需用如下方式 ) # 更正对于cryptography库通常使用以下方式对原始消息签名 signature private_key.sign( message_to_sign, padding.PSS( mgfpadding.MGF1(hashes.SHA256()), salt_lengthpadding.PSS.MAX_LENGTH ), hashes.SHA256() ) print(Signature (hex):, signature.hex()) # 2. 验签使用公钥 try: public_key.verify( signature, message_to_sign, # 验证原始消息 padding.PSS( mgfpadding.MGF1(hashes.SHA256()), salt_lengthpadding.PSS.MAX_LENGTH ), hashes.SHA256() ) print(Signature is VALID.) except Exception as e: # 通常捕获InvalidSignature异常 print(fSignature is INVALID: {e})实战要点密钥管理私钥是最高机密。在生产环境中私钥文件必须加密存储使用serialization.BestAvailableEncryption并且有严格的访问控制。绝对不要将私钥硬编码在代码或提交到版本控制系统。填充选择加密用OAEP签名用PSS。这是当前的安全最佳实践。PKCS#1 v1.5填充由于历史原因仍被支持但新项目应优先使用OAEP和PSS。消息长度RSA算法本身能加密的数据长度受限于密钥大小和填充开销。例如一个2048位的密钥256字节使用OAEP填充SHA-256后最多只能加密约190字节的明文。对于更长的数据必须采用混合加密随机生成一个对称密钥如AES密钥用RSA公钥加密这个对称密钥然后用该对称密钥加密实际数据。性能考量RSA运算比较慢尤其是解密和签名私钥操作。它不适合加密大量数据。通常只用于加密对称密钥或进行数字签名。5. 常见问题、调试技巧与安全陷阱在实现和使用RSA的过程中你会遇到各种各样的问题。下面是一些典型场景和解决方案。5.1 密钥格式与加载问题这是最常见的问题之一。不同的库、工具生成的密钥格式可能不同。问题“RSA密钥格式不正确”、“不支持的密钥格式”、“Invalid PEM”。排查确认编码密钥文件是PEM格式ASCII以-----BEGIN XXX-----开头还是DER格式二进制确认类型PEM文件开头是BEGIN PRIVATE KEY(PKCS#8) 还是BEGIN RSA PRIVATE KEY(PKCS#1)公钥是BEGIN PUBLIC KEY还是BEGIN RSA PUBLIC KEY使用正确的加载方法# cryptography 库加载PEM格式私钥 from cryptography.hazmat.primitives import serialization with open(private_key.pem, rb) as key_file: private_key serialization.load_pem_private_key( key_file.read(), passwordNone, # 如果密钥被加密这里传入密码bytes backenddefault_backend() ) # 加载PEM格式公钥 with open(public_key.pem, rb) as key_file: public_key serialization.load_pem_public_key( key_file.read(), backenddefault_backend() )检查密钥完整性确保密钥文件没有损坏、没有多余的空格或换行符。可以用文本编辑器打开PEM文件检查。5.2 加解密或签名验签失败问题解密出错或验签抛出InvalidSignature异常。排查清单密钥配对你确定用的是对应的公钥和私钥吗用错密钥对是最常见的低级错误。填充方案匹配加密时用的什么填充OAEPPKCS1_v1_5解密时必须使用完全相同的填充方案和参数如哈希算法。签名和验签同理。OAEP加密的数据不能用PKCS1_v1_5解密反之亦然。数据编码在加密/签名前你的消息是bytes类型吗如果是字符串是否正确地进行了编码如.encode(utf-8)解密/验签后得到的bytes是否用正确的编码解码数据长度加密的数据是否超过了填充方案允许的最大长度计算一下密钥长度(字节) - 填充开销(字节)。对于2048位密钥OAEP with SHA-256最大明文长度约为256 - 2*32 - 2 190字节。哈希算法签名和验签使用的哈希算法必须一致。如果你用SHA256签名就必须用SHA256验签。5.3 性能问题与优化现象RSA解密或签名操作非常慢尤其是在嵌入式设备或处理高频请求时。优化思路使用合适的密钥长度在满足安全需求的前提下不要盲目使用过长的密钥。目前2048位是平衡安全与性能的通用选择。4096位密钥的操作耗时可能是2048位的数倍。采用混合加密体系这是解决性能问题的根本方法。RSA只用于加密一个随机的、短暂的对称密钥如AES-256密钥然后用速度极快的AES对称加密算法来加密实际的海量数据。硬件加速一些平台如Intel CPU的AES-NI指令集或专用的密码学硬件模块可以提供硬件级加速。cryptography库在支持的情况下会自动利用这些优化。缓存与复用对于需要多次用同一私钥签名的场景可以考虑在内存中缓存初始化好的私钥对象避免反复从文件加载和解析。5.4 安全陷阱警示绝对不要使用“教科书RSA”我们前面自己实现的、无填充的版本千万不能用于任何真实的数据保护。它只是教学工具。保护好你的私钥私钥泄露意味着所有用对应公钥加密的数据都可被解密所有签名都可被伪造。使用强密码加密存储私钥文件并严格控制访问权限。使用随机性良好的随机数生成器密钥生成、OAEP/PSS填充中的随机盐都必须使用密码学安全的随机源如os.urandom或secrets模块。使用普通随机数生成器会严重削弱安全性。及时弃用弱算法MD5、SHA1哈希算法以及PKCS#1 v1.5填充在某些场景下已被认为是不安全的。新项目应统一使用SHA256/SHA384/SHA512作为哈希算法OAEP作为加密填充PSS作为签名填充。注意侧信道攻击即使是使用了安全填充和算法不正确的实现比如在计算签名时因为分支条件不同而导致执行时间差异也可能泄露私钥信息。这就是为什么推荐使用cryptography这类经过广泛审计的库而不是自己从头实现核心运算。实现一个RSA算法从数学原理到代码实践再到安全应用是一次对密码学基础的深度探索。亲手推导一遍密钥生成过程编写快速模幂算法能让你对“非对称加密”这个概念有血肉般的理解。而后续使用标准库进行安全开发的实践则让你掌握了在真实项目中正确运用这门技术的钥匙。记住在密码学领域理解原理是为了更安全、更明智地使用工具而不是鼓励你去发明自己的轮子。当你下次再看到“RSA”这个词时希望你的脑海中浮现的不再是一个黑盒而是一幅清晰的、从欧拉定理延伸到现代网络安全的完整图景。