RSA 加密方案的深入学习

RSA 是一种非常流行的非对称加密算法，它是由 Ron Rivest、Adi Shamir、Leonard Adleman 在1977年一起提出的，RSA 就是他们三人姓氏开头字母拼在一起组成的。相对于对称加密算法使用相同的密钥进行加解密，非对称加密算法需要两把不同的密钥，一个是公钥，一个是私钥，公钥可以公开提供给任何人，私钥不可以公开。可以用公钥加密、私钥解密，也可以用私钥加密、公钥解密。

RSA 的密钥生成过程

1. 选择两个大的质数 p 和 q，计算两个质数的乘积 N，素数是指在大于 1 的自然数中，除了 1 和自身外，无法被其他自然数整除的数。
2. 对 p 和 q 使用欧拉函数运算得到各自的互质数的数量 Φ (p) = (p-1) , Φ (q) = (q-1) 并将各个结果进行相乘 R = Φ (p) * Φ (q)，欧拉函数Φ (n)是小于等于 n 的正整数中与 n 互质的数的数目
3. 在大于 1 小于 R 的区间中选择一个整数 E，并且该整数与 R 互质。
4. 求 E 关于 R 的模逆元 D，即 E * D ≡ 1 (mod R)。

通过上述的步骤可以得到公钥 (N, E) 和私钥 (N, D)，用一个例子带入说明就是：

1. 选择两个质数 p (3) 和 q (11)
2. 并两只质数的乘积 N (33) = p (3) * q (11)
3. 根据欧拉函数计算 R (20) = (3 - 1) * (11 - 1)
4. 选择一个与 20 互质的整数 E (3)
5. 计算 E(3) * D % R(20) = 1 ，得到 D 的为 7

通过上述计算公钥为（33, 3），私钥为（33, 7）。

RSA 对明文加解密过程

• 加密
  使用公钥进行加密，将明文每个字符转换为数字，可以转换为 ASCII 值，每个明文数字做 E 次方运算，然后再计算和 N 的余数，得到的结果就是加密后的密文。例：现在有一个明文数字9，密文生成的过程就是先计算 9 的 3 次方等于 729，再计算和 33 的余数为 3，3 就是最终的密文。

• 解密
  使用私钥进行解密，将拿到的密文先求 D 次方运算，然后再计算和 N 的余数，得到的结果就是解密后的明文。例：根据上一步得到的密文 3，先计算 3 的 7 次方等于 2187，再计算和 33 的余数为 9，这样就得到了明文。

RSA 加密标准

RSA 算法通常对输入数据的长度有限制，一般不能超过模数 N 的长度，如果明文数据较长，需要将其分成若干块进行加密。加密标准主要分为 PKCS1 和 OAEP。OAEP 目前更加安全，推荐使用 OAEP 的标准。

RSA 的安全性

RSA 的安全性非常依赖于密钥生成第一步中两个质数的范围，当质数非常大时，因数分解会变得非常困难，这也是 RSA 算法之所以安全的核心点，随着计算机硬件能力逐步提升，512 位和 768 位的质数已经被人分解了，目前常用的 1024 位质数在理论上已经不安全了，推荐以后使用 2048 位或者更高 4096 位质数来生成密钥。在理论上来说，量子计算机被应用之前，RSA 算法都是安全的。

RSA 的应用场景

RSA 的加解密速度很慢，并且明文长度是不能超过公钥 N 的长度的，所以无法加密数据量大的明文，实际中常常搭配 AES 加密方式做混合加解密。通过 RSA 将 AES 密钥加密，传递密钥后两端利用 AES 进行数据加密传输。

代码实现

• php

// 公钥加密数据
$pubFilepath = 'public_key.pem';
$fp = fopen($filepath,"rb");
$pubContent = fread($fp, filesize($filepath);
$publicKey = openssl_get_publickey($pubContent);
openssl_public_encrypt("hello", $data, $publicKey);

// 私钥解密数据
$priFilepath = 'private_key.pem';
$pr = fopen($priFilepath, 'rb');
$priContent = fread($pr, filesize($priFilepath);
$privateKey = openssl_get_privatekey($priContent);
openssl_private_decrypt($data, $result, $privateKey);

• go

// Demo 密钥生成以及加解密示例
func Demo() string {
    rng := rand.Reader

    //生成密钥，选择2048位长度
    pri, err := rsa.GenerateKey(rng, 2048)
    if err != nil {
        panic(err)
    }

    //明文
    text := "hello world"
    cipherText := RsaEncrypt(&pri.PublicKey, text)
    result := RsaDecrypt(pri, cipherText)

    return result
}

// RsaEncrypt 加密
func RsaEncrypt(pub *rsa.PublicKey, text string) string {
    rng := rand.Reader

    result, err := rsa.EncryptOAEP(sha256.New(), rng, pub, []byte(text), []byte("test hello"))
    if err != nil {
        panic(err)
    }

    //将加密的密文字节转为base64方便传输
    content := base64.StdEncoding.EncodeToString(result)

    return content
}

// RsaDecrypt 解密
func RsaDecrypt(pri *rsa.PrivateKey, cipherText string) string {
    //将base64转为密文字节
    de, err := base64.StdEncoding.DecodeString(cipherText)
    if err != nil {
        panic(err)
    }

    rng := rand.Reader

    ra, err := rsa.DecryptOAEP(sha256.New(), rng, pri, de, []byte("test hello"))
    if err != nil {
        panic(err)
    }

    return string(ra)
}