- •Глава 36. Схемы шифрования rsa, Эль Гамаля, Полига-Хеллмана
- •Часть 5. Шифры с открытым ключом шифрования
- •Глава 36.
- •36.1. Основные понятия модулярной арифметики
- •Основные способы нахождения обратных величин a–1 1 (mod n).
- •36.2. Криптосистема шифрования данных rsa
- •X((Pх)) y (modQ).
- •36.3. Схема шифрования Эль Гамаля
- •36.4. Схема шифрования Полига-Хеллмана
- •Глава 37.
- •Глава 38.
- •38.1. Основные принципы построения протоколов идентификации и аутентификации
- •Доказательство проверяемого a:
- •38.3. Типовые схемы идентификации и аутентификации пользователя информационной системы
- •38.4. Особенности применения пароля для аутентификации пользователя
- •38.5. Взаимная проверка подлинности пользователей
- •38.6. Протоколы идентификации с нулевой передачей знаний
- •38.7. Упрощенный вариант схемы идентификации с нулевой передачей знаний. Протокол Фиата-Шамира
- •38.8. Параллельная схема идентификации с нулевой передачей знаний (с нулевым раскрытием)
- •38.9. Модифицированный протокол Фиата-Шамира
- •38.10. Схема идентификации Шнорра
- •38.11. Схема идентификации Гиллоу-Куискуотера
- •38.12. Способ проверки подлинности, где не требуется предъявлять секретный пароль
- •38.13. Проверка подлинности с помощью систем шифрования с открытым ключом
- •38.14. Биометрическая идентификация и аутентификация пользователя
- •Глава 39.
- •39.1. Основные понятия
- •39.4. Однонаправленные хэш-функции
- •Схемы безопасного хэширования, у которых длина хэш-значения равна длине блока
- •39.5. Отечественный стандарт хэш-функции
- •Глава 40.
- •40.1. Электронная цифровая подпись для аутентификации данных
- •40.2. Алгоритмы электронной цифровой подписи
- •40.3. Алгоритм цифровой подписи rsa
- •Обобщенная схема цифровой подписи rsa
- •40.4. Недостатки алгоритма цифровой подписи rsa
- •40.5. Алгоритм цифровой подписи Эль – Гамаля
- •40.6. Цифровая подпись Эль-Гамаля
- •40.7. Особенности протокола Эль-Гамаля
- •40.8. Алгоритм цифровой подписи dsa
- •40.10. Цифровые подписи с дополнительными функциональными свойствами
- •40.11. Алгоритм неоспоримой цифровой подписи д.Чома
- •40.12. Протокол подписи, позволяющий отправителю сообщения не предоставлять право получателю доказывать справедливость своей подписи
- •Глава 41.
- •41.1. Генерация ключей
- •41.2. Концепция иерархии ключей
- •41.3. Распределение ключей
- •41.4. Протокол аутентификации и распределения ключей для симметричных криптосистем
- •41.5. Протокол для асимметричных криптосистем с использованием сертификатов открытых ключей
- •41.6. Использование криптосистемы с открытым ключом для шифрования и передачи секретного ключа симметричной криптосистемы
- •Длины ключей для симметричных и асимметричных криптосистем при одинаковой их криптостойкости
- •41.7. Использование системы открытого распределения ключей Диффи-Хеллмана
- •41.8. Протокол skip управления криптоключами
- •Глава 42.
- •42.1. Основные понятия конечных полей
- •42.2. Криптографические протоколы. Протокол Диффи-Хеллмана
- •42.3. Протокол электронной цифровой подписи
42.2. Криптографические протоколы. Протокол Диффи-Хеллмана
Пусть p>2 простое число. Эллиптическая а кривая Е определена уравнением
(*)
над конечным простым полем . Предположим, что группа содержит подгруппу простого порядка q, которая порождается точкой . Приведем здесь два протокола, безопасность которых основана на сложности проблемы дискретного логарифмирования в группе . Это протокол Диффи – Хеллмана и протокол электронной цифровой подписи, который реализован в принятом в 1998 году федеральном стандарте США.
Пусть имеется два участника А и Б, которые хотят выработать секретный ключ , обмениваясь несекретной информацией. Предварительно А и Б выбирают уравнение кривой (*), в том числе и простое p, а также точку и простое число q, которое является порядком этой точки в группе . Далее они выполняют следующие шаги.
1) А выбирает случайное число , где , вычисляет точку в группе . Тогда , где . А высылает по открытому каналу связи Б.
2) Б выбирает случайное число , где , вычисляет точку в группе . Тогда , где . Б высылает по открытому каналу связи А.
3) Получив , А вычисляет , решая квадратное уравнение . В результате . Далее А вычисляет . Тогда .
4) Получив , Б вычисляет , решая квадратное уравнение . В результате . Далее Б вычисляет . Тогда .
Легко видеть, что и . Значит , и протокол действительно решает задачу выработки ключа посредством обмена несекретной информацией. Противник располагает двумя точками , где , . Его задача вычислить x – координату точки . Это аналог проблемы Диффи – Хеллмана для группы точек эллиптической кривой.
42.3. Протокол электронной цифровой подписи
Пользователь А публикует эллиптическую кривую (*), в том числе простое число p, точку и простое число q, которое является порядком этой точки в группе . А выбирает свой секретный ключ , и публикует свой открытый ключ из . Пусть вычет – хэш – значение подписываемого сообщения. Чтобы получить подпись для m, А выполняет следующие шаги.
1) А выбирает случайный секретный вычет , где , вычисляет точку =, где представитель класса вычетов выбирается из фиксированного интервала .
2) А вычисляет . Если , то перейти к шагу 1. В противном случае вычислить
.
Если , то перейти к шагу 1. В противном случае пара чисел c, d, где есть подпись для m.
Чтобы проверить подпись А под сообщением m (хэш – значением сообщения), Б выполняет следующие шаги.
1) Б вычисляет и вычеты , .
2) Б вычисляет точку , .
3) Если , то подпись принимается, в противном случае – отвергается.
Замечание. 1) Легко показать, что подпись А не будет отвергнута Б. Действительно, видим, что
,
так как . Поэтому и следовательно . Значит . Из этих рассуждений также следует, что Р является аффинной точкой, то есть и имеет вид .
2) Объем хранимой информации можно уменьшить, если вместо точек G, W хранить их x – координаты.