Защита информации 2 5 (стр. 9 из 14)

вычисляет

– сообщение с подписью

Вычисляем значение хеш-функции, получим

Подпись верна.

Определение Хеш-функции.

Хеш-функцией называется любая функция

, которая строке сообщения произвольной длины ставит в соответствие целое число фиксированной длины.

9. Криптографические алгоритмы

9.1 Шифр Эль-Гамаля

Пусть имеются абоненты

, которые хотят передавать друг другу зашифрованные сообщения, не имея никаких защищённых каналов связи.

Для всей группы абонентов выбирается некоторое большое простое число

и число , такие, что различные степени – различные числа по модулю . Числа и передаются абонентам в открытом виде.

Затем каждый абонент выбирает своё секретное число

, , и вычисляет соответствующе ему открытое число ,

( )

В результате получаем следующую таблицу ().

Абонент	Открытый ключ	Секретный ключ

Табл(). Ключи пользователей в системе Эль=Гамаля.

Алгоритм передачи сообщения

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

Шаг 1. Алиса формирует случайное число

, , вычисляет числа:

(9.1.2)

(9.1.3)

и передаёт пару чисел

абоненту Бобу.

Шаг 2. Боб, получив

, вычисляет

(9.1.4)

/*Пример*/

Алиса хочет передать Бобу сообщение

. Допустим Пусть Боб выбрал для себя секретное число и вычислил по формуле (9.1.1)

Алиса выбирает случайное число

, например , и вычисляет по (9.1.2) и (9.1.3):

.

Теперь Алиса посылает Бобу шифрограмму (17,12). Боб вычисляет по формуле (9.1.4):

Боб расшифровал сообщение

Электронная подпись на базе Эль-Гамаля.

Алиса выбирает большое простое число

и число , такие, что различные степени – это различные числа по модулю . Эти числа передаются или хранятся в открытом виде и могут быть общими для целой группы пользователей. Алиса выбирает случайное число , , которое она держит в секрете. Это её секретный ключ.

Затем она вычисляет число

(9.1.5)

Это число

Алиса публикует в качестве открытого ключа. Заметим, что при больших , зная , невозможно найти (это задача дискретного логарифмирования).

Теперь Алиса может подписывать сообщения. Допустим, она хочет подписать сообщение

. Опишем последовательность действий для построения подписи.

Вначале Алиса вычисляет значение хеш-функции для сообщения

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

(9.1.6)

Далее Алиса вычисляет числа:

(9.1.7)

(9.1.8).

Под

в (9.1.8) подразумевается число, удовлетворяющее уравнению

(9.1.9)

Такое

существует, так как и взаимно просты, и может быть найдено по алгоритму Евклида. Наконец Алиса формирует подписанное сообщение

(9.1.10).

Получив сообщение Боб заново вычисляет значение хеш-функции

и проверяет подпись, используя равенство

(9.1.11)

/*Пример*/

Пусть общие параметры для некоторого сообщества пользователей

. Алиса выбирает свой секретный ключ и вычисляет открытый ключ по формуле (9.1.5):