为什么大型 RSA 密钥不加密为唯一值？

Question

我正在使用 BigInteger 的 probablePrime 方法计算两个 2048 位素数，如下所示：BigInteger.probablePrime(2048, new Random());。我们分别称这些质数为 p 和 q。我正在使用以下代码计算私有指数：BigInteger.TWO.multiply(r).add(BigInteger.ONE).divide(e); 其中 e 相当于 BigInteger.valueOf(3)，r 相当于一个 BigInteger，其值为：(p - 1)(q - 1).

创建加密的 BigInteger 的过程如下：message.modPow(e, r)，其中 message 是一个 BigInteger。

假设我想加密 774356626352684872522728355634287624183747537718011900969524254770659766752605764866132228010801740792162094。这个大整数被 "The quick brown fox jumped over the lazy dog." 转换为二进制，然后再转换为十进制。我的结果是 464326058229369014486528960945777245568243099145851675968955902027904135435059026247893552949145149936678174588724345105141605583511438062567406913039976998983678282605288609470234530610515268764924240227134432014767865301287496131771559993377618477929696113174968779730288058725125905006272019930686696412137679303439126584.

无论我运行上面的代码多少次，它总是加密到相同的精确值。它生成的素数似乎无关紧要 - 对于特定的 message 值，加密值始终为上述值。

这就是它变得特别奇特的地方，如果我生成 512 位素数，结果是唯一的。每次我运行上面的代码，生成 512 位素数而不是 2048 位甚至 1024 位素数，它每次运行都会生成一个唯一的结果。但是，如果我想生成 1024 位或 2048 位素数，无论生成的是什么素数，结果总是一样的。

谁能解释为什么会发生这种情况，或者需要对代码进行哪些更改才能使用 2048 位质数生成唯一的加密整数？具体来说，为什么它适用于 512 位或更低位的素数，而不适用于 1024 位或更大位的素数？如果这不是最完善的问题，我深表歉意，所以如果有什么令人困惑的地方，请不要犹豫，要求澄清。

谢谢。

编辑：这是产生问题的代码：

import java.io.IOException;
import java.math.BigInteger;
import java.security.SecureRandom;

public class Yeet {
    public static void main(String[] args) throws IOException {
        int t = (int) (System.currentTimeMillis() / 1000);

        byte[] date = new byte[]{
          (byte) (t >> 24),
          (byte) (t >> 16),
          (byte) (t >> 8),
          (byte) t,
        };  

        BigInteger p = BigInteger.probablePrime(2048, new SecureRandom(date));
        BigInteger q = BigInteger.probablePrime(2048, new SecureRandom(date));
        BigInteger e = BigInteger.valueOf(3);
        BigInteger r = p.subtract(BigInteger.ONE).multiply(q.subtract(BigInteger.ONE));

        BigInteger message = new BigInteger("774356626352684872522728355634287624183747537718011900969524254770659766752605764866132228010801740792162094");

        System.out.println(message.modPow(e, r));
    }
}

运行想看多少遍就看多少遍。它总是产生 464326058229369014486528960945777245568243099145851675968955902027904135435059026247893552949145149936678174588724345105141605583511438062567406913039976998983678282605288609470234530610515268764924240227134432014767865301287496131771559993377618477929696113174968779730288058725125905006272019930686696412137679303439126584。现在，如果我们在第 16 和 17 行将 2048 换成 512，每个运行都会产生一个唯一值...

Answer 1

您正在执行原始/教科书 RSA，其中加密只是使用 public 指数的模幂运算。好吧，当然还有对整数的一些转换、更改或解释。

现在你的 public 指数非常小：3。所以很可能一个小的输入明文在取幂后比模数更小。 The quick brown fox jumped over the lazy dog. 是 45 个字符/字节，或 360 位。如果您有一个 360 位的数字并用 3 执行取幂，那么您将得到 360 x 3 = 1080 位的值，远低于 2 x 2048 = 4096 位模数，因此不会执行模归约。 2 x 512 = 1024，因此对于这些素数大小，您的值仅比模数大“几位”，因此模数值很重要。

当然，您可以使用值为 65537 的费马第五素数 (F4)。这将导致模数缩减为 360 x 65537 > 4096。但是，为了安全起见，您应该使用 PKCS#1 v2.2 中指定的填充方法。这些将扩展明文值，因此依赖于明文的数字表示将更接近模数，以位为单位。模幂运算的结果实际上将执行至少一些模数减少，因此取决于不同的模数值。

更重要的是，PKCS#1 v1.5 或 PKCS#1 v2.2 中指定的 OAEP 填充本身是随机的，因此加密相同的明文将导致不同的密文 即使使用相同的密钥对/模数。对于更大的密钥大小，即使指数 3 也被认为是安全的，尽管 F4 仍然是大多数 RSA 实现（OpenSSL、Java、C#/.NET 等）的首选。

为什么大型 RSA 密钥不加密为唯一值？

Why aren't large RSA keys encrypting to a unique value?

java

cryptography

rsa

biginteger

key-pair