AES算法是一种对称加密算法，必须将密钥传递给对方才能解密，如何保证密钥的安全性成为关键问题。 1977年，三位数学家Rivest、Shamir、Adleman设计了一种非对称加密，也就是实现本文讨论的RSA算法的算法。 要使用非对称加密算法，必须生成公钥和私钥，用公钥加密，并用私钥解密。
互惠关系
首先让我们回顾一下素数的定义。 “素数”(prime number )也称为素数，有无限个。 大于1的自然数不能被1和除此以外的自然数整除。 换言之，其数量不再具有1和其自身以外的因数。 否则我们称之为合数。
如果两个正整数除了1以外没有其他公因子，我们把这两个数称为相互质量的关系。 在互质关系中，两个数不必是素数，合数也可以与一个素数构成互质关系。
欧拉函数
对于正整数n，欧拉函数是小于n的正整数中，与n相互独立的整数，且由表示。 例如(8)=4，是因为1 )3)5) 7和8是互质的。 欧拉函数可以表示为如下
此处，p1、p2 …… pn为x的所有质因数，x为非0的整数。 且(1)=1。 每个质因数只有一个。 例如12=2 * 2 * 3那样
(12 )=12*(1-1/2) )1-1/3)=4
n是素数p的k次幂，p的倍数以外的数全部与n相互素时
如果m、n互为质
n为奇数时
n为素数时
模式反转元素
如果两个正整数a和n相互为素数，则一定可以找到整数b，使ab - 1能被n整除，或ab能被n整除的馀数为1。 此时，b被称为a的“模反元素”。 您将看到以下内容：
是ab1(modn )
例如，在3和11相互为素数的情况下，第三模式反转元素为4。 因为(3 4 )- 1可以被11整除。 很明显，模式反转元素有多个，411的整数倍都是3的模式反转元素{ .-18、-7、- 4、15、26、 }。 也就是说，如果b是a的模式反转元素，则b k n都是a的模式反转元素。
欧拉定理
欧拉定理是关于同余的性质。 欧拉定理在n，a为正整数，且n，a相互为素的情况下，表示了以下情况
a^(n ) )1) modn ) )
证明过程很复杂，所以在这里跳过。
假设正整数a和素数p互为素，由于(p )=p-1，欧拉定理可写为
a^(p-1 )1) modp ) )
RSA公钥和私钥的生成
要生成密钥，请执行以下操作：
首先选择两个素数p和q。 而且越大越好。
计算n=pq时，n的二进制位数就是密钥的位数。
计算n的欧拉函数
(n )=) p )) q ) ) p-1 ) q-1 ) ) ) ) ) ) ) )。
随机选择整数e。 条件是1
计算e相对于(n )的模逆元素d
ed1(mod(n ) )
上式与以下一元二次方程等价，d和k有无限的组合方式，选择一个d值即可
EDk(n )=1
将n和e封装为公钥，将n和d封装为私钥
RSA加密和解密
使用公开密钥(n，e )的加密过程，可以表示为如下式，实际上是基于明文m的
计算密文c的过程。 m必须是整数，且字符串可以是ascii或unicode值，m必须小于n。
是m^ec(modn )
使用私钥(n，d )解密的过程可以由以下公式表示，实际上是根据密文c计算明文m的过程。 这里的证明很复杂，感兴趣的朋友可以自己看看。
c^dm(modn ) )。
RSA加密过程示例
首先生成密钥：
设p=61、q=53
计算出n=61 * 53=3233
计算n的欧拉函数(3233 )=60 * 52=3120
随机选择整数e=17
计算e相对于(n )的模逆元素d=2753
用公开密钥进行加密，假设明文m=65，表示大写字母a，根据公式计算密文2790。
65172790 (模3233 )
使用机密密钥进行解密，将密文设为2790，根据公式计算出明文为65，表示大写字母a。
790 ^ 275365 (模3233 )
分享学习笔记和技术总结。 内容涉及Java高级化、体系结构设计、尖端技术、算法和数据结构、数据库、中间件等多个领域，敬请关注。 本文从微信公众号“后端开发那么一点小事”开始。