在公钥加密领域，RSA是一个无法绕过的经典算法。它不仅是首个同时支持数据加密与数字签名的方案，而且因其易于理解和操作，多年来始终占据着核心地位。该算法的名称直接取自三位发明者：Ron Rivest、Adi Shamir 和 Leonard Adleman。有趣的是，RSA的安全性至今尚未得到严格的理论证明——尽管它经历了无数种攻击方式的考验，却始终未被完全攻破。接下来，我们将从原理到安全细节，逐步拆解这一经典算法。

一、RSA算法

RSA算法的构造过程实际上相当清晰。首先，需要确定三个数：p、q、r。其中p和q是两个不同的大质数，r是一个与(p-1)(q-1)互质的数。这三个数构成私钥（private key）。

接下来，需要找到一个整数m，使得 r·m ≡ 1 mod (p-1)(q-1)。这个m必然存在，因为r与(p-1)(q-1)互质，通过辗转相除法（欧几里得算法）即可求出。同时计算 n = p·q。那么，m和n就构成了公钥（public key）。

编码过程如下：假设待加密的数据为a，将其视为一个大整数，且要求 a < n。如果 a ≥ n，则将a表示成s进制（s ≤ n，通常取 s = 2^t），使得每一位都小于n，然后分段编码。接着计算 b ≡ a^m mod n（0 ≤ b < n），b就是加密后的密文。

解码过程则是计算 c ≡ b^r mod pq（0 ≤ c < pq），解码完成。接下来会证明，c和a实际上是相等的。

如果第三方进行窃听，他会获得几个数：m、n(=pq)、b……要解码就必须得到r。而要得到r，他必须先对n进行质因数分解。要防止分解，最有效的方法就是选择两个非常大的质数p、q，使第三者进行因数分解时面临巨大的计算困难。

定理：若p、q是相异质数，r·m ≡ 1 mod (p-1)(q-1)，a是任意正整数，b ≡ a^m mod pq，c ≡ b^r mod pq，则 c ≡ a mod pq。

证明过程会用到费马小定理（叙述如下：m是任一质数，n是任一整数，则 n^m ≡ n mod m；换句话说，如果n和m互质，则 n^m-1 ≡ 1 mod m）。运用一些基本的群论知识就能轻松证明费马小定理。下面是定理的详细证明：

因为 r·m ≡ 1 mod (p-1)(q-1)，所以 r·m = k(p-1)(q-1) + 1，其中k是整数。在模运算中乘法是保持的（若 x ≡ y mod z 且 u ≡ v mod z，则 xu ≡ yv mod z），所以 c ≡ b^r ≡ (a^m)^r ≡ a^rm ≡ a^{k(p-1)(q-1)+1} mod pq。

分四种情况讨论：

1. 如果a既不是p的倍数也不是q的倍数，则根据费马小定理有 a^p-1 ≡ 1 mod p 且 a^q-1 ≡ 1 mod q，进而 a^k(p-1)(q-1) ≡ 1 mod p 和 mod q，所以 p、q均整除 a^k(p-1)(q-1) - 1，即 pq | a^k(p-1)(q-1) - 1。因此 a^k(p-1)(q-1) ≡ 1 mod pq，于是 c ≡ a^{k(p-1)(q-1)+1} ≡ a mod pq。
2. 如果a是p的倍数但不是q的倍数，则 a^q-1 ≡ 1 mod q，类似可得 a^k(p-1)(q-1) ≡ 1 mod q，所以 c ≡ a mod q，即 q | c - a；同时因为 p | a，有 c ≡ 0 mod p，即 p | c - a。所以 pq | c - a，即 c ≡ a mod pq。
3. 如果a是q的倍数但不是p的倍数，证明同上。
4. 如果a同时是p和q的倍数，则 pq | a，因此 c ≡ 0 mod pq，且 pq | c - a，即 c ≡ a mod pq。

Q.E.D. 这个定理说明，a经过编码为b再经过解码为c时，有 a ≡ c mod n（n = pq）。实际编码解码时限制 0 ≤ a < n、0 ≤ c < n，所以 a就等于c，这个过程确实实现了编码解码的功能。

二、RSA 的安全性

RSA的安全性依赖于大数分解的困难性。但需要指出的是，其安全性是否完全等价于大数分解，至今未获理论证明——因为没有证据表明破解RSA就一定要进行因数分解。当然，假设存在一种无须分解大数的破解算法，那它一定可以被修改成一个大数分解算法。目前，RSA的一些变种已被证明等价于大数分解。不管怎样，分解n仍然是最直接也是最常用的攻击方法。如今，人们已经能够分解多个十进制位的大素数。因此，模数n的选取必须足够大，具体大小需根据实际应用场景来确定。

三、RSA 的速度

由于涉及的都是大数计算，RSA的处理速度要比对称算法（如DES）慢上几个数量级，无论是软件实现还是硬件实现。速度一直是RSA的明显短板。正因为如此，RSA通常只用于少量数据的加密，比如密钥交换或数字签名，而不会用来加密大块数据。

四、RSA 的选择密文攻击

RSA在选择密文攻击面前表现得相当脆弱。攻击者通常会将某一信息做一下伪装（Blind），然后让拥有私钥的实体签署。经过计算，攻击者就能得到他想要的信息。实际上，这种攻击利用的是同一个弱点：乘幂运算保留了输入的乘法结构，即 (X·M)^d = X^d·M^d mod n。这个固有的问题来自于公钥密码系统最实用的特征——每个人都能使用公钥。但从算法层面无法彻底解决，主要防范措施有两条：一是采用良好的公钥协议，确保工作过程中实体不会对其他实体任意产生的信息进行解密，也不会对自己一无所知的信息进行签名；二是绝不对陌生人送来的随机文档直接签名，签名前首先要使用单向散列函数（One-Way Hash Function）对文档做哈希处理，或者同时使用不同的签名算法。

五、RSA 的公共模数攻击

如果系统中只用一个公共模数n，但不同的人拥有不同的e和d，那么系统将非常危险。最普遍的情况是：同一信息用不同的公钥加密，这些公钥共模且互质，那么该信息无需私钥就能恢复。设明文为P，两个加密密钥为e1和e2，公共模数为n，则密文 C1 = P^e1 mod n，C2 = P^e2 mod n。密码分析者知道n、e1、e2、C1和C2，就能得到P。因为e1和e2互质，用欧几里得算法可以找到r和s，满足 r·e1 + s·e2 = 1。假设r为负数，再用欧几里得算法计算C1^-1，则 (C1^-1)^-r · C2^s ≡ P mod n。此外还有其它几种利用公共模数攻击的方法。总之，如果知道给定模数的一对e和d，一方面有利于攻击者分解模数，另一方面有利于攻击者计算出其他成对的e'和d'，而无需分解模数。解决办法只有一个：不要共享模数n。

另外还有小指数攻击。有一种提高RSA速度的建议是让公钥e取较小的值，这样加密会更易于实现，速度有所提升。但这样做是不安全的，应对办法就是让e和d都取较大的值。

从整体来看，RSA算法是第一个能同时用于加密和数字签名的算法，而且易于理解和操作。它也是被研究得最广泛的公钥算法，从提出到现在已近二十年，经历了各种攻击的考验，逐渐被业界普遍接受，目前仍被认为是最优秀的公钥方案之一。RSA的安全性依赖于大数的因子分解，但并没有从理论上证明破译RSA的难度与大数分解难度等价。也就是说，RSA的一个重大缺陷是无法从理论上把握它的保密性能到底如何，而且密码学界多数人士倾向于认为因子分解不属于NPC问题。

RSA的主要缺点还有：第一，产生密钥很麻烦，受限于素数产生技术，难以做到一次一密；第二，分组长度太大，为保证安全性，n至少也要600 bits以上，导致运算代价很高，速度比对称密码算法慢几个数量级；而且随着大数分解技术的发展，这个长度还在不断增加，不利于数据格式的标准化。目前，在SET（安全电子交易）协议中，要求CA采用比特长的密钥，其他实体则使用比特的密钥。