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应该是无限的,所以它不应该是边界问题……而不是可能的？对于我的任务,我总是可以用少量数字实现这一点,但这非常荒谬……

解决方法:

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

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

ed(modφ(n))的结果不是1,它是32589339.

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

您需要为较大的数字选择合适的d常数.这是关于φ(n)的e的模的逆,其可以用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