- •Министерство образования и науки Российской Федерации
- •В.И. Аверченков, м.Ю. Рытов, с.А. Шпичак
- •Брянск Издательство бгту
- •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. Квантовая криптография
- •Контрольные вопросы
- •Приложение
- •Заключение
- •Список использованной и рекомендуемой литературы
- •Учебное издание
- •Аверченков Владимир Иванович Рытов Михаил Юрьевич Шпичак Сергей Александрович
Контрольные вопросы
Дайте понятие шифра простой замены.
Какие шифры стали развитием шифров короткопериодичной замены?
Какие шифры стали развитием шифров биграммной замены?
Назовите основные виды криптографических систем.
Из каких компонентов состоит ключевая система?
Чем различаются понятия многозначной и многоалфавитной замены?
В чем различие между симметричным и асимметричным шифрованием?
В чем различие между пассивной и активной атаками?
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. Практические вопросы повышения надежности.
2.1. Модели шифров и открытых текстов
Математические модели шифра и открытого текста требуются в криптографии для получения и доказательства точных математических результатов. Модели делятся на два класса – алгебраические (детерминированные) и вероятностные (стохастические).
2.1.1. Алгебраические модели шифров.
Алгебраическая модель, предложенная К. Шенноном.
Пусть X, K, Y – конечные множества открытых текстов, ключей и шифртекстов соответственно, |X| > 1, |K| > 1, |Y| > 1, Ek : X Y и Dk: Ek(X) X – правила зашифрования и расшифрования, отвечающие ключу k K, E = {Ek : k K}, и D = {Dk : k K}. Через Ek(X) мы обозначили множество E = {Ek(x) : x X}. Если ключ k K, представляется в виде пары k = (kз, kр), где kз – ключ зашифрования, а kр – ключ расшифрования (причем kз kр), то Ek понимается как Ekз, а Dk – как Dkр.
Определение: Алгебраической моделью шифра назовем совокупность
A = (X, K, Y, E, D)
введенных множеств, для которых выполняются условия
при любых x X и k K выполняется равенство Dk(Ek(x)) = x;
справедливо равенство .
Условие 1) отвечает требованию однозначности расшифрования. Условие 2) означает, что любой элемент y Y может быть представлен в виде Ek(x) для подходящих элементов x X и k K. В общем случае Ek могут быть многозначными отображениями, но здесь мы ограничиваемся изучением лишь однозначных шифров, получивших наибольшее распространение.
Шифр называется эндоморфным, если Y = X. Для эндоморфного шифра правило зашифрования Ek осуществляет биективное отображение множества X на себя. В этом случае удобно рассматривать правила зашифрования как подстановки множества X, и опускать индекс в записи Ek, предполагая, что правила зашифрования пронумерованы ключами. По сути, вся информация об эндоморфном шифре содержится во множествах X и K.
Определение: Подстановочной моделью эндоморфного шифра назовем упрощенную совокупность П = (X, E)
Примеры.
1. Шифр простой замены в алфавите А:
Пусть , где S(A) – симметрическая группа подстановок множества А и L натуральное число. k K, x = (x1, .. xl), y = (y1, .. yl): Ek(x) = (k(x1), .. , k(xl)),
Dk(y) = (k-1(y1), .. , k-1(yl)), где k-1 – подстановка, обратная к k.
Подстановочной моделью данного эндоморфного шифра является совокупность (X, E), для которой e(x1, .. xl) = k(x1), .. , k(xl). Здесь x = x1, .., xl X, e E, а k – ключ, поставленный в соответствие подстановке e.
2. Шифр перестановки.
Пусть X = Y = AL, K SL, где SL - симметрическая группа подстановок множества
{1, 2, .. , L}. k K, x = (x1, .. xL), y = (y1, .., yL):
где k-1 – подстановка, обратная к k.
3. Шифр RSA.
Пусть n = pq (q и p - простые), X = Y = Zn – кольцо вычетов по модулю n.
K = {(n, p, q, a, b): a, b Zn, n = pq, ab 1(mod (n))}, где - функция Эйлера.
k = (kз, kр), где kз = (n, b) и kр = (n, p, q, a) – ключи. Правила зашифрования и расшифрования для x X и y Y определяются формулами
Уточним алгебраическую модель шифра, выбрав за основу модель, в которой открытыми и шифрованными текстами служат шифрвеличины и шифробозначения, с которыми оперирует шифр. Назовем выбранную модель опорным шифром. Будем шифровать фрагменты открытого текста одним из априорно заданных правил зашифрования, составляющих опорный шифр. Назовем эти отображения простыми заменами. Простые замены будем выбирать при помощи вспомогательной последовательности, которую назовем ключевым потоком. Ключевой поток может определяться случайным образом или вычисляться детерминированно в зависимости от выбранного ключа шифра. Большинство шифров использует детерминированный ключевой поток.
Определение: Опорным шифром назовем совокупность
= (U, K, V, E, D),
состоящую из: U и V - множеств шифрвеличин и шифробозначений с которыми оперирует шифр; K – множества ключей (номеров простых замен); E и D – множеств простых замен Ek : U V, k K, и обратных к ним отображений Dk : Ek(U) U.
Если шифр использует s простых замен, то примем в качестве множества ключей опорного шифра множество целых чисел K = {0, 1, …, s – 1}. Опорный шифр определяет способ зашифрования фрагментов открытого текста – шифрвеличин. Для работы с последовательностью шифрвеличин требуется степень опорного шифра.
Определение: l-й степенью опорного шифра назовем совокупность множеств
l = (U l, K l, V l, E (l), D(l)),
где U l, K l, V l - декартовы степени; множество E (l) состоит из отображений , таких что для и
;
множество D (l) состоит из отображений , таких что для и
.
Теперь рассмотрим построение ключевого потока, то есть последовательности k1…kl, kj K, , номеров простых замен, используемых для зашифрования открытого текста .
Имеется два принципиально разных способа построения такой последовательности.
В первом случае она строится случайно. Устройство, вырабатывающее случайный ключевой поток называется случайным генератором ключевого потока. Формально его можно представить отображением : N K*, (С* - множество слов конечной длины в алфавите С), ставящим в соответствие натуральному числу l последовательность из l испытаний некоторой случайной величины, принимающей значение из K с некоторыми ненулевыми вероятностями. Простейший случайный генератор – игровая рулетка.
Во втором случае шифр имеет некоторое, априорно заданное, конечное множество ключей K. Каждому ключу ĸ K и натуральному числу l N ставится в соответствие однозначно определенный ключевой поток k1…kl, ki K, . Этот поток вырабатывается детерминированным генератором ключевого потока.
Определение: пусть
: K N K*
- произвольное отображение, такое, что для любых ĸ K, l N, и некоторых ki K, , (ĸ, l) = k1 … kl, причем {(ĸ, l), ĸ K} = K. Назовем последовательность k1 … kl ключевым потоком, отвечающим ключу ĸ и числу l, а само отображение - детерминированным генератором ключевого потока.
Если шифр использует случайный генератор, ключами шифра считают сами ключевые потоки. В таком случае, допуская вероятность зашифрования последовательности шифрвеличин любой конечной длины, мы получаем шифр с бесконечным множеством ключей. Если же шифр использует детерминированный генератор ключевого потока, множеством ключей является конечное множество K. Характер генератора ключевого потока делит все множество шифров на два класса.
Определение: Совокупность
Н = (l, l N; ),
- степеней опорного шифра, в которых для зашифрования последовательностей шифрвеличин u1,…,ul по правилу ключевой поток строится с помощью случайного генератора , назовем алгебраической моделью шифра с неограниченным ключом (или просто шифром с неограниченным ключом).
Определение: Совокупность
О = (l, l N; ),
- степеней опорного шифра, в которых для зашифрования последовательностей шифрвеличин u1,…,ul по правилу ключевой поток строится с помощью детерминированного генератора , назовем алгебраической моделью шифра с ограниченным ключом (или просто шифром с ограниченным ключом).
Криптографические свойства шифра с ограниченным ключом пределяются в первую очередь, свойствами его генератора ключевого потока. Например, если (ĸ, l) = k’ … k’, для любого ĸ K и подходящего k’ K, то получаем «слабый» шифр простой замены. Если (ĸ, l) = k1 … kp k1 … kp… представляет собой периодическую последовательность (в которой |{k1 … kp}| 2), то получаем более стойкий шифр периодической замены. Например шифр Виженера.