Небольшой глюк в реализации алгоритма RSA

Question

Я пытаюсь реализовать алгоритм RSA , но по какой-то причине мой код ниже не дает правильных результатов (обратите внимание, что отображается только соответствующий код).

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

Пример вывода с использованием 127 и 131 в качестве входных данных простых чисел (обратите внимание, что 16637 - это правильно, а 7683 и 0 - нет):

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

Спасибо за любую помощь!

Answer 1

Комментарии верны.Вы должны использовать modInverse () метод BigInteger для вычисления обратного.Поэтому последняя строка должна быть:

BigInteger d = e.modInverse(totient);

Кроме того, я не совсем уверен, что понимаю условие в цикле while.Может быть, последний && должен быть ||?Лично я бы использовал отдельный метод, который возвращает случайное число в правильном диапазоне.