1

我正在用 Java 实现 RSA 公钥加密算法。它需要生成两个随机素数。我一直在使用 SecureRandom 类来生成两个 1024 位数字来创建一个 2048 位密钥。我使用 BigInteger 类处理数字。我使用 isProbablePrime() 函数来确定它是否为素数，确定性为 100。但是，我注意到该函数对负数返回 true，即使根据定义，素数不能为负数。

4

2 回答 2

2

对于“为什么”这个问题，我们无法给您一个明确的答案。为此，您需要与设计 API 的人交谈。

我倾向于同意@weston 的猜想，即“没关系”；看到这个链接。该链接的另一个要点是，它取决于素数是否为负数的定义。（根据最广泛使用的定义，它们不是，但是......）

但是，我可以告诉你，实现行为是经过深思熟虑的。该方法的实现如下：

public boolean isProbablePrime(int certainty) {
    if (certainty <= 0)
        return true;
    BigInteger w = this.abs();
    if (w.equals(TWO))
        return true;
    if (!w.testBit(0) || w.equals(ONE))
        return false;
    return w.primeToCertainty(certainty, null);
}

注意在测试之前它是如何获取候选人的绝对值的。

这种行为已经存在很长时间了（据我所知）零记录了关于它的 Java 错误报告。这支持@weston 的猜想。

不管isProbablePrime的行为是否正确，务实的解决方案是在测试之前添加一个测试，看看你的候选人是否为阴性。

于 2017-01-08T00:25:57.657 回答
2

在素数上，我指出这可能无关紧要。但重要的是在将 1024 个随机位转换为整数时，您必须考虑哪种方法是正确的；将其视为已签名（就像您一样）或未签名？

因此，例如在 8 位中，如果我随机生成11010011它，则将其211视为无符号整数，它是一个素数。

如果我将相同的位11010011视为有符号整数，-45即使您接受负素数，我也会得到它不是素数。

弄错了，您的代码将错误地排除有效键并错误地接受无效键。如果为了安全起见排除所有负数，那么您将只能得到 1023 位素数（二进制补码负数的最高有效位始终为 1）。

因此，您处理从位到整数的转换的方式能够避免负数并避免负素数的整个问题，并且 RSA 对选择作为密钥的数字只有一种正确的解释。我的猜测是解释是无符号的。

于 2017-01-08T14:51:04.673 回答