RSA算法原理

RSA是一种"非对称加密算法"

相关知识

互质关系

如果两个正整数除1以外没有其他公因子，我们就称这两个数互质(coprime)。

比如：15和32，没有公因子，所以它们是互质关系。这说明不是质数也可以构成互质关系。

a*b=c, a和b是c的因子

补充：

质数，指在大于1的自然数中，除了1和它本身以外不再有其他因数的自然数。

公因数(公约数)，它是一个能被若干个整数同时均整除的整数。如果一个整数同时是几个整数的约数，称这个整数为它们的“公约数”；公约数中最大的称为最大公约数。对任意的若干个正整数，1总是它们的公因数。

公因子，是一个数学概念，指的是能同时整除几个整数的整数，可以用辗转相除法算出。

加密的原理

公钥(E, N), E:指数, N:模数

公式:

假设公钥为(7, 33), 私钥为(3, 33), 私钥的指数是不公开的, 公私钥的模数会是相同的

假设数据源为:

C, A, O

将C, A, O转换成十进制为:

3, 1, 15

使用公钥的指数进行求幂:

, ,

2187 ,1 , 170859375

使用公,私钥的模数进行求余:

, ,

得到密文

9, 1, 27

解密的原理

私钥(D, N), D:指数, N:模数

公式:

收到的密文

9, 1, 27

使用私钥的指数进行求幂:

, ,

729, 1, 19683

使用私钥的模数求余:

, ,

得到原文:

3, 1, 15

公钥和私钥生成的原理

1. 选出两个质数
2. 质数相乘
3. 欧拉函数
4. 选出公钥E 质数;1<公钥<T;不是T的因子
5. 算私钥D