![]() |
Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | |
Этот протокол, опубликованный в 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; Прочитано: 1822 | Нарушение авторского права страницы | Мы поможем в написании вашей работы! |
Воспользуйтесь поиском по сайту: