Java - BigInteger strange behaviour

Question

Something strange is going on with BigInteger. I'm trying to implement my own RSA for an assignment. The code is as follows, and work great with small numbers. If I choose p=11, q=5, e=7 and d=23 then the output on the terminal is

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

If I change the numbers with bigger ones, though, it does not work anymore. The following code:

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());
    }
}

Outputs this:

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

I already checked, twice, that the numbers are good for RSA. Precisely

e*d = 4232182107 * 65537 = 1 mod 9998000099

where

9998000099 = 99989 * 99991 (both primes)

Now, from my understanding BigInteger should be unlimited so it should not be a boundary issue... than what could be? I can always implement this with small numbers for my assignment but it's quite ridiculous...

Answer 1

The requirement for e and d isn't that their product is congruent to 1 (mod n), it's that their product must be congruent to 1 (mod φ(n)), according to the Wikipedia page on RSA.

That is the totient function, which for the 2 primes multiplied is (p - 1)(q - 1), or 997800120.

The result of ed (mod φ(n)) is not 1, it's 32589339.

The reason that your smaller numbers worked is because φ(n) for 5 and 11 is 4 * 10 = 40, and 7 * 23 (mod 40) is 1.

You will need to choose a proper d constant for your larger numbers. This is the modular inverse of e with respect to φ(n), which can be calculated with BigInteger's modInverse method.

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

This reveals d to be 2598113033. Using d yields the proper output.

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