RSA 算法介绍与 DEMO

请注意,本文编写于 157 天前,最后修改于 82 天前,其中某些信息可能已经过时。

聊聊 RSA 算法,并给出一个 C++ Demo。

引言

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

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

对称加密与非对称加密

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

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

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

RSA 算法原理

RSA 算法的步骤如下:

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

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

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

$$encrypt=x^{e}\quad Mod\quad 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';
}
Comments

添加新评论

已有 17 条评论

大佬我弄好了,一个文件夹的名字错了。
就是主题的名字错了。
话说你的邮件评论真心不错,可否分享下,初次玩这个程序。很多不解

熊猫小A 熊猫小A 回复 @大叔

CommentToMail插件

为啥我这里没有表情,表情包没有、用的是你的主题。

熊猫小A 熊猫小A 回复 @大叔

1.看主题说明。2. 你不带上出错页面链接,仅凭这一句话别人很难帮你。3. 请到主题介绍页面下面留言,现在这篇文章并没有在讲主题的事。

大佬……

看起来很不错

熊猫小A 熊猫小A 回复 @张小飞

大佬见笑了

表示根本看不懂

哈哈 我也是略知皮毛而已

表示看不懂

大佬谦虚了

妈呀,我看不到啊~

熊猫小A 熊猫小A 回复 @沙扬娜拉

我学生物而不是编程真是太好了(数学差的不是一丁点……)

熊猫小A 熊猫小A 回复 @mikusa

+1 数学差,现在头疼得一逼

高产dalao!

熊猫小A 熊猫小A 回复 @ohmyga

都是水文而已啦