RSA | AutoSecure

RSA

RSA 是一种公钥密码算法，它的名字是由它的三位开发者，即 RonRivest、Adi Shamir 和 Leonard Adleman 的姓氏的首字母组成的。

RSA 加密

在 RSA 中，明文、密钥和密文都是数字。RSA 的加密过程可以用下列公式来表达。

也就是说，RSA 的密文是对代表明文的数字的 E 次方求 mod N 的结果。换句话说，就是将明文和自己做五次乘法，然后将其结果除以 N 求余数，这个余数就是密文。

RSA 的加密是求明文的 E 次方 mod N，因此只要知道 E 和 N 这两个数，任何人都可以完成加密的运算。所以说，E 和 N 是 RSA 加密的密钥，也就是说，E 和 N 的组合就是公钥。

E 和 N 这两个数并不是密钥对（公钥和私钥的密钥对）。E 和 N 两个数才组成了一个公钥，因此我们一般会写成“公钥是（E，N）” 或者“公钥是{E，N}” 这样的形式，将 E 和 N 用括号括起来。

RSA 解密

RSA 的解密和加密类似。

也就是说，对表示密文的数字 D 次方求 mod N 就可以得到明文。换句话说，将密文和自己做D次乘法，再对其结果除以 N 求余数，就可以得到明文。

这里所使用的数字 N 和加密时使用的数字 N 是相同的。数 D 和数 N 组合起来就是 RSA 的解密密钥，因此 D 和 N 的组合就是私钥。只有知道 D 和 N 两个数的人才能够完成解密的运算。

当然，D 也并不是随便什么数都可以的，作为解密密钥的 D，和数字 E 有着相当紧密的联系。否则，用 E 加密的结果可以用 D 来解密这样的机制是无法实现的，整理入下表。

生成密钥对

由于 E 和 N 是公钥，D 和 N 是私钥，因此求 E、D 和 N 这三个数就是生成密钥对。RSA 密钥对的生成步骤如下。

(1) 求 N （模数）
(2) 求 L （是仅在生成密钥对的过程中使用的数）
(3) 求 E
(4) 求 D

(1) 求 N
首先准备两个很大的质数。

这两个很大的质数为 p 和 q。

p 和 q 太小的话，密码会变得容易破译，但太大的话计算时间又会变得很长。例如，假设 p 和 q 的大小都是 512 比特，相当于 155 位的十进制数字。

要求出这样大的质数，需要通过伪随机数生成器生成一个 512 比特大小的数，再判断这个数是不是质数。如果伪随机数生成器生成的数不是质数，就需要用伪随机数生成器重新生成另外一个数。

判断一个数是不是质数并不是看它能不能分解质因数，而是通过数学上的判断方法来完成。

准备好两个很大的质数之后，我们将这两个数相乘，其结果就是数 N。也就是说，数 N 可以用下列公式来表达。

(2) 求 L
L 这个数在 RSA 的加密和解密过程中都不出现，它只出现在生成密钥对的过程中.

L 是 p - 1 和 q - 1 的最小公倍数（least common multiple, 1cm）。如果用 lcm(X,Y) 来表示”X 和 Y 的最小公倍数”，则 L 可以写成下列形式。

(3) 求 E
E 是一个比 1 大、比 L 小的数。此外，£ 和 L 的最大公约数（greatest common divisor，gcd）必须为 1。如果用 gcd(X,Y)来表示 X 和 Y 的最大公约数，则 E 和 L 之间存在下列关系。

要找出满足 gcd(E,L)=1 的数，还是要使用伪随机数生成器。通过伪随机数生成器在 1 < E < L 的范围内生成 E 的候选数，然后再判断其是否满足 gcd(E，L)=1 这个条件。求最大公约数可以使用欧几里得的辗转相除法。

简单来说，之所以要加上 E 和 L 的最大公约数为 1 这个条件，是为了保证一定存在解密时需要使用的数 D。

(4) 求 D
数 D 是由数 E 计算得到的。D、E 和 L 之间必须具备下列关系。

只要数 D 满足上述条件，则通过 E 和 N 进行加密的密文，就可以通过 D 和 N 进行解密。简单来说，(E x D) mod L = 1 保证了对密文进行解密时能够得到原来的明文。

上面的内容中出现了很多符号和公式，我们先来整理一下

模数

这里的模数指的就是上文中提到的 N，也就是 p 和 q 的乘积，模数越大安全性越高，目前推荐使用2048位或更长的模数以确保安全性。

密钥格式

PKCS#1：主要用于RSA算法的公钥和私钥，直接包含RSA参数，结构更简单。
PKCS#8： 更通用，支持多种算法（如RSA、DSA、EC等），结构更灵活，可以包含额外信息。

密钥显示/明文/密文格式

十六进制： 以十六进制数值显示。
Base64： Base64是一种将二进制数据转换为文本的编码方法，常用于网络传输。
PKCS#1/PKCS#8： 基于密钥格式的选择。
文本： 文本格式，即 UTF-8 编码，人类可直接阅读的纯文本数据表示方式。