视频教程：https://www.bilibili.com/video/BV1XP4y1A7Ui

前置知识

  • 因数：a * b = c，a 和 b 就是 c 的因数
  • 质数：只能由 1 和数字本身相乘得到的数字
  • 余数：a % b = c，a 除以 b 的余数是 c
  • 互质：两个数的最大公约数是 1
  • 公约数：两个数的公约数是能同时整除这两个数的数

加密和解密过程

假设公钥为（7, 33），私钥为（3, 33）

  1. 加密过程
    1. 明文为 3，加密后的密文为 3^7 % 33 = 9
    2. 明文为 1，加密后的密文为 1^7 % 33 = 1
    3. 明文为 15，加密后的密文为 15^7 % 33 = 27
  2. 解密过程
    1. 密文为 9，解密后的明文为 9^3 % 33 = 3
    2. 密文为 1，解密后的明文为 1^3 % 33 = 1
    3. 密文为 27，解密后的明文为 27^3 % 33 = 15

公钥加密的密文只能由私钥解密，私钥加密的密文只能由公钥解密

公式

  • 公钥：(E, N)
  • 私钥：(D, N)
  • 加密：密文 = 明文^E % N
  • 解密：明文 = 密文^D % N

公钥和私钥的制作过程

流程

  1. 选择两个质数 p 和 q
  2. 计算 N = p * q
  3. 计算 T = (p - 1) * (q - 1)
  4. 选择一个 E，1 < E < T，且 E 和 T 互质
  5. 计算 D，使得 D * E % T = 1

T 是欧拉函数，表示小于 N 的数中与 N 互质的数的个数

举例

  1. p = 3, q = 11
  2. N = 3 * 11 = 33
  3. T = (3 - 1) * (11 - 1) = 20
  4. E = 3
  5. D = 7