Принципы построения блочных шифров с закрытым ключом
В этой лекции рассматриваются принципы построения современных блочных алгоритмов: операции, используемые в блочных алгоритмах симметричного шифрования; структура блочного алгоритма; требования к блочному алгоритму шифрования. Дается понятие сети Фейстеля.
Понятие композиционного шифра
Будем предполагать, что противнику известен метод шифрования, но неизвестен ключ. Если противник перехватит сообщение НГЛИСА, ему понадобится не более 720 попыток (при использовании метода полного перебора: число возможных перестановок d!=1*2*...*(d-1)*d). В последнем примере d=6, следовательно, число перестановок равно 6!=1*2*3*4*5*6=720. Для того чтобы изучить 720 вариантов на самом деле требуется не так уж много времени. Предположим, что на изучение каждого варианта у противника уходит 1 секунда. Тогда на все 720 попыток потребуется всего 12 минут. Таким образом, не более чем за 12 минут работы противник узнает наш ключ и сможет в дальнейшем расшифровывать все сообщения, закрытые тем же ключом. Если же анализ производится с использованием компьютера, для дешифрации НГЛИСА и поиска ключа потребуется гораздо меньше времени.
Каким образом можно усложнить задачу криптоанализа нашего шифра? Можно увеличивать размер периода перестановки, то есть блока, в котором переставляются символы, например, до тысячи знаков. Однако, во-первых, перебор сотен и тысяч знаков на современных компьютерах производится за доли минуты, а во-вторых, при этом до тысячи символов возрастет и размер ключа. Такой ключ уже достаточно трудно запомнить и использовать. Попробуем пойти по другому пути и применим перед перестановкой в блоке из 6 символов простую замену по методу Цезаря. Обозначим ключ в методе Цезаря k1 (1<=k1<=31), а ключ при перестановке – k2. Тогда общий ключ K = (k1, k2). Таким образом, если К = (5, 436215), это значит, что вначале шифруемые символы заменяются по методу Цезаря с ключом 5, а затем в каждом блоке из шести символов производится перестановка с ключом 436215. Выполним в два этапа шифрование слова СИГНАЛ:
Можно записать также и так:
В результате двух подряд выполненных циклов шифрования слово СИГНАЛ превратилось в УХЛОЧЫ. При этом пространство ключей шифра не изменилось, однако за счет двухкратного шифрования статистические закономерности исходного текста замаскировались сильнее.
В реальных шифрах также используется комбинация нескольких простейших операций над цепочками или блоками знаков. Для повышения криптостойкости эти операции выполняются циклически несколько раз, образуя раунды или шаги. На стойкость шифра влияют такие факторы, как размер блока, размер ключа, количество раундов шифрования. Современные шифры с закрытым ключом обрабатывают только двоичные данные, поэтому в них помимо обычных замены и перестановки применяются некоторые другие специфичные для двоичных чисел операции.
Алгоритмы симметричного шифрования могут обрабатывать исходный текст блоками или потоком. В зависимости от этого различаютблочные алгоритмы симметричного шифрования и поточные. Блок текста рассматривается как неотрицательное целое число либо как несколько независимых неотрицательных целых чисел. Длина блока всегда выбирается равной степени двойки, например, 64, 128, 256бит.
Операции, используемые в блочных алгоритмах симметричного шифрования
Рассмотрим операции, используемые в большинстве алгоритмов симметричного шифрования. Будем при этом помнить, что рассматриваемые операции применяются к двоичным данным. Любая информация, например, изображения или текст, могут быть представлены в двоичном виде. Благодаря этому при шифровании не приходится задумываться о смысле передаваемых сообщений.
Одна из часто используемых операций – операция побитового сложения по модулю 2, обозначаемая XOR или 
. При сложении по модулю 2 операнды обрабатываются поразрядно. В разряде результата ставится единица, если в соответствующих разрядах операндов присутствует нечетное число единиц. Например, сложим по модулю 2 два 16-разрядных числа:
Эта операция имеет очень удобное свойство: вычитание по модулю два есть то же самое, что и сложение, поэтому один из операндов может быть получен путем прибавления к сумме другого операнда.
Также в блочных алгоритмах шифрования широко используется операция сложения по модулю 232 или по модулю 216. Эта операция представляет собой обыкновенное сложение двоичных чисел без учета переноса в старший 32-й или 16-й разряд результата. Например, сложим по модулю 216 два 16-разрядных числа:
Перенос из 15-го разряда, обозначенный в примере как единица в скобках, дальше не используется и поэтому отбрасывается.
Циклический сдвиг передвигает цепочку бит на некоторое число разрядов влево или вправо. Двоичное число при выполнении операции сдвига напоминает длинную гусеницу, выползающую с одной стороны туннеля и заползающую с другой. При циклическом сдвиге влево биты, выходящие слева за разрядную сетку дописываются справа на освободившиеся места. При циклическом сдвиге вправо все биты передвигаются цепочкой вправо, а те, которым не хватает места, переносятся в хвост цепочки.
Например, выполним циклический сдвиг двоичного числа влево на 3 разряда. Для этого будем 3 раза переписывать двоичные цифры, каждый раз смещая их влево на 1 разряд и перенося знаки, выходящие из пятнадцатого разряда на место нулевого.
Аналогично выполняется и циклический сдвиг вправо. Например, при сдвиге вправо на 3 разряда нулевой, первый и второй биты исходного числа выходят из разрядной сетки и запоминаются, все остальные биты перемещаются вправо на 3 позиции, затем запомненные цифры записываются на тринадцатое, четырнадцатое и пятнадцатое места.
При выполнении табличной подстановки группа битов отображается в другую группу битов. При этой операции один блок двоичных данных заменяется по определенному правилу или таблице другим блоком. Например, можно заменять каждую группу из трех двоичных цифр другой группой из трех цифр по следующей таблице:
Если каждое значение, записанное в столбцах "Вход" и "Выход" записать не в двоичном, а в десятичном виде, то ту же самую таблицу замен можно будет записать более кратко, например, так:
Первая цифра в такой записи представляет значение на входе, а вторая – на выходе. Если значения входов упорядочены по возрастанию в обычном порядке, то можно вообще не писать первую цифру, а записать только соответствующие значения выходов:
То есть в качестве замены для значения 3-битового блока выбирается элемент из таблицы замен с порядковым номером, равным значению заменяемого блока.
Если необходимо заменять группы из четырех двоичных цифр, то таблица замен должна содержать уже 16 значений. В общем случае для n-битовых блоков таблица замен должна содержать 2n элементов.
Табличную подстановку в литературе иногда называют заменой с использованием S-блоков или S-box. (Буква S взята от английского слова substitution – подстановка).
С помощью операции перемещения биты сообщения переупорядочиваются. Перемещение называют также permutation или P-блоком.
Структура блочного алгоритма симметричного шифрования
Таким образом, в алгоритмах симметричного шифрования часто используются операции сложения по модулю 2, сложения по модулю 216или 232, циклического сдвига, замены и перестановки.
Эти операции циклически повторяются в алгоритме N раз, образуя так называемые раунды или шаги. Исходными данными для каждого раунда являются выход предыдущего раунда и ключ, который получен по определенному алгоритму из общего ключа шифрования K. Ключ раунда называется подключом Кi. В результате блочный алгоритм шифрования может быть представлен следующим образом (рис. 1):
Рис. 1. Структура блочного алгоритма симметричного шифрования
Блочные алгоритмы шифрования применяются к двоичным данным. В общем случае процедура блочного шифрования преобразовывает n-битный блок открытого текста в k-битный блок зашифрованного текста. Число блоков длины n равно 2n. Для того чтобы преобразование было обратимым, каждый из таких блоков должен преобразовываться в свой уникальный блок зашифрованного текста. Длина блока всегда выбирается равной степени двойки, например, 64, 128, 256 бит.
Требования к блочному алгоритму шифрования
К современным алгоритмам блочного шифрования предъявляют достаточно жесткие требования, связанные с областью применения, возможностью реализации на различных вычислительных платформах и другими факторами. Рассмотрим основные из требований.
- Алгоритм должен обеспечивать высокий уровень стойкости, и эта стойкость не должна основываться на сохранении втайне самого алгоритма.
- Незначительное изменение исходного сообщения должно приводить к существенному изменению зашифрованного сообщения даже при использовании одного и того же ключа.
- Алгоритм должен успешно противостоять атакам по выбранному тексту, то есть таким, чтобы нельзя было узнать ключ, даже зная достаточно много пар (зашифрованное сообщение, незашифрованное сообщение), полученных при шифровании с использованием данного ключа.
- Алгоритм шифрования должен иметь возможность быть реализованым на различных платформах, которые предъявляют различные требования. Для наиболее быстрых приложений используется специальная аппаратура. Несмотря на это, программные реализации применяются также достаточно часто. Поэтому алгоритм должен допускать эффективную программную реализацию на универсальных микропроцессорах. Алгоритм должен также работать на микроконтроллерах и других процессорах среднего размера.
- Алгоритм должен использовать простые операции, которые эффективны на микропроцессорах, т.е. исключающее или, сложение, табличные подстановки, умножение по модулю. Не должно использоваться сдвигов переменной длины, побитных перестановок или условных переходов.
- Алгоритм должен эффективно реализовываться на специализированной аппаратуре, предназначенной для выполнения операций шифрования и расшифрования, то есть реализация алгоритма в виде электронных устройств должна быть экономичной.
- Алгоритм шифрования должен быть применим во многих приложениях. Алгоритм должен быть эффективен при шифровании файлов данных или большого потока данных, при создании определенного количества случайных битов, а также должна быть возможность его использования для формирования односторонней хеш-функции (контрольной суммы).
- Алгоритм должен быть простым для написания кода, чтобы минимизировать вероятность программных ошибок. Также это дает возможность анализа и уменьшает закрытость алгоритма.
- Алгоритм должен допускать любую случайную строку битов нужной длины в качестве возможного ключа (это называется иметь плоское пространство ключей ). Не должно быть "слабых" ключей, облегчающих криптоанализ.
- Алгоритм должен легко модифицироваться для различных уровней безопасности и удовлетворять как минимальным, так и максимальным требованиям.
Некоторое уточнение необходимо сделать относительно пункта 1, требующего высокую криптостойкость алгоритма шифрования. Обычно под "высокой криптостойкостью" понимают, что шифр должен быть стоек по отношению к атаке по выбранному тексту. Это автоматически подразумевает его стойкость по отношению к атакам по шифротексту и по известному тексту. Однако известно, что при атаке по выбранному тексту шифр всегда может быть взломан путем перебора ключей. Поэтому требование стойкости шифра можно уточнить следующим образом: "Шифр стоек (при атаке по выбранному тексту), если для него не существует алгоритма взлома, существенно более быстрого, чем прямой перебор ключей". Интересно, что по состоянию на сегодняшний день ни для одного используемого шифра не доказано строго соответствие этому определению стойкости.
Сеть Фейстеля
На рисунке 1 была представлена общая структура блочного алгоритма шифрования. Понятно, что само преобразование данных выполняется в раундах или шагах шифрования. Какие же действия надо выполнить в одном раунде, чтобы в результате выполнения всего алгоритма получить надежно зашифрованные данные?
Большой вклад в исследования принципов разработки блочных шифров внес американский ученый Х. Фейстель (Horst Feistel). Он, в частности, принимал участие в разработке системы шифрования "Люцифер" фирмы IBM. Фейстель предложил структуру, называемую в настоящее время сетью Фейстеля. Сети Фейстеля получили широкое распространение, так как, с одной стороны, они удовлетворяют всем требованиям к алгоритмам симметричного шифрования, а с другой стороны, достаточно просты и удобны в использовании.
Раунд, организованный по сети Фейстеля имеет следующую структуру. Входной блок делится на несколько частей равной длины. Эти части блока называются ветвями. Так, например, если блок имеет длину 64 бита, используются две ветви по 32 бита каждая. Ветви обрабатываются по отдельности, после чего осуществляется циклический сдвиг всех ветвей влево. В случае двух ветвей каждый раунд имеет структуру, показанную на рисунке 2.
Рис. 2. i-й раунд сети Фейстеля
Функция F называется образующей. Каждый раунд состоит из вычисления функции F для одной ветви и побитового выполнения операции "сумма по модулю 2" результата F с другой ветвью. После этого ветви меняются местами. Число раундов может быть различным для разных алгоритмов. В некоторых алгоритмах рекомендуется от 8 до 32 раундов, в других – больше. В целом увеличение количества раундов увеличивает криптостойкость алгоритма. Возможно, эта особенность и повлияла на столь активное распространение сети Фейстеля, так как для большей криптостойкости достаточно просто увеличить количество раундов, не изменяя сам алгоритм. В последнее время количество раундов не фиксируется, а лишь указываются рекомендуемые пределы.
В последнее время все чаще используются различные разновидности сети Фейстеля для 128-битного блока с четырьмя ветвями. Увеличение количества ветвей, а не размерности каждой ветви связано с тем, что наиболее популярными до сих пор остаются процессоры с 32-разрядными словами, следовательно, оперировать 32-разрядными словами эффективнее, чем с 64-разрядными.
В блочных алгоритмах, построенных на основе сети Фейстеля, основной операцией является вычисление образующей функции F. Эта функция использует подключ раунда и одну ветвь входного блока для вычисления результата. Именно тем, как определяется функция F, системы шифрования и отличаются друг от друга. В некоторых алгоритмах введены также начальные преобразования входного блока данных, придающие некоторую "случайность" входному тексту (это называется рандомизацией данных.) Рандомизация производится для того, чтобы уменьшить естественную избыточность входного сообщения.
УЧЕНЬЕ - СВЕТ, А НЕУЧЕНЬЕ - ЧУТЬ СВЕТ И НА РАБОТУ!
