大家好,又见面了,我是你们的朋友全栈君。
背景
RSA加密算法是公钥密码最著名的算法之一,是由MIT三位(Ron Rivest, Adi Shamir, Len Adleman)提出的,也就以三位的名字首字母命名。
该算法的理论基础是“大数分解和素数检测“,如果说有一天,大数分解和素数检测的数学理论被证明可以简单解决,那么RSA算法的加密将没有任何意义。有提出说量子计算机的出现可以大大提高RSA的破解效率。下面我们将简单学习RSA加密算法的基本知识。
算法描述
RSA算法使用平方运算,明文以分组为单位进行加密,每个分组的二进制值小于n,即分组的大小必须小于等于log2(n)+1位(通常n的大小为1024位二进制数或309为十进制数,即n<2^1024)。对明文分组M和密文分组C,加密解密过程如下:
加密:
解密:
收发双方均已知n,发送方已知e,只有接收方已知d,因此RSA加密算法的公钥PU为{n,e},私钥PR为{n,d}。
d,e,n应满足如下条件:
- 可以找到e,d,n,使得对所有M< n,有;
- 对所有M< n,计算M^e和C^e是比较容易的;
- 由e,n预测d是不可行的。
算法理解
该算法使用上非常简单,将明文分组M进行加密操作得到密文分组C,接收方再对密文分组C进行解密操作得到明文分组M,加密过程也很好理解,就是对明文分组C取指数e后模n。解密过程为对密文分组M取指数d后模n。但是为什么可以这么做呢?如何得到合适的e,d,n呢?
这里面有一个非常重要的等式:
当e和d互为模的乘法逆时,上述关系式成立。
其中为欧拉函数。也就是说当n=ed时,算法成立。
在《公钥密码 之 素数,费马定理与欧拉定理》中我们提到,对于素数p和q,有。
e和d应满足如下关系:
即e和d互为模的乘法逆。
根据模算数的性质,仅当d(和e)与互素时,d和e是模的乘法逆元。因为d和互素,则一定存在一个整数是d的模反元素。同理对于e也是如此。因此可知d和e互为模反元素,则得到上式等价于
这里面涉及到了模反元素,模反函数的定义为:
如果两个正整数a和n互素,那么一定可以找到整数b,使得 ab-1 被n整除,或者说ab被n除的余数是1。
其中b叫做a的模反元素。
RSA加密算法密钥生成过程:
这里面模反元素d比较难计算,可以利用扩展的欧几里得算法计算。大多数情况下我们的素数pq会选的很大,这样得到的n也会很大,可以增加加密算法的安全性。但是为什么呢?
RSA加密算法的安全性
RSA加密算法中一共涉及到p,q,n,,e,d六个数字,其中{n,e}为公钥,也就是说n,e是暴露的,那么能否通过n,e来得到密钥{n,d}呢?其中关键就是得到d。
我们来看如何得到d:
1。
其中e是已知的,那么关键就是如何得到。
2。
p,q成为得到的关键,而pq可以从n中得到,并且n是已知的。
3。n=pq,那么对n进行因式分解即可。
到这一步你就知道为什么要使得n很大了吧!也就解释了在一开始提到的该算法的理论基础是“大数分解和素数检测“。如果大数分解被证明是可以很快计算的,那么RSA加密后的密文就相当于裸奔了。
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/135707.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...