RSA加密过程详解 | 公钥加密| 密码学| 信息安全
简介
RSA加密算法是一种非对称加密算法,所谓非对称,就是指该算法加密和解密使用不同的密钥,即使用加密密钥进行加密、解密密钥进行解密,分别称为公钥和私钥
在RAS算法中,公钥是公开的,而私钥是需要保密的。加密算法和解密算法也都是公开的。虽然私钥是由公钥决定的,但由于无法计算出大数n的欧拉函数phi(N),所以不能根据公钥计算出私钥,这就是RSA的安全性
使用方法:
- 乙方生成两把密钥(公钥和私钥)。公钥是公开的,任何人都可以获得,私钥则是保密的。
- 甲方获取乙方的公钥,然后用它对信息加密。
- 乙方得到加密后的信息,用私钥解密。
数论基础
欧拉函数
φ(n)表示小于n且与n互素的正整数
- 对于素数来说,φ(n) = n - 1
- 对于不是素数的数来说,可以将n进行质因数分解,再套用
φ
(
n
)
=
n
∗
(
1
−
1
p
1
)
(
1
−
1
p
2
)
.
.
.
.
.
.
(
1
−
1
p
c
)
φ(n)=n*(1-frac{1}{p_1})(1-frac{1}{p_2})......(1-frac{1}{p_c})
欧拉函数的原理这里就不介绍了,只需要知道素数的欧拉函数等于它-1即可
欧拉定理
aφ(n) % n = 1
乘法逆元
(a*b)%n=1,就称b是a在模n下的乘法逆元,求逆元的方法有两种,如果n是素数,那利用费马小定理可以知道逆元b = a n-1%n,如果不是素数,就只能用扩展欧几里得计算了,这里就不展开
RSA算法流程
密钥的产生
- 取两个保密的大素数p和q
- 计算n = p * q, n的欧拉函数值为φ(n) = (p - 1) * (q - 1)
- 任取一个整数 e, 1<e<n,且与φ(n)互素
- 计算e在模φ(n)意义下的乘法逆元
- 公钥为(e, n), 私钥为(d, n)
加密
密
文
=
明
文
e
m
o
d
N
密文=明文^emodN
密文=明文emodN
也就是
c
=
m
e
m
o
d
N
c = m^emodN
c=memodN,m为明文,c为密文
解密
明
文
=
密
文
d
m
o
d
N
明文 = 密文^{d}modN
明文=密文dmodN
也就是
m
=
c
d
m
o
d
N
m = c^dmodN
m=cdmodN