- •Министерство образования и науки Российской Федерации
- •В.И. Аверченков, м.Ю. Рытов, с.А. Шпичак
- •Брянск Издательство бгту
- •Isbn 978-5-89838-596-5
- •Редактор издательства т.И. Королева
- •Темплан 2011г., п. 57
- •1. Введение в криптографию 10
- •2. Стойкость криптографических систем 34
- •3. Принципы построения симметричных криптографических алгоритмов 61
- •4. Принципы построения асимметричных криптографических алгоритмов 98
- •5. Криптографические хэш-функции и электронно-цифровая подпись 133
- •6. Организация сетей засекреченной связи 160
- •7.Криптоанализ и перспективные направления в криптографии 183
- •Предисловие
- •1. Введение в криптографию
- •1.1. Краткая история развития криптографических методов.
- •1.2. Основные понятия криптографии
- •1.2.1. Термины и определения
- •1.2.2. Классификация шифров
- •1.2.3. Характер криптографической деятельности
- •Контрольные вопросы
- •2. Стойкость криптографических систем
- •2.1. Модели шифров и открытых текстов
- •2.1.1. Алгебраические модели шифров.
- •2.1.2. Вероятностные модели шифров.
- •2.1.3. Математические модели открытых сообщений.
- •2.2. Криптографическая стойкость шифров
- •2.2.1. Теоретико-информационный подход к оценке криптостойкости шифров
- •2.2.2. Практическая стойкость шифров.
- •2.3. Имитостойкость и помехоустойчивость шифров
- •2.3.1. Имитостойкость шифров. Имитация и подмена сообщения
- •2.3.2. Способы обеспечения имитостойкости
- •2.3.3. Помехостойкость шифров
- •2.3.4. Практические вопросы повышения надежности.
- •Контрольные вопросы
- •3. Принципы построения симметричных криптографических алгоритмов
- •3.1. Виды симметричных шифров. Особенности программной и аппаратной реализации.
- •3.2. Принципы построения блочных шифров
- •3.2.1. Базовые шифрующие преобразования
- •3.2.2. Сеть Файстеля
- •3.3. Современные блочные криптоалгоритмы
- •3.3.1. Основные параметры блочных криптоалгоритмов.
- •3.3.2. Алгоритм des
- •3.3.3. Блочный шифр tea
- •Var key:tLong2x2;
- •Var y,z,sum:longint; a:byte;
- •Inc(sum,Delta);
- •3.3.4. Международный алгоритм idea
- •3.3.5. Алгоритм aes (Rijndael)
- •InverseSubBytes(s);
- •InverseShiftRows(s);
- •InverseSubBytes(s) End;
- •3.4. Принципы построения поточных шифров
- •3.4.1. Синхронизация поточных шифрсистем
- •3.4.2. Структура поточных шифрсистем
- •3.4.3.Регистры сдвига с обратной связью
- •3.4.4. Алгоритм Берленкемпа-Месси
- •3.4.5. Усложнение линейных рекуррентных последовательностей
- •3.5. Современные поточные криптоалгоритмы
- •3.5.1. Алгоритм Гиффорда
- •3.5.2. Алгоритм a5
- •3.6. Режимы использования шифров
- •Контрольные вопросы
- •4. Принципы построения асимметричных криптографических алгоритмов
- •4.1. Математические основы асимметричной криптографии
- •4.1.1. Свойства операций
- •4.1.2. Функция Эйлера. Поле. Теоремы Эйлера - Лагранжа и Ферма
- •4.1.3. Конечные поля
- •4.1.4. Основные алгоритмы
- •Алгоритм разложения чисел на простые множители.
- •4.1.5. Алгоритмы нахождения нод и мультипликативного обратного по модулю
- •4.1.6. Китайская теорема об остатках
- •4.1.7. Символы Лежандра и Якоби. Извлечение корней
- •4.2. Примеры современных асимметричных шифров
- •4.2.1. Криптосистема rsa
- •4.2.2. Взаимосвязь компонентов rsa
- •Слабые моменты реализации rsa
- •4.2.3. Криптосистема Эль-Гамаля
- •4.2.4. Криптосистема Рабина
- •4.2.5. Рюкзачные криптосистемы
- •4.2.6. Шифрсистема Мак-Элиса
- •Контрольные вопросы
- •5. Криптографические хэш-функции и электронно-цифровая подпись
- •5.1. Криптографические хэш-функции
- •5.1.1. Блочно-итерационные и шаговые функции
- •5.1.2. Ключевые функции хэширования
- •5.1.3 Бесключевые функции хэширования
- •5.1.4. Схемы использования ключевых и бесключевых функций
- •5.2. Электронно-цифровая подпись
- •5.2.1. Задачи и особенности электронно-цифровой подписи
- •5.2.2. Асимметричные алгоритмы цифровой подписи на основе rsa
- •5.2.3. Алгоритм цифровой подписи Фиата – Фейге – Шамира
- •5.2.4. Алгоритм цифровой подписи Эль-Гамаля
- •5.2.5. Алгоритм цифровой подписи Шнорра
- •5.2.6. Алгоритм цифровой подписи Ниберга-Руппеля
- •5.2.7. Алгоритм цифровой подписи dsa
- •5.2.8. Симметричные (одноразовые) цифровые подписи
- •Контрольные вопросы
- •6. Организация сетей засекреченной связи
- •6.1. Протоколы распределения ключей
- •6.1.1. Передача ключей с использованием симметричного шифрования
- •6.1.2. Передача ключей с использованием асимметричного шифрования
- •6.1.3. Открытое распределение ключей
- •6.1.4. Предварительное распределение ключей
- •6.1.5. Схемы разделения секрета
- •6.1.6. Способы установления ключей для конференц-связи
- •6.2. Особенности использования вычислительной техники в криптографии
- •6.2.1. Методы применения шифрования данных в локальных вычислительных сетях
- •6.2.2. Обеспечение секретности данных при долгосрочном хранении.
- •6.2.4. Обеспечение секретности ключей при долгосрочном хранении
- •6.2.5. Защита от атак с использованием побочных каналов
- •7.1.2. Атаки на хэш-функции и коды аутентичности
- •7.1.3. Атаки на асимметричные криптосистемы
- •7.2. Перспективные направления в криптографии
- •7.2.1. Эллиптические кривые
- •7.2.2. Эллиптические кривые над конечными полями
- •7.2.3. Алгоритм цифровой подписи ec-dsa
- •7.2.4. Квантовая криптография
- •Контрольные вопросы
- •Приложение
- •Заключение
- •Список использованной и рекомендуемой литературы
- •Учебное издание
- •Аверченков Владимир Иванович Рытов Михаил Юрьевич Шпичак Сергей Александрович
5.1.3 Бесключевые функции хэширования
Обычно требуется, чтобы бесключевые хэш-функции обладали следующими свойствами:
1) однонаправленность, (по Y = h(X) трудно определить X)
2) устойчивость к коллизиям, (по X трудно найти X’, такое, что h(X) = h(X’).
3) устойчивость к нахождению второго прообраза, (трудно найти пару X, X’ такие, что h(X) = h(X’))
Например, хэш-функция CRC-32, представляющая собой контрольную сумму, является линейным отображением и поэтому не соответствует ни одному из этих трех свойств.
Использование в качестве бесключевой хэш-функции функции, построенной на основе алгоритма блочного шифрования в режиме выработки имитовставки, также нецелесообразно, так как обратимость блочного шифрования позволяет подбирать входное сообщение для любого значения свертки при фиксированном и общеизвестном ключе.
Для построения примера хэш-функции, удовлетворяющей свойству 1), рассмотрим функцию, заданную формулой gk(x) = Еk(х) х, где Еk — алгоритм блочного шифрования. Такая функция является однонаправленной по обоим аргументам. Поэтому на ее основе можно построить хэш-функцию, определив одношаговую сжимающую функцию одной из следующих формул:
f(x, H) = EH(x) x или f(х, Н) = Ех(Н) Н.
Первая из этих функций лежит в основе российского стандарта хэш-функции, а вторая - в основе американского стандарта SHA.
Обе приведенные выше шаговые функции хеширования принадлежат семейству:
Не все функции данного семейства стойки к коллизиям. Стойкие к известным методам криптоанализа конструкции шаговых функций хеширования сведены в таблицу.
Таблица 8. Шаговые функции хеширования f(X, Y), использующие блочное шифрование Ek. (длина блока равна длине ключа или ключ дополнен до длины блока)
EY(X) X EY(X Y) X Y EY(X) X Y EY(X Y) X |
EX(Y) Y EX(X Y) X Y EX(Y) X Y EX(X Y) Y |
EX Y(X) X EX Y(Y) Y EX Y(X) Y EX Y(Y) X |
Трудоемкость подбора прообраза для однонаправленной функции или трудоемкость поиска второго- прообраза оцениваются величиной О(2n). В то же время трудоемкость поиска коллизии оценивается величиной О(2n/2), так как в данной ситуации применима атака, основанная на парадоксе "дней рождений".
Значением любой из хэш-функций, построенных из приведенных одношаговых сжимающих функций, является вектор длины n, равной размеру блока. В случае если эта величина оказывается недостаточной, ее можно увеличить, заменив одношаговую функцию f на функцию f’ с удвоенной размерностью значений. Это можно сделать, например, путем двукратного применения функции f с последующим перемешиванием полублоков согласно формуле:
f’(x, Hl, H2) = π(f(x, Hl), f(x, H2)),
в которой π переставляет произвольные полублоки а, b, с, d по правилу π((a,b),(c,d)) = (a,d,c,b) . Такой подход реализован в конструкции одношаговой функции MDC-2.
Другие примеры бесключевых хэш-функций дают известные алгоритмы MD-4, MD-5 и SHA. Они оперируют с блоками длины n, совпадающей с длиной результирующего значения свертки, причем п = 128 для алгоритма MD-4 и п = 160 для MD-5 и SHA. Указанные алгоритмы спроектированы специально с учетом эффективной реализации на 32-разрядных ЭВМ.
При их использовании исходное сообщение М разбивается на блоки длиной т = 512 бит. Последний блок формируется путем дописывания к концу сообщения комбинации 10...0 до получения блока размера 448 бит, к которому затем добавляется комбинация из 64 бит, представляющая битовую длину сообщения. Затем вычисляется значение свертки с использованием одношаговой сжимающей функции, заданной формулой f(x, H)=Ex(H) H, где х - блок сообщения длины т = 512 бит, Н - блок из п бит, а Ех - некоторое преобразование множества блоков. Значение начального вектора определяется в описании преобразования Ех. В стандарте хэш-функции ГОСТ Р 34.11-94 приняты значения п = т = 512. Одношаговая сжимающая функция f(x,H), используемая для вычисления последовательности значений Hi = f(xi, Hi-1), построена на базе четырех параллельно работающих схем блочного шифрования (ГОСТ 28147-89), каждая из которых имеет 256-битовый ключ и оперирует с блоками размера 64 бита. Каждый из ключей вычисляется в соответствии с некоторой линейной функцией от блока исходного сообщения xi и значения Hi-1. Значение Hi, является линейной функцией от результата шифрования, блока исходного сообщения xi, и значения Hi-1. После вычисления значения HN для последовательности блоков M1,M2,..,MN применяют еще два шага вычисления согласно формуле
H = h(M) = f(Z MN, f(L, HN)),
где Z — сумма по модулю два всех блоков сообщения, a L — длина сообщения.