这是生成RSA密钥的正确方法吗？

9 投票

2 回答

3652 浏览

提问于 2025-04-15 22:31

这段代码能给我正确的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

加密算法数字签名 rsa 密钥生成公钥加密安全通信解密问题

2 个回答

我猜你这样做是为了好玩和学习，而不是为了需要真正安全性的事情。

以下是我注意到的一些问题（没有特定顺序）：

你不能保证变量 n 的长度一定是 bits。它可能会短到 bits - 4。
random 这个函数并不是一个安全的随机数生成器。
通常情况下，选择公钥指数 e 为 65537 是很常见的做法，这个数字是一个质数，所以你可以用除数检查来替代互质检查。
通过设置 e = tot 来寻找 e 有点奇怪（因为互质检查肯定会失败）。

除此之外，看起来没什么问题。密钥似乎也能正常工作。你有没有一个没有正确解密的块的例子？记住，你只能加密小于 n 的数据。所以如果你用的是 128 位的密钥（就像你例子里那样），你不能加密所有的 128 位数字。

回答于 2025-04-15 由 Python大师

分享举报

从数学上看，你的 n、e 和 d 看起来符合 RSA 的规则（也就是说，对于每个能整除 n 的质数 r，r² 不能整除 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 的微软 RSA 标准实现中遇到过这个问题）。只需比较 p 和 q，如果有必要就交换它们。

在实际应用中，一些广泛使用的 RSA 实现会拒绝使用公共指数 e 超出 32 位整数范围的 RSA 密钥（这包括 Windows 中使用的 RSA 实现，特别是 Internet Explorer 连接 HTTPS 网站时使用的 -- 所以当我说“广泛使用”时，我是认真的）。RSA 的安全性似乎不受 e 选择的影响，因此通常选择一个小的 e，这可以加快使用公钥的部分（也就是加密，相对于解密，或签名验证，相对于签名生成）。e = 3 是一个不错的选择，但出于传统原因（包括对某种弱点的历史误解），e=65537 经常被使用。你只需要确保 e 与 p-1 和 q-1 互质。在实际实现中，你首先选择 e，然后在生成 p 和 q 时循环，直到它们符合这个额外的规则。

从安全的角度来看：

你的生成过程并不均匀，因为某些质数会比其他质数更频繁地被选择。特别是，质数 p 如果 p+2 也是质数，几乎不会被选择。只要模数大小合适，这应该不是问题（这种特殊的偏差已经被研究，发现并不是大问题），但这仍然是个不好的公众形象。
如果 p 和 q 都接近它们生成范围的下限，你的 n 可能会比目标大小小一点。避免这种情况的简单方法是将范围限制在 [sqrt(2)*2^b-1, 2^b] 之间。
我不能保证你使用的 random 模块的安全性。一个 加密安全 的随机数生成器并不是那么容易实现。
一般来说，正确实现 RSA 而不通过各种侧信道（如时间、缓存内存使用等）泄露机密信息并不是一件容易的事。如果你想在实际环境中获得安全性，真的应该 非常非常 使用现有的包。我相信 Python 有办法与 OpenSSL 进行接口。

回答于 2025-04-15 由 Python大师

分享举报

这是生成RSA密钥的正确方法吗？

2 个回答

撰写回答