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

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

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

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

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

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

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

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

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

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

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

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

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

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

Ссылка на источник