- •Федеральное агенство по образованию Государственное образовательное учреждение высшего профессионального образования «Санкт-Петербургский государственный электротехнический университет» («лэти»)
- •Введение
- •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. Заключение
- •Список литературы
6.1.2. Хранение ключей
Между сеансами работы программы ключи для всех алгоритмов сохранялись в заданном файле. Пример такого файла приведен в приложении 2. Ключи хранятся в файле в виде чисел в 10-чной – для асимметричных алгоритмов или 16-ричной – для симметричных алгоритмов системе и снабжаются текстовыми комментариями. Поэтому пользователь может легко проанализировать содержимое файла с ключами. Изменение файла вручную не предусмотрено, т.к. в противном случае приходилось бы проверять каждый ключ при считывании. Для предотвращения ручного изменения файла он подвергается процедуре электронной подписи. При загрузке будет выявлено любое изменение файла.
6.1.3. Длина ключа
Максимальная длина для двухключевых алгоритмов, которую может задавать пользователь, определялась 2 условиями.
Генерация ключа и работа алгоритма, использующая этот ключ не должна занимать слишком много времени.
Пользователь должен иметь возможность задавать такую длину ключа, которая в настоящее время считается достаточной для защиты важной информации.
Минимально возможная длина ключа определялась, исходя из удобства реализации. Если длина модуля равна nбит, то сообщение должно рассматриваться как последовательность чисел длиной поn-1 бит. Но еслиn-1 не кратно 8, то реализация чтения данных становится очень неудобной, т.к. придется считывать отдельные биты. Поэтому длина считываемых данных определяется какn/8 – 1 байт. Единица вычитается для ситуации, когдаnкратно 8, что чаще всего и используется. Значит, необходимо, чтобыn/8 – 1>1.
Алгоритм |
наименьшая длина модуля, бит |
наибольшая длина модуля, бит |
RSA |
20 |
2048 |
DSA |
32 |
1024 |
схема Эль-Гамаля |
16 |
1024 |
ГОСТ 34.10-94 |
32 |
1024 |
Данные о длине ключа, при которой обеспечивается достаточная безопасность, взяты из [2] и [3].
6.2. Особенности реализации асимметричных алгоритмов
6.2.1. Модульная арифметика
Алгоритм вычисления ad mod m [1]
Представить dв двоичной системе счисленияd=d02r+…+dr-12 +dr, гдеdi, цифры в двоичном представлении, равны 0 или 1,d0=1.
Положить a0=aи затем дляi=1,…,rвычислить
ai = ai-12 * adi mod m.
arбудет искомым значением.
Решение сравнения ax 1 (mod b) при условии, что (a, b)=1 [1]
Такое сравнение имеет единственное решение при (a,b)=1. Эта задача равносильна поиску целых решений уравненияax+by=1, а решение этого уравнения можно получить с помощью расширенного алгоритма Евклида.
6.2.2. Представление многозначных чисел
При использовании асимметричных алгоритмов постоянно приходится использовать числа намного длиннее 32 и 64 бит. Поскольку язык C++, на котором велась разработка, непосредственно не поддерживает чисел такого размера, то все арифметические операции с этим типом данных приходится разрабатывать самостоятельно.
Многозначное число хранится в виде массива 32-битовых беззнаковых чисел std::vector. Знак числа хранится отдельно. При этом в элементах массива с меньшими индексами хранятся младшие разряды числа.
6.2.3. Сложение многозначных чисел
Сложение происходит аналогично сложению в столбик, но вместо отдельных цифр выступают целые 32-битовые слова. При этом надо учитывать перенос. C++ не позволяет достаточно просто определить, произошел ли перенос. Но существует машинная командаadc– сложить с учетом флага переноса. Поэтому при определении арифметических операций над многозначными числами использовался встроенный вMSVisualC++ ассемблер.