RSA 算法介绍与演示

前言

RSA 算法是一种常用的非对称加密算法，它的加密基础是对大数做因数分解的困难程度。虽然其安全性尚没有在理论上被证明，但在秘钥长度足够（1024 位以上）时，以目前发现的破解方法来看成本难以承受，因此可以认为是安全的。本文简要介绍了对称加密算法、非对称加密算法，然后罗列了 RSA 算法的实现步骤，最后给出一个 C++ 编写的 Demo。

注意，文中略去了大部分的数学证明过程；另外 Demo 仅用于帮助理解算法，几乎不能应用在任何实际场景中。

对称加密与非对称加密

假设 A 要将一则消息传递给 B，却不想让任何第三方人员得知消息内容，这就需要对消息进行加密。借用经典的「箱子-钥匙」的比喻，只需要制造一个箱子，并为之配两把钥匙，A、B 各执一把，即可完成对消息的保密过程。步骤是：A 使用钥匙将消息放在箱子里锁住并发送给 B，B 收到后再使用手上的钥匙打开箱子获得消息的原文。这种加密方法简单易用，但是面临秘钥分发的问题：如何让 A、B 都有一样的钥匙呢？传递钥匙的过程本身就面临着泄露的风险，为了克服这个问题（以及其他的一些问题），非对称加密上场了。

非对称加密中，秘钥是成对的：一个公钥，一个私钥，二者不同。公钥可以广而告之，任何人都能拿到，但是私钥只能由接收信息的一方自己保存。一个非对称加密算法总是想要实现这么一个效果：任何想要发送信息的人都必须使用接收方所提供的公钥对信息进行加密得到密文，接收方收到密文后再用自己的私钥对其解密得到原文。在整个过程中，私钥没有被传递，因此解决了秘钥分发的问题。

RSA 算法就是一种非对称加密算法，接下来对其进行简要介绍。

RSA 算法原理

RSA 算法的步骤如下：

首先选取两个不相同的大质数 $p$ 与 $q$ ，计算 $N=p\times q$ ；
然后求欧拉函数 $r=(p-1)\times (q-1)$ ；
选择一个数 $e$ ， $0<e<r$ ，且 $e$ 与 $r$ 互质，求 $e$ 关于 $r$ 的模反元素 $d$ ，即此方程中 $d$ 的非负整数解: $e\times d+r\times y=1$ 。

则得到了公钥 $(N,e)$ 与私钥 $(N,d)$ 。

若要对数 $x$ 进行加密，只需要按照此方法计算密文：

e n c r y p t = x^{e} M o d N

$encrypt=x^{e}\quad Mod\quad N$

由密文计算原文的方式是很类似的：

d e c r y p t = e n c r y p t^{d} M o d N

$decrypt=encrypt^{d}\quad Mod\quad N$

需要注意的是，加密的密文长度不能超过 $N$ ，但是如果 $N$ 选得过大，又会使得计算速度减慢，因此 RSA 算法还是更适合小规模数据的加密。

RSA 有效的基础是从 $N$ 与 $e$ 反推 $p$ 与 $q$ 是很困难的，一般选取的 $N$ 的位数高达 1024。

一个 Demo

RSA 算法过程是很明了的，但是如果真的按照理论步骤直接写……你会发现并不可行，这是由于涉及到的幂次运算数字非常大，不可能直接完成。

下面的 Demo 给出了一个示例。其中 exp_mod() 方法值得注意，它降低了加解密过程的计算量。

#include <iostream>

// 扩展欧拉定理，求私钥
long gcdEx(long a, long b, long *x, long *y)
{
    if (b == 0)
    {
        *x = 1, *y = 0;
        return a;
    }
    else
    {
        long r = gcdEx(b, a%b, x, y);
        long t = *x;
        *x = *y;
        *y = t - a / b * *y;
        return r;
    }
}

// 计算公钥 (n,e) 与私钥 (n,d)
void GenKey(long p, long q, long& n, long& e, long& d)
{
    e = 19;  // 一般选择 65537
    n = p*q;    // 与 e 构成公钥
    long fn = (p - 1)*(q - 1);
    long x, y;
    gcdEx(e, fn, &x, &y);

    // 保证 x 为正数
    while (x < 0)
        x += fn;

    d = x;
}

// 计算求幂后取模的值 (base^e) mod m
long exp_mod(long base, long e, long m)
{
    int N = 0;
    int nRet = 1;
    int nMaxBit = 0;
    int nMax = 1;

    // 获取b的最高有效位
    while (nMax < e){
        nMax <<= 1;
        ++nMaxBit;
    }
    // 求模 
    for (N = nMaxBit; N >= 0; --N){
        nRet = (nRet * nRet) % m;
        if (e & (1 << N)){
            nRet = (nRet * base) % m;
        }
    }

    return nRet;
}

int main()
{
    long p = 127, q = 131;
    long n, e, d;

    // 生成密钥对
    GenKey(p, q, n, e, d);
    std::cout 
        << "e: " << e << '\n'
        << "n: " << n << '\n'
        << "d: " << d << '\n';

    long text = 12345;

    // 加密
    long encrypted = exp_mod(text, e, n);
    std::cout << "encrypted: " << encrypted << '\n';

    // 解密
    long decrypted = exp_mod(encrypted, d, n);
    std::cout << "decrypted: " << decrypted << '\n';
}