公钥加密算法——RSA算法
- 一、加密解密过程
- 二、算法原理
- 三、分析
- 附:视频链接
在实际应用场景中,由于效率较低,所以通常在通信建立连接时使用RSA算法,在传输过程中采用对称加密算法
一、加密解密过程
e为公钥,d为私钥(解密密钥)
通过合并可以看出,公钥和密钥是相对的,所以基于安全性,公钥密钥的选取就非常关键了
二、算法原理
1、公钥密钥的选取
mn为互质的两个数
举个例子
2、私钥求解
指数部分相同
目前来说,φ(n)\varphi(n)φ(n)唯一的通法就是质因数分解对于大数来说,非常困难
对于一个质数来ppp说,φ(p)=p−1\varphi(p)=p-1φ(p)=p−1
同时,φ(n)\varphi(n)φ(n)本身具有可拆分的特性
3、举个例子
k的选取要让d满足为整数
三、分析
对于破译者来说,难点
1、求大数n的互质数φ(n)\varphi(n)φ(n)需要质因数分解,数字越大,越难求出
2、即使知道公钥e,但是没有k值,d的结果(私钥)是不唯一的。由于每一次都是对密文的指数级运算,所以计算代价非常大。
附:视频链接
“公钥加密算法RSA”的工作原理