- •1. Алгоритмы с открытым ключом
- •2.Алгоритмы на основе задачи об укладке ранца
- •3.Сверхвозрастающие ранцы
- •4.Ранцевый механизм. Создание открытого ключа по закрытому.
- •5. Открытое распределение ключей
- •6. Криптографическая система с открытым ключом
- •8. Схема Поллинга-Хеллмана
- •9. Схема Рабина
- •10.Схема Вильямса
- •11. Схема Эль-Гамаля
- •12. Шифрование Эль-Гамаля
- •13. Режим электронной подписи Эль-Гамаля
- •14. Эцп и проблемы аутентификации
- •15. Система формирования эцп (процедуры)
- •16. Однонаправленные хэш-функции
- •17. Основы построения хэш-функций
- •Однонаправленные хэш-функции на основе симметричных блочных алгоритмов
- •Алгоритм md-5
- •Алгоритм sha
- •Отличие md-5 от sha
- •Российский стандарт хэш-функций
- •26.Стандарт цифровой подписи гост р 34.10-94
- •27.Беспроводные сети. Способы зашифрования данных.
- •28.Протокол 802.1 X
- •Алгоритм цп на эллиптических кривых, формирование цп.
- •Алгоритм цп на эллиптических кривых, проверка цп.
- •Алгоритмы удвоения точки эллиптической кривой
- •43 Квантовая криптография
- •Простейший алгоритм генерации секретного ключа (bb84)
11. Схема Эль-Гамаля
Генерация ключей
Генерируется случайное простое число длины битов.
Выбирается случайное целое число такое, что .
Выбирается случайное целое число такое, что .
Вычисляется .
Открытым ключом является тройка , закрытым ключом — число .
Работа в режиме подписи
Цифровая подпись служит для того чтобы можно было установить изменения данных и чтобы установить подлинность подписавшейся стороны. Получатель подписанного сообщения может использовать цифровую подпись для доказательства третьей стороне того, что подпись действительно сделана отправляющей стороной. При работе в режиме подписи предполагается наличие фиксированной хеш-функции , значения которой лежат в интервале .
Подпись сообщений
Для подписи сообщения выполняются следующие операции:
Вычисляется дайджест сообщения :
Выбирается случайное число взаимно простое с и вычисляется
С помощью расширенного алгоритма Евклида вычисляется число , удовлетворяющее сравнению:
Подписью сообщения является пара .
Проверка подписи
Зная открытый ключ , подпись сообщения проверяется следующим образом:
Проверяется выполнимость условий: и . Если хотя бы одно из них не выполняется,то подпись считается неверной.
Вычисляется дайджест
Подпись считается верной, если выполняется сравнение:
12. Шифрование Эль-Гамаля
Генерация ключей
Генерируется случайное простое число длины битов.
Выбирается случайное целое число такое, что .
Выбирается случайное целое число такое, что .
Вычисляется .
Открытым ключом является тройка , закрытым ключом — число .
Работа в режиме шифрования
Шифрсистема Эль-Гамаля является фактически одним из способов выработки открытых ключей Диффи — Хеллмана. Шифрование по схеме Эль-Гамаля не следует путать с алгоритмом цифровой подписи по схеме Эль-Гамаля.
Шифрование
Сообщение шифруется следующим образом:
Выбирается сессионный ключ — случайное целое число такое, что
Вычисляются числа и .
Пара чисел является шифротекстом.
Нетрудно видеть, что длина шифротекста в схеме Эль-Гамаля длиннее исходного сообщения вдвое.
Расшифрование
Зная закрытый ключ , исходное сообщение можно вычислить из шифротекста по формуле:
При этом нетрудно проверить, что
и поэтому
.
Для практических вычислений больше подходит следующая формула:
13. Режим электронной подписи Эль-Гамаля
Цифровая подпись служит для того чтобы можно было установить изменения данных и чтобы установить подлинность подписавшейся стороны. Получатель подписанного сообщения может использовать цифровую подпись для доказательства третьей стороне того, что подпись действительно сделана отправляющей стороной. При работе в режиме подписи предполагается наличие фиксированной хеш-функции, значения которой лежат в интервале .
Для подписи сообщения выполняются следующие операции:
Вычисляется дайджест сообщения :
Выбирается случайное число взаимно простое с и вычисляется
С помощью расширенного алгоритма Евклида вычисляется число , удовлетворяющее сравнению:
Подписью сообщения является пара .
Проверка подписи
Зная открытый ключ , подпись сообщения проверяется следующим образом:
Проверяется выполнимость условий: и . Если хотя бы одно из них не выполняется,то подпись считается неверной.
Вычисляется дайджест
Подпись считается верной, если выполняется сравнение:
Главным преимуществом схемы цифровой подписи Эль-Гамаля является возможность вырабатывать цифровые подписи для большого числа сообщений с использованием только одного секретного ключа. Чтобы злоумышленнику подделать подпись, ему нужно решить сложные математические задачи с нахождением логарифма в поле .