1. 从一次“公钥丢失”的线上故障说起那天下午运维群里突然炸了锅好几个业务接口接连报错日志里清一色地刷着“RSA public key not find”。开发同学紧急排查发现是负责管理密钥对的服务因为一个配置同步的延迟导致新部署的节点没能及时拉取到最新的公钥。短短十分钟的故障却让整个团队对“RSA公钥”这个平时藏在代码深处的概念有了切肤之痛。这让我想起无论是处理navicat15激活时的密钥错误还是研究小程序抓包时面对HTTPS的加密流量亦或是实现会话存档解密、探讨前端RSAAES加密的安全性RSA算法都像一把看不见的钥匙守护着数字世界的信任边界。很多人对RSA的印象停留在“非对称加密”、“公钥加密私钥解密”这几个名词上。但当我们需要在STM32F103C8T6这类资源受限的MCU上实现加密或者用Python、Java去实现一个完整的加解密流程时仅仅知道名词是远远不够的。你会遇到一系列具体问题如何安全地生成一组合规的、足够强壮的大素数模数n到底取多大才既安全又不至于让计算慢到无法接受那个神秘的私钥d究竟是怎么算出来的为什么加密后的数据长度会膨胀以及当别人告诉你“RSA不能直接加密长数据”时背后的原因到底是什么这篇文章我将从一个实践者的角度彻底拆解RSA算法的数学原理、实现步骤以及那些在Linux驱动层做透明加密、处理非标准M1卡解密、乃至思考量子加密威胁时我们都必须清楚的底层逻辑。我会用具体的数字示例带你手算一遍RSA然后给出Python和Java的核心实现代码并深入讨论在真实工程中如何与AES结合、如何处理填充如OAEP、以及如何管理那些令人头疼的密钥。我们不止于原理更要通向实现并理解每一个参数选择背后的“为什么”。2. RSA算法的数学心脏单向陷门函数要理解RSA必须先理解其赖以生存的数学基础。它不是魔法而是建立在数论领域一个公认的难题之上大整数的质因数分解。RSA的核心思想是构建一个“单向陷门函数”。所谓“单向”是指正向计算很容易但逆向计算极其困难。想象一把弹子锁用钥匙陷门信息开锁很容易但想通过拨动弹子来反推出钥匙的齿形就非常困难。在RSA中这个函数就是模幂运算。2.1 关键数论定理欧拉定理在深入RSA之前需要重温欧拉定理。它表述为如果正整数a和n互质即最大公约数gcd(a, n) 1那么a^φ(n) ≡ 1 (mod n)。这里的φ(n)是欧拉函数表示小于n且与n互质的正整数的个数。有一个特例至关重要如果n是两个质数p和q的乘积即n p * q那么φ(n) (p-1)*(q-1)。这是因为在1到n之间只有p的倍数有q个和q的倍数有p个与n不互质且p*q这个数被重复计算了一次所以总数是n - p - q 1 pq - p - q 1 (p-1)(q-1)。这个公式是计算RSA私钥的基石。2.2 从欧拉定理到RSA加解密RSA的巧妙之处在于利用了欧拉定理的一个变形。我们选择两个大质数p和q计算n p * q以及φ(n) (p-1)(q-1)。然后选择一个整数e满足1 e φ(n)且e与φ(n)互质。这个e就是公钥指数通常是655370x10001因为它二进制表示中1很少能加速计算且安全性足够。接着计算e对于φ(n)的模反元素d。也就是说找一个整数d使得(e * d) ≡ 1 (mod φ(n))。这个d就是私钥指数。计算d需要用到扩展欧几里得算法。现在我们有了公钥(n, e)和私钥(n, d)。加解密过程如下加密对于明文消息m需要将其转换为一个小于n的整数计算密文c ≡ m^e (mod n)。解密对于密文c计算明文m ≡ c^d (mod n)。为什么这样能解密我们来推导一下 因为c ≡ m^e (mod n)所以c^d ≡ (m^e)^d ≡ m^(e*d) (mod n)。 根据d的定义e*d ≡ 1 (mod φ(n))即存在整数k使得e*d 1 k*φ(n)。 因此c^d ≡ m^(1 k*φ(n)) ≡ m * (m^φ(n))^k (mod n)。 这里分两种情况如果m和n互质直接由欧拉定理m^φ(n) ≡ 1 (mod n)得到c^d ≡ m * 1^k ≡ m (mod n)。如果m和n不互质由于np*qm要么是p的倍数要么是q的倍数证明稍复杂但利用中国剩余定理同样可以证明等式成立。这就确保了对于所有小于n的m加解密都能正确进行。2.3 安全性到底在哪里攻击者能看到的是公钥(n, e)和密文c。他想从c反推出m就需要计算c^d mod n但他没有d。想得到d根据定义需要知道φ(n)。而想计算φ(n) (p-1)(q-1)就必须对n进行质因数分解得到p和q。这就是RSA安全性的核心假设当n足够大例如2048位、3072位或以上时将其分解为两个大质数p和q在计算上是不可行的。这就是那个“单向”的部分已知p和q求n乘法很容易但已知n求p和q分解极其困难。d就是那个“陷门”知道p和q陷门信息就能轻松算出d不知道就只能望洋兴叹。注意选择p和q不是随便找两个大数。它们本身必须足够大、随机并且要有足够的间距以防止通过n的平方根附近试除的“费马分解法”攻击。在实际工程中应使用密码学安全的随机数生成器CSPRNG来生成。3. 手算演示给RSA拍一张X光片理解了原理我们用一个非常小的数字来手算一遍给算法拍个X光。请注意这里为了演示使用的数字小到毫无安全性可言实际应用必须使用非常大的质数。3.1 密钥生成步骤选择质数选择p 61,q 53。计算nn p * q 61 * 53 3233。n的长度决定了密钥长度这里是12位二进制约合4位十进制实际中至少需要2048位约617位十进制。计算φ(n)φ(n) (p-1)*(q-1) 60 * 52 3120。选择公钥指数e选择一个与3120互质的数。通常选e17实际常用65537。检查gcd(17, 3120) 1满足条件。公钥为(3233, 17)。计算私钥指数d计算d使得(e * d) mod φ(n) 1即(17 * d) mod 3120 1。这需要用到扩展欧几里得算法。通过计算过程略我们可以得到d 2753。因为17 * 2753 4680146801 mod 3120 1。私钥为(3233, 2753)。3.2 加密与解密过程假设我们要加密明文m 65对应字母‘A’。首先必须确保m n65 3233。加密计算密文c m^e mod n 65^17 mod 3233。 直接计算65^17是一个天文数字我们需要用模幂运算快速幂算法来简化。计算过程如下采用平方乘方法65^1 mod 3233 6565^2 mod 3233 4225 mod 3233 99265^4 mod 3233 992^2 mod 3233 984064 mod 3233 29865^8 mod 3233 298^2 mod 3233 88804 mod 3233 164165^16 mod 3233 1641^2 mod 3233 2692881 mod 3233 115因为17 16 1所以65^17 65^16 * 65^1。 因此c (115 * 65) mod 3233 7475 mod 3233 2790。 所以密文c 2790。解密计算明文m‘ c^d mod n 2790^2753 mod 3233。 同样这个计算量巨大必须用快速幂算法。经过一系列复杂的平方乘运算过程省略最终可以得到结果m‘ 65。 成功恢复明文这个手算过程清晰地展示了e和d在模n运算下的互逆关系。尽管e和d在数值上毫无关联但通过φ(n)这个桥梁它们共同构成了一个可逆的数学变换。4. 从理论到代码Python与Java实现核心逻辑明白了数学原理实现代码就变得直观。但请注意以下代码仅为教学演示展示了最核心的密钥生成和原始加解密过程。它缺少了至关重要的填充方案如PKCS#1 OAEP、大数库的优化以及完整的错误处理绝对不可用于生产环境。生产环境请务必使用经过严格审计的密码学库如Python的cryptography、Java的java.security。4.1 Python实现演示import random from math import gcd def is_prime_miller_rabin(n, k5): 米勒-拉宾素性测试一个概率性测试用于大数判断 if n 2: return False for p in [2, 3, 5, 7, 11]: if n % p 0: return n p # 将n-1写成 d * 2^s 的形式 s, d 0, n - 1 while d % 2 0: s 1 d // 2 for _ in range(k): a random.randrange(2, n - 1) x pow(a, d, n) if x 1 or x n - 1: continue for _ in range(s - 1): x pow(x, 2, n) if x n - 1: break else: return False return True def generate_prime_candidate(bitlength): 生成一个奇数候选质数 p random.getrandbits(bitlength) # 确保是奇数且足够大 p | (1 bitlength - 1) | 1 return p def generate_large_prime(bitlength512): 生成一个大质数 p 4 while not is_prime_miller_rabin(p): p generate_prime_candidate(bitlength) return p def extended_gcd(a, b): 扩展欧几里得算法返回 (gcd, x, y) 使得 ax by gcd(a, b) if a 0: return b, 0, 1 gcd_val, x1, y1 extended_gcd(b % a, a) x y1 - (b // a) * x1 y x1 return gcd_val, x, y def modinv(e, phi): 计算模逆元即求 d 使得 (e * d) % phi 1 gcd_val, x, _ extended_gcd(e, phi) if gcd_val ! 1: raise Exception(e 和 φ(n) 不互质无法求逆元) return x % phi def rsa_key_generation(bitlength1024): 生成RSA密钥对 (n, e, d) print(f正在生成 {bitlength} 位质数...) p generate_large_prime(bitlength // 2) q generate_large_prime(bitlength // 2) while p q: # 确保p和q不同 q generate_large_prime(bitlength // 2) n p * q phi_n (p - 1) * (q - 1) # 选择公钥指数e通常为65537 e 65537 if gcd(e, phi_n) ! 1: # 极罕见情况需要重新选择e e 65537 while gcd(e, phi_n) ! 1: e random.randrange(2, phi_n) # 计算私钥指数d d modinv(e, phi_n) # 返回 公钥(n, e), 私钥(n, d) return (n, e), (n, d) def rsa_encrypt(m, public_key): 原始RSA加密m^e mod n n, e public_key if m 0 or m n: raise ValueError(明文m必须满足 0 m n) # 使用内置的pow函数进行模幂运算效率很高 return pow(m, e, n) def rsa_decrypt(c, private_key): 原始RSA解密c^d mod n n, d private_key return pow(c, d, n) # 演示 if __name__ __main__: # 生成密钥对这里使用较小位数以便演示 public_key, private_key rsa_key_generation(bitlength128) n, e public_key _, d private_key print(f公钥 (n, e): n{n}\n e{e}) print(f私钥 (n, d): n{n}\n d{d}) # 加密解密一个数字 original_message 123456789 print(f\n原始消息: {original_message}) ciphertext rsa_encrypt(original_message, public_key) print(f加密后密文: {ciphertext}) decrypted_message rsa_decrypt(ciphertext, private_key) print(f解密后消息: {decrypted_message}) print(f加解密是否成功: {original_message decrypted_message})4.2 Java实现演示Java标准库提供了强大的java.security包我们这里演示如何使用它进行标准的RSA操作。import javax.crypto.Cipher; import java.security.*; import java.security.spec.PKCS8EncodedKeySpec; import java.security.spec.X509EncodedKeySpec; import java.util.Base64; public class RSAExample { public static KeyPair generateKeyPair(int keySize) throws NoSuchAlgorithmException { KeyPairGenerator keyGen KeyPairGenerator.getInstance(RSA); keyGen.initialize(keySize); // 通常为2048或4096 return keyGen.generateKeyPair(); } public static String encrypt(String plainText, PublicKey publicKey) throws Exception { Cipher cipher Cipher.getInstance(RSA/ECB/OAEPWithSHA-256AndMGF1Padding); // 使用OAEP填充 cipher.init(Cipher.ENCRYPT_MODE, publicKey); byte[] encryptedBytes cipher.doFinal(plainText.getBytes()); return Base64.getEncoder().encodeToString(encryptedBytes); } public static String decrypt(String cipherText, PrivateKey privateKey) throws Exception { Cipher cipher Cipher.getInstance(RSA/ECB/OAEPWithSHA-256AndMGF1Padding); cipher.init(Cipher.DECRYPT_MODE, privateKey); byte[] decodedBytes Base64.getDecoder().decode(cipherText); byte[] decryptedBytes cipher.doFinal(decodedBytes); return new String(decryptedBytes); } public static void main(String[] args) throws Exception { // 1. 生成密钥对 KeyPair keyPair generateKeyPair(2048); PublicKey publicKey keyPair.getPublic(); PrivateKey privateKey keyPair.getPrivate(); // 将密钥转换为Base64字符串便于查看和传输 String publicKeyStr Base64.getEncoder().encodeToString(publicKey.getEncoded()); String privateKeyStr Base64.getEncoder().encodeToString(privateKey.getEncoded()); System.out.println(公钥(Base64):\n publicKeyStr); System.out.println(\n私钥(Base64):\n privateKeyStr); // 2. 加密 String originalText 这是一条需要加密的敏感信息; System.out.println(\n原始文本: originalText); String encryptedText encrypt(originalText, publicKey); System.out.println(加密后文本(Base64): encryptedText); // 3. 解密 String decryptedText decrypt(encryptedText, privateKey); System.out.println(解密后文本: decryptedText); System.out.println(加解密是否成功: originalText.equals(decryptedText)); // 4. 演示从字符串加载密钥 // 假设我们从配置文件中读取了Base64编码的密钥 KeyFactory keyFactory KeyFactory.getInstance(RSA); // 加载公钥 X509EncodedKeySpec publicKeySpec new X509EncodedKeySpec(Base64.getDecoder().decode(publicKeyStr)); PublicKey loadedPublicKey keyFactory.generatePublic(publicKeySpec); // 加载私钥 PKCS8EncodedKeySpec privateKeySpec new PKCS8EncodedKeySpec(Base64.getDecoder().decode(privateKeyStr)); PrivateKey loadedPrivateKey keyFactory.generatePrivate(privateKeySpec); System.out.println(\n从字符串加载密钥后再次解密成功: originalText.equals(decrypt(encrypt(originalText, loadedPublicKey), loadedPrivateKey))); } }关键提示对比Python演示代码和Java代码你会发现一个重大区别Java的Cipher.getInstance(“RSA/ECB/OAEPWithSHA-256AndMGF1Padding”)指定了完整的算法和填充模式。而Python演示代码是“裸”的RSA即直接计算m^e mod n。这正是下一节要讨论的核心工程问题。5. 裸RSA的致命缺陷与工程实践中的“组合拳”如果你只理解了前四节就贸然用演示代码去加密用户数据那将是非常危险的。原始的、教科书式的RSA我们称之为“裸RSA”或“教科书RSA”存在几个致命缺陷。5.1 缺陷一确定性加密与语义安全在裸RSA中同样的明文m同样的公钥永远会得到同样的密文c。这意味着攻击者可以通过反复尝试加密一些猜测的明文例如“是”、“否”、“admin”、“123456”并将结果与截获的密文对比来推测出原始明文。这破坏了“语义安全”。解决方案是引入随机化填充。在加密前先对明文进行填充加入随机盐salt使得每次加密同一明文都会产生不同的密文。PKCS#1 v1.5旧标准和OAEP最优非对称加密填充新标准就是干这个的。5.2 缺陷二不能加密长数据RSA算法本身要求明文m必须小于模数n。对于2048位的密钥n大约是256字节。但PKCS#1 OAEP等填充方案本身会占用几十字节。因此实际能用RSA直接加密的数据长度非常有限例如对于2048位密钥和OAEP填充可能只能加密约190字节的明文。这就是为什么你会看到“RSA不能直接加密长数据”的说法。5.3 工程标准方案RSA AES或其它对称算法为了解决上述问题现代密码学实践采用“混合加密系统”发送方随机生成一个一次性的对称密钥例如一个256位的AES密钥。用这个对称密钥采用AES-GCM等认证加密模式加密实际的长明文数据。这一步速度很快。用接收方的RSA公钥加密上一步生成的对称密钥。因为对称密钥本身很短几十字节完全在RSA的加密能力范围内。将RSA加密后的对称密钥和AES加密后的密文一起发送给接收方。接收方用自己的RSA私钥解密出对称密钥再用该对称密钥解密出原始明文。这种方式结合了非对称加密的密钥分发便利性和对称加密的高效性。这也是前端RSAAES加密常见架构的由来前端用后端的RSA公钥加密一个随机生成的AES密钥然后用这个AES密钥加密请求体。后端用私钥解密出AES密钥再解密请求体。5.4 关于填充模式的选择PKCS#1 v1.5 Padding历史久远存在一些潜在的适应性选择密文攻击风险但在许多场景下仍被广泛使用和认为是安全的。OAEP Padding目前推荐的标准。它提供了更强的安全性证明在随机预言机模型下应作为新系统的首选。Java示例中使用的就是OAEP。无填充绝对禁止用于加密业务数据仅在某些特殊场景如数字签名或与其他机制组合时在专家指导下使用。5.5 密钥管理真正的挑战“RSA public key not find”错误的根源在于密钥管理。在实际系统中密钥生成与存储私钥必须被极其安全地存储通常使用硬件安全模块HSM或至少是加密的密钥库。公钥则可以公开分发。密钥分发与轮换如何将公钥安全地分发给所有客户端如前端、移动App如何定期轮换密钥更新密钥对而不导致服务中断这需要设计良好的密钥分发协议和版本管理机制。密钥格式密钥通常以PEM-----BEGIN PUBLIC KEY-----、DER或JWKJSON Web Key格式存储和传输。不同平台和库对格式的支持有差异需要正确处理。6. 不止于加密RSA在数字签名与密钥交换中的应用RSA除了用于加密还有两个极其重要的用途数字签名和密钥交换尽管现代更推荐使用ECDH进行密钥交换。6.1 数字签名数字签名的目的是验证数据的完整性和来源真实性。流程与加密相反签名发送方用自己的私钥对数据的哈希值如SHA-256进行加密签名运算得到签名值。验签接收方用发送方的公钥对签名值进行解密验证运算得到哈希值H1。同时接收方自己计算收到数据的哈希值H2。如果H1等于H2则证明数据在传输过程中未被篡改且确实来自持有对应私钥的发送方。这解决了“中间人攻击”的问题。在小程序抓包场景中如果服务器对响应做了正确的RSA签名即使你能截获流量也无法伪造服务器的响应因为你没有服务器的私钥。6.2 在TLS/SSL和SSH中的角色在HTTPSTLS/SSL建立连接的过程中RSA曾长期被用于“密钥交换”。客户端生成一个预备主密钥Pre-Master Secret用服务器的RSA公钥加密后发送过去服务器用私钥解密。双方再基于此生成会话密钥。不过由于RSA不具备“前向安全性”如果服务器私钥未来泄露过去所有通信的预备主密钥都能被解密现代TLS更推荐使用基于迪菲-赫尔曼D-H或椭圆曲线迪菲-赫尔曼ECDH的密钥交换算法。但RSA仍然广泛用于服务器身份认证服务器证书中的公钥通常是RSA公钥。在Linux中获取用户的RSA密钥~/.ssh/id_rsa正是用于SSH协议的身份认证。客户端用自己的私钥对一段会话数据进行签名服务器用存储的公钥验签从而证明客户端的身份。7. 现实世界的挑战与未来7.1 性能考量RSA的加解密尤其是解密私钥运算是非常消耗CPU的计算。这就是为什么在STM32F103C8T6这类嵌入式设备上使用2048位RSA进行大量数据解密会非常吃力。在实际中我们通常在服务端使用硬件加速卡来提升RSA性能。在资源受限环境考虑使用更轻量的椭圆曲线加密ECC它能在更短的密钥长度下提供相当的安全性。遵循“混合加密”原则用RSA保护对称密钥用对称算法加解密数据。7.2 侧信道攻击攻击者可能通过测量加密过程的时间、功耗或电磁辐射来推断私钥信息。这就是侧信道攻击。专业的密码学实现如OpenSSL、Bouncy Castle会包含“常数时间”实现等对抗措施。自己实现RSA核心运算如模幂是极其危险的很容易引入侧信道漏洞。7.3 量子计算的威胁Shor算法在理论上可以在多项式时间内分解大整数从而破解RSA。这就是量子加密被热议的原因。虽然大规模实用的量子计算机尚未出现但“后量子密码学”PQC的研究和迁移已经提上日程。NIST正在标准化抗量子计算的加密算法。对于需要长期保密超过10-20年的数据需要考虑这种远期威胁。回到开头那个“公钥找不到”的故障其根本原因是对“非对称加密体系是一个基础设施”的认识不足。它不仅仅是两行调用加密函数的代码而是一套包含密钥生成、存储、分发、轮换、使用填充、模式、废弃的完整生命周期管理。理解RSA的原理能帮助我们在选择加密库是加密库还是自己造轮子、设计系统架构何时用RSA何时用AES、以及排查那些深奥的加密错误时做出正确的判断。当你再看到navicat激活的密钥错误、或是研究Cobalt Strike加密流量的解密、亦或是评估前端RSAAES方案是否安全时希望这篇文章能提供一个坚实的逻辑起点。密码学的正确使用永远在“理解原理”和“遵循最佳实践”的交汇点上。
RSA算法深度解析：从数学原理到Python/Java工程实践
1. 从一次“公钥丢失”的线上故障说起那天下午运维群里突然炸了锅好几个业务接口接连报错日志里清一色地刷着“RSA public key not find”。开发同学紧急排查发现是负责管理密钥对的服务因为一个配置同步的延迟导致新部署的节点没能及时拉取到最新的公钥。短短十分钟的故障却让整个团队对“RSA公钥”这个平时藏在代码深处的概念有了切肤之痛。这让我想起无论是处理navicat15激活时的密钥错误还是研究小程序抓包时面对HTTPS的加密流量亦或是实现会话存档解密、探讨前端RSAAES加密的安全性RSA算法都像一把看不见的钥匙守护着数字世界的信任边界。很多人对RSA的印象停留在“非对称加密”、“公钥加密私钥解密”这几个名词上。但当我们需要在STM32F103C8T6这类资源受限的MCU上实现加密或者用Python、Java去实现一个完整的加解密流程时仅仅知道名词是远远不够的。你会遇到一系列具体问题如何安全地生成一组合规的、足够强壮的大素数模数n到底取多大才既安全又不至于让计算慢到无法接受那个神秘的私钥d究竟是怎么算出来的为什么加密后的数据长度会膨胀以及当别人告诉你“RSA不能直接加密长数据”时背后的原因到底是什么这篇文章我将从一个实践者的角度彻底拆解RSA算法的数学原理、实现步骤以及那些在Linux驱动层做透明加密、处理非标准M1卡解密、乃至思考量子加密威胁时我们都必须清楚的底层逻辑。我会用具体的数字示例带你手算一遍RSA然后给出Python和Java的核心实现代码并深入讨论在真实工程中如何与AES结合、如何处理填充如OAEP、以及如何管理那些令人头疼的密钥。我们不止于原理更要通向实现并理解每一个参数选择背后的“为什么”。2. RSA算法的数学心脏单向陷门函数要理解RSA必须先理解其赖以生存的数学基础。它不是魔法而是建立在数论领域一个公认的难题之上大整数的质因数分解。RSA的核心思想是构建一个“单向陷门函数”。所谓“单向”是指正向计算很容易但逆向计算极其困难。想象一把弹子锁用钥匙陷门信息开锁很容易但想通过拨动弹子来反推出钥匙的齿形就非常困难。在RSA中这个函数就是模幂运算。2.1 关键数论定理欧拉定理在深入RSA之前需要重温欧拉定理。它表述为如果正整数a和n互质即最大公约数gcd(a, n) 1那么a^φ(n) ≡ 1 (mod n)。这里的φ(n)是欧拉函数表示小于n且与n互质的正整数的个数。有一个特例至关重要如果n是两个质数p和q的乘积即n p * q那么φ(n) (p-1)*(q-1)。这是因为在1到n之间只有p的倍数有q个和q的倍数有p个与n不互质且p*q这个数被重复计算了一次所以总数是n - p - q 1 pq - p - q 1 (p-1)(q-1)。这个公式是计算RSA私钥的基石。2.2 从欧拉定理到RSA加解密RSA的巧妙之处在于利用了欧拉定理的一个变形。我们选择两个大质数p和q计算n p * q以及φ(n) (p-1)(q-1)。然后选择一个整数e满足1 e φ(n)且e与φ(n)互质。这个e就是公钥指数通常是655370x10001因为它二进制表示中1很少能加速计算且安全性足够。接着计算e对于φ(n)的模反元素d。也就是说找一个整数d使得(e * d) ≡ 1 (mod φ(n))。这个d就是私钥指数。计算d需要用到扩展欧几里得算法。现在我们有了公钥(n, e)和私钥(n, d)。加解密过程如下加密对于明文消息m需要将其转换为一个小于n的整数计算密文c ≡ m^e (mod n)。解密对于密文c计算明文m ≡ c^d (mod n)。为什么这样能解密我们来推导一下 因为c ≡ m^e (mod n)所以c^d ≡ (m^e)^d ≡ m^(e*d) (mod n)。 根据d的定义e*d ≡ 1 (mod φ(n))即存在整数k使得e*d 1 k*φ(n)。 因此c^d ≡ m^(1 k*φ(n)) ≡ m * (m^φ(n))^k (mod n)。 这里分两种情况如果m和n互质直接由欧拉定理m^φ(n) ≡ 1 (mod n)得到c^d ≡ m * 1^k ≡ m (mod n)。如果m和n不互质由于np*qm要么是p的倍数要么是q的倍数证明稍复杂但利用中国剩余定理同样可以证明等式成立。这就确保了对于所有小于n的m加解密都能正确进行。2.3 安全性到底在哪里攻击者能看到的是公钥(n, e)和密文c。他想从c反推出m就需要计算c^d mod n但他没有d。想得到d根据定义需要知道φ(n)。而想计算φ(n) (p-1)(q-1)就必须对n进行质因数分解得到p和q。这就是RSA安全性的核心假设当n足够大例如2048位、3072位或以上时将其分解为两个大质数p和q在计算上是不可行的。这就是那个“单向”的部分已知p和q求n乘法很容易但已知n求p和q分解极其困难。d就是那个“陷门”知道p和q陷门信息就能轻松算出d不知道就只能望洋兴叹。注意选择p和q不是随便找两个大数。它们本身必须足够大、随机并且要有足够的间距以防止通过n的平方根附近试除的“费马分解法”攻击。在实际工程中应使用密码学安全的随机数生成器CSPRNG来生成。3. 手算演示给RSA拍一张X光片理解了原理我们用一个非常小的数字来手算一遍给算法拍个X光。请注意这里为了演示使用的数字小到毫无安全性可言实际应用必须使用非常大的质数。3.1 密钥生成步骤选择质数选择p 61,q 53。计算nn p * q 61 * 53 3233。n的长度决定了密钥长度这里是12位二进制约合4位十进制实际中至少需要2048位约617位十进制。计算φ(n)φ(n) (p-1)*(q-1) 60 * 52 3120。选择公钥指数e选择一个与3120互质的数。通常选e17实际常用65537。检查gcd(17, 3120) 1满足条件。公钥为(3233, 17)。计算私钥指数d计算d使得(e * d) mod φ(n) 1即(17 * d) mod 3120 1。这需要用到扩展欧几里得算法。通过计算过程略我们可以得到d 2753。因为17 * 2753 4680146801 mod 3120 1。私钥为(3233, 2753)。3.2 加密与解密过程假设我们要加密明文m 65对应字母‘A’。首先必须确保m n65 3233。加密计算密文c m^e mod n 65^17 mod 3233。 直接计算65^17是一个天文数字我们需要用模幂运算快速幂算法来简化。计算过程如下采用平方乘方法65^1 mod 3233 6565^2 mod 3233 4225 mod 3233 99265^4 mod 3233 992^2 mod 3233 984064 mod 3233 29865^8 mod 3233 298^2 mod 3233 88804 mod 3233 164165^16 mod 3233 1641^2 mod 3233 2692881 mod 3233 115因为17 16 1所以65^17 65^16 * 65^1。 因此c (115 * 65) mod 3233 7475 mod 3233 2790。 所以密文c 2790。解密计算明文m‘ c^d mod n 2790^2753 mod 3233。 同样这个计算量巨大必须用快速幂算法。经过一系列复杂的平方乘运算过程省略最终可以得到结果m‘ 65。 成功恢复明文这个手算过程清晰地展示了e和d在模n运算下的互逆关系。尽管e和d在数值上毫无关联但通过φ(n)这个桥梁它们共同构成了一个可逆的数学变换。4. 从理论到代码Python与Java实现核心逻辑明白了数学原理实现代码就变得直观。但请注意以下代码仅为教学演示展示了最核心的密钥生成和原始加解密过程。它缺少了至关重要的填充方案如PKCS#1 OAEP、大数库的优化以及完整的错误处理绝对不可用于生产环境。生产环境请务必使用经过严格审计的密码学库如Python的cryptography、Java的java.security。4.1 Python实现演示import random from math import gcd def is_prime_miller_rabin(n, k5): 米勒-拉宾素性测试一个概率性测试用于大数判断 if n 2: return False for p in [2, 3, 5, 7, 11]: if n % p 0: return n p # 将n-1写成 d * 2^s 的形式 s, d 0, n - 1 while d % 2 0: s 1 d // 2 for _ in range(k): a random.randrange(2, n - 1) x pow(a, d, n) if x 1 or x n - 1: continue for _ in range(s - 1): x pow(x, 2, n) if x n - 1: break else: return False return True def generate_prime_candidate(bitlength): 生成一个奇数候选质数 p random.getrandbits(bitlength) # 确保是奇数且足够大 p | (1 bitlength - 1) | 1 return p def generate_large_prime(bitlength512): 生成一个大质数 p 4 while not is_prime_miller_rabin(p): p generate_prime_candidate(bitlength) return p def extended_gcd(a, b): 扩展欧几里得算法返回 (gcd, x, y) 使得 ax by gcd(a, b) if a 0: return b, 0, 1 gcd_val, x1, y1 extended_gcd(b % a, a) x y1 - (b // a) * x1 y x1 return gcd_val, x, y def modinv(e, phi): 计算模逆元即求 d 使得 (e * d) % phi 1 gcd_val, x, _ extended_gcd(e, phi) if gcd_val ! 1: raise Exception(e 和 φ(n) 不互质无法求逆元) return x % phi def rsa_key_generation(bitlength1024): 生成RSA密钥对 (n, e, d) print(f正在生成 {bitlength} 位质数...) p generate_large_prime(bitlength // 2) q generate_large_prime(bitlength // 2) while p q: # 确保p和q不同 q generate_large_prime(bitlength // 2) n p * q phi_n (p - 1) * (q - 1) # 选择公钥指数e通常为65537 e 65537 if gcd(e, phi_n) ! 1: # 极罕见情况需要重新选择e e 65537 while gcd(e, phi_n) ! 1: e random.randrange(2, phi_n) # 计算私钥指数d d modinv(e, phi_n) # 返回 公钥(n, e), 私钥(n, d) return (n, e), (n, d) def rsa_encrypt(m, public_key): 原始RSA加密m^e mod n n, e public_key if m 0 or m n: raise ValueError(明文m必须满足 0 m n) # 使用内置的pow函数进行模幂运算效率很高 return pow(m, e, n) def rsa_decrypt(c, private_key): 原始RSA解密c^d mod n n, d private_key return pow(c, d, n) # 演示 if __name__ __main__: # 生成密钥对这里使用较小位数以便演示 public_key, private_key rsa_key_generation(bitlength128) n, e public_key _, d private_key print(f公钥 (n, e): n{n}\n e{e}) print(f私钥 (n, d): n{n}\n d{d}) # 加密解密一个数字 original_message 123456789 print(f\n原始消息: {original_message}) ciphertext rsa_encrypt(original_message, public_key) print(f加密后密文: {ciphertext}) decrypted_message rsa_decrypt(ciphertext, private_key) print(f解密后消息: {decrypted_message}) print(f加解密是否成功: {original_message decrypted_message})4.2 Java实现演示Java标准库提供了强大的java.security包我们这里演示如何使用它进行标准的RSA操作。import javax.crypto.Cipher; import java.security.*; import java.security.spec.PKCS8EncodedKeySpec; import java.security.spec.X509EncodedKeySpec; import java.util.Base64; public class RSAExample { public static KeyPair generateKeyPair(int keySize) throws NoSuchAlgorithmException { KeyPairGenerator keyGen KeyPairGenerator.getInstance(RSA); keyGen.initialize(keySize); // 通常为2048或4096 return keyGen.generateKeyPair(); } public static String encrypt(String plainText, PublicKey publicKey) throws Exception { Cipher cipher Cipher.getInstance(RSA/ECB/OAEPWithSHA-256AndMGF1Padding); // 使用OAEP填充 cipher.init(Cipher.ENCRYPT_MODE, publicKey); byte[] encryptedBytes cipher.doFinal(plainText.getBytes()); return Base64.getEncoder().encodeToString(encryptedBytes); } public static String decrypt(String cipherText, PrivateKey privateKey) throws Exception { Cipher cipher Cipher.getInstance(RSA/ECB/OAEPWithSHA-256AndMGF1Padding); cipher.init(Cipher.DECRYPT_MODE, privateKey); byte[] decodedBytes Base64.getDecoder().decode(cipherText); byte[] decryptedBytes cipher.doFinal(decodedBytes); return new String(decryptedBytes); } public static void main(String[] args) throws Exception { // 1. 生成密钥对 KeyPair keyPair generateKeyPair(2048); PublicKey publicKey keyPair.getPublic(); PrivateKey privateKey keyPair.getPrivate(); // 将密钥转换为Base64字符串便于查看和传输 String publicKeyStr Base64.getEncoder().encodeToString(publicKey.getEncoded()); String privateKeyStr Base64.getEncoder().encodeToString(privateKey.getEncoded()); System.out.println(公钥(Base64):\n publicKeyStr); System.out.println(\n私钥(Base64):\n privateKeyStr); // 2. 加密 String originalText 这是一条需要加密的敏感信息; System.out.println(\n原始文本: originalText); String encryptedText encrypt(originalText, publicKey); System.out.println(加密后文本(Base64): encryptedText); // 3. 解密 String decryptedText decrypt(encryptedText, privateKey); System.out.println(解密后文本: decryptedText); System.out.println(加解密是否成功: originalText.equals(decryptedText)); // 4. 演示从字符串加载密钥 // 假设我们从配置文件中读取了Base64编码的密钥 KeyFactory keyFactory KeyFactory.getInstance(RSA); // 加载公钥 X509EncodedKeySpec publicKeySpec new X509EncodedKeySpec(Base64.getDecoder().decode(publicKeyStr)); PublicKey loadedPublicKey keyFactory.generatePublic(publicKeySpec); // 加载私钥 PKCS8EncodedKeySpec privateKeySpec new PKCS8EncodedKeySpec(Base64.getDecoder().decode(privateKeyStr)); PrivateKey loadedPrivateKey keyFactory.generatePrivate(privateKeySpec); System.out.println(\n从字符串加载密钥后再次解密成功: originalText.equals(decrypt(encrypt(originalText, loadedPublicKey), loadedPrivateKey))); } }关键提示对比Python演示代码和Java代码你会发现一个重大区别Java的Cipher.getInstance(“RSA/ECB/OAEPWithSHA-256AndMGF1Padding”)指定了完整的算法和填充模式。而Python演示代码是“裸”的RSA即直接计算m^e mod n。这正是下一节要讨论的核心工程问题。5. 裸RSA的致命缺陷与工程实践中的“组合拳”如果你只理解了前四节就贸然用演示代码去加密用户数据那将是非常危险的。原始的、教科书式的RSA我们称之为“裸RSA”或“教科书RSA”存在几个致命缺陷。5.1 缺陷一确定性加密与语义安全在裸RSA中同样的明文m同样的公钥永远会得到同样的密文c。这意味着攻击者可以通过反复尝试加密一些猜测的明文例如“是”、“否”、“admin”、“123456”并将结果与截获的密文对比来推测出原始明文。这破坏了“语义安全”。解决方案是引入随机化填充。在加密前先对明文进行填充加入随机盐salt使得每次加密同一明文都会产生不同的密文。PKCS#1 v1.5旧标准和OAEP最优非对称加密填充新标准就是干这个的。5.2 缺陷二不能加密长数据RSA算法本身要求明文m必须小于模数n。对于2048位的密钥n大约是256字节。但PKCS#1 OAEP等填充方案本身会占用几十字节。因此实际能用RSA直接加密的数据长度非常有限例如对于2048位密钥和OAEP填充可能只能加密约190字节的明文。这就是为什么你会看到“RSA不能直接加密长数据”的说法。5.3 工程标准方案RSA AES或其它对称算法为了解决上述问题现代密码学实践采用“混合加密系统”发送方随机生成一个一次性的对称密钥例如一个256位的AES密钥。用这个对称密钥采用AES-GCM等认证加密模式加密实际的长明文数据。这一步速度很快。用接收方的RSA公钥加密上一步生成的对称密钥。因为对称密钥本身很短几十字节完全在RSA的加密能力范围内。将RSA加密后的对称密钥和AES加密后的密文一起发送给接收方。接收方用自己的RSA私钥解密出对称密钥再用该对称密钥解密出原始明文。这种方式结合了非对称加密的密钥分发便利性和对称加密的高效性。这也是前端RSAAES加密常见架构的由来前端用后端的RSA公钥加密一个随机生成的AES密钥然后用这个AES密钥加密请求体。后端用私钥解密出AES密钥再解密请求体。5.4 关于填充模式的选择PKCS#1 v1.5 Padding历史久远存在一些潜在的适应性选择密文攻击风险但在许多场景下仍被广泛使用和认为是安全的。OAEP Padding目前推荐的标准。它提供了更强的安全性证明在随机预言机模型下应作为新系统的首选。Java示例中使用的就是OAEP。无填充绝对禁止用于加密业务数据仅在某些特殊场景如数字签名或与其他机制组合时在专家指导下使用。5.5 密钥管理真正的挑战“RSA public key not find”错误的根源在于密钥管理。在实际系统中密钥生成与存储私钥必须被极其安全地存储通常使用硬件安全模块HSM或至少是加密的密钥库。公钥则可以公开分发。密钥分发与轮换如何将公钥安全地分发给所有客户端如前端、移动App如何定期轮换密钥更新密钥对而不导致服务中断这需要设计良好的密钥分发协议和版本管理机制。密钥格式密钥通常以PEM-----BEGIN PUBLIC KEY-----、DER或JWKJSON Web Key格式存储和传输。不同平台和库对格式的支持有差异需要正确处理。6. 不止于加密RSA在数字签名与密钥交换中的应用RSA除了用于加密还有两个极其重要的用途数字签名和密钥交换尽管现代更推荐使用ECDH进行密钥交换。6.1 数字签名数字签名的目的是验证数据的完整性和来源真实性。流程与加密相反签名发送方用自己的私钥对数据的哈希值如SHA-256进行加密签名运算得到签名值。验签接收方用发送方的公钥对签名值进行解密验证运算得到哈希值H1。同时接收方自己计算收到数据的哈希值H2。如果H1等于H2则证明数据在传输过程中未被篡改且确实来自持有对应私钥的发送方。这解决了“中间人攻击”的问题。在小程序抓包场景中如果服务器对响应做了正确的RSA签名即使你能截获流量也无法伪造服务器的响应因为你没有服务器的私钥。6.2 在TLS/SSL和SSH中的角色在HTTPSTLS/SSL建立连接的过程中RSA曾长期被用于“密钥交换”。客户端生成一个预备主密钥Pre-Master Secret用服务器的RSA公钥加密后发送过去服务器用私钥解密。双方再基于此生成会话密钥。不过由于RSA不具备“前向安全性”如果服务器私钥未来泄露过去所有通信的预备主密钥都能被解密现代TLS更推荐使用基于迪菲-赫尔曼D-H或椭圆曲线迪菲-赫尔曼ECDH的密钥交换算法。但RSA仍然广泛用于服务器身份认证服务器证书中的公钥通常是RSA公钥。在Linux中获取用户的RSA密钥~/.ssh/id_rsa正是用于SSH协议的身份认证。客户端用自己的私钥对一段会话数据进行签名服务器用存储的公钥验签从而证明客户端的身份。7. 现实世界的挑战与未来7.1 性能考量RSA的加解密尤其是解密私钥运算是非常消耗CPU的计算。这就是为什么在STM32F103C8T6这类嵌入式设备上使用2048位RSA进行大量数据解密会非常吃力。在实际中我们通常在服务端使用硬件加速卡来提升RSA性能。在资源受限环境考虑使用更轻量的椭圆曲线加密ECC它能在更短的密钥长度下提供相当的安全性。遵循“混合加密”原则用RSA保护对称密钥用对称算法加解密数据。7.2 侧信道攻击攻击者可能通过测量加密过程的时间、功耗或电磁辐射来推断私钥信息。这就是侧信道攻击。专业的密码学实现如OpenSSL、Bouncy Castle会包含“常数时间”实现等对抗措施。自己实现RSA核心运算如模幂是极其危险的很容易引入侧信道漏洞。7.3 量子计算的威胁Shor算法在理论上可以在多项式时间内分解大整数从而破解RSA。这就是量子加密被热议的原因。虽然大规模实用的量子计算机尚未出现但“后量子密码学”PQC的研究和迁移已经提上日程。NIST正在标准化抗量子计算的加密算法。对于需要长期保密超过10-20年的数据需要考虑这种远期威胁。回到开头那个“公钥找不到”的故障其根本原因是对“非对称加密体系是一个基础设施”的认识不足。它不仅仅是两行调用加密函数的代码而是一套包含密钥生成、存储、分发、轮换、使用填充、模式、废弃的完整生命周期管理。理解RSA的原理能帮助我们在选择加密库是加密库还是自己造轮子、设计系统架构何时用RSA何时用AES、以及排查那些深奥的加密错误时做出正确的判断。当你再看到navicat激活的密钥错误、或是研究Cobalt Strike加密流量的解密、亦或是评估前端RSAAES方案是否安全时希望这篇文章能提供一个坚实的逻辑起点。密码学的正确使用永远在“理解原理”和“遵循最佳实践”的交汇点上。
