当前位置:网站首页>RSA非对称加密算法

RSA非对称加密算法

2020-11-08 18:11:39 HachikoT

RSA

1977年,三位数学家 Rivest、Shamir 和 Adleman 设计了一种算法,可以实现非对称加密。算法用他们三个人的名字命名,叫做 RSA 算法。
RSA算法的安全性是基于判断一个数是否为质数很简单,但是要对一个数进行质因子分解很困难这样一个事实。

RSA公私钥生成步骤

  1. 找两个大的质数\(P\)\(Q\),越大越好,计算\(P\)\(Q\)的乘积\(N\)

\[N=P\times Q \]

  1. 计算N的欧拉函数\(\varphi(N)\),令其值为\(M\)

\[M=\varphi(N)=(P-1)(Q-1) \]

  1. 找一个和\(M\)互质的整数\(E\)

\[gcd(E,M)=1 \]

  1. 计算整数\(E\)\(M\)的乘法逆元\(D\)

\[E\times D\equiv 1\,mod\,M \]

最终,将\((N,D)\)作为私钥,\((N,E)\)作为公钥

RSA加解密步骤

下面是用私钥加密,公钥解密的过程:

  • 加密

\[X^D\,mod\,N=Y \]

  • 解密

\[Y^E\,mod\,N=X \]

这里可以还原出加密的数据是因为

\[\begin{align} (X^D)^E &\equiv X^{D\times E}\,mod\,N\\ &\equiv X^{kM}X\,mod\,N\\ &\equiv X^{k\varphi(N)}X\,mod\,N\\ &\equiv X\,mod\,N\\ \end{align}\]

上面的推导中利用了欧拉定理:\(X^{\varphi(N)}\equiv 1\,mod\,N\),但这需要\(X\)\(N\)互质
\(X\)不与\(N\)互质时,只可能\(X=tP\)或者\(X=tQ\),这里推导\(X=tP\)的情况,这里有\(tP\)\(Q\)一定是互质的

\[\begin{align} (tP)^{DE} &\equiv (tP)^{k\varphi(P)\varphi(Q)}(tP)\,mod\,Q\\ &\equiv tP\,mod\,Q\\ \end{align}\]

推出

\[(tP)^{DE}=t'Q+tP \]

由于\(P|t'Q\)所以

\[(tP)^{DE}=t''PQ+tP \]

上式等价于

\[(tP)^{DE}\equiv tP\,mod\,N \]

\[(X)^{DE}\equiv X\,mod\,N \]

RSA安全性

RSA公私钥生成过程中可知,要从\(E\)推导出\(D\)或者相反,必须要知道数\(N\)的欧拉函数\(\varphi(N)=(P-1)(Q-1)\)
所以RSA算法的安全性就等价于对大整数\(N\)进行因式分解找出大质数\(P\)\(Q\),而目前质因子分解并没有多项式解法,所以可能保证一份公私钥对在一定时间内无法被破解

版权声明
本文为[HachikoT]所创,转载请带上原文链接,感谢
https://www.cnblogs.com/HachikoT/p/13945119.html