Основы построения симметричных блочных алгоритмов криптографии на примере шифра DES Стажер ITLab Курылёв А. Л. НИЖНИЙ НОВГОРОД 2003

Содержание Симметричные шифры Классификация симметричных шифров Принцип Кирхгофа Условия стойкости Блочные шифры Архитектура блочных шифров Перестановки Замены Функциональные преобразования Пример составной системы Сети Файстеля СЛАЙД 2

Содержание Алгоритм DES Описание Общая схема Раундовая функция Выработка подключей Режимы шифрования Режим ECB Режим CBC Режим CFB Режим OFB Заключение Литература Вопросы? Комментарии? СЛАЙД 3

Симметричные шифры Одно-ключевые (симметричные) шифры – криптографические алгоритмы процессы за- и расшифровывание в которых отличаются лишь порядком выполнения и направлением некоторых простых шагов (в отличие асимметричных или алгоритмов с открытым ключом). Особенности симметричных шифров: каждый из участников обмена может как зашифровать, так и расшифровать сообщение; необходима специальная служба для изготовления и доставки секретных ключей; позволяют защищать сообщения от прочтения и некоторых видов модификации. не позволяют подтверждать или опровергать авторство сообщений. СЛАЙД 4

Классификация… Требования, предъявляемые к практическим симметричным алгоритмам шифрования: шифр должен быть технически применим для закрытия массивов данных произвольного объема; шифр должен быть эффективно реализуем в виде устройства, имеющего ограниченный объем памяти. Следовательно, криптоалгоритм, должен быть пошаговым – сообщение разбивается на блоки ограниченного размера, и за один шаг шифруется один блок: P = (P 1, P 2,…, P n ), |P i | N, для i от 1 до n, где N максимальный размер блока. Практически всегда размер блока полагают постоянным: |P 1 | = |P 2 | = … = |P n-1 | = N, |P n | N, СЛАЙД 5

Классификация шифров В блочных шифрах результат зашифрования очередного блока зависит только от него самого и не зависит от других блоков шифруемого массива данных: C i = E(P i ). В результате зашифрования двух одинаковых блоков открытого текста одним алгоритмом получаются идентичные блоки шифротекста: P i = P j E(P i ) = E(P j ). В поточных или потоковых шифрах результат зашифрования очередного блока зависит от него самого и, в общем случае, от всех предыдущих блоков массива данных: C i = E(P 1, P 2,…, P i ). СЛАЙД 6

Классификация шифров К потоковым шифрам также относится важный частный случай, когда результат зашифрования очередного блока зависит этого блока и от его номера: C i = E(i, P i ). Иногда потоковыми называют только такие шифры, в которых шифруемый за один шаг блок имеет размер один бит или один символ текста, а шифры с большим размером блока, формально относящиеся к потоковым, причисляют к блочным. СЛАЙД 7

Принцип Кирхгофа Шифр – параметризованный алгоритм, состоящий из процедурной части, и параметров различных элементов данных, используемых в преобразованиях. Раскрытие только процедурной части не должно приводить к увеличению вероятности успешного дешифрования сообщения злоумышленником выше допустимого предела. Особого смысла хранить процедурную часть в секрете нет. В секрете держится некоторая часть параметров алгоритма, которая называется ключом шифра. СЛАЙД 8

Принцип Кирхгофа Следствия: разглашение конкретного шифра (алгоритма и ключа) не приводит к необходимости полной замены реализации всего алгоритма, достаточно заменить только скомпрометированный ключ; ключи можно отчуждать от остальных компонентов системы шифрования хранить отдельно от реализации алгоритма в более надежном месте и загружать их в шифрователь только по мере необходимости и только на время выполнения шифрования. СЛАЙД 9

Условия стойкости Условия стойкости блочного шифра (по К. Шеннону) : рассеивание – один бит исходного текста должен влиять на несколько битов шифротекста, оптимально на все биты в пределах одного блока. При шифровании двух блоков данных с минимальными отличиями между ними должны получаться совершенно непохожие друг на друга блоки шифротекста. Аналогично и для зависимости шифротекста от ключа один бит ключа должен влиять на несколько битов шифротекста; перемешивание – шифр должен скрывать зависимости между символами исходного текста и шифротекста. Если шифр достаточно хорошо «перемешивает» биты исходного текста, то соответствующий шифротекст не содержит никаких статистических, и, тем более, функциональных закономерностей. СЛАЙД 10

Условия стойкости Если шифр обладает обоими указанными свойствами, то любые изменения в блоке открытых данных приведут к тому, что все биты в зашифрованном блоке данных с вероятностью ½ независимо друг от друга так же поменяют свои значения. Такой шифр невозможно вскрыть способом, менее затратным с точки зрения количества необходимых операций, чем полный перебор по множеству возможных значений ключа. СЛАЙД 11

Блочные шифры Если известен закон распределения блоков открытого текста, то, проанализировав статистику блоков шифротекста, можно установить соответствие между ними. Для того чтобы исключить подобную возможность, размер блока должен быть выбран достаточно большим. Для большинства современных шифров блок имеет размер 64 бита, для нее исчерпывающий анализ практически исключен из-за невозможности набрать соответствующую статистику шифротекстов. СЛАЙД 12

Архитектура… Шифр обычно составляют из более простых шифрующих преобразований. Простое шифрующие преобразование – преобразование, которое реализуется аппаратно относительно несложной логической схемой или программно несколькими компьютерными командами. Основные шифрующие преобразования: перестановка (permutation) – перестановка структурных элементов шифруемого блока данных (битов, символов, цифр); замена, подстановка (substitution) – замена группы элементов шифруемого блока на другую группу по индексной таблице; функциональное преобразование (function) – различные сдвиги, логические и арифметические операций. СЛАЙД 13

Перестановки Перестановку можно представить как устройство с n входами и выходами. Имеется n! возможных вариантов коммутации проводов внутри этого устройства (ключей блока перестановок). Свойства блока перестановок: легко может быть аппаратно построен для достаточно больших n; очень неэффективно реализуются программно на процессорах общего назначения; путем использования набора специально сконструированных сообщений (содержащих одну единственную единицу в n-1 различных позициях) можно целиком определить ключ такой системы всего за n-1 операцию. СЛАЙД 14

Перестановки Пример блока перестановок: СЛАЙД 15

Замены Замена (подстановка) может быть представлена устройство с n входами и выходами. Устройство содержит мультиплексор и демультиплексор, а также 2 n внутренних соединений их выводов, которые могут быть выполнены 2 n ! различными способами (ключ блока подстановок). Свойства блока подстановок: включает любые линейные и нелинейные преобразования, может заменить любой входной блок цифр на любой выходной блок; аппаратно реализуется с помощью запоминающих устройств, программно – индексированным чтением из оперативной памяти, размером (в битах): V = 2 n n; СЛАЙД 16

Замены путем перебора 2 n –1 наборов сообщений можно целиком определить ключ такой системы за 2 n –1 операцию. Обычно n – мало и такой анализ реально осуществим. Пример блока подстановок: СЛАЙД 17

Функциональные… Функциональные преобразования унарные и бинарные логические и арифметические операции, реализуемые аппаратно логическими схемами, программно одной- двумя процессорными командами. Обычно используют операции, которые имеются в наборах команд универсальных процессоров и реализованы аппаратно в виде микросхем (инверсия, побитовые «и», «или», «исключающее или», изменение знака, сложение, вычитание, умножение, деление по модулю некоторого числа, циклические сдвиги). СЛАЙД 18

Пример составной системы Составная шифрующая система объединяет S-блоки и P- блоки в единую конструкцию. P-блоки имеют большое количество входов, а S-блоки – небольшое, легко реализуемое количество входов. P-блоки тасуют биты, обеспечивая рассеивание, S-блоки выполняют нелинейные преобразования и обеспечивают перемешивание. Поскольку S-блоки нелинейны, они потенциально увеличивают число единиц, тогда как P-блоки просто двигают единицы с места на место. Результатом может быть непредсказуемая лавина единиц. СЛАЙД 19

Пример составной системы Сложность вскрытия составной шифрующей системы, составленной из относительно простых блоков преобразований, будет намного выше, если структура этой системы отлична от линейной и содержит ветвления, циклы или обратные связи. Компактность реализации алгоритма приводит к идеологии его построения из одинаковых групп преобразований, повторенных нужное число раз (итеративность). СЛАЙД 20

Пример составной системы СЛАЙД 21

Сети Файстеля В сети Файстеля шифрование блока данных осуществляется путем поочередного преобразования двух подблоков данных с использованием некоторой простой процедуры шифрования, называемой раундом шифрования или раундовой функцией шифрования f i. Для любой (необязательно обратимой) функции f i расшифрование осуществляется путем выполнения тех же процедур преобразования, но с использованием подключей K i в обратном порядке. Подключи K i генерируются из ключа K специальными алгоритмами, разрабатываемыми вместе с шифром. СЛАЙД 22

Сети Файстеля СЛАЙД 23 L i, R i – левая и правая части входного блока T i ; ° – любая обратимая бинарная операция; K i – подключ i-го этапа; f i (L i, K i ) – i-я шифрующая функция;

Сети Файстеля Если последовательность раундовых функций палиндромиальна (т.е. если f 1 = f n, f 2 = f n1, f n/2 = f n + 1 n/2, и, в частности, если все f i – одинаковы), то за- и расшифрование различаются только порядком использования подключей. Использование одинаковых функций шифрования позволяет достигнуть итеративности. Размер левой и правой частей блока может изменяться от раунда к раунду, но обычно эти величины постоянны. Если они равны друг другу, то такая схема называется сбалансированной, а если нет то несбалансированной сетью Файстеля. Обычно «°» – операция побитового исключающего ИЛИ, если используется другая подходящая бинарная операция, то сеть Файстеля называется обобщенной. СЛАЙД 24

Алгоритм DES Описание Data Encryption Standard (DES), Data Encryption Algorithm (DEA, DEA-1) – стандарт шифрования данных был принят в качестве криптографического стандарта NIST, ANSI, ISO. Основные параметры: симметричный блочный шифр, размер блока 64 бит; длина ключа – 56 бит (обычно используется 64-битное число, но каждый восьмой бит используется для проверки четности и игнорируется); представляет собой 16 раундовую сбалансированную сеть Файстеля, плюс две перестановки не влияющих на криптостойкость; алгоритм может быть легко реализован аппаратно, программная реализация несколько более сложна. СЛАЙД 25

Алгоритм DES Общая схема СЛАЙД 26

Алгоритм DES Раундовая функция СЛАЙД 27

Алгоритм DES Выработка подключей СЛАЙД 28

Режимы шифрования Режим шифрования (криптографический режим) обычно объединяет базовый шифр, какую-либо обратную связь и ряд простых операций. Безопасность результирующего алгоритма определяется используемым шифром, а не режимом. Различные криптографические режимы применяются с целью: скрыть структуру открытого текста; затруднить манипулирование открытым текстом; обеспечить возможность шифрования нескольких сообщений одним ключом; обеспечить устойчивость к сбоям, добавлению или потере битов. СЛАЙД 29

Режимы шифрования Режим ECB ECB (Electronic Codebook) – режим электронной шифровальной книги, режим простой замены. СЛАЙД 30 ЗашифрованиеРасшифрование

Режимы шифрования Режим ECB Размер сообщения должен быть кратен размеру блока. Возможно шифрование файлов с произвольным доступов (например, записей баз данных). Ошибка в одном бите шифротекста приводит к неверному расшифрованию соответствующего блока открытого текста. При потере (добавлении) битов весь последующий текст становится нечитаемым. Возможны удаление, повтор, подмена блоков без знания ключа и даже алгоритма. Рекомендуется только для шифрования случайных и небольших по размеру данных, например ключей. СЛАЙД 31

Режимы шифрования Режим CBC CBC (Cipher block chaining) – режим сцепление блоков шифра. СЛАЙД 32 ЗашифрованиеРасшифрование

Режимы шифрования Режим CBC Размер сообщения должен быть кратен размеру блока. Шифрование каждого блока зависит от всех предыдущих блоков. Два одинаково начинающихся сообщения будут одинаково зашифрованы до первого различия, против этого применяют вектор инициализации (initialization vector, IV), который не обязательно хранить в секрете. Ошибка в одном бите широтекста текста портит этот блок сообщения и один бит следующего блока. Потеря (добавление) бита полностью искажают весь открытый текст, начиная с этого блока. Возможна подмена последних битов сообщения. Отлично подходит для шифрования файлов. СЛАЙД 33

Режимы шифрования Режим CFB CFB (Cipher-feedback) – режим обратной связи по шифру, режим гаммирования с обратной связью (с зацеплением блоков). СЛАЙД 34 ЗашифрованиеРасшифрование

Режимы шифрования Режим CFB Единица зашифрованных данных может быть меньше размера блока шифра. Шифрование каждого блока зависит от всех предыдущих блоков. Вектор инициализации обязательно должен быть уникален. Ошибка в бите шифротекста влияет на текущий и определенное число следующих блоков открытого текста, затем ошибка самоустраняется. Шифр самовосстанавливается после потери (добавления) бита шифротекста. СЛАЙД 35

Режимы шифрования Режим CFB Возможна подмена последних битов сообщения. Рекомендуется использовать для шифрования разреженного потока данных, например ввода с терминала. СЛАЙД 36

Режимы шифрования Режим OFB OFB (Output-feedback) – режим выходной обратной связи, режим гаммирования. СЛАЙД 37 ЗашифрованиеРасшифрование

Режимы шифрования Режим OFB Единица зашифрованных данных может быть меньше размера блока шифра (что не рекомендуется). Вектор инициализации обязательно должен быть уникален. Нет распространения ошибок – неправильный бит шифротекста приведет к одному неправильному биту открытого текста. Потеря добавление бита шифротекста портит весь открытый текст с этого места. Отлично подходит для шифрования аудио или видео потоков. СЛАЙД 38

Заключение Все современные надежные шифры являются составными, то есть строятся из большого числа относительно несложных шифрующих преобразований так, чтобы в полной мере обеспечить наличие свойств перемешивания и рассеивания. В качестве «строительных элементов» шифров используются битовые перестановки, замены (подстановки) в битовых группах, арифметические и логические операции. При этом наибольшее перемешивание и рассеивание каскада из шифрующих преобразований достигается, если смежные операции в цепочке как можно сильней отличаются друг от друга. СЛАЙД 39

Заключение Наиболее простой и популярный способ создать шифрующие структуры называются сетями Файстеля. Для использование на раундах шифрования обычно требуется больше ключевой информации, чем содержится в ключе шифрования. Для выработки нужного объема ключевой информации в раундах используют различные схемы, от самых простых – повторного использования одних и тех же фрагментов ключа, до наиболее сложных – выработки ключевых элементов с использованием тех же самых шифрующих преобразований, что используются при шифровании. Для того, чтобы скрыть структуру открытого текста, затруднить манипулирование им, обеспечить устойчивость шифра к сбоям, добавлению или потере битов служат различные криптографические режимы. СЛАЙД 40

Литература Шнайер Б. Прикладная криптография. [ Menezes A., van Oorschot P., Vanstone S. Handbook of Applied Cryptography. [ FIPS PUB 46 – Data Encryption Standard (DES). [ FIPS PUB 74 – Guidelines for Implementing and Using the NBS Data. [ FIPS PUB 81 – Des Modes of Operation. [ СЛАЙД 41

Литература Файстель Х. Криптография и компьютерная безопасность. [ Шеннон К. Теория связи в секретных системах [ Винокуров А. Криптография, ее истоки и место в современном обществе. [ СЛАЙД 42

Вопросы? Комментарии? СЛАЙД 43