大家好，又见面了，我是你们的朋友全栈君。
背景
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加密后的密文就相当于裸奔了。
发布者：全栈程序员栈长，转载请注明出处：https://javaforall.cn/135707.html原文链接：https://javaforall.cn
