技术 / 读书 /《算法导论》/ RSA加密原理

[huanzhiyazi]

1 RSA 用到的数论原理

整个数论算法这一章，都是为了最终阐述 RSA 加密的底层原理。换句话说，RSA 加密算法的本质就是部分数论原理的运用。具体来说，用了以下数论原理：

1. 用反复平方法进行模取幂运算：设 a，b 为非负数，n 为正整数，计算 a^b mod n。用于 RSA 加密和解密运算；
2. 求解模线性方程：ax ≡ b(mod n)，其中 a>0，n>0。用于 RSA 密钥的计算；
3. 模运算以及相关概念：模n加法，模n乘法，群，模n加法群，模n乘法群，群规模（尤其是模n乘法群的规模φ(n)）。用于模取幂运算和模线性方程求解的方法的证明，同时φ(n)用于 RSA 公钥和密钥的计算；
4. 欧几里得算法求解最大公约数：对任意非负整数 a 和任意正整数 b，gcd(a,b) = gcd(b, a mod b)。用于互质的验证和相关定理的证明；
5. 基础数论：整除性，约数，素数与合数，余数，等模，以及相关的定理。

2 加密概念和加密方式

在密码学中，关于加密有很多概念：加密，密钥，公钥，对称加密，非对称加密，数字签名，证书。

2.1 相关概念

• 明文传输最容易被窃听，所以将明文通过某种算法编码之后变成密文的过程称为 加密。

• 对应的，用相同的算法对密文解析回明文的过程叫 解密。

• 加密和解密算法可以看做两个函数，函数计算过程用到的关键参数称之为 钥匙，钥，key。

• 我们把这两个函数称为 变换。特别的，如果钥是需要保密的，就叫做 密钥，如果是公开的，则称为 公钥。

• 对于同一条信息，如果在加密和解密中，使用的是相同的密钥，则这样的变换算法我们称之为 对称加密。

• 对于同一条信息，如果用公钥加密，用私钥解密；或者用私钥加密，用公钥解密，则这样的变换算法我们称之为 非对称加密。

• 设公共变量：M 为明文，C 为密文，p 为公钥，s 为密钥。

• 对于对称加密，设：加密变换为 E()，解密变换为 D()，所以有 E(M,s) = C，D(C,s) = M，即 D(E(M,s),s) = M。

• 对于非对称加密，设：公钥变换为 P()，私钥变换为 S()，且 P() 和 S() 互为逆变换，即 S(M,s) = C，P(C,p) = M；P(M,p) = C，S(C,s) = M；S(P(M,p),s) = P(S(M,s),p) = M。

• 我们假设一条身份信息为：I，将身份信息用私钥变换加密后，与明文身份信息组成一个二元组 [I,S(I,s)]，然后其它任何人都可以通过公钥变换将二元组的加密信息还原，并与二元组的明文身份进行核对，如果核对无误，说明该身份验证成功，即数字签名的验证过程为： I = P(S(I,s),p)。
  密钥变换结果 S(I,s) 称为 数字签名。

• Alice 发送加密信息给 Bob 的时候，Bob 一般需要确认两件事：一是 Alice 是一个可信任的发送方而不是恶意攻击者，所以 Alice 需要一个权威的公信组织的证明，这个证明由一个公开的组织 CA（certificate authority，证书颁发机构）以数字签名的方式颁发，称之为 证书；二是 Alice 的公钥，用以对加密信息进行解密，而这个公钥也是附加在证书里的。

• 注意，证书是一个数字签名，为了验证证书，每个人都知道证书的公钥，所以每个人都能对证书进行验证。

• 证书里存储的信息除了 Alice 的公钥以外，还包括：证书版本号、序列号、证书签名算法、证书颁发者、有效期、Alice 的个人信息等。Bob 在收到 Alice 的证书之后，通过公钥变换核对证书的真伪。如果 Bob 是一个浏览器，则会保存很多权威 CA 的信息，以便于验证真伪。

2.2 RSA 加密系统

• 欧拉 phi 函数（即模n乘法群规模大小） φ(n) 的定义如下：

• 模线性方程的一个推论：对任意 n>1，如果 gcd(a,n) = 1，那么方程 ax ≡ 1(mod n) 对 n 有唯一解；否则方程无解。此处，x 称为 a 对模 n 的乘法逆元。

• RSA 加密算法是一种非对称加密算法。

• RSA 加密生成公钥和密钥的过程：

  1. 随机选取两个大素数 q1 和 q2，使得 q1≠q2，例如，素数 q1 和 q2 可能各有 1024 位。
  2. 计算 n=q1q2。
  3. 选取一个与 φ(n) 互质的小奇数 e，根据 φ(n) 的定义可知：φ(n)=(q1-1)(q2-1)。
  4. 对模 φ(n)，计算出 e 的乘法逆元 d 的值，由上述推论可知，d 是存在且唯一的，给定 e 和 φ(n)，可以通过求解模线性方程求得 d。
  5. 生成公钥为一个二元组： p=[e, n]，并公开。
  6. 生成密钥为一个二元组：s=[d, n]，并保密。
  7. 公钥变换为：P(M,p) = P(M,e,n) = M^e mod n，此处 M 也可以为 C。
  8. 私钥变换为：S(C,s) = S(C,d,n) = C^d mod n，此处 C 也可以为 M。

• RSA 的正确性：P(S(M,s),p) = S(P(M,p),s) = M^(ed) (mod n) = M，证明略。

• RSA 的安全性：找出大素数 q1 和 q2 比较容易，但是给定大整数 n，要对 n 进行质因数分解成 q1q2 则相当困难。具体来说，最终需要破解密钥，即知道 d 是什么，而要求解 d，根据上述过程 4 可知，必须先求得 φ(n)，而根据过程 3 又可知 φ(n)=(q1-1)(q2-1)，这个求解难度等价于求解 n=q1q2。

• 加密在网络通信中最经典的运用就是 HTTPS，核心是 SSL 安全协议，在 HTTP权威指南/SSL握手原理 中已有详细总结。

算法导论 / 第31章 数论算法