9

这段代码是否会给我正确的 RSA 密钥值（假设其他函数是正确的）？我无法让我的程序正确解密，因为某些块没有正确解密

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

生成一组密钥：

e = 3daf16a37799d3b2c951c9baab30ad2d

d = 16873c0dd2825b2e8e6c2c68da3a5e25

n = dc2a732d64b83816a99448a2c2077ced

4

2 回答 2

16

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

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

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

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

从安全的角度来看：

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

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

  • 我不能保证random您使用的模块的安全性。加密安全的随机数生成器并非易事。

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

于 2010-05-10T11:45:48.513 回答
5

我假设您这样做是为了娱乐和学习，而不是为了需要真正的安全性。

以下是我注意到的一些事情（排名不分先后）：

  1. 您不能保证 n 会有 length bits。它可能短至bits - 4.

  2. random不是加密安全的随机数生成器。

  3. 选择公共指数 , 到 65537 是很常见的（并且同样安全）。e这是一个素数，因此您可以用除数检查替换互素检查。

  4. e通过设置搜索有点奇怪e = tot（互质检查肯定会失败）。

否则它看起来很好。钥匙似乎也可以正常工作。你有没有正确解密的块的例子吗？请记住，您只能加密小于n. 因此，使用 128 位密钥（如您的示例），您无法加密所有 128 位数字。

于 2010-05-10T08:25:03.010 回答