RSA 加密算法原理学习笔记-2

RSA算法原理（二） - 阮一峰的网络日志

密钥的生成

随机选择两个不相等的质数（上面互质关系结论的第二点，所以这两个数互质）。这两个数越大越难破解，比如 61、53。
计算两数乘积：n = 61 * 53 = 3233。n 便是密钥的长度，n 的二进制 110010100001 长度为 12，因此密钥长度为 12。
- 实际应用中，第 1 步选取的两个质数较大，这里的 n 一般为 1024 位，重要场合则为 2048 位。
计算 n 的欧拉函数 φ(n)：φ(n) = φ(p)φ(q) = (p-1)(q-1)，所以已知密钥的两个质数因数可以快速计算出 φ(n) = 60 * 52 = 3120。
随机选择一个整数 e 满足：1 < e < φ(n)，且与 φ(n) 互质的数。假设选择 17，实际应用中常选择 65537（因为）。
此时，n 和 e 便是我们的公钥内容。
计算 e 的模反元素 d，注意，这里的环境是 φ(n)，不使用欧拉定理求模逆元：
等价于：
所以实际上就是求解二元一次方程：，其中 e 和 φ(n) 是已知数。
- 这个方程仅有一个已知等式，有无数个解，使用扩展欧几里得算法（辗转相除法）可以解出一个特殊的解。
此时，n 和 d 便是我们的私钥内容。采用 ASN.1 格式表达将 n 和 e 封装成公钥，n 和 d 封装成私钥。

RSA 算法的可靠性

公钥是我们对外的公开的，私钥是我们隐藏的。推算出私钥便会使数据丧失安全性（为什么？见下一节加解密过程）。
那么如果要用公钥推出私钥有多难？
已知公钥（n，e），推 d：

。只有知道 e 和 φ(n)，才能算出 d。
。只有知道 p 和 q，才能算出 φ(n)。
。只有将 n 因数分解为两个质数，才能算出 p 和 q。

结论：如能将 n 因式分解为两个质数，则可破解出私钥。
但是要将一个很大的数（1024 位（最小值是 2^1023^+1）、2048 位）因式分解是一件很难的事。

加解密

加密使用公钥（n，e）
假设有数据 m（m 为整数，字符串可取其 ascii 值或 unicode 值），
且 m 必须小于 n（这是一个重要的条件，大于 n 的情况见本节末尾）：

c 便是我们得到的密文。
假设公钥（3233，17），数据 m 为 65，计算 c：(65^17^) mod 3233 = 2790，所以密文 c 为 2790。（快速幂取模算法 - 王陸 - 博客园）
- 已知 n，c，e 了，推不出 m：这就是破解密文了，m^17^=2790 (mod 3233) 即 (m^17^ + 2790) / 3233 = k，可以看到 m，k 是有无数种可能的。每个二元一次方程都有无数对方程的解。
解密使用私钥（n，d）
解密算法（该算法证明在后面）：

此时私钥是（3233，2753），代入得：2790^2753^ = m (mod 3233)，求得 m = 65。

那么如果数据 m 大于 n 的情况下，选择将数据分块单独加密，或者先选择一种”对称性加密算法”加密数据（比如 3DES 或 AES），再用 RSA 加密这种对称加密的密钥。

私钥解密的证明

证明解密算法：

加密算法使用：
即：（不明白的可以看上面同余定理中的变式）
替换解密算法中的 c 得：
等同于求证： $①$

需要回忆一下二项式定理，对原式进行拆分：二项式定理_持剑的龙套的博客-CSDN博客_二项式定理。
首先对左边进行拆分：$(m^e - kn)^d = m^{ed} + m^{e(d-1)}(kn)^1 + m^{e(d-2)}(kn)^2 + \dots + m^e(kn)^{d-1} + (kn)^d $只有第一个不包含，后面均包含，相当于：$ (m^e - kn)^d = m^{ed} + zn $，代表那些复杂的式子，是一个整数，因此都是可以被整除的，求$ (m^e - kn)^d \equiv m \pmod n $相当于求证$ m^{ed} ≡ m \pmod n$。
这种幂的求余数需要记一下，方便应用。

下面分两种情况证明：
（1）m 与 n 互质

（这个 h 就是我们上面经常用到的 k 了）
代入式子①得：
原题可变成求证： $②$

m 与 n 互质，满足欧拉定理：
即式②

依旧是展开式的应用。
因为 m 与 n 互质，满足欧拉定理，可改写成：，
而它的任意正整数 h 次方展开式为，只有最后一个不包含 n。
可以看出除以 n 余数恒为 1，即，也就是说，任意正整数次方不影响余数。

证明式②成立，即式①成立。

（2）m 与 n 不是互质关系
m 与 n 不是互质关系，且，p、q 为不等的两个质数，
或

因为 n 是两个互质的质数（等价于不等两个的质数）p、q 之积，所以 n 的因子除 1 和 n 外只有 p、q。
又因为 m 与 n 不是互质关系且 m < n，说明 m 与 n 有公因数，所以 m 一定是 p 或 q 的倍数，而且不会是 n。

以为例，则此时 k 与 q 必然互质，则 m 与 q 互质

因为 m = kp，n = pq，而算法中已要求 m < n，所以 k < q。
又因为 q 为质数， k 不等于 q，所以 k 与 q 互质。
因此，由均与 q 互质的 k、p 组成的 m 明显也与 q 互质（都没有公因数）。

m、q 互质，满足欧拉定理：
进一步得到：，即

这里与 m 和 n 互质的证明那里相似。

又，即：
改写成等式：
此时，t 一定能被 p 整除

如果将等式左右两边同时除以 p，左边可以得到整数。右边 kp/p 得到整数，而剩余 tq/p 也一定是整数。因为 q 不是 p 的倍数，所以即 t/p 为整数。

设，则原式变为：
$，$
原式变为：
即，证明式①成立。