抱歉,您的浏览器无法访问本站

本页面需要浏览器支持(启用)JavaScript


了解详情 >

数学是一种很奇妙的东西

质数:只能被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

哔哔