RSA 算法
| RSA | |
|---|---|
| 术语名称 | RSA |
| 英语名称 | RSA |
| 别名 | Rivest-Shamir-Adleman algorithm |
RSA算法指一种公钥加密系统，是根据 Euler 定理的直接推论。 其安全性基于大质数分解的困难性，目前在作为密钥的大质数足够大的情况下，未有有效破解办法公布。
算法
原理
对大整数 [math]\displaystyle{ \alpha, \beta, n }[/math] ，若有
- [math]\displaystyle{ n = pq }[/math]， 其中 [math]\displaystyle{ p,q }[/math] 是两个大质数；
- [math]\displaystyle{ \alpha \beta \equiv 1 \pmod{\varphi(n)} }[/math] 即 [math]\displaystyle{ \alpha \beta \equiv 1 \pmod{(p-1)(q-1)} }[/math] 。
则有
- 对任意整数 [math]\displaystyle{ m }[/math] ，有 [math]\displaystyle{ m^{\alpha\beta} \equiv m \pmod n }[/math] （根据欧拉定理 [math]\displaystyle{ m^{\varphi(n)} \equiv 1 \pmod{n} }[/math] 及 [math]\displaystyle{ \alpha \beta \equiv 1 \pmod{\varphi(n)} }[/math] 易得）
- 对任意整数 [math]\displaystyle{ A }[/math] ，有 [math]\displaystyle{ 0 \leq A \lt n }[/math] ，都存在唯一 [math]\displaystyle{ B }[/math] 满足 [math]\displaystyle{ 0 \leq B \lt n }[/math] 且 [math]\displaystyle{ B \equiv A^\alpha \pmod n }[/math] ，同时有 [math]\displaystyle{ B^\beta \equiv A^{\alpha\beta} \equiv A \pmod n }[/math] 。
同时，如果不知道 [math]\displaystyle{ p, q }[/math] ，通过 [math]\displaystyle{ n }[/math] 得知 [math]\displaystyle{ \varphi(n) }[/math] 需要通过质因数分解。这是一个已知的困难问题。
注：由于最初论文中使用的是 [math]\displaystyle{ \alpha \beta \equiv 1 \pmod{\varphi(n)} }[/math] ，以上也使用这一表述。实际上这是要计算一个 [math]\displaystyle{ k^{\alpha \beta} \equiv 1 \pmod{n} }[/math] 的 [math]\displaystyle{ \alpha\beta }[/math] 整体， Euler 定理保证 Euler 函数 [math]\displaystyle{ \varphi(n) }[/math] 的倍数总是满足这一条件，但这是一个充分不必要条件，其充要条件是 Carmichael 函数 [math]\displaystyle{ \lambda(n) }[/math] 的倍数。
算法
密钥生成
- 随机选取两个大质数 [math]\displaystyle{ p, q }[/math] ，为保证难以破解，应当尽量随机、两个数较大且差也较大。
- 选取的方式一般随机生成大数并进行质数测试直到确认两个数都是质数为止。
- 计算 [math]\displaystyle{ n = pq }[/math] 。
- 计算 [math]\displaystyle{ \lambda(n) = \operatorname{lcm}(\lambda(p), \lambda(q)) = \operatorname{lcm}(p-1, q-1) }[/math]
- 选择整数 [math]\displaystyle{ \alpha }[/math] ，要求满足 [math]\displaystyle{ 2 \lt \alpha \lt \lambda(n) }[/math] ，且与 [math]\displaystyle{ \lambda(n) }[/math] 互质。
- 由于后续会被公开，往往会选择一个二进制位1较少的较小值来提高效率。
- 计算满足 [math]\displaystyle{ \alpha\beta \equiv 1 \pmod{\lambda(n)} }[/math] 的 [math]\displaystyle{ \beta }[/math] 。
- 由于 [math]\displaystyle{ \alpha }[/math] 和 [math]\displaystyle{ \lambda(n) }[/math] 互质，可以直接通过扩展欧几里得算法得到。
密钥分发
将 [math]\displaystyle{ n, \alpha }[/math] 作为公钥通过可信信道进行分发，不要求是加密信道。同时 [math]\displaystyle{ \beta }[/math] 作为私钥被保密，不应该被分发。
这一后就能保证双方可以交接信息。
加密
发送信息 [math]\displaystyle{ M }[/math] 时，可能先通过某种随机的结构化填充，得到 [math]\displaystyle{ m }[/math] 。
计算 [math]\displaystyle{ c \equiv m^\alpha \pmod n }[/math] 。这里可以使用模算术版本的快速幂的算法计算。
- 存在一些数使得 [math]\displaystyle{ c=m }[/math] 但因为概率上很难取到，实践中可以忽略。
- 填充步骤是为了防止一些极特殊取值被推算出来，比如 [math]\displaystyle{ m }[/math] 较小时可能直接取到对应的幂，哪怕不知道模数，也可以直接开方出来。
解密
计算 [math]\displaystyle{ c^\beta \equiv m^{\alpha\beta} \equiv m \pmod n }[/math] ，即可得到被填充的信息。
按填充的方式反过来提取出原本部分，就得到了原信息 [math]\displaystyle{ M }[/math] 。