RSA 加密

一种非对称加密技术

公钥的生成

公钥的生成选取两个质数字 $p = 3$ 和 $q = 11$

这两个质数相乘得到了 $N = p \times q = 3 \times 11 = 33$

同时，计算小于 $N$ 并且与 $N$ 互质的正整数的个数。

通过欧拉函数快速计算得到 $ϕ (N) = (p - 1) \times (q - 1) = 2 \times 10 = 20$

然后随机选取一个加密指数 $e$ ， $e$ 必须大于 1 小于 $ϕ (N)$ 并且与 $ϕ (N)$ 互质，这里我们选取 $e = 3$

得到公钥 $(e, N) = (3, 33)$

私钥的生成

计算 $e$ 对于 $ϕ (N)$ 的模反元素 $d$ ，即求解以下方程：

$3 \times d \equiv 1 (\mod 20)$

通过辗转相除法，我们可以得到 $d = 7$

得到私钥 $(d, N) = (7, 33)$

公钥的加密

假设明文为 12

密文 $= {明文}^{e} mod N = 12^{3} mod 33 = 17$

私钥的解密

密文 $= 17$

明文 $= {密文}^{d} mod N = 17^{7} mod 33 = 12$

结论

私钥是通过 $e$ 和 $ϕ (N)$ 计算得到的，而 $e$ 是公开的，所以只有知道 $ϕ (N)$ 才能计算得到私钥。

因此，破解者的目标就是想得到 $ϕ (N)$ ，即 $p$ 和 $q$ 。

$ϕ (N)$ 是通过 $p$ 和 $q$ 两个质数计算得到的。

这个问题属于大整数的因数分解问题，从一个数字倒推出两个质数相乘，难度非常地大

RSA256 和 RSA512

我们或许看到过上面两种加密方式，其中的 256 和 512 指的是模数 N 的比特长度，也就是质数 $p$ 和 $q$ 相乘得到的数字的位数。

位数越多，质数 $p$ 和 $q$ 越大，因数分解的难度就越大，加密强度也就越高。

生成公钥和私钥

利用 openssl 生成 RSA2048 的公钥和私钥

$ openssl genrsa -out private_key.pem 2048

得到

通过私钥生成公钥

openssl rsa -in private_key.pem -out public_key.pem -pubout

得到公钥

加密和解密数据

创建一份测试数据

$ echo "hello world" > data.txt

使用公钥加密数据：

$ openssl pkeyutl -encrypt -inkey public_key.pem -pubin -in data.txt -out data.enc

得到了一个二级制文件 data.enc，内容如下：

$ cat data.enc 
\�dz՚�׆{]�{�풱��^���*4�O�y�+(�`(]�h���
                                      e�&�����ŞcD|ؒ���|1$h�����Ƙ����(���Co��
t�y綿'O�g��NN                                                              �l�"ī�N�M�V'E��²h����}y����;��_Å��
V}����yپ)����i9v�x|��W-�h�IP���>=�HD�;{�
���q@4q:�K�%

我们使用私钥解密这个文件的数据：

$ openssl pkeyutl -decrypt -inkey private_key.pem -in data.enc -out data-gen.txt

得到了 data-gen.txt，内容和 data.txt 一致：

$ cat data-gen.txt
hello world

JS 生成 RSA 公钥和私钥

通过在浏览器中生成 RSA 公钥和私钥，可以直接看到公钥中的 e 和 n，以及私钥中的 d 和 n 的值

let crypto = await window.crypto.subtle.generateKey({
    name: "RSA-OAEP",
    modulusLength: 2048,
    publicExponent: new Uint8Array([1, 0, 1]),
    hash: "SHA-256"
}, true, ["encrypt", "decrypt"]);

let publicKey = await window.crypto.subtle.exportKey("jwk", crypto.publicKey);
let privateKey = await window.crypto.subtle.exportKey("jwk", crypto.privateKey);

console.log(publicKey, privateKey);

publicKey.e //=> AQAB
publicKey.n //=> kY2z-liG4XSdAlK88oihw-Sjsol6mmeCw8d2ZY6_Lk4Cp9cGRZEtmGeZvmprG29eCBWvkuCWFOOTw1iMO3tfKNlLZUxzgJhCOFtBMLv3GuBAN2bPH4cHrq08rGnjGy5NO5SAPZf-a5MP_3l1kHvrMo8nzuQ4n3MqwSWDByoI1wRYNE3hwjQ2TJ4-ZCEevY98XHUyNuZ3tRgK9wNQXFoNR7gmO7lGsefMP5OTMUL2nWVDgnhlzFQ4XgAf_TchmudVBaSNLkj8txB-B4rpHZyCFxNW5T1KwYK8PPclmMpfGHJSAFJh8-A53Dl42siWagHfIzK9vSPmOD0VdJsi1mwWaQ

privateKey.d //=> CKF67rLWJXZ8b7lUck5vLSyYsL43MpwSfgwM6LiLFjKFzmPRMuNvbTSWqMEqfCEUvDnKkSG957VkIZBVss2kSfzmKOnchXkOoCt4SGzOgJD6LdU4t4YsJFiQZ8OlnFeya7O1p2SLL3macfJgg49D78BBj4j34V77LFXOZbV0rbwBl7oLf5rQl3TLDH179mgHUA7hYwcrVlGwQWO8XUIz58HZP8Zw9HcZQDo1cR_uc9u3fzEZC3Jlw5NKy1ifB8ojPDlJWlc53-JFY8I5sj_0rWUcLp6LUDflb-OJoKljQnMvRlvW2tZIQA1hPJ6HdbJYW6oFBIJHanuedXB5IerBOw
privateKey.n //=> kY2z-liG4XSdAlK88oihw-Sjsol6mmeCw8d2ZY6_Lk4Cp9cGRZEtmGeZvmprG29eCBWvkuCWFOOTw1iMO3tfKNlLZUxzgJhCOFtBMLv3GuBAN2bPH4cHrq08rGnjGy5NO5SAPZf-a5MP_3l1kHvrMo8nzuQ4n3MqwSWDByoI1wRYNE3hwjQ2TJ4-ZCEevY98XHUyNuZ3tRgK9wNQXFoNR7gmO7lGsefMP5OTMUL2nWVDgnhlzFQ4XgAf_TchmudVBaSNLkj8txB-B4rpHZyCFxNW5T1KwYK8PPclmMpfGHJSAFJh8-A53Dl42siWagHfIzK9vSPmOD0VdJsi1mwWaQ

参考资料：

4zahvcJ9glg、BV1XP4y1A7Ui

RSA 加密 ​

公钥的生成 ​

私钥的生成 ​

公钥的加密 ​

私钥的解密 ​

结论 ​

RSA256 和 RSA512 ​

生成公钥和私钥 ​

加密和解密数据 ​

JS 生成 RSA 公钥和私钥 ​

参考资料： ​