RSA Asymmetric Encryption Algorithm
RSA 是 1977 年由三位数学家 Rivest Shamir 和 Adleman 设计的一种非对称加密算法，名称是三人名字的首字母。
RSA 算法非常可靠，密钥越长就越难破解。
其它加密算法，包括：ECDH、AES，及量子计算时代的 PQC DS、PQC KEM。
据已披露文献，目前被破解的最长 RSA 密钥是 232 个十进制位，也就是 768 个二进制位。
可这样认为，1024 位的 RSA 密钥基本安全，2048 位的密钥会更安全 (量子计算机除外)。
由于通过数学算法加密和解密 RSA， 效率会比较低； therefore, RSA 的主战场一般是加密比较小的数据。
如对大数据先进行对称加密， 再用 RSA 给对称加密的 KEY 进行加密 (或加密 Hash Value )， 也就是数字签名。
Prime Number, Mutual Prime and Congruence
指在一个大于 1 的自然数中， 除 1 和整数本身外， 不能被其他自然数整除的数。
若 N 个整数的最大公因子为 1， 则称这 N 个整数互素。
模是 Mod 的音译， 和模运算紧密相关的一个概念就是同余。 数学上， 当两个整数除以同一个正整数， 若得相同余数， 则二整数同余。
任意给定一个正整数 n， 在小于等于 n 的正整数之中， 有多少个与 n 构成互质关系？ 计算这个值的方法就叫做欧拉函数，以 φ(n) 表示。
和 8 互质的是 1 2 3 4 5 6 7 8。
若 n 是质数的某一个次方， 即 n = p^k (p 为质数，k 为大于等于 1 的整数)， 则 φ(n) = φ(p^k) = p^k - p^(k - 1)。
如 φ(8) = φ(2^3) =2^3 - 2^2 = 8 - 4 = 4。
和 7 互质的是 1 2 3 4 5 6 7。
若 n 为质数， 则 φ(n) = n - 1。 因为质数与小于它的每一个数， 都构成互质关系。
如 5 与 1 2 3 4 都构成互质关系。
若 n 可分解成两个互质的整数之积， 即 n = p * k， 则 φ(n) = φ(p * k) = φ(p1) * φ(p2)。
若两个正整数 m 和 n 互质， 那么 m 的 φ(n) 次方减去 1， 可以被 n 整除。
如 8 和 7 互质， 那么 8 的 φ(7) 次方减去 1， 可以被 8 整除。 即 (8 φ(7) - 1) / 7 = (262144 - 1) / 7 = 37449。
欧拉定理的特殊情况， 若两个正整数 m 和 n 互质， 且 n 为质数， 那么 φ(n) 结果就是 n - 1。
如 8 和 7 互质， 且 7 为质数， 那么 φ(7) ＝ 7 - 1。
若两个正整数 e 和 x 互质， 那么一定可以找到某个整数 d， 使得 ed - 1 可被 x 整除 (或者说 ed 被 x 除的余数是 1)， 那么 d 就是 e 相对于 x 的模反元素。
如 8 和 7 互质， 8 * 5 - 1 可被 7 整除， 那么 5 就是 8 相对于 7 的模反元素。
根据 Euler Theorem ， 由于 1^k ≡ 1， 等号左右两边都来个 k 次方。
由于 1 * m ≡ m， 等号左右两边都乘以 m。
根据模反元素， 因为 e*d 一定是 x 的倍数加 1。
m 的 ed 次方为加密运算， 得到结果 c， c 模以 n 为解密运算， 得到结果 m。
m 通过 n φ(n) e 还有 d 几个参数， 运算得到的结果，仍然是 m。
Note: 当整数 e 和 φ(n) 互质， 一定有一个整数 d 是 e 相对于 φ(n) 的 Modular Element .
如 m 取值为 4， n 取值为 15 (m 和 n 无需互质，但 m 必须小于 n)， 则 φ(n) = 8 (如 1 2 4 7 8 11 13 14)。 若 e 取值为 3， 则 d 可以为 11 19 27 ... (模反元素明显不止一个，就是解二元一次方程)。
若按这种算法进行加密 解密， 加密的结果会非常大， 明文数据将非常小 (虽然 RSA 用于加密的数据也很小， 但没这么大悬殊)。 真正的 RSA 要更加强大， 那么 RSA 是怎么演变来的呢？ 早期很多数学家也停留在了这一步， 直到 1967 年出现迪菲赫尔曼密钥交换打破了僵局。
随机数 15 仅服务器拥有， 3^15 mod 17 = 6， 然后把公布 6 并发送给客户端。 拿到客户端的 12， 然后 12^15 mod 17 = 10 (10 就是交换得到的密钥)。
随机数 13 仅客户端拥有， 客户端用 3^13 mod 17 = 12， 然后公布 12 并发送给服务器。 拿到服务器的 6， 然后 6^13 mod 17 = 10 (10 就是交换得到的密钥)。
只能拿到 6 和 12， 因为没有私钥 13 15， 所以没法得到结果 10。
6^13 mod 17 和 12^15 mod 17 的结果都为 10， 这就是迪菲赫尔曼密钥交换的核心规律。
如 3^3 mod 17 = 10 再 10^2 mod 17 和 3^2 mod 17 = 9 再 9^3 mod 17 的结果都是 15。
m^e % n = c 是加密，c^d % n = m 是解密，m 是原始数据，c 是密文，公钥是 n 和 e，私钥是 n 和 d，所以只有 n 和 e 是公开的。
加密时要知道 φ(n) 的值， 最简单方式是 2 质数之积， 别人想破解 RSA 也要知道 φ(n) 值， 就要对 n 进行因数分解。
若不想 m 被破解， n 的值就要非常大， 长度可为 1024 或 2048 位二进制。
Python 3.6.8 (tags/v3.6.8:3c6b436a57, Dec 24 2018, 00:16:47) [MSC v.1916 64 bit (AMD64)] on win32 Type "copyright", "credits" or "license()" for more information. >>> 7 ** 3 % 15 13 # 加密 >>> 13 ** 19 % 15 7 # 解密 >>> 5 ** 23 % 66 59 # 加密 >>> 59 ** 7 % 66 5 # 解密 >>>
以上为通过 Digital IDE Shell 选项卡获得的结果。
其中， n = 15 (随机数)， 则 φ(n) = 8 (如 1 2 4 7 8 11 13 14)， m = 12 (随机数，必须比 n 小)， e = 3 必须与 φ(n) 互质。
d = 19 (也可为 3 11 等)，必须与 φ(n) 互质，且 (ed - 1) / φ(n) = 整数。
某些特殊 n e d 值的组合， 一系列每 m 值 == 每加密 c 值 == 每解密 m 值。 由于每次加密 中间值 解密始终保持不变， 没有加密 (相当于明文)。
有时 e == d， 也能完美加密解密； e d 值还可大于 n。
See also:
Copyright Notice: This article is exclusive original manuscripts, copyrighted by Happy Digits Software , shall not be reproduced without permission.
Table of contents
Previous topic
Next topic
Quick search
