c++ - 关于RSA加密的各种问题

Question

我目前正在为 Unix 用 C++ 编写我自己的 ASE/RSA 加密程序。我已经浏览了大约一个星期的文献，我已经开始考虑这一切，但我仍然有一些紧迫的问题:

1) 根据我的理解，最基本形式的 RSA key 是所使用的两个素数 (R) 和指数的乘积的组合。对我来说很明显，以明文形式存储 key 将完全违背加密任何东西的目的。因此，我可以以什么形式存储我生成的公钥和私钥？向用户询问密码并使用 ASCII 表对 key 的各个数字进行一些“简单”移位/替换？或者还有其他一些我没有遇到过的标准吗？此外，当生成 key 时，R 和相应的指数是否只是按顺序存储？即##primeproduct####exponent##？在这种情况下，解密算法如何将 key 解析为两个单独的值？

2)鉴于我已决定使用 65537 作为所有加密的公共(public)指数，我将如何以编程方式生成私有(private)指数？我有方程 P*Q = 1mod(M)，其中 P 和 Q 以及指数和 M 是 Euler 的 Totient 函数的结果。这是否只是生成随机数并测试它们与公共(public)指数的相对素数的问题，直到您支付污垢？我知道你不能简单地从 1 开始并递增直到找到这样一个数字，因为任何人都可以简单地做同样的事情并自己得到你的私有(private)指数。

3)在生成字符等价集的时候，我明白这个集合中使用的数字不能小于P*Q并且相对质数。同样，这是测试数字与 P*Q 的相对素性的问题。测试相对素性的速度是否与您正在处理的数字的大小无关？还是需要特殊的算法？

提前感谢任何花时间阅读和回答的人，干杯!

Answer 1

有一些用于存储/交换 RSA key 的标准格式，例如 RFC 3447 .不管是好是坏，大多数(无论如何)都使用 ASN.1 编码，这增加了比大多数人喜欢的更多的复杂性，所有这些都是单独的。少数使用 Base64 编码，这更容易实现。

就什么构成 key 而言:就其最基本的形式而言，您是正确的；公钥包括模数(通常称为 n )和指数(通常称为 e )。

要计算 key 对，您需要从两个大素数开始，通常称为 p和 q .您计算模数 n如 p * q .您还计算了一个数字(通常称为 r )，即 (p-1) * (q-1) .
e然后是一个或多或少随机选择的数字，它是相对于 r 的质数.警告:您不想要 e虽然非常小 - log(e) >= log(n)/4 作为最低限度。

然后计算 d (私有(private)解密 key )作为满足关系的数字:

d * e = 1 (mod r)

您通常使用 Euclid 算法计算此值，但还有其他选项(见下文)。再说一次，你不想要 d也非常小，所以如果结果非常小，您可能想尝试 e 的另一个值。 ，并计算一个新的 d匹配。

还有另一种方法来计算您的 e和 d .您可以先找到一些与 1 mod r 全等的数字 K，然后将其分解。将质因数放在一起得到大小大致相等的两个因数，并将它们用作 e和 d .

至于攻击者计算您的 d去:你需要 r计算这个，并知道 r靠知道 p和 q .这正是分解 RSA 的原因/地点/方式。如果您考虑 n ，那么你就知道 p和 q .从它们中，您可以找到 r ，来自 r你可以计算 d匹配一个已知的 e .

因此，让我们通过数学运算来创建 key 对。我们将使用太小而无效的素数，但应该足以证明所涉及的想法。

因此，让我们从选择 p 和 q 开始(当然，两者都需要是素数):

p = 9999991
q = 11999989

从我们计算 n和 r :

n = 119999782000099
r = 119999760000120

接下来我们需要选择 e否则计算 K ，然后将其分解为 e和 d .目前，我们将采用您的建议 e=65537(因为 65537 是素数，它的唯一可能性和 r 不是相对素数是如果 r 是 65537 的精确倍数，我们可以验证不是很容易的情况)。

由此，我们需要计算我们的 d .我们可以使用 Euclid 算法的“扩展”版本(如您所提到的)Euler's Totient、Gauss' 方法或其他许多方法中的任何一个来相当容易地(尽管不一定非常快)做到这一点。

目前，我将使用高斯方法计算它:

template <class num>
num gcd(num a, num b) {
    num r;
    while (b > 0) {
        r = a % b;
        a = b;
        b = r;
    }
    return a;
}

template <class num>
num find_inverse(num a, num p) {
    num g, z;

    if (gcd(a, p) > 1) return 0;

    z = 1;

    while (a > 1) {
        z += p;
        if ((g=gcd(a, z))> 1) {
            a /= g;
            z /= g;
        }
    }
    return z;
}

我们得到的结果是:

d = 38110914516113

然后我们可以将这些插入到 RSA 的实现中，并使用它们来加密和解密消息。

所以，让我们加密“非常 secret 的消息!”。使用 e和 n上面给出，加密为:

74603288122996
49544151279887
83011912841578
96347106356362
20256165166509
66272049143842
49544151279887
22863535059597
83011912841578
49544151279887
96446347654908
20256165166509
87232607087245
49544151279887
68304272579690
68304272579690
87665372487589
26633960965444
49544151279887
15733234551614

并且，使用 d上面给出，解密回原始。进行加密/解密(使用硬编码 key 和模数)的代码如下所示:

#include <iostream>
#include <iterator>
#include <algorithm>
#include <vector>
#include <functional>

typedef unsigned long long num;

const num e_key = 65537;
const num d_key = 38110914516113;
const num n = 119999782000099;

template <class T>
T mul_mod(T a, T b, T m) {
    if (m == 0) return a * b;

    T r = T();

    while (a > 0) {
        if (a & 1)
            if ((r += b) > m) r %= m;
        a >>= 1;
        if ((b <<= 1) > m) b %= m;
    }
    return r;
}

template <class T>
T pow_mod(T a, T n, T m) {
    T r = 1;

    while (n > 0) {
        if (n & 1)
            r = mul_mod(r, a, m);
        a = mul_mod(a, a, m);
        n >>= 1;
    }
    return r;
}

int main() {
    std::string msg = "Very Secret Message!";
    std::vector<num> encrypted;

    std::cout << "Original message: " << msg << '\n';

    std::transform(msg.begin(), msg.end(),
        std::back_inserter(encrypted),
        [&](num val) { return pow_mod(val, e_key, n); });

    std::cout << "Encrypted message:\n";
    std::copy(encrypted.begin(), encrypted.end(), std::ostream_iterator<num>(std::cout, "\n"));

    std::cout << "\n";

    std::cout << "Decrypted message: ";
    std::transform(encrypted.begin(), encrypted.end(),
        std::ostream_iterator<char>(std::cout, ""),
        [](num val) { return pow_mod(val, d_key, n); });

    std::cout << "\n";
}

为了获得安全的希望，您需要使用更大的模数 - 至少数百位(对于偏执狂可能是一千或更多)。您可以使用普通的任意精度整数库或专门为手头任务编写的例程来做到这一点。 RSA 本质上是相当慢的，所以一度大多数实现都使用带有大量优化的代码来完成这项工作。如今，硬件足够快，您可能可以相当轻松地摆脱相当平均的大型整数库(特别是因为在实际使用中，您只想使用 RSA 加密/解密对称算法的 key ，而不是加密原始数据)。

即使具有合适大小的模数(并且修改了代码以支持所需的大数)，这仍然是有时被称为“教科书 RSA”的内容，并且它并不真正适合于真正的加密方式。例如，现在，它一次加密一个字节的输入。这会在加密数据中留下明显的模式。看上面的加密数据很简单，第二个和第七个字是一样的——因为都是 e的加密形式。 (这也发生在消息中的其他几个地方)。

就目前而言，这可以作为一个简单的替换代码进行攻击。 e是英文中最常见的字母，所以我们可以(正确)猜测加密数据中最常见的词代表 e (各种语言中字母的相对频率是众所周知的)。更糟糕的是，我们还可以查看诸如成对和三联字母之类的东西来改进攻击。例如，如果我们在加密数据中连续两次看到同一个单词，我们就知道我们看到的是一个双字母，它只能是普通英文文本中的几个字母。底线:尽管 RSA 本身可以非常强大，但上面显示的使用方式绝对不是。

为了防止出现这个问题，使用(比如)512 位 key ，我们还将以 512 位块的形式处理输入。这意味着如果原始输入中有两个地方一次占 512 位，并且完全相同，那么我们只有一个重复。即使发生这种情况，也很难猜测会是这样，因此尽管这是不可取的，但它并不像上面显示的逐字节版本那样容易受到攻击。此外，您总是希望将输入填充为被加密大小的倍数。

引用

https://crypto.stackexchange.com/questions/1448/definition-of-textbook-rsa