- •Федеральное агенство по образованию Государственное образовательное учреждение высшего профессионального образования «Санкт-Петербургский государственный электротехнический университет» («лэти»)
- •Введение
- •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. Заключение
- •Список литературы
4.3. Схема подписи Эль-Гамаля
Описание алгоритма приведено в [2]. Открытые и секретные ключи те же, что и в схеме шифрования Эль-Гамаля. Перед формирование подписи надо представить сообщение в виде числа, меньшего чем p. Если сообщение слишком большое, то надо либо разбить его на части, либо, что гораздо эффективнее, подписывать дайджест сообщения.
Алгоритм формирования подписи числа m:
Выбрать k– случайное число, взаимно простое сp-1.
Вычислить числа aиb, которые и будут подписью:
a = gk mod p
b – такое что m=(xa + kb) mod (p-1).
Проверка подписи:
Если yaabmodp=gmmodp, то признается что сообщениеmподписано пользователем, который предоставил открытый ключy.
4.4. Алгоритм гост
Это российский стандарт цифровой подписи ГОСТ 34.10-94 [5].
Открытый ключ:
p– простое число
q– простое число, которое делитp-1
a– число меньшее, чемp-1, такое чтоaqmodp=1
y=axmodp
Секретный ключ:
x– число, меньшее чемq
Алгоритм генерации подписи:
выбрать случайным образом число k:k<q
подписью сообщения mбудет пара чисел:
r=(ak mod p) mod q
s=(xr+k*H(m))modq
Алгоритм проверки подписи:
v=H(m)q-2 mod q
z1=(sv) mod q
z2=((q-r)*v) mod q
u=((az1*yz2)mod p) mod q
если u=r, то признается что сообщениеmподписано пользователем, который предоставил открытый ключy.
В стандарте определено, что длина числа pдолжна составлять от 509 до 512 бит или от 1020 до 1024 бит, длина числаq– от 254 до 256 бит. Эти требования связаны с тем, что при таких длинах достигается достаточная вычислительная стойкость. Но алгоритм цифровой подписи будет работать, даже если используются числаpиqдругой длины.
4.5. Хеш-функция SHA
Для использования в криптографических приложениях любая хеш-функция h=H(M) должна удовлетворять следующим требованиям [3]:
Для заданного сообщения Mлегко вычислитьH(M).
Для заданного hвычислительно трудно найтиM, такое чтоH(M)=h.
Для заданного Mвычислительно трудно найти другое сообщениеM1, такое чтоH(M)=H(M1).
Вычислительно трудно найти два случайных сообщения MиM1, таких чтоH(M)=H(M1).
В SHA-1 [7] используются функцииf(t,B,C,D), где 0t79;B,CиD– 32-битовые слова.
f(t,B,C,D) = (BC)((B)D) при 0t19
f(t,B,C,D) =BCDпри 20t39
f(t,B,C,D) = (BC)(BD)(CD) при 40t59
f(t,B,C,D) =BCDпри 60t79
При этом используются логические побитовые операции.
Используется также набор констант:
Kt= 5A827999 при 0t19
Kt= 6ED9EBA1 при 20t39
Kt= 8F1BBCDCпри 40t59
Kt=CA62C1D6 при 40t79
Алгоритм вычисления хеш-функции SHA-1
Вход: сообщение длиной <264бит.
Дополнить сообщение: добавить в конец сообщения 1, затем 0 или более нулей, а затем 64-битовое представление длины сообщения до дополнения. Количество добавленных нулевых битов должно быть таким, чтобы длина дополненного сообщения в битах была кратна 512. Дополненное сообщение состоит из блоков M1,M2, … ,Mn, длиной по 512 бит.
Инициализировать переменные
H0 := 67452301, H1 := EFCDAB89, H2 := 98BADCFE,
H3 := 10325476, H4:= C3D2E1F0
i := 1
Разделить блок Miна 16 32-битовых словw0,w1, …,w15.
Для всех t: 16t79wt:= (wt-3wt-8wt-14wt-16)1, где «n» - циклический сдвиг влево наnбит.
A := H0, B := H1, C := H2, D := H3, E := H4.
Для всех tот 0 до 79
TEMP := (A 5 + f(t, B, C, D) + E + wt + Kt) mod 232;
E := D; D := C; C := B 30; B := A; A := TEMP.
H0 := H0 + A, H1 := H1+B, H2 := H2 + C, H3 := H3 + D, H4 := H4 + E,
где все сложения производятся по модулю 232.
Если i<n, тоi:=i+1 и перейти к шагу 4.
Выход: дайджест длиной 160 бит – конкатенация 32-битовых слов H0 |H1 |H2 |H3 |H4.