python - 这是生成 rsa key 的正确方法吗？

Question

这段代码是否会给我正确的 RSA key 值(假设其他函数是正确的)？我无法正确解密我的程序，因为某些 block 没有正确解密

这是在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

生成的一组 key :

e = 3daf16a37799d3b2c951c9baab30ad2d

d = 16873c0dd2825b2e8e6c2c68da3a5e25

n = dc2a732d64b83816a99448a2c2077ced

Answer 1

从数学上讲，您的 n、e 和 d 似乎遵守 RSA 规则(即对于除 n 的每个素数 r，r2 不除 n，而 d 是 e 模 r-1 的倒数)。然而，RSA 远不止于此；它还规定了一些填充规则，这些规则控制如何将消息(字节序列)转换为整数模 n 并返回。标准填充(见 PKCS#1)意味着至少 11 个字节被添加到消息中，并且结果仍然必须不再是 n。因此，具有 128 位模数
就像您展示的那样，加密的最大输入消息长度为 5 个字节。

此外，一些 RSA 实现将拒绝使用对于安全来说太小的 RSA key 。 128 位模数可以在几秒钟内分解(请参阅 this page 以获取分解 Java 小程序，它使用 ECM 和二次筛法分解相对较小的数字，例如您的)。因式分解的当前记录是 768 位；为了短期安全，建议模数长度至少为 1024 位。典型的 RSA 实现将接受使用 512 位 key ，但许多人会拒绝任何比这更短的 key 。

另一个可能的问题是 p 和 q 的相对顺序。 PKCS#1 中列出的方程假设 p > q(否则，在 CRT 部分需要执行额外的减法运算)。如果您有 p < q，那么某些实现可能会出错(我在 Windows 中使用 Microsoft 的 RSA 标准实现时遇到过这种情况)。只需将 p 与 q 进行比较，并在必要时交换它们。

仍然在实用性层面，一些广泛使用的 RSA 实现将拒绝 RSA key ，使得公共(public)指数 e 不适合 32 位整数(这包括 Windows 中使用的 RSA 实现，特别是 Internet Explorer 用于连接到 HTTPS Web网站——所以当我写“广泛”时，我是认真的)。 RSA 的安全性似乎不受e 的选择影响，所以习惯上选择一个小的e，这会加快使用公钥的部分(即加密，而不是解密，或签名验证，而不是签名生成)。 e = 3 是你能做的最好的，但由于传统原因(包括对所谓弱点的历史误解)，经常使用 e=65537。您只需要让 e 与 p-1 和 q-1 互质即可。在实际实现中，您首先选择 e，然后在 p 和 q 的生成中循环，只要它们不匹配该附加规则。

从安全的角度来看:

您的生成过程并不统一，因为某些素数将比其他素数更频繁地被选择。特别是，几乎永远不会选择素数 p 使得 p+2 也是素数。使用适当的模数大小，这应该不是问题(研究了这种特殊的偏见并发现这不是一个大问题)，但它仍然是糟糕的公共(public)关系。

您的 n 可能比您的目标大小小一点，以防 p 和 q 都接近其生成范围的下限。避免这种情况的一种简单方法是将 p 和 q 的范围限制为 [sqrt(2)*2b-1, 2b]。

我不能保证 random 的安全性你使用的模块。加密安全的随机数生成器不是一件容易的事情。

一般来说，正确实现 RSA 而不通过各种侧 channel (时序、缓存使用......)泄漏 secret 信息并不是一件容易的事。如果您希望在实际设置中获得安全性，您应该真正使用现有的包。我相信 Python 有办法与 OpenSSL 交互.