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

根据RSA上的维基百科页面,要求e并且d不是他们的产品与1(mod n)一致,而是他们的产品必须与1(modφ(n))一致.

这是一个完整的函数,对于2个素数乘以(p - 1)(q - 1),即997800120.

结果ED(MODφ(ñ))不是1,它的32589339.

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

您需要d为较大的数字选择适当的常数.这是模逆e相对于?(n),其可与被计算BigInteger的modInverse方法.

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