RSA加密算法详解
1、寻找两个不相同的质数
-
随意选择两个大的质数p和q，p不等于q，计算N=p*q;
-
什么是质数?我想可能会有一部分人已经忘记了，定义如下：
除了1和该数自身外，无法被其他自然数整除的数（也可定义为只有1该数本身两个正因数)的数）。
2、根据欧拉函数获取r
-
r = φ(N) = φ(p)φ(q) = (p-1)(q-1) -
欧拉函数的定义：
欧拉函数 φ(n)是小于或等于n的正整数中与n互质的数的数目。
- 互质的定义：
如果两个或两个以上的整数的最大公约数是 1，则称它们为互质
例如：φ(8) = 4，因为1,3,5,7均和8互质。
3、选择一个小于r并与r互质的整数e
-
选择一个小于r并与r互质的整数e，求得e关于r的模反元素，命名为d（***ed = 1(mod r)***模反元素存在，当且仅当e与r互质），e我们通常取65537。
-
模反元素：
如果两个正整数a和n互质，那么一定可以找到整数b，使得 ab-1 被n整除，或者说ab被n除的余数是1。
比如3和5互质，3关于5的模反元素就可能是2，因为3*2-1=5可以被5整除。所以很明显模反元素不止一个，2加减5的整数倍都是3关于5的模反元素*{…-3, 2,7,12…}* 放在公式里就是3*2 = 1 (mod 5)
4、销毁p和q
- 此时我们的*(N , e)是公钥，(N, d)为私钥，爱丽丝会把公钥(N, e)传给鲍勃，然后将(N, d)*自己藏起来。一对公钥和私钥就产生了
备注
- p,q：我们随机挑选的两个大质数
- N：是由两个大质数p和q相乘得到的。N = p * q
- r：由欧拉函数得到的N的值，r = φ(N) = φ§φ(q) = (p-1)(q-1)
- e：随机选择和和r互质的数字，实际中通常选择65537
- d： d是以欧拉定理为基础求得的e关于r的模反元素，ed = 1 (mod r)
N和e我们都会公开使用，最为重要的就是私钥中的d，d一旦泄露，加密也就失去了意义。那么得到d的过程是如何的呢？如下:
- 比如知道e和r，因为d是e关于r的模反元素；r是φ(N) 的值
- 而φ(N)=(p-1)(q-1)，所以知道p和q我们就能得到d