RSA 的全称是 Rivest–Shamir–Adleman，是一个目前广泛应用的公钥加密算法，最早发布于 1977 年。
说到 RSA 的安全性，我们所有人都知道，RSA 的安全性是基于大整数因子分解很难。举个例子，我们在小学二年级就学过乘法，\(3 \times 5 = 15\)，做一个乘法是非常简单的，而如果给出一个数字，想要分解他的因子，也就是知道这个数字是由哪几个数字做乘法得来的，在目前是一件非常困难的事情。
有些人可能会说，这有什么难的，15 不就是 3 乘以 5吗。那如果这个数字非常大，大到什么程度呢，以 2048 长度的 RSA 来说，这个数字可能是
23751939336536470261136035986127868580580013376303055622742197014665745532345838414254961295211432206652645660881172046738144700230582851852412897407267707825265659707882496106233435089871937383123529844897328569622885750129821750381869695126176555312010318470664467685217068576481540380764179180718718748541512748412460828119426794562225189555560608155357051040988044104005098330063593679320422173611058554557379094408930016505918744565366123796867896830012898057844059719240121138156157772424924265497783684076143187973825846878384942707714387008955931013035742722917775354524976037792446214031702112293289714369811
而如果是 4096 长度的 RSA，则会更长，例如
970887821447876723099274081171132322690768707736990709547349985559698585014343823848491216084168309247143332922334909853251887599588208736654918578195926734553373649429594333815577793981010259773161386515344105807187606600148257910149300226284095098378657319712263177456523807223512372026272134228425798618020534050253138922641792089754172353741796541568709039482295705714207673880147743032415796299484160862514242361547199335138088112342046240745131179767695332444310543927032555708848278094501259607120869100473276768564689479906445508257743430968391692842765196097710779501210085757386597587871315544277759289546336402967246985333077029473010248855320671985158109000116941255113806208763639295228013339269077644239058504801996765844380554214760961639113703495392605765036966403408662503978419519740815451600768786081188210924241265385480830983409923335417845393693685351608019319581059677737553580725670857997205133382912183365362441716694836507429917415264444404996736248377654059326736567151550436391499769380313778632000020838476174255390331511247764813249980146057229298407638372670799853846504038681732955734529568735886627812845653363470145677530091407694422088146301708105890177543062780343547129267638592021701229885002507
其中 2048 和 4096 代表的就是这个数字的比特位有多少。
好了，现在请读者尝试分解一下上面的两个数字是由哪两个质素做乘积的出来的。是不是发现以现在的算力来说，这几乎是一件不可能的事情。因此 RSA 在这种情况下可以算是安全的。
那么为什么我们无法分解这个数字，就代表了 RSA 安全呢？在 RSA 中又是如何运用到这个原理的呢，其实非常的简单。
RSA 的加密解密算法
其实 RSA 算法的原理我们每个人都很早就学会了。举个例子，还是以开头的算式为例，\(3 \times 5 = 15\)，其中 3 代表了我们要加密的原文，而 5 则代表了公钥，计算的结果 15 代表的是加密后的结果，即密文。
当我们有了密文 15 之后，该如何解密获取原文 3 呢？只需要灵活的运用我们在小学三年级就学会的数学概念，分数。不难发现，只要我们对密文 15 做以下计算
$$ 15 \times \frac{1}{5} = 3 $$
也就是再乘以公钥的倒数，\(\frac{1}{5}\)，即可进行解密，而这个倒数就是私钥，是不是非常简单。
于是你就学会了 RSA 的原理，好吧，其实并不是这样的，在正式介绍之前，我们先要介绍几个概念，方便对数学不了解的读者理解后续的公式和证明。
余数
余数的概念相信大家都明白，我们使用一个数去除另一个数，除不尽的部分就是余数。例如计算 \(7 / 3\)，余数就是 1。那么这个运算有一个很常见的叫法，模运算，一般写作 mod n。常见的编程语言当中，一般会用 % 符号。
模运算会有一些基本的性质，例如
$$ (a + b) \bmod n = ((a \bmod n) + (b \bmod n)) \bmod n $$
$$ a \times b \bmod n = ((a \bmod n) \times (b \bmod n)) \bmod n $$
也就是说我们对一个算式中的每个数字都对 n 取模，结果和对算式的最终结果取模是一样的。
同余
有了余数的概念，同余就很好理解了。如果有两个数字 a 和 b，他们对另一个数字 n 进行取模，得出的结果一样，那我们就说 a 和 b 对 n 同余。记作
$$ a \equiv b \pmod n $$
同余也有一些性质，比较重要的有两条。
如果有 \( a \equiv b \pmod n \) 和 \( c \equiv d \pmod n \)，那么就有 \( a \pm c \equiv b \pm d \pmod n \)
对于乘法也是一样的，即如果有 \( a \equiv b \pmod n \) 和 \( c \equiv d \pmod n \)，那么就有 \(a \times c \equiv b \times d \pmod n\)
RSA 基本原理
有了上面的一点小概念，我们就可以理解 RSA 是怎么操作的。RSA 基本上就是说，我们能够找到三个数字，e、d、n，使得下面的等式成立，其中 m 的取值需要满足 \( 0 \le m < n \)
$$ (m^e)^d \equiv m \pmod n $$
也就是说，存在一组数字，使得我们给 m 做两次指数运算之后，其结果对 n 取模，结果仍然等于 m。
而且就算我们知道了 e 和 n 的值，甚至知道了其中的一个 m 的值，还是没办法或者非常难计算出 d 的值。
这三个数字中，e 和 n 就是我们熟知的公钥，而私钥就是 d，当然了，在解密的过程中，不光需要 d，还需要知道 n 的值，所以私钥一般来说也会存一份 n 的值。
那么上面的公式怎么加密和解密呢。
当我们需要加密的时候，只需要计算一下
$$ m^e \bmod n $$
得出的值记为 c，也就是密文。
而解密的时候，再把这个密文进行计算
$$ c^d \bmod n $$
就可以得出原来的 m 了。
密钥生成
在上面说了，我们可以找到三个数字 e、d、n，满足上面的公式，那如何找到这三个数字呢，这就是密钥生成时候需要做的事情了。
密钥生成的第一步就是，选择两个非常大的质数，记为 p 和 q，多大算大呢，这个就取决于密钥长度，比如他是 2048 的还是 4096 的。p 和 q 生成好之后，不能够公开，因为这两个其实也算私钥的一部分。
接下来计算 p 和 q 的乘积，记为 n。这个的值就是在上面提到的 mod n 里面的n，同时也是文章一开头给出的两个非常长的数字。n 的长度就是密钥长度。
由于 n 是公钥的一部分，所以 n 是公开的，然而 p 和 q 却是不公开的，并且一开头就说了，你很难把 n 再分解回去。
第三步就是要计算一个特殊的值，在 RSA 最一开始的实现当中，用的是欧拉函数，也就是 \(\phi(n)\)，而后来的 RSA 中，则改成了 Carmichael 函数，\(\lambda(n)\)。
那首先什么是欧拉函数呢，对于一个正整数 n，欧拉函数就是小于 n 的正整数里面，与 n 互质的数的个数。
有了欧拉函数，就有欧拉定理，这个定理说，如果有两个数，a 和 n，他们互质，那么就有
$$ a^{\phi(n)} \equiv 1 \pmod n $$
也就是对 a 进行 \(\phi(n)\) 次幂之后，对 n 取模的结果为 1。
而 Carmichael 函数呢，也是类似的，只不过它定义的是，a 和 n 互质的情况下，满足下面公式的最小的 m 的值
$$ a^m \equiv 1 \pmod n $$
可以看出其实和欧拉定理是类似的，只不过不同点在于，欧拉函数计算出来的 \(\phi(n)\) 不一定就是最小的，但一定是满足条件的。比如说当 n 的值为 15 的时候，\(\phi(n)\) 的值是 8，而 \(\lambda(n)\) 的值是4。并且 \(\lambda(n)\) 的值要么等于 \(\phi(n)\)，要么就是后者的一半，具体的定义和证明就不是本文的内容了。
那为啥要计算这个值呢？翻回最一开始举的例子，里面说，公钥就是 5，而私钥是它的倒数 \(\frac{1}{5}\)，二者的乘积就是1。我说这就是 RSA 的原理，当然不是在乱说，只是以一种便于理解的方式举个例子。
而在 RSA 真正原理中，我们可以看出来，如果 e 乘以 d 的值就是1，那么上面的公式显然就是成立的，所谓的加密和解密只不过是来回倒腾。但是这样非常的不安全，分解大数很难，但是计算除法确是很简单的事情，公开了 e 之后，我直接做 e 的倒数，不就有私钥了吗？那还要 n 的值做什么。
所以 e 和 d 的计算方式肯定不是这么简单的，事实上，e 和 d 的确满足类似的关系
$$ e \times d \equiv 1 \pmod{\lambda(n)} $$
也就是 e 和 d 的乘积对 \(\lambda(n)\) 取余的结果为 1。对于这种情况，也有一个称呼，e 和 d 在模 \(\lambda(n)\) 下是乘法逆元。
第四步就是要选择一个 e，e 只需要满足两个条件即可，第一个是范围，\(1 < e < \lambda(n)\)，第二个条件就是，e 和 \(\lambda(n)\) 互质即可。
根据公式，e 的值如果比较小的话，那么在加密的时候性能就会比较高，因为做 3 次运算要比做 7 次运算要快。但是 e 越小的话，有时候安全性也不高，因为 e 越小，那么你的 d 就越大，d 如果很大的话，你使用 e 和 n 就越可能计算出 d 的值。
所以 e 的取值现在有很多种，比如有直接用最小可能的值，3，也有用 7 的，但是更常见的情况是，e 的值是 \(2^16 + 1\)，也就是 65537。比如说在我之前一篇 X509 的文章中，结尾部分查看了一个 RSA 的信息，其中有个值是 :010001，这个就是 e 了，可以看出它的值就是 65537。
第五步，当选择好 e 的值之后，就可以根据公式 \( e \times d \equiv 1 \pmod{\lambda(n)} \) 来计算 d 的值了。也就是
$$ d \equiv e^{-1} \pmod{\lambda(n)} $$
全部计算好之后，我们就拥有了三个满足条件的数字，e、d、n，把 e 和 n 作为公钥部分发出去，而 d 作为私钥保存起来，就完成了一次 RSA 密钥生成。其中 p 和 q 和 \(\lambda(n)\) 也不可以公开，但是这三个的值其实可以在生成好之后直接销毁，因为加密解密并不需要这三个值。
当然在实际上，为了能够达到更高的安全性，还有一些其他的细节，例如 p 和 q 的选择也是有一定的要求，他们的大小应该相似，但是长度不一样；再比如 p – 1 和 q – 1 也有一些要求。所以经常在生成一个 RSA 密钥对的时候，要花很长的时间，因为要找到满足条件的 p 和 q，以及 e 也要互质。
证明
就算看了上面的密钥生成过程，其实也是没办法搞清楚的。可能会有很多疑惑，比如为啥不能干脆直接随机三个数字，e、d、n，而是要搞这么复杂，又是 p 和 q，又是 \(\lambda(n)\) 的，有啥意义？
再比如这样生成出来的三个数字，就一定能满足 \((m^e)^d \equiv m \pmod n\)吗？
这些问题都可以通过证明的方式来解答。那么证明什么呢？即如果这个公式满足了，那么 e 和 d 的关系一定满足
$$ e \times d \equiv 1 \pmod{\lambda(pq)} $$
反过来也是一样的，这样就可以说明在密钥生成过程中，e 和 d 的计算不是乱算的，而是有理有据的，保证计算出来的值可以用于 RSA。
那如果我们真的用了三个随机数来做参数，使得上面的公式不满足，会发生什么呢，当然是没办法用 RSA 了。具体来说，就是当你计算了 \((m^e)^d \bmod n\) 之后会发现，得出来的结果居然不是 m 了！我加密后的内容无法解密了！
证明的方式有两种，第一种是用欧拉定理来证明，第二种则是用费马小定理。我们首先来看第一种方式。
证明-欧拉定理
首先我们先来看 e 和 d 在使用欧拉函数时候的形式，
$$ e \times d \equiv 1 \pmod{\phi(n)} $$
这说明，e 和 d 的乘积除以 \(\phi(n)\)，余数是1，换句话说，e 和 d 的乘积可以表示为，
$$ ed = k \cdot \phi(n) + 1, \qquad k \in \mathbb{Z} $$
也就是说，ed 是 k 个 \(\phi(n)\) 加上一个 1。
于是 RSA 原理公式就可以改写成
$$ (m^e)^d \equiv m^{ed} \equiv m^{k \cdot \phi(n) + 1} \pmod n $$
再进一步变化下形式
$$ m^{k \cdot \phi(n) + 1} \equiv (m^{\phi(n)})^k \cdot m \pmod n $$
根据欧拉定理，
$$ a^{\phi(n)} \equiv 1 \pmod n $$
当 m 和 n 互质的时候，可以替换成
$$ (m^{\phi(n)})^k \cdot m \equiv 1^k \cdot m \equiv m \pmod n $$
这样我们就证明了在 m 和 n 互质的情况下，之前算出来的 e、d、n 确实可以让RSA 公式成立。
那如果 m 和 n 不是互质的呢？由于 n 是 p 和 q 的乘积，那么当 m 恰好是 p 或者 q 的整数倍的时候，m 就和 n 不互质，欧拉定理就没办法应用在上面的证明，这是不是就说明，RSA 没办法用来加密恰好是 p 或者 q 整数倍的消息呢？并不是，只要 m 是小于 n 的，那么 RSA 都是适用的。这一点又如何证明呢，就要用到费马小定理了。
证明-费马小定理
费马小定理说，对于一个质数 p，以及任意的一个数字 a，下面的公式都满足
$$ a^p \equiv a \pmod p $$
换一个说法就是，\(a^p – a\) 可以被 p 整除。
而且如果 a 不能被 p 整除，也就是 a 和 p 互质的时候，费马小定理还可以成为
$$ a^{p – 1} \equiv 1 \pmod p $$
除了费马小定理之外，还需要用到另一个定理，叫做中国剩余定理，缩写一般是 CRT，即 chinese remainder theorem。
这个定理可以得出一个推论，
$$ \begin{cases} a \equiv b \pmod{p_1} \\ a \equiv b \pmod{p_2} \end{cases} $$
其中 \(p_1\) 和 \(p_2\) 都是质数，当上面两个都成立的时候，等价于下面的式子也成立
$$ a \equiv b \pmod{p_1 \times p_2} $$
而 RSA 中的 n 的值就是两个质数的乘积。所以我们只需要证明，
$$ \begin{cases} (m^e)^d \equiv m \pmod{p} \\ (m^e)^d \equiv m \pmod{q} \end{cases} $$
这两个式子同时成立，就可以证明 RSA 的公式了。
分为两种情况，第一种情况当然是欧拉定理没办法处理的部分，也就是如果 m 是 p 的整数倍，非常不巧的是，在这种情况下，费马小定理也没办法证明。但不代表我们走进了死胡同，因为如果 m 是 p 的整数倍，那么 \(m \equiv 0 \pmod p\) 显然是成立的，因为 m 对 p 取余就是0，那 \((m^e)^d\) 对 p 取余的结果是什么，根据我们在小学二年级就学到的数学，0 乘以其他都是 0，那么一堆的 0 乘起来是什么，还是 0。
所以我们就证明了 \((m^e)^d \equiv 0 \equiv m \pmod p\)。
那第二种情况自然就是 m 并不是 p 的整数倍，由于 p 是质数，所以 m 和 p 理所当然的互质了，这样我们就可以用费马小定理了。
为了能够进行下一步的证明，还需要知道如何计算 \(\phi(n)\) 的值，也就是欧拉函数的值。
当 n 可以进行分解的时候，\(\phi(p \cdot q)\) 就可以变成 \(\phi(p) \cdot \phi(q)\)，也就是分别对 p 和 q 计算欧拉函数的值。根据定义，我们可以知道，因为 p 是质数，所以 \(\phi(p)\) 的值就是 p – 1，这很好理解，从 1 到 p – 1 的值都和 p 互质，毕竟 p 就是质数，他没有其他的因子了。所以 \(\phi(n)\) 就等于 \((p – 1) \cdot (q – 1)\) 了。
和上一节用到的方法一样，我们同样可以把 ed 改写成
$$ e \cdot d = k \cdot (p – 1) \cdot (q – 1) +1, \qquad k \in \mathbb{Z} $$
再把等式右边的 1 移动到左边，变成
$$ e \cdot d – 1 = k \cdot (p – 1) \cdot (q – 1), \qquad k \in \mathbb{Z} $$
同理对 RSA 的公式进行变形
$$ (m^e)^d = m^{e \cdot d} = m^{e \cdot d – 1} \cdot m = m^{k \cdot (p – 1) \cdot (q – 1)} \cdot m = (m^{p – 1})^{k \cdot (q – 1)} \cdot m $$
此时根据费马小定理
$$ a^{p – 1} \equiv 1 \pmod p $$
如果我们对上面变形后的式子对 p 取模，而且此时已经限定了 m 和 p 是互质的，那么就可以使用费马小定理替换，得到
$$ (m^{p – 1})^{k \cdot (q – 1)} \cdot m = 1^{k \cdot (q – 1)} \cdot m \equiv m \pmod p $$
然后使用相同的方式，对 q 也进行一样的证明，我们就可以证明对 p 和 q 都成立，进而得出结论，对 p 和 q 的乘积 n 也成立。成功的推广到了不论 m 对 n 是否互质，都可以实现 RSA 算法了。
证明-Carmichael函数
这时候肯定还会有人有疑问，上面证明了一大堆，只是证明了使用 \(\phi(n)\) 来生成密钥时候的正确性，但是我又说现在一般都是用 Carmichael 函数的，那怎么证明呢。
其实已经有人证明了满足 \(e \times d \equiv 1 \pmod{\phi(n)}\) 的 e 和 d，同样也满足 \( e \times d \equiv 1 \pmod{\lambda(n)}\)了。
但是我们也可以用同样的方式来证明，首先同样需要知道 \(\lambda(n)\) 怎么计算。
当 n 同样的可以进行分解的时候，\(\lambda(n)\) 在这个场景下，就等于 \(lcm(\lambda(p),\lambda(q))\)，其中 lcm 就是最小公倍数的意思。并且此时的 \(\lambda(p)\) 就是 \(\phi(p)\)，即 p – 1。
$$ \lambda(p \cdot q) = lcm(\lambda(p), \lambda(q)) = lcm(\phi(p), \phi(q)) = lcm(p – 1, q – 1) $$
最小公倍数是什么意思呢，如果一个数能被 a 整除，也能被 b 整除，并且它是所有满足这个条件的数里面最小的，就是最小公倍数。也就是说
$$ e \cdot d \equiv 1 \pmod{\lambda(p \cdot q)} $$
等价于
$$ e \cdot d – 1 \equiv 0 \pmod{\lambda(p \cdot q)} $$
于是 \(e \cdot d – 1\) 就既可以写成是 k 个 p – 1，也可以写成是 k 个 q – 1。使用同样的办法就可以用费马小定理证明了。
安全性
所以有了上面的内容之后，我们就会发现，在生成 e 和 d 的时候，是使用了 p 和 q 的，p 和 q 虽然作为私有部分不公开，而他们的乘积 n 却是公开的。如果我们的算力增长到能够在很短的时间内把 n 分解，找出 p 和 q 的值，那么我们就可以直接从公钥的 n 里面，再加上公开的 e，计算出 \(\phi(n)\) 或者 \(\lambda(n)\)，进而把私钥 d 也计算出来。
只要目前 n 没办法在短时间内分解出来，那么 RSA 就可以看作是还算安全的。
例子
我们来模拟以下 RSA 的密钥生成、加密与解密，来帮助更好的理解。
首先第一步，选择两个质数，我们这里选择 p = 61，q = 53。
然后计算 n，\(n = 61 \times 53 = 3233\)。
计算
$$\lambda(n) = \lambda(3233) = lcm(61 – 1, 53 – 1) = lcm(60, 52) = 780 $$
再来选择一个 e，这里选择 e = 17。它和 780 互质。
然后计算 d，也就是计算 e 在 \(\lambda(n)\) 下的乘法逆元，得出 d = 413。因为
$$ (17 \times 413) \mod 780 = 1 $$
这样我们就可以得到公钥(n = 3233, e = 17)，以及私钥(n = 3233, d = 413)。
现在我们来进行一次加密，例如要加密的原文 m 为 65，那么加密过程就是
$$ c = 65^17 \mod 3233 = 2790 $$
而解密的过程就是
$$ m = 2790^413 \mod 3233 = 65 $$
RSA 的签名
RSA 除了能用作加密和解密，还可以用作签名。需要注意的是，RSA 算法既能加密解密，也能签名，只是恰好 RSA 可以这么做，这并不代表其他的公钥体系算法也可以同时加密解密和签名。
例如目前流行的 Ed25519 来说，它就是一个签名算法，并不能用来加密和解密。
RSA 的签名很常见的一个说法就是，签名是用私钥加密，公钥解密。为什么这么说呢，先来看看具体是怎么做的。
要做签名，首选需要有一个摘要算法，或者叫哈希算法。
我们计算出要签名的信息的摘要，h = hash(m)，然后签名的时候，则计算的是
$$ h^d \mod n $$
也就是用私钥的 d 来做指数运算。而当验证签名的时候，则再用公钥的 e 做一次指数运算。
$$ (h^d)^e \bmod n $$
就可以拿出 h 的值，随后验证方再计算一次消息的摘要，对比两个内容，就可以知道签名是否有效，数据有没有被更改了。
其中摘要算法用的多的就是 SHA256了，比如我们说 RS256 的时候，就是指的是 RSA+SHA256 的签名方案。
那么我们叫签名是用私钥来加密这个说法对不对呢，严格的来说，不算是正确的。因为签名这个步骤不光是只有使用 d 做指数运算，还包括了算摘要的过程。
而且加密也不光是只有用 e 做指数运算，原文 m 还必须经过一些预处理，比如说 padding 的步骤。
就好比南方人在食堂或者饭店问你“吃饭吗”，他可能就是在问你，要不要点一份大米。而如果一个北方人在这种情况下问你“吃饭吗”，你可能会觉得他没睡醒，我都坐在桌子上了，你问我吃不吃饭？不吃饭我来这里干啥，难道是来看其他人吃饭的吗。这就是因为在南方人的概念中，“饭”就是指的是 “大米饭”，而北方人的“饭”是一个统称。
结语
以上就是本文的全部内容了，由于我也不是专业的数学研究者，也没有很系统的学习过数论之类的东西，上面的大部分数学内容都是我花了十分钟学习和整理的内容，也可能会存在一些不足。
参考资料
[1] https://math.stackexchange.com/questions/772063/to-solve-for-the-decryption-exponent-why-do-we-solve-the-congruence-de-1-mo
[2] http://www.cs.sjsu.edu/~stamp/CS265/SecurityEngineering/chapter5_SE/RSAmath.html
[3] https://en.wikipedia.org/wiki/RSA_(cryptosystem)
[4] https://en.wikipedia.org/wiki/Fermat%27s_little_theorem
[5] https://en.wikipedia.org/wiki/Euler%27s_totient_function
[6] https://en.wikipedia.org/wiki/Carmichael_function
[7] https://crypto.stackexchange.com/a/11528
[8] https://www.youtube.com/watch?v=Z8M2BTscoD4