关于RSA加密的各种问题 [英] Various questions about RSA encryption

问题描述

我目前在C ++中为Unix编写我自己的ASE / RSA加密程序。我已经经历了大约一个星期了，我已经开始包围我的头了，但我还有一些紧迫的问题：

1）根据我的理解，RSA密钥在其最基本的形式是使用的两个素数（R）的乘积和指数的组合。对我来说明显的是，以明文形式存储密钥会破坏加密任何东西的目的。因此，我可以以什么形式存储我生成的公钥和私钥？要求用户输入密码，并用ASCII表对密钥的各个数字进行简单移位/替换？还是有一些其他标准，我没有遇到过？此外，当生成密钥时，是R和相应的指数简单地顺序存储吗？即## primeproduct #### exponent ##？在这种情况下，解密算法如何将密钥解析成两个单独的值？

2）我将如何编程生成私有指数， ve决定使用65537作为我所有加密的公共指数？我有方程P * Q = 1mod（M），其中P和Q和指数和M是欧拉的函数的结果。这只是一个生成随机数和测试它们的相对原始对公共指数的问题，直到你打沉重？我知道你不能简单地从1开始增量，直到你找到这样的数字，因为任何人都可以做同样的事情，并得到你的私人指数本身。

3）当生成字符等价集合时，我理解集合中使用的数字不能必须小于P * Q且与P * Q互质。同样，这是一个测试数字的相对原始性到P * Q的问题。是测试相对原始性的速度独立于你正在使用的数字的大小吗？

解决方案

有一些标准格式用于存储/交换RSA密钥，例如 RFC 3447 。对于更好或更坏，大多数（许多，反正）使用ASN.1编码，这增加了比大多数人喜欢的复杂性，本身。一些使用Base64编码，这是很容易实现。

至于什么构成一个键：在其最基本的形式，你是正确的;公钥包括模数（通常称为 n ）和指数（通常称为 e ）。

要计算密钥对，请从两个大质数开始，通常称为 p 和 q 。您计算 n 为 p * q 。您还计算（p-1）*（q-1）的数字（通常称为 r / p>

e 是一个或多或少随机选择的数字，相对于 code>警告：你不希望 e 真的很小，虽然 - log（e）> = log（n）/ 4为最低。

然后，您将 d （私人解密密钥）计算为满足以下关系的数字：

  d * e = 1（mod r）
  

你通常使用Euclid的算法来计算，虽然有其他选项（见下文）。再次，你不希望 d 真的很小，所以如果它工作到一个非常小的数字，你可能想尝试另一个值 e ，并计算新的 d 以匹配。

计算您的 e 和 d 的方法。你可以从找到一个与1 mod r一致的数K开始，然后因子。将素因子放在一起得到大小相等的两个因子，并将它们用作 e 和 d p>

对于计算你的 d 的攻击者：你需要 r 来计算，并且知道 r 取决于知道 p 和 q 。这就是为什么/在哪里/如何因素打破RSA。如果你因素 n ，那么你知道 p 和 q 。从它们，你可以找到 r ，从 r 可以计算 d 与已知的 e 匹配。

所以，让我们通过数学创建一个键对。我们将使用太小而不能有效的素数，但应足以证明所涉及的想法。

因此，让我们首先选择ap和q（当然，都需要是素数）：

  p = 9999991 
q = 11999989 
  

从我们计算 n 和 r ：

  n = 119999782000099 
r = 119999760000120 
  

接下来我们需要选择 e c $ c> 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克，Z者除外; 
 
 if（gcd（a，p）> 1）return 0; 
 
 z = 1; 
 
而（一个大于1）{
 Z + =磷; 
如果（（G =最大公约数（A，Z））→1）{
 A / =克; 
 z / = g; 
} 
} 
 return z; 
} 
  

我们得到的结果是：

D = 38110914516113

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

所以，让我们加密非常秘密的消息！使用电子和 N 上面给出，即加密为：

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

然后使用 d 上面给出的，解密回原来的。执行加密/解密（使用硬编码密钥和模数）的代码如下所示：

  #include< iostream& 
 #include< iterator> 
 #include< algorithm> 
 #include< vector> 
 #include< functional> 
 
 typedef unsigned long long num; 
 
 const num e = 65537; 
 const num d = 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％ 
 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; 
} 
 
 struct crypt：std :: binary_function< num，num，num> {
 num operator（）（num input，num key）const {
 return pow_mod（input，key，n）; 
} 
}; 
 
 int main（）{
 std :: string msg =非常秘密的消息！ 
 std :: vector< num>加密; 
 
 std :: transform（msg.begin（），msg.end（），
 std :: back_inserter（encrypted），
 std :: bind2nd（crypt e））; 
 
 std :: copy（encrypted.begin（），encrypted.end（），std :: ostream_iterator< num>（std :: cout，\\\
））; 
 
 std :: cout<< \\\
; 
 
 std :: transform（encrypted.begin（），encrypted.end（），
 std :: ostream_iterator< char>（std :: cout，），
 std :: bind2nd（crypt（），d））; 
 std :: cout<< \\\
; 
 
 return 0; 
} 
  

为了有一个希望需要使用更大的模数 - 至少数百位（对于偏执型可能一千或更多）。你可以使用一个普通的任意精度整型库，或者为手头的任务专门编写的例程。 RSA固有地相当慢，所以一次大多数实现使用代码与许多毛茸茸的优化来做这项工作。现在，硬件是足够快的，你可以很容易地摆脱一个相当平均的大整数库相当容易（特别是，因为在实际使用中，你只想使用RSA加密/解密的对称算法的密钥，而不是加密原始数据）。

I'm currently writing my own ASE/RSA encryption program in C++ for Unix. I've been going through the literature for about a week now, and I've started to wrap my head around it all but I'm still left with some pressing questions:

1) Based on my understanding, an RSA key in its most basic form is the combination of the product of the two primes (R) used and the exponents. It's obvious to me that storing the key in such a form in plaintext would defeat the purpose of encryption anything at all. Therefore, in what form can I store my generated public and private keys? Ask the user for a password and do some "simple" shift/replacing on the individual digits of the key with an ASCII table? Or is there some other standard I haven't run across? Also, when the keys are generated, are R and the respective exponent simply stored sequentially? i.e. ##primeproduct####exponent##? In that case, how would a decryption algorithm parse the key into the two separate values?

2) How would I go about programatically generating the private exponent, given that I've decided to use 65537 as my public exponent for all encryptions? I've got the equation P*Q = 1mod(M), where P and Q and the exponents and M is the result of Euler's Totient Function. Is this simply a matter of generating random numbers and testing their relative primality to the public exponent until you hit pay dirt? I know you can't simply start from 1 and increment until you find such a number, as anyone could simply do the same thing and get your private exponent themselves.

3) When generating the character equivalence set, I understand that the numbers used in the set can't be must be less than and relatively prime to P*Q. Again, this is a matter of testing relative primality of numbers to P*Q. Is the speed of testing relative primality independent of the size of the numbers you're working with? Or are special algorithms necessary?

Thanks in advance to anyone who takes the time to read and answer, cheers!

解决方案

There are some standard formats for storing/exchanging RSA keys such as RFC 3447. For better or worse, most (many, anyway) use ASN.1 encoding, which adds more complexity than most people like, all by itself. A few use Base64 encoding, which is a lot easier to implement.

As far as what constitutes a key goes: in its most basic form, you're correct; the public key includes the modulus (usually called n) and an exponent (usually called e).

To compute a key pair, you start from two large prime numbers, usually called p and q. You compute the modulus n as p * q. You also compute a number (often called r) that's (p-1) * (q-1).

e is then a more or less randomly chosen number that's prime relative to r. Warning: you don't want e to be really small though -- log(e) >= log(n)/4 as a bare minimum.

You then compute d (the private decryption key) as a number satisfying the relation:

d * e = 1 (mod r)

You typically compute this using Euclid's algorithm, though there are other options (see below). Again, you don't want d to be really small either, so if it works out to a really small number, you probably want to try another value for e, and compute a new d to match.

There is another way to compute your e and d. You can start by finding some number K that's congruent to 1 mod r, then factor it. Put the prime factors together to get two factors of roughly equal size, and use them as e and d.

As far as an attacker computing your d goes: you need r to compute this, and knowing r depends on knowing p and q. That's exactly why/where/how factoring comes into breaking RSA. If you factor n, then you know p and q. From them, you can find r, and from r you can compute the d that matches a known e.

So, let's work through the math to create a key pair. We're going to use primes that are much too small to be effective, but should be sufficient to demonstrate the ideas involved.

So let's start by picking a p and q (of course, both need to be primes):

p = 9999991
q = 11999989

From those we compute n and r:

n = 119999782000099
r = 119999760000120

Next we need to either pick e or else compute K, then factor it to get e and d. For the moment, we'll go with your suggestion of e=65537 (since 65537 is prime, the only possibility for it and r not being relative primes would be if r was an exact multiple of 65537, which we can verify is not the case quite easily).

From that, we need to compute our d. We can do that fairly easily (though not necessarily very quickly) using the "Extended" version of Euclid's algorithm, (as you mentioned) Euler's Totient, Gauss' method, or any of a number of others.

For the moment, I'll compute it using Gauss' method:

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;
}

The result we get is:

d = 38110914516113

Then we can plug these into an implementation of RSA, and use them to encrypt and decrypt a message.

So, let's encrypt "Very Secret Message!". Using the e and n given above, that encrypts to:

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

And, using the d given above, that decrypts back to the original. Code to do the encryption/decryption (using hard-coded keys and modulus) looks like this:

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

typedef unsigned long long num;

const num e = 65537;
const num d = 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;
}

struct crypt : std::binary_function<num, num, num> {
    num operator()(num input, num key) const {
        return pow_mod(input, key, n);
    }
};

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

    std::transform(msg.begin(), msg.end(),  
        std::back_inserter(encrypted),
        std::bind2nd(crypt(), e));

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

    std::cout << "\n";

    std::transform(encrypted.begin(), encrypted.end(), 
        std::ostream_iterator<char>(std::cout, ""), 
        std::bind2nd(crypt(), d));
    std::cout << "\n";

    return 0;
}

To have even a hope of security, you need to use a much larger modulus though--hundreds of bits at the very least (and perhaps a thousand or more for the paranoid). You could do that with a normal arbitrary precision integer library, or routines written specifically for the task at hand. RSA is inherently fairly slow, so at one time most implementations used code with lots of hairy optimization to do the job. Nowadays, hardware is fast enough that you can probably get away with a fairly average large-integer library fairly easily (especially since in real use, you only want to use RSA to encrypt/decrypt a key for a symmetrical algorithm, not to encrypt the raw data).

这篇关于关于RSA加密的各种问题的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！