Теория проектирования блочного шифра
Принципы Шеннона для смешения и рассеяния спустя пятьдесят лет после того, как были впервые сформулированы остаются краеугольным камнем проектирования хорошего блочного шифра.
Смешение служит для маскировки взаимосвязей между открытым текстом, шифротекстом и ключом. Помните, как даже незначительная зависимость между этими тремя вещами может быть использована при дифференциальном и линейном криптоанализе? Хорошее смешение настолько усложняет статистику взаимосвязей, что не работают даже мощные криптографические средства.
Диффузия распространяет влияние отдельных битов открытого текста на как можно большее количество шифротекста. Это также маскирует статистические взаимосвязи и усложняет криптоанализ.
Для безопасности достаточно одного смешения. Алгоритм, состоящий из единственной зависящей от ключа таблицы соответствия 64 битов открытого текста 64 битам шифротекста был бы достаточно сильным. Проблема в том, что для такой таблицы потребовалось бы слишком много памяти: 1020 байтов. Смысл создания блочного шифра и состоит в создании чего-то похожего на такую таблицу, но предъявляющего к памяти более умеренные требования.
Прием состоит в том, чтобы в одном шифре в различных комбинациях периодически перемежать смешивание (с гораздо меньшими таблицами) и диффузию. Это называется результирующим шифром. Иногда блочный шифр, который включает последовательные перестановки и подстановки, называют сетью перестановок-подстановок (substitution-permutation network), или SP-сетью.
Взгляните снова на функцию f в DES. Перестановка с расширением и Р-блок реализуют диффузию, a S-блоки - смешение. Перестановка с расширением и Р-блок линейны, S-блоки - нелинейны. Каждая операция сама по себе очень проста, но вместе они работают очень хорошо.
На примере DES также можно показать еще несколько принципов проектирования блочного шифра. Первым является идея итеративного блочного шифра При этом предполагается, что простая функция этапа будет последовательно использована несколько раз. Двухэтапный DES не очень силен, чтобы все биты результата зав и-сели от всех битов ключа и всех битов исходных данных, нужно 5 этапов [1078, 1080]. 16-этапный DES - это сильный алгоритм, 32-этапный DES еще сильнее.
Сети Фейстела
Большинство блочных алгоритмов являются сетями Фейстела (Felstel networks). Эта идея датируется нач а-лом 70-х годов. Возьмите блок длиной n и разделите его на две половины длиной n/2: L и R. Конечно, n должно быть четным. Можно определить итеративный блочный шифр, в котором результат j-го этапа определяется результатом предыдущего этапа:

Kj - это подключ, используемый на j-ом этапе, a f - это произвольная функция этапа.
Эту концепцию можно увидеть в DES, Lucifer, FEAL, Khufu, Khafre, LOKI, COST, CAST, Blowfish и других алгоритмах. Почему это так важно? Гарантируется, что эта функция является обращаемой. Так как для объединения левой половины с результатом функции этапа используется XOR, следующее выражение обязательно является истинным:

Гарантируется, что шифр, использующий такую конструкцию, обратим, если можно восстановить исходные данные f на каждом этапе. Сама функция f неважна, он не обязана быть обратимой. Мы можем спроектировать f настолько сложной, насколько захотим, и нам не потребуется реализовывать два различных алгоритма - один для шифрования, а другой для дешифрирования. Структура сети Фейстела автоматически позаботится об этом.
Простые соотношения
DES обладает следующим свойством: если Ek(P) = С, то EK(P’) = С, где Р', С' и К' - побитовые дополнения Р, С и К. Это свойство вдвое уменьшает сложность вскрытия грубой силой. Свойства комплиментарности алгоритма LOKI уменьшают сложность вскрытия грубой силой в 256 раз.
Простое соотношение можно определить так :
Если Еk(Р) = С, то Ef(k) (g(P,K)) = h(C,K)
Где f, g и h - простые функции. Под "простыми функциями" я подразумеваю функции, которые вычисляются легко, намного легче, чем выполнение итерации блочного шифра. В DES f представляет собой побитовое дополнение К, g - побитовое дополнение Р, a h - побитовое дополнение С. Это является результатом вкрапления ключа в часть текста с помощью XOR.
Для хорошего блочного шифра не существует простых соотношений.
Групповая структура
При изучении алгоритма возникает вопрос, не образует ли он группу. Элементами группы являются блоки шифротекста для каждого возможного ключа, а групповой операцией является композиция. Изучение групповой структуры алгоритма представляет собой попытку понять, насколько увеличивается пространство шифрования при множественном шифровании.
Полезным, однако, является не вопрос о том, действительно ли алгоритм является группой, а о том, насколько он близок к группе. Если не хватает только одного элемента, то алгоритм не образует группу, но двойное шифрование было бы - статистически говоря - просто потерей времени. Работа над DES показала, что DES очень далек от группы. Существует также ряд интересных вопросов о полугруппе, получаемой при шифровании DES. Содержит ли она тождество, то есть, не образует ли она группу? Иными словами, не генерирует ли когда-нибудь некоторая комбинация операций шифрования (не дешифрирования) тождественную функцию? Если так, насколько длинна самая короткая такая комбинация?
Целью исследования является оценка пространства ключей для теоретического вскрытия грубой силой, а результат представляет собой наибольшую нижнюю границу энтропии пространства ключей.
Слабые ключи
В хорошем блочном шифре все ключи одинаково сильны. Обычно нет проблем и при алгоритме с малым количеством слабых ключей, таком как DES. Вероятность случайно выбрать один из них очень мала, такой ключ легко проверить и при необходимости отбросить. Однако, иногда эти слабые ключи могут быть задействованы, если блочный фильтр используется как однонаправленная хэш-функция.
Устойчивость к дифференциальному и линейному криптоанализу
Исследование дифференциального и линейного криптоанализа значительно прояснило теорию проектирования хорошего блочного шифра. Авторы IDEA ввели понятие дифференциалов, обобщение основной идеи характеристик. Они утверждали, что можно создавать блочные шифры, устойчивые к вскрытиям такого типа. Результатом подобного проектирования и является IDEA. Позднее это понятие было формализовано, когда Кайса Ниберг (Kaisa Nyberg) и Ларе Кнудсен (Lars Knudsen) показали, как создавать блочные шифры доказуемо безопасные по отношению к дифференциальному криптоанализу. Эта теория была расширена на дифференциалы высших порядков и частичные дифференциалы. Кажется, что дифференциалы высших порядков применимы только к шифрам с малым числом этапов, но частичные дифференциалы прекрасно объединяются с дифференциалами.
Линейный криптоанализ новее, и он все еще совершенствуется. Были определены понятия классификации ключей и нескольких приближений .Была предпринята попытка объединить дифференциальный и линейный криптоанализ в одном вскрытии. Пока неясно, какая методика проектирования сможет противостоять подобным вскрытиям.
Кнудсен добился некоторого успеха, рассматривая некоторые необходимые (но, возможно, не достаточные) критерии того, что он назвал практически безопасными сетями Фейстела- шифров, устойчивых как к дифференциальному, так и к линейному криптоанализу. Ниберг ввел для линейного криптоанализа аналог понятия дифференциалов в дифференциальном криптоанализе .
Достаточно интересной кажется двойственность дифференциального и линейного криптоанализа. Эта двойственность становится очевидной как при разработке методики создания хороших дифференциальных характеристик и линейных приближений, так и при разработке критерия проектирования, обеспечивающего устойчивость алгоритмов к обоим типам вскрытия. Пока точно неизвестно, куда заведет это направление исследований. Для начала Дэймен разработал стратегию проектирования алгоритма, основанную на дифференциальном и линейном криптоанализе.
Проектирование S-блоков
Сила большинства сетей Фейстела - и особенно их устойчивость к дифференциальному и линейному криптоанализу - непосредственно связана с их S-блоками. Это явилось причиной потока исследований, что же образует хороший S-блок.
S-блок - это просто подстановка: отображение m-битовых входов на n-битовые выходы. Ранее я упоминал об одной большой таблице отображения 64-битовых входов на 64-битовые выходы, такая таблица представляла бы собой S-блок размером 64*64 бита. S-блок с  m-битовым входом и n-битовым выходом называется  m*n-битовым S-блоком. S-блоки обычно являются единственным нелинейным действием в алгоритме, именно они обеспечивают безопасность блочного шифра. В общем случае чем S-блоки больше, тем лучше.
В DES восемь различных 6*4-битовых S-блоков. В Khufu и Khafre единственный 8*32-битовый S-блок, в LOKI 12*8-битовый S-блок, а в Blowfish и CAST 8*32-битовые S-блоки. В IDEA S-блоком по сути является умножение по модулю, это 16* 16-битовый S-блок. Чем больше S-блок, тем труднее обнаружить статистические отклонения, нужные для вскрытия с использованием либо дифференциального, либо линейного криптоанализа. Кроме того, хотя случайные S-блоки обычно не оптимальны с точки зрения устойчивости к дифференциальному и линейному криптоанализу, сильные S-блоки легче найти среди S-блоков большего ра з-мера. Большинство случайных S-блоков нелинейны, невырождены и обладают сильной устойчивостью к линейному криптоанализу - и с уменьшением числа входных битов эта доля снижается медленно
Размер т важнее размера n. Увеличение размера n снижает эффективность дифференциального криптоанализа,  но значительно  повышает  эффективность дифференциального  криптоанализа.  Действительно,  если n>2т-т, то наверняка существует линейная зависимость для входных и выходных битов S-блока. И если n>2т, то линейная зависимость существует только для выходных битов.
Заметной частью работы по проектированию S-блоков является изучение логических функций. Для обеспечения безопасности булевы функции, используемые в S-блоках, должны отвечать определенным условиям. Они не должны быть ни линейными, ни аффинными, ни даже быть близкими к линейным или аффинным. Количество нулей и единиц должно быть сбалансированным, и не должно быть никаких корреляций между различными комбинациями битов. При изменении на противоположный любого входного бита выходные биты должны вести себя независимо. Эти критерии проектирования также связаны с изучением функций изгиба: функций, которые, как может быть показано, являются оптимально нелинейными. Хотя они определены просто и естественно, их изучение очень нелегко.
Очень важным свойством представляется лавинный эффект: сколько выходных битов S-блока изменяется при изменении некоторого подмножества выходных битов. Нетрудно задать для булевых функций условия, выполнение которых обеспечивает определенный лавинный эффект, но проектирование таких функций является более сложной задачей. Строгий лавинный критерий (strict avalanche criteria, SAC) обеспечивает, что с изменением одного входного бита изменяется ровно половина выходных битов.. В одной из работ эти критерии рассматриваются в терминах утечки информации .
Несколько лет назад криптографы предложили выбирать S-блоки так, чтобы таблица распределения различий для каждого S-блока была однородной. Это обеспечило бы устойчивость к дифференциальному криптоанализу за счет сглаживания дифференциалов на любом отдельном этапе. Примером такого проектирования является LOKI. Однако такой подход иногда способствует дифференциальному криптоанализу. Действительно, лучшим подходом является минимизирование максимального дифференциала. Кванджо Ким (Kwangjo Kim) выдвинул пять критериев проектирования S-блоков, похожих на критерии проектирования S-блоков DES.
Выбор хороших S-блоков - не простая задача, существует множество различных идей, как лучше сделать это. Можно выделить четыре главных подхода.
Случайно выбрать. Ясно, что небольшие случайные S-блоки небезопасны, но большие случайные S-блоки могут оказаться достаточно хороши. Случайные S-блоки с восемью и более входами достаточно сильны. Еще лучше 12-битовые S-блоки. Устойчивость S-блоков возрастает, если они одновременно являются и случайными, и зависящими от ключа. В ГОЕА используются большие зависящие от ключа S-блоки.
Выбрать и проверить. В некоторых шифрах свойства S-блоков, генерированных случайным образом, проверяются.
Разработать вручную. При этом математический аппарат используется крайне незначительно: S-блоки создаются с использованием интуитивных приемов. Барт Пренел (Bart Preneel) заявил, что "... теоретически интересные критерии недостаточны для выбора булевых функций S-блоков ...", и что "... необходимы специальные критерии проектирования".
Разработать математически. S-блоки создаются в соответствии с математическими законами, поэтому они обладают гарантированной надежностью по отношению к дифференциальному и линейному криптоанализу, а также хорошими диффузными свойствами. Прекрасный пример такого подхода можно найти в .
Существует ряд призывов объединить "математический" и "ручной" подходы, но реально, по видимому, конкурируют случайно выбранные S-блоки и S-блоки с определенными свойствами. Конечно преимуществом последнего подхода является оптимизация против известных методов вскрытия - дифференциального и линейного криптоанализа - но обеспечиваемая этим подходом степень защиты от неизвестных методов вскрытия также неизвестна. Разработчикам DES было известно о дифференциальном криптоанализе, и его S-блоки были оптимизированы соответствующим образом. Скорее всего, о линейном криптоанализе они не знали, и S-блоки DES очень слабы по отношению к такому способу вскрытия . Случайно выбранные S-блоки в DES были бы слабее против дифференциального криптоанализа, но сильнее против линейного криптоанализа.
С другой стороны случайные S-блоки могут не быть оптимальными по отношению к данным способам вскрытия, но они могут быть достаточно большими и, следовательно, достаточно надежными. Кроме того, они, скорее всего, будут достаточно устойчивы и против неизвестных способов вскрытия. Спор все еще кипит, но лично мне кажется, что S-блоки должны быть такими большими, насколько это возможно, случайными и зависеть от ключа.
Проектирование блочного шифра
Проектировать блочный шифр нетрудно. Если вы рассматривает 64-битовый блочный шифр как перестановку 64-битовых чисел, ясно, что почти все эти перестановки безопасны. Трудность состоит в проектировании блочного шифра, который не только безопасен, но также может быть легко описан и просто реализован.
Легко можно спроектировать блочный шифр, если вы используете память, достаточную для размещения S-блоков 48*32. Трудно спроектировать небезопасный вариант DES, если вы собираетесь использовать в нем 128 этапов. При длине ключа 512 битов не стоит беспокоиться о том, нет ли какой-либо зависящей от ключа комплиментарности.