生成公私钥过程
- 随机选择两个大的质数
p、q - 由质数
p和q相乘得到n， - 由欧拉函数求出
φ(n)， - 随机选择与
r互质的数e，通常选择65537 - 最后求出
e关于模数r的模反元素d，
此时得到的{n，e}为公钥，{n，d}为私钥。
数学知识
互质关系
-
定义
如果两个正整数，除了1以外，没有其他公因子，那么这两个数就是互质关系。
欧拉函数
-
定义
任意给定正整数
n， 在小于等于n的正整数之中，有多少个与n构成互质关系（比如，在1到8之中，有多少个数与8构成互质关系）？计算这个值的方法就叫做欧拉函数，以φ(n)表示。 -
公式
- 如果
n = 1，φ(1) = 1； - 如果
n为质数，φ(n) = n - 1； - 如果
n是a的k次幂， - 如果
m，n互质，则φ(mn) = φ(m) * φ(n)
- 如果
欧拉定理
-
定义
若两个正整数
n和m互质，则：
即m的φ(n)次方 整除n的余数是1，其中φ(n)表示在小于n的正整数中与n互质的个数。
费马小定理
-
定义
若
m是不能被质数p整除的数，则：
其实就是欧拉定理的特殊情况，由于p是质数，所以φ(p) = p-1。
模反元素
-
定义
如果两个正整数
e和r互质，那么一定可以找到整数d，使得e * d - 1被r整除，那么d就是e对于模数r的模反元素。
推导
由于
，所以
由于
，所以
由模反元素的定义知道
比较公式
与
当式1中的与
式2中的相等时，
式1就变形成：
将上面的式3进行拆分得到加解密的流程：
其中m为要加密的数据，{n，e}为公钥，{n，d}为私钥，c为加密后的数据。
