数学是一种很奇妙的东西

质数：只能被1和自身整除的数

互质数：两个数的公约数只有1，这两个为互质数

欧拉函数：OL(n)=x，x：从0到n的范围内，和n互质的数 的 个数，也就是从0到n的范围内，和n的公约数只有1的数的个数

RSA加密原理

P：质数1 Q：质数2 N：最小公倍数 OL(N)=X -> X：小于N & 和N互质 的数的个数

E：公钥 D：私钥 M：明文 C：密文

  1. 找出P、Q

    比如：P = 3 Q=11

  2. 找公共模数（求最小公倍数）

    N = P * Q = 3 * 11 = 33 N=33

  3. 欧拉函数

    OL(N) = (P - 1)(Q - 1)

    OL(33) = (3 - 1)(11 - 1) = 20

  4. 计算公钥E

    1 < E < OL(N) = 1 < (1,20) < 20

    E的取值范围{3，5，7，11，13，17，19}

    E必须是整数，E必须和**OL(N)**互质

    假设E=3，3是整数，3和20互质

  5. 计算私钥D

    E * D % OL(N) = 1 = 3 * D % 20 = 1，得出D=7

到这我们就计算出公钥和密钥了，现在我们开始用公钥加密，然后用私钥解密

加密解密

  1. 公钥加密

    比如我们加密数字2：M=2

    C = ME mod N; 即 密文 = 明文公钥 % 最小公倍数

    C = 23 % 33 = 8 C = 8

    明文2经过RSA加密后变成密文8

  2. 私钥解密

    M = Cd mod N; 即 明文 = 密文私钥 % 最小公倍数

    M = 87 % 33 = 2 M = 2

    密文8经过RSA解密后变成明文2