- •Федеральное агенство по образованию Государственное образовательное учреждение высшего профессионального образования «Санкт-Петербургский государственный электротехнический университет» («лэти»)
- •Введение
- •1. Обзор современного состояния темы
- •2. Алгоритмы и атаки, включенные в состав обучающей программы
- •2.1. Критерии отбора алгоритмов
- •2.2. Симметричные алгоритмы шифрования
- •2.3. Описание симметричных криптографических алгоритмов
- •2.3.1. Алгоритм Blowfish
- •2.3.2. Алгоритм гост
- •3. Алгоритмы шифрования с открытым ключом
- •3.1. Алгоритм rsa
- •3.2. Алгоритм Эль-Гамаля
- •4. Алгоритмы цифровой подписи
- •4.1. Схема rsa
- •4.2. Схема dsa
- •4.3. Схема подписи Эль-Гамаля
- •4.4. Алгоритм гост
- •5. Криптографические атаки
- •5.1. Атака на общий модуль против алгоритма rsa
- •5.2. Атака на выбранный шифртекст против алгоритма rsa
- •5.3. Атака против алгоритма dsa
- •6. Особенности реализации алгоритмов
- •6.1. Управление ключами
- •6.1.1. Генерация ключей
- •6.1.2. Хранение ключей
- •6.1.3. Длина ключа
- •6.2. Особенности реализации асимметричных алгоритмов
- •6.2.1. Модульная арифметика
- •6.2.2. Представление многозначных чисел
- •6.2.3. Сложение многозначных чисел
- •6.2.4. Умножение многозначных чисел
- •6.2.5. Деление многозначных чисел
- •6.3. Особенности реализации симметричных алгоритмов
- •6.3.1. Дополнение сообщений
- •6.3.2. Таблицы подстановки для алгоритма шифрования гост 28147-89
- •6.3.3. Подключи и таблицы подстановки для алгоритма Blowfish
- •6.3.4. Режим использования блочных шифров
- •Проектирование интерфейса
- •7.1. Сценарии использования программы
- •7.2. Пошаговое выполнение симметричных алгоритмов
- •7.3. Пошаговое выполнение асимметричных шифров
- •7.4. Пошаговое выполнение алгоритмов цифровой подписи
- •7.5. Демонстрация работы атак
- •7.5.1. Криптоанализ алгоритма rsa на основе выбранного шифртекста
- •7.5.2. Криптоанализ алгоритма rsa для случая общего модуля
- •8. Оценка скорости работы алгоритма
- •9. Структура диалога
- •10. Заключение
- •Список литературы
5.3. Атака против алгоритма dsa
Для каждой новой подписи с помощью DSAтребуется генерировать новое значениеk, а после создания подписи немедленно уничтожать. Если эти требования не выполняются, то противник может вычислить секретный ключ создателя подписи.
Первый сценарий атаки
Противник узнал значение k, которое использовалось при создании подписи. Конкретный способ, который использовал для этого противник, неважен. Возможно, это значениеkне было уничтожено, или противник использовал какие-либо свойства генератора случайных чисел, который сгенерировалk.
Противник знает:
r= (gkmodp)modq,
s = (k-1 (H(m) + xr)) mod q,
k, m.
Противник вычисляет:
s - k-1*H(m) = k-1rx mod q
т.к. q– простое, то можно найти (k-1*r)-1modq, откуда
x = (s – k-1*H(m))* (k-1*r)-1 mod q.
Второй сценарий атаки
Противник не знает значения k, но он получил две подписи, при создании которых использовалось одно и то же значениеk.
Противник знает:
r= (gkmodp)modq,
s1 = (k-1 (H(m1) + xr)) mod q,
s2 = (k-1 (H(m2) + xr)) mod q,
m1,m2.
Противник производит следующие действия.
s1 – s2 = k-1 (H(m1) – H(m2)) mod q (1)
из уравнения (1) вычисляет k-1modq
зная k-1modq, вычисляетk
когда kизвестно, можно произвести те же вычисления, что и в первом сценарии
6. Особенности реализации алгоритмов
6.1. Управление ключами
6.1.1. Генерация ключей
В данной программе ключи для асимметричных алгоритмов не вводятся пользователем, а генерируются случайным образом. Это объясняется тем, что на ключ часто накладываются специальные условия. Например, в алгоритме RSAчислоnдолжно быть произведением двух больших простых чисел. Поэтому пользователю надо только ввести длину ключа в битах.
Алгоритм генерации простых чисел [3]
Вход: длина числа в битах n.
Сгенерировать случайным образом число pдлинойnбит.
Установить младший бит числа равным 1, т.е. сделать его нечетным.
Последовательно вычислять остаток от деления pна все простые числа от 3 до 1471. Еслиpделится хотя бы на одно из этих чисел, то прервать вычисление остатков, увеличитьpна 2 и повторить шаг 3.
Произвести тест Рабина-Миллера 5 раз. Если pпрошло все тесты, то закончить работу алгоритма, иначе увеличитьpна 2 и перейти к шагу 3.
Выход: число p, которое является простым с вероятностью близкой к 1.
Основная идея данного алгоритма заключается в том, что совсем не обязательно производить разложение числа на множители, для того чтобы убедиться в том, что оно составное. Согласно малой теореме Ферма, если число Nпростое, то для любого целогоa, не делящегося наNвыполняется сравнение
aN-1 1 (modN).
Если же при каком-то aэто сравнение нарушается, можно утверждать, чтоN– составное. Миллер предложил проверять несколько иное условие. ЕслиN– простое число,N-1=2st, гдеtнечетно, то согласно малой теореме Ферма для каждогоaс условием (a,N)=1 хотя бы одна из скобок в произведении
делится на N. Обращение этого свойства можно использовать, чтобы отличать составные числа от простых.
Для простого числа Nне существует чиселa, 1<a<N, для которых нарушается одно из двух условий:
Nне делится наa;
at1 (modN) или существует целоеk, 0k<s, такое, что
Если же Nсоставное число, то, как доказал Рабин, их существует не менее.
Алгоритм Рабина-Миллера, доказывающий, что число не является простым [1]:
Выбрать случайным образом число a, 1<a<N, и проверить для этого числа указанные выше условия.
Если хотя бы одно из них нарушается, то число Nсоставное.
Составное число не будет определено как составное после однократного применения теста Рабина-Миллера с вероятностью не большей 4-1. А вероятность не определить его послеkповторений не превосходит 4-k, т.е. убывает очень быстро.
В данной программе тест Рабина-Миллера применялся 5 раз, т.е. вероятность взять вместо простого числа составное не превосходит 4-5. Сама по себе эта величина не так уж мала. Но 4-k- это самая пессимистичная оценка. Практика показывает, что для большинства составныхNтаких чисел не, а примерно[3].
При разработке программы было выяснено, что проведение теста Рабина-Миллера является довольно длительной операцией, поэтому сначала надо попытаться разделить Nна маленькие простые числа. При этом отсеивается большинство составныхN. Было выяснено, что увеличение скорости генерации простых чисел имеет место при делении на все простые числа до 1500.
В алгоритме DSAтребуется два простых числа,pиq, причемqделитp-1. В этом случае сначала генерируетсяq, затем начинается поискp:
p := q*q+1
Пока pявляется составным, увеличиватьpнаq.
Эта процедура конечна, т.к. доказано, что в арифметической прогрессии
a,a+q,a+ 2q,…,
для которой выполняется условие (a,q)=1, бесконечно много простых чисел. В данном случаеa=1.
В алгоритме цифровой подписи ГОСТ требуется получить число a, такое чтоaqmodp= 1. Для этого выбирается случайное числоt, и. При этом требуемое условие выполняется, т.к.tp-1modp=1 по малой теореме Ферма.