这是生成rsa密钥的正确方法吗?

is this code going to give me correct values for RSA keys (assuming that the other functions are correct)? im having trouble getting my program to decrypt properly, as in certain blocks are not decrypting properly

这段代码是否会给出RSA密钥的正确值(假设其他函数是正确的)?我无法让我的程序正确地解密，因为在某些块中无法正确地解密

this is in python:

这是在python中:

import random
def keygen(bits):
    p = q = 3
    while p == q:
        p = random.randint(2**(bits/2-2),2**(bits/2))
        q = random.randint(2**(bits/2-2),2**(bits/2))
        p += not(p&1)                             # changes the values from 
        q += not(q&1)                             # even to odd

        while MillerRabin(p) == False:            # checks for primality
            p -= 2
        while MillerRabin(q) == False:
            q -= 2
    n = p * q   
    tot = (p-1) * (q-1)
    e = tot
    while gcd(tot,e) != 1:
        e = random.randint(3,tot-1)
    d = getd(tot,e)                       # gets the multiplicative inverse
    while d<0:                            # i can probably replace this with mod
        d = d + tot
    return e,d,n

one set of keys generated:

生成一组键:

e = 3daf16a37799d3b2c951c9baab30ad2d

e = 3 daf16a37799d3b2c951c9baab30ad2d

d = 16873c0dd2825b2e8e6c2c68da3a5e25

d = 16873 c0dd2825b2e8e6c2c68da3a5e25

n = dc2a732d64b83816a99448a2c2077ced

2 个解决方案

#1

Mathematically, your n, e and d appear to respect the RSA rules (i.e. for every prime r which divides n, r² does not divide n, and d is an inverse of e modulo r-1). However, RSA is a bit more than that; it also mandates some padding rules, which govern how a message (a sequence of bytes) is to be transformed into an integer modulo n, and back. The standard padding (see PKCS#1) implies that at least 11 bytes are added to the message, and the result must still be no longer by n. Hence, with a 128-bit modulus like the one you show, the maximum input message length for encryption will be 5 bytes.

从数学上讲，n e和d似乎都遵守RSA规则(即，对于每一个除n的素数r, r2不除n, d是e模r-1的逆)。然而，RSA比这多一点;它还要求使用一些填充规则，这些规则控制如何将消息(一个字节序列)转换为整型modulo n并返回。标准的填充(参见PKCS#1)意味着在消息中至少添加了11个字节，并且结果必须不再是n。

Also, some RSA implementations will refuse to work with RSA keys which are much too small for security. A 128-bit modulus can be factor in a matter of seconds (see this page for a factorization Java applet, which uses ECM and quadratic sieve to factor relatively small numbers such as yours). The current record in factorization is 768 bits; a modulus length of at least 1024 bits is recommended for short-term security. A typical RSA implementation will accept to use 512-bit keys, but many will reject anything shorter than that.

此外，一些RSA实现将拒绝使用RSA密钥，因为RSA密钥对于安全性来说太小了。128位的模量可以在几秒内分解(请参阅本页面中的一个分解Java applet，它使用ECM和二次筛来分解相对较小的数字，比如您的)。分解的当前记录是768位;模长至少为1024位是短期安全性的推荐。一个典型的RSA实现会接受使用512位的密钥，但是很多人会拒绝任何更短的密钥。

Another possible issue is in the relative order of p and q. The equations laid out in PKCS#1 assume that p > q (otherwise, there is an extra subtraction to perform in the CRT part). If you have p < q, then some implementations may get it wrong (I encountered that with Microsoft's RSA standard implementation in Windows). Just compare p with q and swap them if necessary.

另一个可能的问题是p和q的相对顺序，PKCS#1中列出的方程假设p > q(否则，在CRT部分有额外的减法)。如果您有p < q，那么一些实现可能会出错(我在Windows中遇到了Microsoft的RSA标准实现)。只是比较p和q，必要时交换它们。

Still on the practicality level, some widespread RSA implementations will refuse a RSA key such that the public exponent e does not fit within a 32-bit integer (this includes the RSA implementation used in Windows, in particular by Internet Explorer to connect to HTTPS Web sites -- so when I write "widespread" I mean it). RSA security does not seem to be impacted by the choice of e, so it is customary to choose a small e, which speeds up the part which uses the public key (i.e. encryption, as opposed to decryption, or signature verification, as opposed to signature generation). e = 3 is about the best you could do, but for traditional reasons (including an historical misunderstanding on an alleged weakness), e=65537 is often used. You just need to have e relatively prime to p-1 and q-1. In a practical implementation, you choose e first, then loop within the generation for p and q as long as they do not match that additional rule.

仍然在实用层面上,一些普遍的RSA的实现会拒绝这样的RSA密钥,公众指数e并不适合一个32位的整数(这包括RSA的实现中使用Windows,尤其是通过Internet Explorer连接到HTTPS Web站点——所以当我写“广泛”我的意思是)。RSA安全性似乎不受e选项的影响，因此通常选择一个小的e，它加快了使用公钥的部分(即加密，而不是解密，或签名验证，而不是签名生成)。e= 3是你能做的最好的，但是由于传统的原因(包括对所谓的弱点的历史误解)，e=65537经常被使用。你只需要e相对于p-1和q-1。在实际的实现中，您首先选择e，然后在生成中循环p和q，只要它们不匹配该附加规则。

From a security point of view:

从安全的角度来看:

Your generation process is not uniform, in that some prime integers will be selected more often than others. In particular, a prime p such that p+2 is also prime will almost never be selected. With a proper modulus size, this should not be an issue (that special kind of bias was studied and found out not to be a big issue) but it is bad public relations nonetheless.

您的生成过程不是统一的，在这个过程中，一些素数将比其他整数更频繁地被选择。特别地，一个素数p (p+2也是素数)几乎不会被选中。在适当的模量大小下，这应该不是一个问题(研究了这种特殊的偏差，发现它不是一个大问题)，但它仍然是糟糕的公共关系。
Your n may be a bit smaller than your target size, in case both p and q are close to the lower bound of their generation range. A simple way to avoid that is to restrict the range to [sqrt(2)*2^b-1, 2^b] for both p and q.

n可能比目标尺寸小一点，如果p和q都接近它们的生成范围的下界。避免这种情况的一个简单方法是将p和q的范围限制为[sqrt(2)*2b- 1,2b]。
I cannot vouch for the security of the random module you use. A cryptographically secure random number generator is not an easy thing to do.

我不能保证您使用的随机模块的安全性。密码安全的随机数生成器并不是一件容易的事情。
Generally speaking, properly implementing RSA without leaking confidential information through various side channels (timing, cache memory usage...) is not an easy task. If you want security in a practical setup, you should really really use an existing package. I believe that Python has ways to interface with OpenSSL.

一般来说，正确地实现RSA而不通过各种侧面通道(计时、缓存内存使用……)泄漏机密信息并非易事。如果您希望在实际的设置中安全，那么您应该真正使用现有的包。我相信Python有与OpenSSL接口的方法。

#2

I assume you are doing this for fun and learning, and not for something that needs actual security.

我猜你这么做是为了娱乐和学习，而不是为了真正需要安全感的东西。

Here is a few things I noticed (in no particular order):

以下是我注意到的一些事情(没有特别的顺序):

You are not guaranteed that n will have length bits. It might be as short as bits - 4.

你不能保证n有长度位。它可能和位4一样短。
random is not a cryptographically secure random number generator.

random不是密码安全的随机数生成器。
It is common (and just as secure) to select the public exponent, e, to 65537. This is a prime, so you can replace the coprime-check with a divisor check.

选择公共指数e到65537是很常见的(也同样安全)。这是一个素数，所以你可以用除数检查来代替coprime-check。
It is a bit strange the search for e by setting e = tot (the coprime-check is bound to fail).

设置e = tot搜索e有点奇怪(copme -check肯定会失败)。

Otherwise it looks fine. The key seems to work fine, too. Do you have an example of a block that is not decrypting correctly? Remember that you can only encrypt data that is smaller than n. So with a 128-bit key (as in you example) you cannot encrypt all 128-bit numbers.

否则它看起来很好。这把钥匙似乎也能用。你有一个没有正确解密的块的例子吗?请记住，您只能对小于n的数据进行加密。因此，使用128位的密钥(例如在您的示例中)，您不能加密所有128位的数字。

#1