Алгоритмы эцп

Цель лекции: познакомиться с некоторыми алгоритмами формирования и проверки электронной цифровой подписи (ЭЦП


, ЭП).

Рассмотренная нами в Лекции 11 схема использования алгоритма RSA при большом модуле N практически не позволяет злоумышленнику получить закрытый ключ и прочитать зашифрованное сообщение. Однако она дает возможность злоумышленнику подменить сообщение от абонента А к абоненту Б, так как абонент А шифрует свое сообщение открытым ключом, полученным от Б по открытому каналу связи. А раз открытый ключ передается по открытому каналу, любой может получить его и использовать для подмены сообщения. Избежать этого можно, используя более сложные протоколы, например, следующий.

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

1. Сначала пользователь А вычисляет числа , то есть шифрует сообщение своим закрытым ключом. В результате этих действий пользователь А подписывает сообщение.
2. Затем пользователь А вычисляет числа , то есть шифрует то, что получилось на шаге 1 открытым ключом пользователя Б. На этом этапе сообщение шифруется, чтобы никто посторонний не мог его прочитать.
3. Последовательность чисел g_i передается к пользователю Б.
4. Пользователь Б получает g_i и вначале вычисляет последовательно числа , используя свой закрытый ключ. При этом сообщение расшифровывается.
5. Затем Б определяет числа , используя открытый ключ пользователя А. За счет выполнения этого этапа производится проверка подписи пользователя А.

• пользователь А не может отказаться от своего сообщения, если он признает, что секретный ключ известен только ему;
• нарушитель без знания секретного ключа не может ни сформировать, ни сделать осмысленное изменение сообщения, передаваемого по линии связи.

Существуют и другие варианты применения алгоритма RSA для формирования ЭЦП. Например, можно шифровать (то есть подписывать) открытым ключом не само сообщение, а хеш-код от него.

Алгоритм RSA можно использовать также и для обмена ключами.

Принцип создания и проверки подписи

Сообщение, предназначенное для подписи, должно быть представлено в виде числа, меньшего модуля Р. При большом размере сообщение разбивается на блоки необходимого размера. В некоторых случаях подписывается не само сообщение, а значение хеш-функции от него. В любом варианте цифровая подпись вычисляется в зависимости от некоторого числа m (m < P).

1. Первый пользователь выбирает случайное секретное число k, взаимно простое с Р-1, и вычисляет число
2. Затем с помощью расширенного алгоритма Евклида необходимо найти значение b в следующем уравнении: Пара чисел (a, b) будет цифровой подписью сообщения m.
3. Сообщение m вместе с подписью (a, b) отправляется пользователю 2.
4. Пользователь 2 получает сообщение m и с использованием открытого ключа первого абонента Y₁ вычисляет два числа по следующим формулам: Если с₁ = с₂, то цифровая подпись первого пользователя верная. Для подписывания каждого нового сообщения должно каждый раз выбираться новое значение k.

Пример вычисления и проверки цифровой подписи

Один из пользователей этой системы связи хочет подписать свое сообщение m=5 цифровой подписью, сформированной по алгоритму Эль-Гамаля. Вначале он должен выбрать себе закрытый ключ, например, Х₁=3 и сформировать открытый ключ Y₁ = 7³ mod 11 = 2. Открытый ключ может быть передан всем заинтересованным абонентам или помещен в базу данных открытых ключей системы связи.

После этого с помощью расширенного алгоритма Евклида находится значение b в уравнении:

Таким образом, пара чисел (8, 9) будет цифровой подписью сообщения m=5.

Так как с₁ = с₂, то цифровая подпись первого пользователя в сообщения m=5 верная.

Источник

• https://www.intuit.ru/studies/courses/691/547/lecture/12393