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...

rgettman · Accepted Answer · 2015-10-20 17:31:14Z

5

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

edited Oct 20, 2015 at 17:31

answered Oct 20, 2015 at 17:20

rgettman

179k30 gold badges282 silver badges365 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

user3753342 Over a year ago

Thanks, You are perfectly right, what a dumbass mistake! I guess the question can be closed!

rgettman Over a year ago

Closing a question in SO means that there were problems with the question that would prevent it from being answered or from being useful. Instead, as the asker of the question, you may accept one answer that you think helps you the best.

Artjom B. · Accepted Answer · 2015-10-20 17:22:16Z

3

You've made an error calculating the private exponent d.

First you need to calculate phi of n: φ(n) = φ(p)φ(q) = (p − 1)(q − 1) = n - (p + q -1)

BigInteger phi = n.subtract(p.add(q).subtract(BigInteger.ONE));

and then you need to take the modular inverse of e with phi as the modulus to get d:

d = e.modInverse(phi);

which results in d = 2598113033.

For reference: Wikipedia

answered Oct 20, 2015 at 17:22

Artjom B.

62k26 gold badges137 silver badges236 bronze badges

Collectives™ on Stack Overflow

Java - BigInteger strange behaviour

2 Answers 2

2 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related