RSA加密算法简介[通俗易懂]

全栈程序员-用户IM • 2022年5月3日下午8:20 • 未分类

大家好，又见面了，我是你们的朋友全栈君。

背景

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进行因式分解即可。