RSA 加密算法

在一些场景中, 我们不希望和他人交流的内容被第三方知道, 所以就产生了一门学问, 密码学. 一开始, 人们用很容易破解的方式讲信息加密, 如把每个单词的字母重排, 或者把所有字母用它的后一位字母代替. 这些方法都是不够安全的, 所以人们发明了对称密钥加密.

对称密钥 (Symmetric-key) 加密

假设 Alice 要发送给 Bob 的明文是 $A$, 他们提前商定好了一个密码 $C$, 规定一个规则 $f(C, A)$, 通过密码和明文可以生成密文 $B = f(C, A)$, 这时 Alice 就可以光明正大地公开传输密文 $B$ 给 Bob. Bob 收到了密文 $B$ 之后, 使用已经提前规定好的 $f$ 的逆规则 $g$, 可以通过密码和密文生成明文 $A = g(C, B)$. 只要密码和规则 $f$ 足够强, 就可以实现加密通话.

我之前也有过类似的实现, 但是安全度不高, 具体是这样的: 认为密码是一个字符串, 我用这个字符串生成了一个哈希值称为 $C$, 模数不大于 $2^{22}$. 明文是一个二进制串 $A$. 我规定一个大于 $2^{30}$ 的大质数 $Mod$, 然后把明文按 $8bit$ 分段, 认为 $A_i$ 是明文的第 $i$ 段, 把它当成是一个 $8$ 位无符号整数, 我们把 $A_i(C!)$ 对 $Mod$ 取模的结果作为密文的第 $i$ 段 $B_i$. 因为 $C < Mod$, 因此对于不同的 $C$, $C!$ 对 $Mod$ 取模的结果一定不同, 也可以通过乘以它的逆元并且对 $Mod$ 取模迅速得到 $A_i$. 可以发现密文的每一段都是 $30$ 位无符号整数. 并且可以在知道 $C$ 的前提下通过模 $Mod$ 意义下数乘 $C!$ 的逆元得到明文 $A$. 为了可以以字符串的形式传输, 对 $[0, 64)$ 的整数映射道 $64$ 个可显示的 ASKII 字符上, 对密文的每一段 $B_i$ 映射到长度为 $5$ 的字符串 $S_i$, 把这些字符串连起来, 得到字符串 $S$ 用来传输密文.

但是显然这样做的缺点是只要第三方知道 $Mod$ 和前面讲到的这些规则, 他们就可以通过枚举不超过 $2^22$ 个 $C$ 来破解密码. 这就是为什么说我之前的实现不够强.

而且即使有了无法破解的密码和生成密文的规则, 对称密钥加密仍然有他的局限性, 每对要通话的人都需要提前秘密商定好密码, 这在互联网时代是非常困难的, 所以人们又发明了非对称密钥加密算法, 又叫公开密钥加密.

公开密钥 (Public-key) 加密

在这种加密方式中, 每个人持有一个公钥 $c$ 和私钥 $d$, 假设 Alice 要给 Bob 发送明文 $A$, 他们公开自己的公钥, 并且保存自己的私钥, 规定规则 $f(c, A)$ 可以通过收信人的公钥和明文生成一段密文. Alice 可以根据 Bob 的公钥 $c_2$ 生成密文 $B = f(c_2, A)$, 并且公开传输密文 $B$ 给 Bob. 规定规则 $g(d, B)$, 可以通过收信人的私钥和密文生成明文. 这时 Bob 可以用自己的私钥 $d_2$ 得到明文 $A = g(d_2, B)$.

这种加密方式可以使得每个人只要公开自己的公钥, 就可以让别人专门为自己生成只有使用自己的私钥可以解密的密文, 无需使每对人提前商定好密码.

最广泛的公开密钥加密算法是 RSA 算法, 接下来就简单介绍一下这种算法.

RSA (Rivest–Shamir–Adleman) Algorithm

RSA 算法的安全性是由大整数分解的困难度保证的, 目前最先进的分解质因数的算法是普通数域筛选法, 其复杂度约为:

$L_n[\frac 13, c] = e^{(\sqrt[3]{\frac{64}{9}} + o(1))\sqrt[3]{\ln n(\ln \ln n)^2}}$

但是如果量子计算技术成熟, 存在更加先进的秀尔算法, 可以在 $O(\log^3 n)$ 时间内分解 $n$, 到时候 RSA 算法的安全性将不复存在.

不过目前为止, RSA 算法在 $n$ 取 $2^{2048}$ 左右时仍然是安全的.

其理论是这样的, 取大质数 $p$, $q$, 得到 $N = pq$, 可以得到 $r = \phi(N) = (p - 1)(q - 1)$, 根据欧拉定理 (数论), 我们知道对于任意正整数 $a < N$, 有 $a^{\phi(N)} \equiv 1 \pmod N$. 这个时候我们可以确定一个 $r$ 以内的整数 $e$, 满足 $\gcd(e, r) = 1$, 并且用 Exgcd 求出 $e$ 在模 $r$ 意义下的乘法逆元 $d$. 我们认为 $(N, e)$ 是一个私钥, $(N, d)$ 是一个公钥, 它们成对产生. 接下来介绍一下一次通话的过程.

这时假设 Alice 要发给 Bob 一条信息 $A$, 她知道了 Bob 的公钥 $(N, d)$, 这时她可以把 $A$ 分段, 每一段 $A_i$ 可以认为是一个小于 $N$ 的正整数. 定义另一个整数序列 $B$, 每一个元素是小于 $N$ 的正整数 $B_i \equiv {A_i}^e \pmod N$. 然后把 $B$ 序列公开传输给 Bob. Bob 收到后, 可以把 $B_i$ 求模 $N$ 意义下 $d$ 次方的结果, 计算出 $({A_i}^e)^d = {A_i}^{ed}$, 由欧拉定理得 ${A_i}^{kr + b} \equiv {A_i}^{b}$, 又因为 $ed \equiv 1 \pmod r$, 因此 ${A_i}^{ed} = A_i$, 这样 Bob 就得到了明文 $A$.

现在的压力给到了如何生成一个大质数, 基本思路是随机生成一个数, 然后判断它是否是质数, 因为 $n$ 以内大约有 $\frac n{\ln n}$ 个质数, 所以期望随机 $\ln n$ 次就可以得到一个质数. 因为大质数都可以写成 $6k - 1$ 或 $6k + 1$ 的形式, 我们还可以通过随机生成 $k$来减少期望得到质数的随机次数. 问题转化为如何快速判断一个数是否是质数, 我们肯定不能用试除法, 所以接下来考虑更加先进的素性测试.

Miller-Rabin 素性测试可以在广义黎曼猜想正确的前提下实现多项式时间的素性判断. 也可以在准确率和效率中做取舍, 减少测试数量, 牺牲准确率来换取效率.

但是对于素性测试已经有确定性的, 不仰仗未经证明的猜想的多项式算法, 这就是印度的计算机科学家发表于 2002 年的 AKS 素性测试.

但是 AKS 的效率还是达不到 Miller-Rabin 那么高, 所以可以采用测试次数被刻意减少的 Miller-Rabin 检测进行初筛, 然后用 AKS 进行确定性检测.

复合加密

因为 RSA 的加密和解密都需要多次对大整数做乘方和取模运算, 所以效率较低, 不适合进行流量大的通讯, 所以应用中可以通过和别的加密方式结合的方式来使用. 比如我们可以用 RSA 和对称密钥加密结合, 用 RSA 来传输密钥, 加密的密文由两部分组成, 前一部分是由 RSA 加密的密钥, 后一部分是对称加密的密文, 这样可以做到每条信息都使用不同的密钥, 达到和 RSA 不相上下的安全度和更高的效率.

参考文献

• Wikipedia - 密码学
• Wikipedia - 对称密钥加密
• Wikipedia - 公开密钥加密
• Wikipedia - RSA加密算法
• 哈尔滨工业大学出版社 - ACM-ICPC 程序设计系列 数论及应用