查看“︁RSA 算法”︁的源代码

[[分类:同余理论]]
[[分类:数论算法]]
[[分类:非对称加密算法]]
{{InfoBox
|name=RSA
|eng_name=RSA
|aliases=Rivest-Shamir-Adleman algorithm
}}
'''RSA'''算法指一种公钥加密系统，是根据 [[Euler 定理（同余理论）|Euler 定理]]的直接推论。
其安全性基于大质数分解的困难性，目前在作为密钥的大质数足够大的情况下，未有有效破解办法公布。

== 算法 ==

=== 原理 ===

对大整数 <math>\alpha, \beta, n</math> ，若有
* <math>n = pq</math>， 其中 <math>p,q</math> 是两个大质数；
* <math>\alpha \beta \equiv 1 \pmod{\varphi(n)}</math> 即 <math>\alpha \beta \equiv 1 \pmod{(p-1)(q-1)}</math> 。
则有
* 对任意整数 <math>m</math> ，有 <math>m^{\alpha\beta} \equiv m \pmod n</math> （根据 Euler 定理 <math>m^{\varphi(n)} \equiv 1 \pmod{n}</math> 及 <math>\alpha \beta \equiv 1 \pmod{\varphi(n)}</math> 易得）
* 对任意整数 <math>A</math> ，有 <math>0 \leq A < n</math> ，都存在唯一 <math>B</math> 满足 <math> 0 \leq B < n </math> 且 <math>B \equiv A^\alpha \pmod n</math> ，同时有 <math>B^\beta \equiv A^{\alpha\beta} \equiv A \pmod n</math> 。

同时，如果不知道 <math>p, q</math> ，通过 <math>n</math> 得知 <math>\varphi(n)</math> 需要通过质因数分解。这是一个已知的困难问题。

注：由于最初论文中使用的是 <math>\alpha \beta \equiv 1 \pmod{\varphi(n)}</math> ，以上也使用这一表述。实际上这是要计算一个 <math>k^{\alpha \beta} \equiv 1 \pmod{n}</math> 的 <math>\alpha\beta</math> 整体， Euler 定理保证 [[Euler 函数]] <math>\varphi(n)</math> 的倍数总是满足这一条件，但这是一个充分不必要条件，其充要条件是 [[Carmichael 函数]] <math>\lambda(n)</math> 的倍数。

=== 算法 ===

==== 密钥生成 ====

# 随机选取两个大质数 <math>p, q</math> ，为保证难以破解，应当尽量随机、两个数较大且差也较大。
#* 选取的方式一般随机生成大数并进行[[质数测试]]直到确认两个数都是质数为止。
# 计算 <math>n = pq</math> 。
# 计算 <math>\lambda(n) = \operatorname{lcm}(\lambda(p), \lambda(q)) = \operatorname{lcm}(p-1, q-1)</math>
# 选择整数 <math>\alpha</math> ，要求满足 <math>2 < \alpha < \lambda(n)</math> ，且与 <math>\lambda(n)</math> 互质。
#* 由于后续会被公开，往往会选择一个二进制位1较少的较小值来提高效率。
#计算满足 <math>\alpha\beta \equiv 1 \pmod{\lambda(n)}</math> 的 <math>\beta</math> 。
#* 由于 <math>\alpha</math> 和 <math>\lambda(n)</math> 互质，可以直接通过[[扩展欧几里得算法]]得到。

==== 密钥分发 ====

将 <math>n, \alpha</math> 作为公钥通过可信信道进行分发，不要求是加密信道。同时 <math>\beta</math> 作为私钥被保密，不应该被分发。

这一后就能保证双方可以交接信息。

==== 加密 ====

发送信息 <math>M</math> 时，可能先通过某种随机的结构化填充，得到 <math>m</math> 。

计算 <math>c \equiv m^\alpha \pmod n</math> 。这里可以使用模算术版本的[[快速幂]]的算法计算。

* 存在一些数使得 <math>c=m</math> 但因为概率上很难取到，实践中可以忽略。
* 填充步骤是为了防止一些极特殊取值被推算出来，比如 <math>m</math> 较小时可能直接取到对应的幂，哪怕不知道模数，也可以直接开方出来。

==== 解密 ====

计算 <math>c^\beta \equiv m^{\alpha\beta} \equiv m \pmod n</math> ，即可得到被填充的信息。

按填充的方式反过来提取出原本部分，就得到了原信息 <math>M</math> 。


{{同余理论}}