Little glitch in implementing RSA algorithm

Question

I am trying to implement the RSA algorithm, but for some reason my code below doesn't produce correct results (note that only the relevant code is shown).

BigInteger n = p.multiply(q);
BigInteger totient = (p.subtract(BigInteger.ONE)).multiply(q.subtract(BigInteger.ONE));

Random rand = new Random();
BigInteger e;
do
{
 e = new BigInteger(totient.bitLength(), rand);
} while ((e.compareTo(BigInteger.ONE) <= 0 || e.compareTo(totient) >= 0)
   && !((e.gcd(totient)).equals(BigInteger.ONE)));

BigInteger d = (BigInteger.ONE.divide(e)).mod(totient);

Sample output using 127 and 131 as the prime-number inputs (note that 16637 is correct, but 7683 and 0 aren't):

Public Key: (16637,7683)
Private Key: (16637,0)

Thanks for any help!

Answer 1

The comments are correct. You should use the modInverse() method of BigInteger to compute an inverse. So the last line should be:

BigInteger d = e.modInverse(totient);

Also, I'm not completely certain I understand the condition in the while loop. Maybe the last && should be an ||? Personally, I would use a separate method that returns a random number in the correct range.