RSA加密算法计算原理

生成公私钥

取两个不同的足够大的质数,p,q,算的乘积为N=p*q

1
2
3
4
#我们取比较小的数字容易计算
p=13
q=17
N=p*q=221

取得r=(p-1)(q-1)
选择一个小于r的整数e,并且re互质
e关于r的模逆元d,ed≡1 (mod r)

1
2
3
4
5
6
7
8
9
10
r=(13-1)(17-1)=192
#取一个小质数便于计算
e=5
#找出符合规则的d值
5d≡1(mod 192)
(5d-1)mod 192=0
5d-1=192*n
d=(192*n+1)/5
#当n=2时,d为正整数,符合条件
d=(192*2+1)/5=77

然后将pq的值销毁,(N,e)即为公钥,(N,d)为私钥

1
2
3
4
#公钥
(221,5)
#私钥
(221,77)

加密消息

对消息原文进行处理,例如将每一个字符转成这个字的Unicode码,然后将这些数字一起组成一个数字n,我们将n使用公钥进行加密操作得到密文c,公式为c≡n^e(mod N)

1
2
3
4
#假如我们的明文是数字123
c≡123^5(mod 221)
#得到密文为106
c=106

解密消息

得到密文c以后,我们可以使用私钥进行解密,公式为n≡c^d(mod N)

1
2
n=106^77(mod 221)
n=123

后记

1.在数学意义上,这里生成的公私钥是对等的,并没有强制哪一方是公钥哪一方是私钥,实际应用里,例如在openssl里生成的的密钥对,私钥的pem里其实是包含了公私钥的信息,而公钥文件里只有公钥本身。
2.由于目前计算机尚且不能在有限时间内对很大的数字进行因数分解,这也保证了RSA算法的可靠性,目前推荐使用RSA2048位及以上进行加解密。
3.RSA的加密速度相对于对称加密算法来说很慢,所以我们一般都是使用对称加密如AES256等工业加密对消息进行加密后,然后使用RSA对对称加密的秘钥进行加密传输。