- •Глава 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. Протокол электронной цифровой подписи
41.7. Использование системы открытого распределения ключей Диффи-Хеллмана
Для решения этой проблемы доставки ключа применяют системы открытого распределения ключей. Эти системы позволяют пользователям обмениваться ключами по незащищенным каналам связи. Интересно отметить, что системы открытого распределения ключей базируются на тех же принципах, что и системы шифрования с открытыми ключами. Для примера подробно рассмотрим алгоритм открытого распределения ключей Диффи–Хеллмана.
Безопасность алгоритма открытого распределения ключей Диффи–Хеллмана обусловлена трудностью вычисления дискретных логарифмов в конечном поле (в отличие от легкости дискретного возведения в степень в том же конечном поле).
Предположим, что два пользователя А и В хотят организовать защищенный коммуникационный канал.
1. Обе стороны заранее уславливаются о модуле N (N должен быть простым числом) и примитивном элементе g ZN,
(1 g N –1), который образует все ненулевые элементы множества ZN, т.е.
{g, g2, ..., gN–1 =1} = ZN – {0}.
Эти два целых числа N и g могут не храниться в секрете. Как правило, эти значения являются общими для всех пользователей системы.
2. Затем пользователи А и В независимо друг от друга выбирают собственные секретные ключи kА и kВ (kА и kВ – случайные большие целые числа, которые хранятся пользователями А и В в секрете).
3. Далее пользователь А вычисляет открытый ключ
yA = (mod N),
а пользователь В – открытый ключ
yВ = (mod N).
4. Затем стороны А и В обмениваются вычисленными значениями открытых ключей yA и yВ по незащищенному каналу. (Мы считаем, что все данные, передаваемые по незащищенному каналу связи, могут быть перехвачены злоумышленником.)
5. Далее пользователи А и В вычисляют общий секретный ключ, используя следующие сравнения:
пользователь А: К = = (mod N);
пользователь В: К´ = = (mod N).
При этом К = К´, так как = (mod N).
Схема реализации алгоритма Диффи–Хеллмана показана на следующем рисунке.
Ключ К может использоваться в качестве общего секретного ключа (ключа шифрования ключей) в симметричной криптосистеме.
Кроме того, обе стороны А и В могут шифровать сообщения, используя следующее преобразование шифрования (типа RSA): С = ЕK (М) = МК (mod N).
Для выполнения расшифрования получатель сначала находит ключ расшифрования К* с помощью сравнения
К∙К* 1 (mod N –1),
а затем восстанавливает сообщение
М = DK (C) = CK*(mod N).
Пример. Допустим, модуль N = 47, а примитивный элемент g = 23. Предположим, что пользователи А и В выбрали свои секретные ключи: kА =12 (mod 47) и kВ = 33 (mod 47).
Для того чтобы иметь общий секретный ключ К, они вычисляют сначала значения частных открытых ключей:
yA = = 2312 = 27 (mod 47),
yВ = = 2333 = 33 (mod 47).
После того, как пользователи А и В обменяются своими значениями yA и yВ , они вычисляют общий секретный ключ
К === 3312 = 2733 = 2312∙33 = 25 (mod 47).
Кроме того, они находят секретный ключ расшифрования, используя следующее сравнение:
К∙К* 1 (mod N –1),
откуда К* = 35 (mod 46).
Теперь, если сообщение М =16, то криптограмма
С = МК =1625 = 21 (mod 47).
Получатель восстанавливает сообщение так:
М = СК* = 2135 =16 (mod 47).
Злоумышленник, перехватив значения N, g, yА и yВ, тоже хотел бы определить значение ключа К. Очевидный путь для решения этой задачи состоит в вычислении такого значения kА по N, g, yА, что mod N = yА (поскольку в этом случае, вычислив kА, можно найти К=mod N). Однако нахождение kА по N, g и yА – задача нахождения дискретного логарифма в конечном поле, которая считается неразрешимой.
Выбор значений N и g может иметь существенное влияние на безопасность этой системы. Модуль N должен быть большим и простым числом. Число (N–1)/2 также должно быть простым числом. Число g желательно выбирать таким, чтобы оно было примитивным элементом множества ZN. (В принципе достаточно, чтобы число g генерировало большую подгруппу мультипликативной группы по mod N.)
Алгоритм открытого распределения ключей Диффи– Хеллмана позволяет обойтись без защищенного канала для передачи ключей. Однако, работая с этим алгоритмом, необходимо иметь гарантию того, что пользователь А получил открытый ключ именно от пользователя В, и наоборот. Эта проблема решается с помощью электронной подписи, которой подписываются сообщения об открытом ключе.
Метод Диффи–Хеллмана дает возможность шифровать данные при каждом сеансе связи на новых ключах. Это позволяет не хранить секреты на дискетах или других носителях. Не следует забывать, что любое хранение секретов повышает вероятность попадания их в руки конкурентов или противника.
Преимущество метода Диффи–Хеллмана по сравнению с методом RSA заключается в том, что формирование общего секретного ключа происходит в сотни раз быстрее. В системе RSA генерация новых секретных и открытых ключей основана на генерации новых простых чисел, что занимает много времени.