Wiki - RSA加密演算法 Wiki - 欧拉函数 Wiki - 模反元素 ASN.1 格式标准 RSA算法原理（二）

注意：

RSA 算法的可靠性基础：对极大整数做因数分解是很困难的。

RSA 是非对称算法，加解密使用不同的密钥。

两个密钥都可以用于加密，解密时需要使用另一个密钥。但是，通常用公钥加密私钥解密，因为公钥是近乎完全公开的，对于私钥加密的数据，有太多的人可以解密了。理论上 A 和 B 之间要通过 RSA 实现保密通信，需要 A 和 B 各自生成一组密钥，同时保管好自己的私钥；用对方的公钥加密要发送的消息，用自己的私钥解密对方发送过来的消息。

在签名的场景下，用私钥签名，公钥验签。

RSA 比 DES 等对称算法慢得多。一般在实际数据传输时，用 RSA 来加密比较短的对称密码，双方交换密码后再使用 DES 等对称算法传输数据。

如果两个正整数，除了 1 以外没有其他公因子，就称这两个数是互质关系。比如 3 和 5，13 和 31 等。

Wiki - 欧拉函数

欧拉函数：求小于 N{\displaystyle N}N 的正整数中与 N{\displaystyle N}N 互质的数的数目。

例如，对应 8，与 8 互质的数有 1，3，5，7，所以 φ(N){\displaystyle \varphi (N)}φ(N) = 4。

RSA 算法使用了欧拉函数的一个特例：如果 N{\displaystyle N}N 可以分解成两个互质的整数之积： N=pq{\displaystyle N=pq}N=pq 则 φ(N)=φ(p)φ(q)=(p−1)(q−1){\displaystyle \varphi (N)=\varphi (p)\varphi (q)=(p-1)(q-1)}φ(N)=φ(p)φ(q)=(p−1)(q−1) 比如，φ(35947)=φ(103)φ(349)=(102)(348)=35496{\displaystyle \varphi (35947)=\varphi (103)\varphi (349)=(102)(348)=35496}φ(35947)=φ(103)φ(349)=(102)(348)=35496。

Wiki - 模反元素

如果两个正整数 aaa 和 nnn 互质，那么一定可以找到整数 bbb，使得 ab−1ab-1ab−1 被 nnn 整除： ab≡1(modn)ab\equiv 1{\pmod {n}}ab≡1(modn) 这时，bbb 就叫做 aaa 的"模反元素"。

欧拉定理证明当 a,n{\displaystyle a,n}a,n 为两个互素的正整数时，则有 aφ(n)≡1(modn){\displaystyle a^{\varphi (n)}\equiv 1{\pmod {n}}}aφ(n)≡1(modn)，其中 φ(n){\displaystyle \varphi (n)}φ(n) 为欧拉函数（小于等于 n{\displaystyle n}n 且与 n{\displaystyle n}n 互素的正整数个数）。

上述结果可分解为 aφ(n)=a⋅aφ(n)−1≡1(modn){\displaystyle a^{\varphi (n)}=a\cdot a^{\varphi (n)-1}\equiv 1{\pmod {n}}}aφ(n)=a⋅aφ(n)−1≡1(modn)，其中 aφ(n)−1{\displaystyle a^{\varphi (n)-1}}aφ(n)−1 即为 a{\displaystyle a}a 关于模 n{\displaystyle n}n 之模反元素。

求整数 3 对同余 11 的模逆元素 x, x≡3−1(mod11){\displaystyle x\equiv 3^{-1}{\pmod {11}}}x≡3−1(mod11) 上述方程可变换为 3x≡1(mod11){\displaystyle 3x\equiv 1{\pmod {11}}}3x≡1(mod11) 在整数范围 Z11{\displaystyle \mathbb {Z} _{11}}Z11​ 内，可以找到满足该同余等式的 xxx 值为4，如下式所示 3(4)=12≡1(mod11){\displaystyle 3(4)=12\equiv 1{\pmod {11}}}3(4)=12≡1(mod11) 并且，在整数范围 Z11{\displaystyle \mathbb {Z} _{11}}Z11​ 内不存在其他满足此同余等式的值。

故，整数3对同余11的模逆元素为4。

(N,e){\displaystyle (N,e)}(N,e) 是公钥， (N,d){\displaystyle (N,d)}(N,d) 是私钥。公钥发送给所有的通信对象（对服务器来说就是所有的客户端），私钥则必须保管好，防止泄露。

假设客户端要向服务器发送消息 m{\displaystyle m}m，服务器的公钥是 N{\displaystyle N}N 和 e{\displaystyle e}e。客户端将消息 m{\displaystyle m}m 转换为一个小于 N{\displaystyle N}N 的非负整数 n{\displaystyle n}n，比如可以将每一个字转换为这个字的 Unicode 码，然后将这些数字连在一起组成一个数字。假如信息非常长的话，可以将这个信息分为几段，然后将每一段转换为 n{\displaystyle n}n。用下面这个公式他可以将 n{\displaystyle n}n 加密为 c{\displaystyle c}c： c≡ne(modN){\displaystyle c\equiv n^{e}{\pmod {N}}}c≡ne(modN) 计算 c{\displaystyle c}c 并不复杂。客户端算出 c{\displaystyle c}c 后就可以将它传递给服务器。

得到消息 c{\displaystyle c}c 后，可以利用密钥 d{\displaystyle d}d 来解码。可以用以下这个公式来将 c{\displaystyle c}c 转换为 n{\displaystyle n}n： cd≡n (mod N){\displaystyle c^{d}\equiv n\ (\mathrm {mod} \ N)}cd≡n (mod N) 得到 n{\displaystyle n}n 后，可以将原来的信息 m{\displaystyle m}m 重新复原。

解码的原理是： cd≡ne⋅d (mod N){\displaystyle c^{d}\equiv n^{e\cdot d}\ (\mathrm {mod} \ N)}cd≡ne⋅d (mod N) 已知 ed≡1(modr){\displaystyle ed\equiv 1{\pmod {r}}}ed≡1(modr)，即 ed=1+hφ(N){\displaystyle ed=1+h\varphi (N)}ed=1+hφ(N)。由欧拉定理得：

ned=n1+hφ(N)=n(nφ(N))h≡n(1)h(modN)≡n(modN){\displaystyle n^{ed}=n^{1+h\varphi (N)}=n\left(n^{\varphi (N)}\right)^{h}\equiv n(1)^{h}{\pmod {N}}\equiv n{\pmod {N}}}ned=n1+hφ(N)=n(nφ(N))h≡n(1)h(modN)≡n(modN)

RSA 也可以用来为一个消息签名。

对消息字符串的散列值（Message digest，用 MD5、SHA256 等算法求得的长度较短且固定的字符串）使用 RSA 的私钥计算签名（实际上仍然是加密消息）后，得到一个签名字符串，将其附加在消息字符串的合适位置后，一并发送。接收方使用对应的公钥可以从签名字符串中解密出原来的散列值，同时对原始消息再计算一次散列值。二者相比较，假如两者相符的话，则认为发信人持有正确的私钥，并且这个消息在传播路径上没有被篡改过。

用户应使用 1024 位密钥，证书认证机构应用 2048 位或以上。

RSA 之所以叫非对称算法，是因为加密和解密的密钥不一样。任何一个密钥都可以用来加密。

通过私钥可以轻松计算出公钥，反之不行。

用公钥加密时，私钥可以解密。反之亦然，私钥加密后的信息用公钥可以解密。

如果是对接其他平台提供的标准接口，如果这个接口用到了 RSA 加密，则需要这个平台提供对应的公钥。

需要提前在 Linux 上安装 OpenSSL，默认生成在当前用户家目录下：

对于 PHP 可以直接使用上面生成的原始私钥。但是 Java 需要将私钥转换成 PKCS8 格式，然后将生成的 PKCS8 格式的私钥去除头尾、换行和空格，作为私钥字符串填入代码中：

查看生成的文件：

查看公钥：

转成 PKCS8 格式的公钥字符串为：

查看私钥：