1. 项目概述从零理解RSA的“魔法”如果你对“加密”这个词的印象还停留在谍战片里复杂的密码本那RSA算法可能会颠覆你的认知。它是一套基于数学难题的“非对称加密”系统简单来说就是加密和解密用的不是同一把钥匙。这听起来有点反直觉但正是这个特性让它成为了现代互联网安全的基石从你登录网站时看到的那个小锁图标HTTPS到数字签名、软件授权背后都有RSA的身影。网上很多教程一上来就扔出一堆数学公式什么欧拉函数、模逆元直接把初学者劝退。这篇内容的目标不同我们不追求数学上的极致严谨而是用“人话”和可运行的代码帮你直观理解RSA的核心思想并亲手实现一个能跑起来的、虽然简单但原理正确的RSA加密解密程序。适合所有对密码学感兴趣但被复杂理论吓到的朋友无论你是前端、后端还是学生都能跟着一步步做出来真正搞懂“公钥加密私钥解密”到底是怎么玩的。2. RSA核心原理的“白话”拆解在动手写代码之前我们必须先在心里建立起RSA的运作模型。你可以把它想象成一个特制的、带有两个钥匙孔的密码盒。2.1 非对称加密一把锁两把钥匙传统的对称加密比如你用同一个密码压缩文件好比是一把挂锁开锁和关锁用的是同一把钥匙。这带来了一个致命问题如何安全地把钥匙交给对方如果钥匙在传递途中被截获整个加密就形同虚设。RSA的聪明之处在于它造了一把结构奇特的锁。这把锁配有两把完全不同的钥匙一把叫公钥可以公开给任何人另一把叫私钥必须由主人严格保密。公钥它的作用就像是一个只能锁上不能打开的锁头。任何人拿到这个锁头公钥都可以把信息“锁”进盒子里。私钥这是唯一能打开那个被公钥锁住的盒子的钥匙由信息接收者自己保管。这样一来通信流程就安全了我想给你发密信就先用你公开在网上的“锁头”你的公钥把信锁好寄给你。路上即使被截获别人也没有你的“私钥”来开锁。只有你本人能用私钥打开阅读。这个过程完美解决了密钥分发的难题。2.2 背后的数学“魔法”大数分解难题RSA的安全性不依赖于复杂的机关而是基于一个简单的数学事实将两个大的质数相乘非常容易但想要将这个巨大的乘积重新分解回原来的两个质数在现有计算能力下极其困难。这就是RSA的基石——大整数分解的困难性。我们整个密钥生成过程就是围绕着一对精心挑选的大质数p和q来进行的。计算n p * q。这个n会作为公钥和私钥的一部分公开出去。攻击者即使知道了n想倒推出p和q也几乎不可能只要p和q足够大比如都是1024位以上的质数。整个RSA的密钥生成、加密、解密公式都是在这个数学基础上搭建起来的。我们不需要深究每一个公式的数学证明但需要理解每个步骤的目的。2.3 密钥生成一步步打造我们的“锁和钥匙”这是RSA最核心的步骤我们来一步步拆解第一步选择两个不相等的质数p和q这是安全性的源头。在实际应用中p和q必须是随机生成且长度很长如1024位的质数。为了演示我们选小的p61,q53。第二步计算模数nn p * q 61 * 53 3233这个n就是那个公开的、难以分解的大数。它的长度这里3233是4位数决定了密钥的强度。n会同时出现在公钥和私钥中。第三步计算欧拉函数φ(n)欧拉函数φ(n)表示在小于n的正整数中与n互质最大公约数为1的数的个数。对于两个质数相乘的情况有一个简单公式φ(n) (p-1) * (q-1)所以φ(3233) (61-1) * (53-1) 60 * 52 3120这个φ(n)是后续计算的关键但它必须被严格保密因为知道它就能轻易推算出私钥。第四步选择公钥指数e公钥由(n, e)组成。e需要满足两个条件1 e φ(n)e和φ(n)必须互质即最大公约数gcd(e, φ(n)) 1。 通常为了计算效率会选择一个较小的、常见的质数比如65537(0x10001)。这个数只有两个比特位是1在二进制下计算非常快。在我们的例子中我们在1 e 3120且与3120互质的数里选一个比如e 17。第五步计算私钥指数d私钥由(n, d)组成。d是e对于φ(n)的模逆元。这意味着d需要满足(e * d) % φ(n) 1换句话说d是这样一个数e和d的乘积除以φ(n)后余数为1。 计算d需要使用扩展欧几里得算法。对于e17, φ(n)3120我们可以计算出d 2753因为(17 * 2753) % 3120 46801 % 3120 1。至此我们得到了公钥:(n3233, e17)私钥:(n3233, d2753)注意以上数字都非常小仅用于教学演示。真正的RSA密钥n是一个长达数百位十进制数的大整数p和q的选取是随机的、长度相近的大质数这是安全性的根本。自己实现时绝对不要用这么小的质数用于真实加密。3. 加密与解密的代码实现Python版理解了原理我们用Python把它实现出来。我们会先实现一个基础版本确保每一步都清晰可见。3.1 基础工具函数最大公约数与模逆元在实现核心功能前我们需要两个数学助手。def gcd(a, b): 计算最大公约数用于判断两个数是否互质。 while b ! 0: a, b b, a % b return a def modinv(e, phi): 使用扩展欧几里得算法计算模逆元 d满足 (e*d) % phi 1。 # 这里我们使用简单的遍历法来寻找d仅适用于教学和小数字。 # 在实际应用中必须使用扩展欧几里得算法。 for d in range(3, phi): if (e * d) % phi 1: return d raise ValueError(f模逆元不存在 for e{e}, phi{phi})3.2 密钥生成函数现在我们把第二部分的理论步骤写成代码。def generate_keypair(p, q): 生成RSA公钥和私钥。 # 1. 计算n和phi n p * q phi (p-1) * (q-1) # 2. 选择公钥指数e要求与phi互质 e 17 # 常见选择也可以从3, 5, 17, 257, 65537中选 while gcd(e, phi) ! 1: e 2 # 确保e是奇数增加与phi互质的概率 # 3. 计算私钥指数d d modinv(e, phi) # 公钥 (e, n), 私钥 (d, n) return ((e, n), (d, n)) # 使用我们例子中的质数 p 61 q 53 public_key, private_key generate_keypair(p, q) print(f公钥 (e, n): {public_key}) print(f私钥 (d, n): {private_key})运行这段代码你会得到和之前手工计算一致的结果公钥: (17, 3233),私钥: (2753, 3233)。3.3 加密函数用公钥“上锁”加密过程很简单将明文一个数字用公钥(e, n)进行运算。 公式是密文 (明文 ^ e) % n在Python中^是异或不是幂运算。幂运算用**但对于大数直接计算(明文 ** e)会得到一个天文数字效率极低且可能溢出。我们必须使用模幂运算它可以在计算过程中不断取模保持数值较小。def encrypt(public_key, plaintext): 使用公钥加密一个整数。 e, n public_key # 使用pow函数进行模幂运算第三个参数n表示取模 ciphertext pow(plaintext, e, n) return ciphertext3.4 解密函数用私钥“开锁”解密是加密的逆过程使用私钥(d, n)。 公式是明文 (密文 ^ d) % n同样我们使用模幂运算。def decrypt(private_key, ciphertext): 使用私钥解密密文返回整数明文。 d, n private_key plaintext pow(ciphertext, d, n) return plaintext3.5 完整流程演示让我们用一个完整的例子串起来。注意RSA算法本身是用于加密整数的。如果要加密文本需要先将文本如字符串转换为整数。# 1. 生成密钥 p 61 q 53 public_key, private_key generate_keypair(p, q) print(f公钥: {public_key}) print(f私钥: {private_key}) # 2. 我们的“明文”是一个数字。比如字符‘A’的ASCII码是65。 plaintext_int 65 print(f\n原始明文整数: {plaintext_int}) # 3. 加密 ciphertext_int encrypt(public_key, plaintext_int) print(f加密后的密文整数: {ciphertext_int}) # 4. 解密 decrypted_int decrypt(private_key, ciphertext_int) print(f解密后的明文整数: {decrypted_int}) # 5. 验证 if plaintext_int decrypted_int: print(\n✅ 加密解密成功) else: print(\n❌ 解密失败)运行这段代码你会看到密文是一个看起来随机的数字2790而解密后又变回了65。魔法生效了实操心得pow(a, b, c)是Python的内置函数它高效地计算(a**b) % c是实现RSA加密解密的利器。自己写循环做模幂运算不仅慢而且容易出错。4. 处理文本消息与常见问题上面的例子只能加密一个很小的数字。现实中我们要加密的是句子、文件。这引出了RSA实际应用中的几个关键问题。4.1 如何加密文本——编码与分块RSA的输入输出都是整数并且这个整数必须小于模数n。所以加密文本需要两步编码将字符串如“Hello”转换为一个整数。简单的方法可以使用ASCII或UTF-8编码将每个字符的码值拼接起来。更通用的做法是使用PKCS#1等填充标准它不仅能编码还能增加安全性。分块如果文本很长转换成的整数可能远超n。这时必须将长整数分割成多个小于n的“块”然后对每一块分别进行RSA加密。下面是一个极简的、不安全的演示展示这个思想def text_to_int(text): 将文本转换为整数演示用非安全标准。 # 将每个字符的ASCII码转为两位数字符串然后拼接 int_str .join(f{ord(c):03d} for c in text) # 用3位确保如‘z’(122)也能表示 return int(int_str) def int_to_text(num): 将整数转换回文本演示用非安全标准。 num_str str(num) # 将数字字符串按3位一组拆分并转换回字符 # 注意这里假设数字字符串长度是3的倍数实际应用需更严谨处理 chars [] for i in range(0, len(num_str), 3): code int(num_str[i:i3]) chars.append(chr(code)) return .join(chars) # 演示 message Hi plain_int text_to_int(message) # 会得到类似 072105 的整数 print(f文本‘{message}’转换为整数: {plain_int}) # 检查是否小于n (3233) if plain_int public_key[1]: cipher_int encrypt(public_key, plain_int) decrypted_int decrypt(private_key, cipher_int) decrypted_msg int_to_text(decrypted_int) print(f解密后的文本: {decrypted_msg}) else: print(明文整数太大需要分块加密)对于长文本你需要实现一个分块循环。但请注意这种简单的ASCII拼接编码方式非常不安全且脆弱极易受到攻击。在实际项目中必须使用像PKCS#1_OAEP这样的标准填充方案Python的cryptography库就提供了这些。4.2 为什么我的RSA程序这么慢你可能已经发现即使加密一个很小的数字如果d很大私钥指数通常都很大pow(c, d, n)的计算量也不小。RSA的核心运算——大数模幂——是比较耗时的。这就是为什么RSA通常不用于直接加密大量数据比如一个视频文件。实际的混合加密系统发送方随机生成一个对称加密密钥比如AES密钥。对称加密如AES速度极快适合加密大数据。发送方用接收方的RSA公钥加密这个对称密钥。发送方用对称密钥加密实际的大数据明文。发送方将加密后的对称密钥和加密后的数据一起发送给接收方。接收方用自己的RSA私钥解密出对称密钥。接收方用解密出的对称密钥解密数据。这样RSA只用于加密一个很短的关键信息对称密钥发挥了其安全分发密钥的长处而繁重的数据加密工作则由高效的对称加密算法完成。4.3 常见错误与排查表在实现和使用RSA时你可能会遇到以下问题问题现象可能原因解决方案加密或解密时程序卡死或内存溢出。使用的质数p,q太小导致n也小无法容纳编码后的明文整数。明文整数 n。1. 使用更大的质数至少数百位。2. 对长明文进行分块确保每块对应的整数 n。解密出来的结果是一堆乱码或数字不对。1. 编码/解码函数与加密/解密过程不匹配。2. 公私钥不配对最常见。3. 在分块加密/解密时块的顺序或处理方式出错。1. 检查并统一编码解码方式如都使用UTF-8。2.务必确认解密使用的私钥和加密使用的公钥是同一对密钥生成的。3. 调试时先尝试加密解密一个简单的整数如65确保核心算法正确再引入编码逻辑。在网络上搜索“RSA公钥加密”时看到公钥是一长串Base64字符。实际使用的公钥/私钥是遵循一定标准格式如PEM进行编码的通常包含密钥类型、参数等并常用Base64编码以便于传输和存储。学习使用标准库如Python的cryptography。它们提供了serialize()和load_pem_public_key()等函数来处理密钥的格式转换。自己手动拼接ASN.1结构非常复杂且易错。自己实现的RSA加密结果和标准库如OpenSSL加密结果不一样。1. 填充方案不同。标准库默认使用OAEP等填充而你的实现可能无填充或使用其他填充。2. 密钥格式或参数编码方式不同。切勿自己实现用于生产环境。理解原理后在实际项目中使用久经考验的库如cryptography、PyCryptodome。它们经过了严格的安全审计。核心避坑指南这个项目最大的价值在于理解原理而不是造一个能用的轮子。密码学极其复杂一个微小的实现失误比如随机数生成质量差、填充方式不当都可能导致整个系统被攻破。因此“看懂”之后请务必转向使用成熟的标准库。用from cryptography.hazmat.primitives.asymmetric import rsa, padding然后调用几行代码比你写几百行自己实现的RSA要安全一万倍。5. 从理解到应用使用标准库经过前面的折腾你应该对RSA的里里外外有了感性认识。现在是时候“站在巨人的肩膀上”了。我们来看看如何用Python的cryptography库安全、正确地完成RSA加密解密。5.1 安装与密钥生成首先安装这个行业标准的库pip install cryptography然后用几行代码生成一个2048位的RSA密钥对from cryptography.hazmat.primitives.asymmetric import rsa from cryptography.hazmat.primitives import serialization # 生成私钥 private_key rsa.generate_private_key( public_exponent65537, # 标准公钥指数 key_size2048, # 密钥长度2048位是当前最低安全要求 ) # 从私钥导出公钥 public_key private_key.public_key() # 将私钥以PEM格式保存到文件务必保密 pem_private private_key.private_bytes( encodingserialization.Encoding.PEM, formatserialization.PrivateFormat.PKCS8, encryption_algorithmserialization.NoEncryption() # 生产环境应使用密码加密 ) with open(private_key.pem, wb) as f: f.write(pem_private) # 将公钥以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) print(RSA密钥对已生成并保存。)5.2 标准的加密与解密流程现在使用生成的密钥进行加密和解密。注意这里使用了推荐的OAEP填充方案。from cryptography.hazmat.primitives.asymmetric import padding from cryptography.hazmat.primitives import hashes # 待加密的消息必须是字节串 message bThis is a secret message that needs to be encrypted using RSA. # 使用公钥加密 # OAEP填充是当前推荐的标准它比古老的PKCS#1 v1.5填充更安全。 ciphertext public_key.encrypt( message, padding.OAEP( mgfpadding.MGF1(algorithmhashes.SHA256()), algorithmhashes.SHA256(), labelNone ) ) print(f密文 (十六进制): {ciphertext.hex()}) # 使用私钥解密 decrypted_message private_key.decrypt( ciphertext, padding.OAEP( mgfpadding.MGF1(algorithmhashes.SHA256()), algorithmhashes.SHA256(), labelNone ) ) print(f解密后的明文: {decrypted_message.decode()})看到没代码简洁且背后是工业级的实现。加密时自动处理了填充和编码解密时亦然。这才是你在真实项目中应该使用的方式。5.3 数字签名与验证RSA另一个重要用途是数字签名用于验证消息的完整性和来源。原理是用私钥对消息的摘要进行“加密”即签名任何人可以用公钥“解密”即验证这个签名并与重新计算的消息摘要对比。from cryptography.hazmat.primitives.asymmetric import padding from cryptography.hazmat.primitives import hashes from cryptography.exceptions import InvalidSignature # 假设我们有一段重要的消息 message bOrder #12345: Pay $100 to account XXX. # 1. 发送方用私钥进行签名 signature private_key.sign( message, padding.PSS( mgfpadding.MGF1(hashes.SHA256()), salt_lengthpadding.PSS.MAX_LENGTH ), hashes.SHA256() ) print(f生成签名: {signature.hex()[:50]}...) # 2. 接收方用公钥验证签名 try: public_key.verify( signature, message, padding.PSS( mgfpadding.MGF1(hashes.SHA256()), salt_lengthpadding.PSS.MAX_LENGTH ), hashes.SHA256() ) print(✅ 签名验证成功消息完整且来自私钥持有者。) except InvalidSignature: print(❌ 签名验证失败消息可能被篡改或来源不可信。)走到这一步你已经从一个对RSA感到神秘的旁观者变成了一个能清晰阐述其原理、能动手实现其核心流程、并懂得如何在实际中正确使用它的实践者。记住那个核心的比喻公钥是只能锁的锁头私钥是唯一的钥匙记住它的安全基石是大数分解之难更重要的是记住理解原理是为了更好地使用工具而非取代工具。在安全领域使用经过千锤百炼的标准库永远是第一选择。