Функция Java XpowYmodN, DiffieHellman

Question

Мне нужно для протокола Диффи-Хеллмана создать функцию XpowYmodN. Я нашел в Интернете следующую функцию:

    public long XpowYmodN(long x, long y, long N) {
    long result = 1;
    final long oneShift63 = ((long) 1) << 63;

    for (int i = 0; i < 64; y <<= 1, i++) {
        result = result * result % N;
        if ((y & oneShift63) != 0)
            result = result * x % N;
    }
    return result;
}

Для этого примера: XpowYmodN(29,83,53) результат равен 43. По подсчетам производителя устройства, результат должен быть 50. Может ли кто-нибудь указать мне, где я делаю это неправильно? Я попробовал с Math.pow(X,Y) % N, для этого примера, и я получил результат 28. Я настроен и хотел бы несколько советов о том, как это исправить. Спасибо.

Answer 1

Ваш ответ правильный. Но ценность, которую предоставляет калькулятор, - это не расчет, а обменный ключ. И ваш ответ относится к общедоступной ценности, которую видит отправитель или получатель.

Answer 2

Я проверил различные числа в этой функции, и она отлично работала. Затем я создал дублирующую функцию, которая использовала следующий код, основанный на ответе Уве Плонуса:

public long XpowYmodN(long x, long y, long N) {
    return BigInteger.valueOf(x).modPow(BigInteger.valueOf(y), BigInteger.valueOf(N)).longValue();
}

Я проверил ваши цифры и получил 43, как и эта функция; так что эта функция, кажется, работает отлично. Человек, который опубликовал 29,83,53 числа, в результате чего 50, кажется, не так. Правильный ответ для 29,83,53 - 43.

Вот полный код, который я использовал:

public class Main {
    public static long XpowYmodN_(long x, long y, long N) {
        long result = 1;
        final long oneShift63 = ((long) 1) << 63;

        for (int i = 0; i < 64; y <<= 1, i++) {
            result = result * result % N;
            if ((y & oneShift63) != 0)
                result = result * x % N;
        }
        return result;
    }

    public static long XpowYmodN(long x, long y, long N) {
        return BigInteger.valueOf(x).modPow(BigInteger.valueOf(y), BigInteger.valueOf(N)).longValue();
    }

    public static void main(String[] args)
    {
        System.out.println("BEGIN main");


        System.out.println(Main.XpowYmodN_(29,83,53));
        System.out.println(Main.XpowYmodN(29,83,53));
    }
}

который дал вывод:

НАЧАТЬ основной
43
43

Answer 3

Почему вы не используете класс java.math.BigInteger? Этот класс имеет метод с именем modPow() который предназначен для использования криптографии.

Использование будет

BigInteger result = BigInteger.valueOf(x).modPow(BigInteger.valueof(y), BigInteger.valueOf(n));

Кстати переменные именованные строчными буквами (n в моем случае).