RSA 非对称加密算法


RSA 是 1977 年由三位数学家 Rivest Shamir 和 Adleman 设计的一种非对称加密算法,名称是三人名字的首字母。

RSA 算法非常可靠,密钥越长就越难破解。

其它加密算法,包括:ECDH、AES,及量子计算时代的 PQC DS、PQC KEM。

据已披露文献,目前被破解的最长 RSA 密钥是 232 个十进制位,也就是 768 个二进制位。

可这样认为,1024 位的 RSA 密钥基本安全,2048 位的密钥会更安全 (量子计算机除外)。

由于通过数学算法加密和解密 RSA, 效率会比较低; 因此, RSA 的主战场一般是加密比较小的数据。

如对大数据先进行对称加密, 再用 RSA 给对称加密的 KEY 进行加密 (或加密 Hash 值 ), 也就是数字签名。

素数 互素 同余


  • 素数又称质数

    指在一个大于 1 的自然数中, 除 1 和整数本身外, 不能被其他自然数整除的数。

  • 互素又称互质

    若 N 个整数的最大公因子为 1, 则称这 N 个整数互素。

  • 同余 模运算 (求余运算)

    模是 Mod 的音译, 和模运算紧密相关的一个概念就是同余。 数学上, 当两个整数除以同一个正整数, 若得相同余数, 则二整数同余。

  • 欧拉函数


    任意给定一个正整数 n, 在小于等于 n 的正整数之中, 有多少个与 n 构成互质关系? 计算这个值的方法就叫做欧拉函数,以 φ(n) 表示。

  • φ(8) = 4

    和 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) = 6

    和 7 互质的是 1 2 3 4 5 6 7。

    若 n 为质数, 则 φ(n) = n - 1。 因为质数与小于它的每一个数, 都构成互质关系。

    如 5 与 1 2 3 4 都构成互质关系。

  • φ(56) = φ(8) * φ(7) = 4 * 6 = 24

    若 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 的模反元素。

    等式转换


    等式转换

    根据 欧拉定理 , 由于 1^k ≡ 1, 等号左右两边都来个 k 次方。

    等式转换

    由于 1 * m ≡ m, 等号左右两边都乘以 m。

    等式转换

    根据模反元素, 因为 e*d 一定是 x 的倍数加 1。

    等式转换

    m 的 ed 次方为加密运算, 得到结果 c, c 模以 n 为解密运算, 得到结果 m。

    m 通过 n φ(n) e 还有 d 几个参数, 运算得到的结果,仍然是 m。

    注意: 当整数 e 和 φ(n) 互质, 一定有一个整数 d 是 e 相对于 φ(n) 的 模反元素

    如 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 Shell 测试

    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.
    >>> 12 ** 3 % 15
    3  #加密
    >>> 3 ** 19 % 15
    12 #解密
    >>> 7 ** 3 % 15
    13 #加密
    >>> 13 ** 19 % 15
    7  #解密
    >>>
    					

    以上为通过 数字 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。

    另请参阅:

    OpenSSL Shell 命令

    版权声明: 本文为独家原创稿件,版权归 乐数软件 ,未经许可不得转载。