Алгоритм

Задача дискретного логарифмирования

Проверка подписи

Подпись сообщений

Цифровая подпись Эль-Гамаля

Код для защиты от подлога

Для подписи сообщения выполняются следующие операции:

1. Вычисляется дайджест сообщения :

2. Выбирается случайное число взаимно простое с и вычисляется

3. Вычисляется число .

4. Подписью сообщения является пара .

Зная открытый ключ , подпись сообщения проверяется следующим образом:

1. Проверяется выполнимость условий: и . Если хотя бы одно из них не выполняется,то подпись считается неверной.

2. Вычисляется дайджест

3. Подпись считается верной, если выполняется сравнение:

Задача дискретного логарифмирования заключается в том, чтобы по данным целым , , решить уравнение:

где и — взаимно просты (примечание: если они не взаимно просты, то описанный ниже алгоритм является некорректным; хотя, предположительно, его можно модифицировать, чтобы он по-прежнему работал).

Здесь описан алгоритм, известный как "baby-step-giant-step algorithm", предложенный Шэнксом (Shanks) в 1971 г., работающий за время за . Часто этот алгоритм просто называют алгоритмом "meet-in-the-middle" (потому что это одно из классических применений техники "meet-in-the-middle": "разделение задачи пополам").

Итак, мы имеем уравнение:

где и взаимно просты.

Преобразуем уравнение. Положим

где — это заранее выбранная константа (как её выбирать в зависимости от , мы поймём чуть позже). Иногда называют "giant step" (поскольку увеличение его на единицу увеличивает сразу на ), а в противоположность ему — "baby step".

Очевидно, что любое (из промежутка — понятно, что такого диапазона значений будет достаточно) можно представить в такой форме, причём для этого будет достаточно значений:

Тогда уравнение принимает вид:

откуда, пользуясь тем, что и взаимно просты, получаем:

Чтобы решить исходное уравнение, нужно найти соответствующие значения и , чтобы значения левой и правой частей совпали. Иначе говоря, надо решить уравнение:

Эта задача решается с помощью метода meet-in-the-middle следующим образом. Первая фаза алгоритма: посчитаем значения функции для всех значений аргумента , и отсортируем эти значения. Вторая фаза алгоритма: будем перебирать значение второй переменной , вычислять вторую функцию , и искать это значение среди предвычисленных значений первой функции с помощью бинарного поиска.

Дата добавления: 2015-04-23