Java - BigInteger 奇怪的行为

Question

BigInteger 发生了一些奇怪的事情。我正在尝试为一项任务实现我自己的 RSA。 代码如下，适用于小数字。 如果我选择 p=11、q=5、e=7 和 d=23，那么终端上的输出是

Original message is: 19
Encryption of message is: 24
Decryption of message is: 19

但是，如果我将数字更改为更大的数字，它就不再起作用了。以下代码:

import java.math.BigInteger;

class RSAdumb{

public static void main(String[] args) {
    BigInteger m = new BigInteger("19");

    BigInteger p = new BigInteger("99989");
    BigInteger q = new BigInteger("99991");
    BigInteger n = p.multiply(q);

    BigInteger e = new BigInteger("65537");
    BigInteger d = new BigInteger("4232182107");

    BigInteger c = m.modPow(e,n); //Returns a BigInteger whose value is (this^e mod n)
    BigInteger check = c.modPow(d,n);

    System.out.println("Original message is: "+m.toString());
    System.out.println("Encryption of message is: "+c.toString());
    System.out.println("Decryption of message is: "+check.toString());
    }
}

输出这个:

Original message is: 19
Encryption of message is: 5609974360
Decryption of message is: 2710593036

我已经检查过两次，这些数字适合 RSA。正是

e*d = 4232182107 * 65537 = 1 mod 9998000099

在哪里

9998000099 = 99989 * 99991 (both primes)

现在，根据我的理解，BigInteger 应该是无限的，所以它不应该是一个边界问题......而不是什么？我总是可以用少量的数字来完成我的任务，但这太荒谬了……

Answer 1

e 和 d 的要求不是它们的乘积等于 1 (mod n)，而是它们的乘积必须根据 Wikipedia page on RSA 与 1 (mod φ(n)) 一致.

这是 totient 函数，2 个素数相乘是 (p - 1)(q - 1)，即 997800120。

ed (mod φ(n)) 的结果不是 1，而是 32589339。

你的较小数字起作用的原因是因为 5 和 11 的 φ(n) 是 4 * 10 = 40，而 7 * 23 (mod 40) 是 1.

您需要为较大的数字选择一个合适的 d 常量。这是 e 关于 φ(n) 的模逆，可以用 BigInteger's modInverse method 计算.

BigInteger phi = p.subtract(BigInteger.ONE).multiply(q.subtract(BigInteger.ONE));
BigInteger d = e.modInverse(phi);

这表明 d 为 2598113033。使用 d 会产生正确的输出。

Original message is: 19
Encryption of message is: 5609974360
Decryption of message is: 19