搞清楚这个算法之前先认识几个量
EDN
公钥（E，N）：公开
私钥（D，N）
秘钥对（E，D，N）
什么是RSA算法
常见的秘钥加密算法分为对称加密算法和非对称加密算法。对称加密算法是指加密和解密使用同一个秘钥。非对称加密算法是指加密和解密使用不同的两个秘钥，公钥和私钥。
RSA是一种非对称加密算法。
RSA加密
密文=明文^E mod N
就是明文的E次方取余除以N求余数的过程。（E，N）这一对是加密秘钥，也就是公钥，只要知道公钥，任何人都可以对明文进行加密。当然E和N是经过严格的计算得出，计算方法在下面。
RSA解密
明文=密文^D mod N
解密的步骤和加密一样。（D，N）就是私钥，知道私钥就可以将密文解密。
生成秘钥对即公钥和私钥
随机找两个质数PQ，数越大越安全
假设P = 7，Q = 17 计算乘积 n = P*Q = 119，119的二进制：1110111，即该加密算法为7位，位数越高，安全系数越高。
计算n的欧拉函数 φ(n)
φ(n) 表示在小于等于 n 的正整数之中，与 n 构成互质关系的数的个数。例如：在 1 到 8 之中，与 8 形成互质关系的是1、3、5、7，所以 φ(n) = 4。
如果 n = P * Q，P 与 Q 均为质数，则 φ(n) = φ(P * Q)= φ(P - 1)φ(Q - 1) = (P - 1)(Q - 1) 。
本例中 φ(n) = 7 * 17= 119，这里记为 m， m = φ(n) = 96
随机选一个数e，要求在1到m之间，并且与M互为质数
选择e = 5
有一个整数 d，可以使得 e*d 除以 m 的余数为 1。
计算公式：(e * d ) % m = 1
5 * 77 % 96 = 1
由此可知：d = 77
由上述计算可知：E = 5 ；D = 77；N = 119
结合开头的概念：
公钥【5,119】 私钥【77,119】秘钥对【5,77,119】
取一个明文m = 19 (m<n)。注意要加解密的文不能超过n。
加密：
c = m^E mod n = 66 mod 119
解密：
c = m^D mod n = 16 mod 119
————————————————
原文链接：https://blog.csdn.net/hujinlong6930/article/details/102490442
网友评论