整理一下RSA算法的内容，主要参考维基百科。

对称加密与非对称加密

首先从对称加密开始，Alice和Bob需要进行加密的通信，Alice传递信息 \(m\) 给Bob。

为了信息安全，Alice首先用字母表替换的方式 \(A\) 将明文m变成密文 \(m'=f_A(m)\)，然后通过公开方式传递给Bob，Bob使用同样约定好的字母表替换方式 \(A\) ，将收到的密文 \(m'\) 变成明文 \(f_A^{−1}(m')=f_A^{−1}(fA(m))=m\) 。

这里我们对信息都视作字符串，从而字母表替换规则 \(A\) 实际上定义了字符串到字符串的加密函数 \(f_A\) 和解密函数 \(f_A^{−1}\) ，这里加密函数和解密函数都是通过 \(A\) 决定的，并且极容易从其中一个推出另一个，因此双方都必须保管好密码本 \(A\) 。

例如，使用替换的字母表 \(A\) 为

1
1->3， 2->4， 3->2， 4->1

用轮换的记号就是\((1324)\)，此时的加密函数 \(f_A\) ，明文\(1234\)，密文 \(f_A(1234)=3421\)。同时得到解密函数 \(f_A^{−1}\)，解密 \(f_A^{−1}(3421)=1234\)。

字母表替换也可以换成其他的加密方法，但是它们都有一个共同的特点，基于同一个“密码本”去定义加密函数和解密函数，并且通过其中一个可以迅速推出另一个，这样带来一个问题：如何安全地让Alice预先把“密码本”交给Bob，而不被第三者获知，一旦密码本被截获，第三者就可以实现加密解密过程，信息传输就不再安全。

我们考虑破坏对称性，希望在上述情景中，加密函数 \(f\) 和解密函数 \(f^{−1}\) 不再可以迅速地相互推出，引入公钥和私钥的概念，Alice 拥有一对钥匙 \(\{A^−,A^+\}\) （公钥，私钥），她把其中的一把视作公钥 \(A^+\) 向所有人公开，把另一把视作私钥 \(A^−\) 对所有人保密。Bob同样也有自己的公钥私钥。

公钥和私钥可以定义出相应的函数 \(f_{A^−},f_{A^+}\) ，满足函数复合后是恒等的 \(f_{A^−}\circ f_{A^+} = f_{A^+} \circ f_{A^−} = I\) ，这里可以发现，公钥和私钥是相互等价的，地位上相互交换也可以，但是必须要人为区分开，并且保证其中一把公开，一把保密。

假定Alice和Bob把自己的公钥公开，并且可以安全地通过信任的第三方平台拿到正确的对方的公钥，也就是说，现在Alice拥有了自己的私钥 \(A^−\) 和Bob的公钥 \(B^+\) ，Bob拥有了自己的私钥 \(B^−\) 和Alice的公钥 \(A^+\) 。

由于我们公开了其中一把，我们需要保证不能在有限的时间内通过其中一把算出另一把。理论上总是可以只通过 \(f\) 推出 \(f^{−1}\) ，这里有限的时间可以理解为信息保密需要的时间，比如第三方使用计算机用穷举法在五百年后终于通过公钥算出了私钥，这种情况我们允许存在，因为信息经过五百年已经失去了保密价值，在这种意义下算法是安全的。

信息加密传递过程主要是这样的：Alice希望把明文 \(m\) 加密传递给Bob，通过Bob的公钥 \(B^+\) 加密，密文 \(m' = f_{B^+}(m)\) 被传递给Bob，Bob使用自己的私钥 \(B^-\) 进行解密，获取原始信息 \[ f_{B^-}(m') = f_{B^-} \circ f_{B^+}(m) = m \] 也就是说，用Bob的公钥加密后，会得到一封只有Bob能打开的密信。由于公钥公开了，谁都可以写这样的信，但是只有Bob可以打开它们。

还可以有这样的过程，Alice要公开发布一个声明 \(m\)，需要签名让所有人确认这是Alice发出，而非其他人伪造的，可以通过上述公钥私钥实现：Alice把公开声明 \(m\) 通过自己的私钥 \(A^-\) 进行加密，然后公开密文 \(m' = f_{A^-}(m)\)，由于Alice公开了自己的公钥 \(A^+\)，所有人都可以使用公钥解密，从而正确读出里面的信息 \[ f_{A+}(m')=f_{A^+}\circ f_{A^-}(m) = m \] 由于只有Alice持有自己的私钥，因此我们相信这个信息 一定是Alice自己发出的。也就是说，Alice用自己的私钥加密后，得到了一封所有人可读，并且证明只有Alice自己可以写入的公开信，相当于Alice对这封公开信进行了不可伪造的签名。

RSA算法的过程

RSA算法是普遍采用的一种非对称加密算法，产生于20世纪70年代，

二战中没有使用非对称加密，德军使用的恩尼格玛密码机相当于一种很复杂的对称加密，但是被盟军得到了一台密码机，从而完成了破译。

RSA算法的安全性依赖于数论中的知识：对一个极大的整数进行素因子分解是困难且低效的。（相对的，大数乘法，辗转相除等操作可以快速实现）

当然进行暴力穷举总是可以的，但是在当前计算机算力下将是漫长的时间。如果找到了一个多项式时间内快速进行大数的素因子分解的算法，那么RSA算法的安全性将不复存在。

RSA的基本过程（参考维基百科）：

  1. 随机生成两个不同的大素数 \(p,q\) ，为了安全建议取得足够大并且两者位数差不多但也不要完全一样。
  2. 记 \(n = pq\)，\(z = z(p,q)\)，这里 \(z\) 的定义在RSA算法中存在不同的实现，最早期使用的是欧拉函数值 \(z = \phi(n)\) ，后来改进为使用卡迈克尔函数值 \(z = \lambda(n)\)，这两个都是数论中的函数。卡迈克尔函数在一些情况下就是欧拉函数值，它总是欧拉函数值的一个因数。对于两素数之积 \(n=pq\)，有 \(\phi(pq) = (p-1)(q-1)\)，\(\lambda(pq) = \text{lcm}(p-1,q-1)\) 。为了简单化，这里使用欧拉函数 \(z = \phi(n) = (p-1)(q-1)\)。
  3. 挑选两个数 \(d,e\) 使得它们在模 \(z\) 的意义下互为乘法逆元，即 \(de = 1 \pmod z\)。（挑选的细节留在下文）
  4. 将 \(p,q\) 的存储销毁，将 \((n,e)\) 作为公钥，将 \((n,d)\) 作为私钥，公开公钥，保留私钥。（也就是说，公钥和私钥就是两个有序的二元数组，当然这里算法给出的公钥私钥具有对称性，把\(d\)放在公钥中，把\(e\)放在私钥中也是一样的）

这里我们统一将所有的信息（明文，密文）视作正整数，而且我们要求待加密的数据 \(m\) 的数值大小不会超过 \(n\)。实践中可以对数据按照固定位数进行划分，按照2进制读取，根据划分长度天然存在上界，在算法生成时要求 \(pq\) 超过即可。

加密解密过程：

  • 对于明文 \(m\)，使用公钥 \(A^+=(n,e)\) 加密，得到密文 \(m'\) \[ m' := f_{A^+}(m) = m^e \pmod{n} \]

  • 对于密文 \(m'\)，使用私钥 \(A^-=(n,d)\) 解密，得到明文 \(m\) \[ m = f_{A^-}(m') = (m')^d = m^{ed} = 1 \pmod{n} \]

RSA算法的加密解密过程的算法描述和实现都很简单：加密就是在模 \(n\) 意义下做 \(e\) 次幂，解密就是在模 \(n\) 意义下做 $d 次幂。在硬件实现上，只需要支持大整数的幂运算和模运算。

我们补全上述过程中略掉的一个细节，也就是 \(d,e\) 的生成。如果任取 \(d\) 并固定，那么满足 \(de = 1 \pmod{z}\) 的 \(e\) 是否存在唯一？我们只能希望在模 \(z\) 的意义下是唯一的。

裴蜀定理可以保证，当且仅当在 \(\text{gcd}(d,z) = 1\) 即 \(d\) 与 \(z\) 互素时，乘法逆元 \(e\) 存在且在模 \(z\) 的意义下唯一。因此我们可以首先挑选与 \(z\) 互素的 \(d\)，然后计算出模 \(z\) 的乘法逆 \(e = d^{-1}\)。

这里涉及一个策略细节：先选 \(d\) 算 \(e\)，还是先选 \(e\) 算 \(d\)？在算法中两者是完全对称的，但是对于实际计算量来说存在差异，我们可以人为控制使得选取的第一个数不太大，但是由此计算得到的第二个数可能非常巨大，而我们需要以此为次数进行幂运算，因此先选 \(d\) 利于快速解密计算，先选 \(e\) 则易于快速加密计算。

我们似乎很难直接挑出一个 \(d\) 与已知的 \(z\) 互素，但是这不是大问题，可以先随机选择，再使用辗转相除法验证，如果最后辗转相除得到 \(1\)，则互素，否则重新挑选 \(d\) 即可。如果 \(d\) 是满足互素要求的，则我们可以再辗转相除算法中，顺便记录下系数 \(x_1,x_2\)，使得 \(d x_1 + z x_2 = 1\)，取 \(e = x_1 \pmod{z}\) 即可。

RSA算法也可能具有某种漏洞，因为算法给出的大素数 \(p\)，\(q\) 的选择不能做到真正的随机，可能具有某种规律性，利用这些规律可能加速算法的暴力破解。

实践中，RSA公钥文件的格式可能形如 

1
ssh-rsa AAAAB3NzaC1yc2EAAAABIwAAAQEArR... user@host

其中使用base64编码了需要的两个数值 \((n,e)\)。RSA私钥文件的格式可能形如 

1
2
3
-----BEGIN OPENSSH PRIVATE KEY-----
b3BlbnNzaC1rZXktdjEAAAAABG5vbmUAAAA...
-----END OPENSSH PRIVATE KEY-----

其中存储的参数比公钥文件更多，不止必须的两个数值 \((n,d)\)，还有更多参数可以加速解密计算。

RSA算法的数学证明

定理一：取两个互异素数 \(p\neq q\) ，记 \(n=pq\) ，记 \(z = \phi(pq)=(p-1)(q-1)\) ，再取固定的数对 \(d,e\) ，满足 \(de = 1 \pmod{z}\)，则：对于 \(0 \le m < n\)，都有 \[ m^{de} = 1 \pmod{n} \]

定理二：取两个互异素数 \(p \neq q\) ，记 \(n=pq\) ，记 \(z=\phi(pq) = (p-1)(q-1)\) ，再取固定的数对 \(d,e\) ，满足 \(de = 1 \pmod{z}\)，则：对于 \(0 \le m < n\)，并且满足 \(\text{gcd}(m,n)=1\)，那么 \[ m^{de} = 1 \pmod{n} \]

欧拉定理：对于 \(n\) 和 \(a\)，如果 \(\text{gcd}(a,n)=1\)，则 \(a^{\phi(n)} = 1 \pmod{n}\)。 费马小定理是欧拉定理的特例：对于素数 \(p\)，以及整数 \(a\)，如果 \(\text{gcd}(a,p)=1\)，则 \(a^{p-1} = 1 \pmod{p}\) 。

定理二的证明：欧拉定理保证 \[ m^z = m^{\phi(n)} = 1 \pmod{n} \] 不妨记 \(de = k z + 1\) ，则有 \[ m^{de} = m^{kz+1} = m \pmod{n} \] 因此定理二得证。

定理一的证明：只需证明不满足互素的例外情形，如果 \(\text{gcd}(m,n) \neq 1\)，不妨设 \(p\) 是 \(m\) 的因子，\(q\) 不是它的因子（\(m\) 不可能同时有素因子\(p,q\)），记 \(m = \lambda p\) ，其中 \(\text{gcd}(\lambda,q) = 1\)，不妨记 \[ de = kz+1 = k(p-1)(q-1)+1 \] 由费马小定理可得 \[ m^{ed} = [(\lambda p)^k]^{(p-1)(q-1)}\, (\lambda p) = \lambda p \pmod{q} \] 显然还有 \[ m^{ed} = (\lambda p)^{ed} = 0 \pmod{p} \] 因此得到方程组 \[ \left\{ \begin{aligned} m^{ed} - m ={}& 0 \pmod{q} \\ m^{ed} - m ={}& 0 \pmod{p} \end{aligned} \right. \] 由中国剩余定理可得 \[ m^{ed} = m \pmod{pq} \] 因此定理一得证。

RSA算法示例

取两个素数 \(p=11,q=13\)，计算可得 \(n = 11\times 13=143\)，\(z = 10 \times 12 = 120\)。

我们挑选 \(d=17\)，通过辗转相除计算 \(e=113\)，满足 \(d e = 17 \times 113 = 1 \pmod{120}\)，从而得到公钥 \((143,113)\)，私钥 \((143,17)\)

取明文 \(m=88\)，加密 \[ m' = m^e = 88^{113} = 121 \pmod{143} \] 解密 \[ m = (m')^d = 121^{17} = 88 \pmod{143} \] 当然这个过于简单的公钥是不安全的，因为 \(n=143\) 显然可以推出素数对为 \(11, 13\)。