深入理解RSA：加密与签名的艺术
隐私计算密码学RSA非对称加密数字签名深入理解RSA：加密与签名的艺术XR2025-07-242025-07-25深入理解RSA：加密与签名的艺术RSA 是当今世界应用最广泛的公钥加密算法，由 Ron Rivest, Adi Shamir 和 Leonard Adleman 在1977年提出。它巧妙地利用了数论中一个核心的难题：将一个巨大的合数分解质因数是极其困难的，但将两个大素数相乘却非常容易。
这份文档将带你走完 RSA 从密钥生成、加密/解密，到数字签名/验证的全过程，并附带一个可手动计算的真实数据示例。
1. 核心数学概念理解RSA需要了解一些基础的数论概念，别担心，我们会用最直观的方式解释。
素数 (Prime Number): 只能被1和自身整除的数，如 7, 11, 13。它们是RSA算法的基石。
模运算 (Modular Arithmetic): 也叫“时钟运算”，即取余数。例如 14 mod 12 等于 2（时钟上的14点就是2点）。公式写作 a ≡ b (mod n)，表示 a 和 b 除以 n 的余数相同。
欧拉函数 (Euler’s Totient Function): φ(n) 表示小于 n 且与 n 互质（没有除1以外的公约数）的数的个数。这是一个关键的函数，它有一个神奇的性质：
如果 n 是两个素数 p 和 q 的乘积，即 n = p * q，那么 **φ(n) = (p-1) * (q-1)**。
欧拉定理 (Euler’s Theorem): 这是RSA能够工作的数学基石。它指出，如果一个整数 a 与 n 互质，那么：
a^φ(n) ≡ 1 (mod n)
模反元素 (Modular Multiplicative Inverse): 如果 e 和 d 满足 (e * d) mod φ(n) = 1，那么我们称 d 是 e 相对于 φ(n) 的模反元素。可以理解为 d 是 e 在模 φ(n) 运算下的“倒数”。
2. 第一步：生成密钥对（公钥与私钥）让我们用一个真实的、可手动计算的例子来生成一套密钥。在真实世界中，所选的素数会非常巨大（几百位长）。
目标： 生成公钥 (n, e) 和私钥 (n, d)。
选择两个不同的素数 p 和 q。
为了简单起见，我们选择 p = 61 和 q = 53。
保密： 这两个数在生成密钥后必须销毁，绝对不能泄露。
计算 n = p * q。
n = 61 * 53 = 3233。
这个 n 是公钥和私钥的一部分，是公开的。
计算欧拉函数 φ(n) = (p-1) * (q-1)。
φ(3233) = (61-1) * (53-1) = 60 * 52 = 3120。
保密： φ(n) 必须保密，因为如果它被泄露，攻击者就能轻易计算出私钥。
选择一个公钥指数 e。
e 必须满足 1 < e < φ(n) 且 e 与 φ(n) 互质。
我们选择 e = 17。（17是素数，且3120不能被17整除，所以它们互质）。
公钥诞生： 我们的公钥是 (n, e) = (3233, 17)。这个可以告诉任何人。
计算私钥指数 d。
d 是 e 相对于 φ(n) 的模反元素。即 (d * e) mod φ(n) = 1。
我们需要找到一个 d 使得 (d * 17) mod 3120 = 1。
这可以通过“扩展欧几里得算法”来解决。这里我们直接给出结果：d = 2753。
（验证一下：2753 * 17 = 46801，然后 46801 mod 3120 = (15 * 3120 + 1) mod 3120 = 1）。
私钥诞生： 我们的私钥是 (n, d) = (3233, 2753)。这个必须死守，天知地知你知。
小结:
公钥 (Public Key): (3233, 17) -> 用于加密，或验证签名
私钥 (Private Key): (3233, 2753) -> 用于解密，或生成签名
3. 第二步：使用RSA进行加密和解密场景： Alice 想给 Bob 发送一个秘密消息。她需要用 Bob 的 公钥 来加密。
原始消息 (Message): M。必须是一个小于 n 的整数。如果消息是文本，需要先转换成数字。我们假设要发送的秘密数字是 M = 123。
加密过程 (Alice操作)Alice 使用 Bob 的 **公钥 (n, e) = (3233, 17)**。
公式: Ciphertext (C) = M^e mod n
计算: C = 123^17 mod 3233
这个计算需要计算器，结果是：C = 855。
现在，Alice 将这个加密后的密文 855 通过不安全的网络发送给 Bob。即使被窃听，攻击者拿到 855 也无法推断出原始消息是 123。
解密过程 (Bob操作)Bob 收到密文 C = 855，他使用自己的 私钥 (n, d) = (3233, 2753) 来解密。
公式: Message (M) = C^d mod n
计算: M = 855^2753 mod 3233
这同样是个巨大的计算，但结果会精确地回到：M = 123。
为什么能解密？这背后的数学原理是欧拉定理。C^d = (M^e)^d = M^(e*d)。由于 e*d mod φ(n) = 1，我们可以把 e*d 写成 k*φ(n) + 1 的形式。所以：M^(e*d) mod n = M^(k*φ(n) + 1) mod n = (M^φ(n))^k * M^1 mod n根据欧拉定理, M^φ(n) mod n 等于 1。所以上式变为 1^k * M mod n，最终结果就是 M。
欧拉定理要求 M 与 n 互质（即gcd(M,n)=1）。在示例中M=123，n=3233，因123=3×41，n=61×53，两者互质，故成立。但若M是p或q的倍数（如M=61），欧拉定理不直接适用，此时需用中国剩余定理（CRT）保证解密正确性。实际RSA实现均依赖CRT优化。
4. 第三步：使用RSA进行数字签名和验证场景： Alice 想发布一个软件，她需要对软件签名，以证明这个软件确实是她发布的（真实性），并且没有被篡改（完整性）。
签名的过程与加密正好相反，是用私钥“加密”，用公钥“解密”。
重要： 直接对大数据（如整个软件）进行签名，速度极慢且不安全。正确的做法是 “先哈希，再签名”。
哈希 (Hashing): Alice 先用一个密码学哈希函数（如 SHA-256）计算软件的哈希值（一个简短的、独一无二的“指纹”）。
为简化计算，我们假设软件的哈希摘要转换成数字后是 H = 99。
签名过程 (Alice操作)Alice 使用她自己的 私钥 (n, d) = (3233, 2753) 来签名。
公式: Signature (S) = H^d mod n
计算: S = 99^2753 mod 3233
计算结果为 S = 2426。
Alice 将 (原始软件, 签名S=2426) 一起发布。
验证过程 (Bob操作)Bob 下载了软件和签名 2426。他需要用 Alice 的 公钥 (n, e) = (3233, 17) 来验证。
第一步： Bob 对他下载的软件 使用完全相同的哈希算法（SHA-256）计算哈希值。结果必然也是 H1 = 99。
第二步： Bob 使用 Alice 的公钥对签名进行“解密”操作。
公式: Verified_Hash (H2) = S^e mod n
计算: H2 = 2426^17 mod 3233
计算结果为 H2 = 99。
第三步：比较
Bob 比较他自己计算的哈希 H1 和从签名中还原出的哈希 H2。
H1 (99) 是否等于 H2 (99)？ 是的。
结论： 签名有效。Bob 可以确信，这个软件确实是 Alice 发布的，并且从发布到现在，一个比特都没有被改动过。如果有人篡改了软件，H1 将会改变，验证就会失败。
5. 为什么RSA是安全的？—— 理论与现实的差距理论上的安全性RSA的安全性根植于一个数学难题——大数质因数分解。攻击者知道公钥 (n, e)，但要推导出私钥 d，就必须先计算出 φ(n) = (p-1)(q-1)。而要计算 φ(n)，就必须知道 n 的两个质因数 p 和 q。当 n 足够大时（如2048位），分解 n 在计算上是不可行的。
现实中的致命漏洞然而，理论上的安全不等于实践中的安全。如果我们直接使用上面介绍的“教科书式”RSA进行签名，会存在一个致命的漏洞，即存在性伪造攻击 (Existential Forgery)。这个攻击生动地展示了为什么填充 (Padding) 是绝对必要的。
深度剖析：存在性伪造攻击 (Existential Forgery)攻击者如何“凭空”创造有效签名
攻击者 Eve 完全不知道您的私钥 d，但她知道您的公钥 (n, e)。她的目标是构造出一对 (伪造的消息 m', 伪造的签名 s')，并让它通过验证。思路完全是逆向的：
第一步 (选择一个“签名”): Eve 随机挑选一个数字 s'，并决定把它当作一个“签名”。比如，Eve 随便选一个数字 s' = 12345 (只要小于 n 即可)。
第二步 (使用公钥计算“消息”): Eve 利用验证公式和公钥来反向计算这个“签名”对应的“消息”：m' = (s')^e mod n
第三步 (伪造完成): Eve 得到了一对数据：(m', s')。她将这对数据发给接收者。
为什么这个伪造会通过验证？
接收者执行标准验证流程：用公钥 e 计算 (s')^e mod n，然后将结果与收到的 m' 比较。根据 Eve 的构造方法，这个计算结果**正好就是 m'**，因此验证通过！接收者会误以为这是一个合法的签名。
这破解了RSA吗？
没有。Eve 并没有 找出私钥 d，她也无法为任何她指定的、有意义的消息（比如“转账100万”）伪造签名。她伪造出的消息 m' 几乎肯定是无意义的乱码。这种攻击因此被称为“存在性伪造”——只能证明一个有效的 (消息, 签名) 对的存在，但无法控制其内容。
解决方案：密码学填充 (Padding) 的威力
为了阻止这种逆向攻击，现实世界的标准（如 PKCS#1）引入了强制的格式要求，这就是填充。
流程： 在签名之前，必须先计算消息的哈希值 H(m)，然后将哈希值与其他约定好的数据（如固定前缀）打包成一个高度结构化的数据块 Formatted_Block。最后才对这个 Formatted_Block 进行签名。
如何挫败攻击： 现在，当 Eve 再次尝试攻击时，她计算出的 m' = (s')^e mod n 必须符合这个预先定义好的、严格的结构。一个随机计算的结果恰好满足这种复杂格式的概率是微乎其微的，在计算上可以认为是不可能的。
一句话总结：填充方案是确保RSA在现实世界中安全使用的生命线，绝不可省略。
6. 签名时不进行哈希可行吗？这个是我在看SGX中使用签名防止篡改时想到的一个问题。我的好奇：哈希保证了签名的安全，还是非对称加密，还是两种共同保证了签名的安全。为什么不能直接使用私钥进行签名，然后使用公钥验证？（当时在想这个问题的时候，我还不是很清楚填充）。不过即使后来了解到存在性伪造攻击与填充，我还是有点点疑惑。那我把数据进行填充了呢？
我的新问题： 如果我的原始数据已经很短了（比如一个64字节的ID），我不能跳过哈希，直接对它进行**填充(Padding)**然后签名吗？这样既解决了数据长度问题，也通过填充防止了我们之前讨论的存在性伪造攻击。从安全角度看，这可行吗？
哈哈，我问了AI（豆包和gemini-2.5）这个问题，它的回答是：这个想法非常敏锐，但答案是：**强烈不推荐，这样做会引入严重的安全风险。过程中，我和多个ai模型讨论了这个点，很多ai反复和我强调必须要使用哈希来进行签名。但是一直没回答的要点上，后面我发现了答案。
虽然“填充后直接签名”确实可以抵御最基础的伪造攻击，但它忽略了哈希函数在此流程中扮演的另一个至关重要的、但更微妙的角色：破坏消息的数学结构。
让我们看看为什么省略哈希是危险的：
6.1 未知的结构性攻击 (Structural Attacks)RSA算法依赖于模幂运算，这个运算本身具有一些数学特性（例如，乘法同态性：sig(m1) * sig(m2) = sig(m1 * m2)）。虽然我们使用的填充方案（如PKCS#1 v1.5）旨在破坏这些特性，但它是围绕着签名一个哈希值来设计的。
如果被签名的内容不是一个近乎随机的哈希值，而是包含特定结构（比如全零的字节、重复的序列、或者与其他消息有数学关联）的原始数据，那么即使经过了填充，也可能存在一些未知的、非常巧妙的攻击方法，可以利用这些原始数据的内在结构来伪造签名。
哈希函数在这里起到了“随机预处理”的作用。无论你的原始数据是什么结构，经过哈希后，都会变成一串毫无规律、近乎随机的比特。这串“随机”的数据再被填充和签名，其安全性就大大增强了，因为它彻底消除了原始数据结构可能带来的任何风险。
6.2 来自历史的教训：密码学标准曾因此犯错这不仅仅是理论上的担忧，而是有真实案例的（才知道原来不是只有我想过这个）。
历史上，确实存在过一些为了效率而设计的签名标准（如早期版本的 ISO/IEC 9796，我搜的一些资料说的好像是1994版），它们就采用了“填充后直接签名短消息”的方案。然而，后来密码学家们发现了针对这些标准的严重漏洞，证明了可以在不知道私钥的情况下伪造签名。
这些攻击非常复杂，它们正是利用了被签名消息的非随机性（即没有经过哈希处理）这个弱点。最终，这些标准不得不被废弃或进行重大修订。
结论“先哈希，再签名” (Hash-then-Sign) 并不仅仅是为了压缩数据，它是一个经过了数十年研究和实战检验的安全范式。
哈希：负责将任意长度、任意结构的输入，转换为一个固定长度、无结构的、近乎随机的摘要。
填充：负责为这个摘要提供一个安全的、标准化的封装，以抵御针对RSA算法本身的攻击。
签名：对填充后的数据块执行核心的非对称加密操作。
这三个步骤环环相扣，缺一不可。省略掉哈希，就相当于绕过了安全体系中的第一道也是至关重要的一道防线，即使后面的防线看起来很坚固，整个体系的安全性也会因此受到极大损害。
所以，结论是：无论原始数据多短，都必须先进行哈希，然后再进行填充和签名。这是确保数字签名安全的黄金准则。
密码学确实是一门很精妙的艺术，充满了美感