Студопедия.Орг Главная | Случайная страница | Контакты | Мы поможем в написании вашей работы!  
 

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



Этот протокол, опубликованный в 1984 году, послужил прототипом стандартов США и России электронной цифровой подписи.

Зафиксируем конечное поле , где p – простое число. Пусть g – первообразный вычет по mod p. Вычет является секретным ключом отправителя А, а вычет является его открытым ключом. Обозначим через сообщение (хэш-значение сообщения), которое хочет подписать А. Протокол подписи и проверки.

1) А выбирает случайное секретное , вычисляет , .

2) Отправитель сообщения А, применяя расширенный алгоритм Евклида, вычисляет с помощью секретного ключа x целое число из уравнения m = x∙a + k b (mod (p –1)) и формирует подписанное сообщение (m,a,b) (пара, (a,b) есть подпись сообщения m).

3) Для проверки подписи получатель Б вычисляет и . Если вычисленные значения совпадают, то подпись принимается, в противном случае отвергается.

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

. (*)

Следует отметить, что выполнение каждой подписи по методу Эль – Гамаля требует нового значения k, причем это значение должно выбираться случайным образом. Если нарушитель раскроет когда-либо значение k, повторно используемое отправителем, то он сможет раскрыть секретный ключ x отправителя.

Пример. Выберем: числа p =11, g = 2 и секретный ключ x = 8. Вычисляем значение открытого ключа:

y = gx mod p =28 mod 11 = 3.

Предположим, что исходное сообщение M характеризуется хэш-значением m = 5.

Для того чтобы вычислить цифровую подпись для сообщения M, имеющего хэш-значение m = 5, сначала выберем случайное целое число k = 9. Убедимся, что числа k и (p – 1) являются взаимно простыми. Действительно,

НОД (9, 10) = 1.

Далее вычисляем элементы a и b подписи:

a = gk mod p = 29 mod 11 = 6,

элемент b определяем, используя расширенный алгоритм Евклида:

m = x∙a + k b (mod (p – 1)).

При m = 5, a = 6, x = 8, k = 9, p = 11 получаем 5 = (6∙8 + 9∙b)(mod 10)

Или 9∙b º – 43 (mod 10). Решение: b = 3. Цифровая подпись представляет собой пару: а = 6, b = 3.

Далее отправитель передает подписанное сообщение. Приняв подписанное сообщение и открытый ключ y = 3, получатель вычисляет хэш-значение m = 5 для сообщения M, а затем вычисляет два числа:

1) yaab (mod p) = 36∙63 (mod 11) =10 (mod 11);

2) gm (mod p) = 25 (mod 11) =10 (mod 11).

Так как эти два целых числа равны, принятое получателем сообщение признается подлинным.

Следует отметить, что схема Эль–Гамаля является характерным примером подхода, который допускает пересылку сообщения M в открытой форме вместе с присоединенным аутентификатором (a,b). В таких случаях процедура установления подлинности принятого сообщения состоит в проверке соответствия аутентификатора сообщению.





Дата публикования: 2015-02-18; Прочитано: 1882 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!



studopedia.org - Студопедия.Орг - 2014-2024 год. Студопедия не является автором материалов, которые размещены. Но предоставляет возможность бесплатного использования (0.006 с)...