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的过程是如何的呢？如下:

1. 比如知道e和r，因为d是e关于r的模反元素；r是φ(N) 的值
2. 而φ(N)=(p-1)(q-1)，所以知道p和q我们就能得到d