Симметричные шифры. Свойства, принципы построения. SP-сети. Сети Файстеля.

Симметричными называют шифры, в которых ключ шифрования = ключу дешифрования и неизвестен размер блока.

Cимметричные шифр — способ шифрования, в котором для шифрования и расшифрования применяется один и тот же криптографический ключ.
До изобретения схемы асимметричного шифрования единственным существовавшим способом являлось симметричное шифрование. Ключ алгоритма должен сохраняться в секрете обеими сторонами. Ключ алгоритма выбирается сторонами до начала обмена сообщениями.

Требования

Полная утрата всех статистических закономерностей исходного сообщения является важным требованием к симметричному шифру. Для достижения такого шифр должен иметь «эффект лавины» — сильное изменение шифроблока при 1битном изменении входных
данных (в идеале должны меняться значения 1/2 бит шифроблока).

Также важным требованием является отсутствие линейности (то есть условия f(a) xor f(b) = f(a xor b)), в противном случае облегчается применение дифференциального криптоанализа к шифру.

Общая схема

В настоящее время симметричные шифры — это:

 блочные шифры. Обрабатывают информацию блоками определённой длины (обычно 64, 28 бит), применяя к блоку ключ в установленном порядке, как правило, несколькими циклами перемешивания и подстановки, называемыми раундами.

Результатом повторения раундов является лавинный эффект — нарастающая потеря соответствия битов между блоками открытых и зашифрованных данных.

 поточные шифры, в которых шифрование проводится над каждым битом либо байтом исходного (открытого) текста с использованием гаммирования. Поточный шифр может быть легко создан на основе блочного (например, ГОСТ 28147-86 в режиме гаммирования), запущенного в специальном режиме.

Большинство симметричных шифров используют сложную комбинацию большого количества подстановок и перестановок. Многие такие шифры исполняются в несколько (иногда до 80) проходов, используя на каждом проходе «ключ прохода». Множество «ключей прохода» для всех проходов называется «расписанием ключей» (key schedule). Как правило, оно создается из ключа выполнением над ним неких операций, в том числе перестановок и подстановок.

Типичным способом построения алгоритмов симметричного шифрования является сеть Фейстеля. Алгоритм строит схему шифрования на основе функции F(D, K), где D — порция данных, размеров вдвое меньше блока шифрования, а K — «ключ прохода» для данного прохода. От функции не требуется обратимость — обратная ей функция может быть неизвестна. Достоинства сети Фейстеля — почти полное совпадение дешифровки с шифрованием (единственное отличие — обратный порядок «ключей прохода» в расписании), что сильно облегчает аппаратную реализацию.

Операция перестановки перемешивает биты сообщения по некоему закону. В аппаратных реализациях она тривиально реализуется как перепутывание проводников. Именно операции перестановки дают возможность достижения «эффекта лавины». Операция перестановки линейна — f(a) xor f(b) == f(a xor b)

Операции подстановки выполняются как замена значения некоей части сообщения (часто в 4, 6 или 8 бит) на стандартное, жестко встроенное в алгоритм иное число путем обращения к константному массиву. Операция подстановки привносит в алгоритм нелинейность.

Зачастую стойкость алгоритма, особенно к дифференциальному криптоанализу, зависит от выбора значений в таблицах подстановки (S-блоках). Как минимум считается нежелательным наличие неподвижных элементов S(x) = x, а также отсутствие влияния какого-то бита входного байта на какой-то бит результата — то есть случаи, когда бит результата одинаков для всех пар входных слов, отличающихся только в данном бите.

Параметры алгоритмов

Параметры:

 стойкость

 длина ключа

 число раундов

 длина обрабатываемого блока

 сложность аппаратной/программной реализации

SP-сеть и шифры Файстеля

Способ, которым следует сочетать принципы перемешивания и рассеивания для получения криптографической стойкости, можно описать следующим образом. Мы увидели, что перестановки общего вида не могут быть реализованы для больших значений n, скажем для n = 128, и поэтому мы должны ограничиваться схемами подстановки, имеющими подходящий размер… мы выбрали n = 4 в системе, разработанной в IBM и названной Lucifer. Хотя это может показаться слишком маленьким числом, такая подстановка может оказаться вполне эффективной, если ключ подстановки… выбран верно.Х. Файстель. Криптография и компьютерная безопасность.

Lucifer — проект фирмы IBM 70-х годов по созданию криптоустойчивого блочного шифра. В проекте участвовали, ставшие позднее известными криптографами Хорст Фейстель (англ. Horst Feistel) и Дон Копперсмит (англ. Don Coppersmith). Развития «Люцифера» привело к созданию алгоритма DES.

Первая версия алгоритма использовала блоки и ключи длиной по 48 бит и основывалась на SP-сетях. Последующая модификация алгоритма была запатентована в ноябре того же года (US Patent 3,796,830; Nov 1971), и использовала сеть Фейстеля. В патенте содержится как описание собственно самого алгоритма, так и сети Фейстеля. В этом шифре использовались 64-х разрядные ключи и 32-х битные блоки. И, наконец, последняя версия предложена в 1973 году и оперировала с 128-мибитными блоками и ключами.

Структура алгоритма Люцифер образца июня 1971 года представляет из себя «сендвич» из слоёв двух типов, используемыех по очереди - так называемые SP-сети(или подстановочно-перестановочная сеть). Первый тип слоя — P-блок разрядности 128 бит, за ним идёт второй слой, представляющий из себя 32 модуля, каждый из которых состоит их двух четырёхбитных S-блоков, чьи соответствующие входы закорочены и на них подаётся одно и то же значение с выхода предыдущего слоя. Но сами блоки подстановок различны (отличаются таблицами замен). На выход модуля подаются значения только с одного из S-блоков, какого конкретно определяется одним из битов в ключе, номер которого соответствовал номеру S-блока в структуре. Упрощённая схема алгоритма меньшей разрядности и неполным числом раундов приведена на рисунке. В ней используется 16 модулей выбора S-блоков(всего 32 S-блока), таким образом такая схема использует 16-битный ключ.

Рассмотрим теперь, как будет меняться шифротекст, в приведённом выше алгоритме, при изменении всего одного бита. Для простоты возьмём таблицы замен S-блоков такими, что если на вход S-блока подаются все нули, то и на выходе будут все нули. В силу нашего выбора S-блоков, если на вход шифрующего устройства подаются все нули, то и на выходе устройства будут все нули. В реальных системах такие таблицы замен не используются, так как они сильно упрощают работу криптоаналитика, но в нашем примере они наглядно иллюстрируют сильную межсимвольную взаимосвязь при изменении одного бита шифруемого сообщения. Видно, что благодаря первому P-блоку единственная единица сдвигается перемещается в центр блока, затем следующий нелинейный S-блок «размножает» её, и уже две единицы за счёт следующего P-блока изменяют своё положение и т.д. В конце устройства шифрования, благодаря сильной межсимвольной связи, выходные биты стали сложной функцией от входных и от используемого ключа. В среднем на выходе половина бит будет равна «0» и половина «1».

По своей сути сеть Фейстеля является альтернативой SP-сетям и используется намного шире. С теоретической точки зрения раундовая функция шифрования может быть сведена к SP-сети, однако сеть Фейстеля является более практичной, так как шифрование и дешифрование может вестись одним и тем же устройством, но с обратным порядком используемых ключей. Вторая и третья версия алгоритма(использующие сеть Фейстеля) оперировали над 32-битными блоками с 64-битным ключом и 128-битными блоками со 128-битными ключами. В последней(третьей) версии раундовая функция шифрования была устроена очень просто — сначала шифруемый подблок пропускался через слой 4-битных S-блоков(аналогично слоям в SP-сетях, только S-блок является константным и не зависит от ключа), затем к нему по модулю 2 добавлялся раундовый ключ, после чего результат пропускался через P-блок.

Файстель в своей статье представил способ организации шифра по Шеннону. Этот шифр обладал хорошими свойствами перемешивания и рассеивания. Для достижения вышеозначенного эффекта предлагалось использовать блоки подстановок и перестановок. Архитектура подобных шифров носит название SP-сети, от двух названий используемых в ней компонентов: S-box и P-box.

Данные представлялись в виде подблоков небольшого размера, например, в 3 или 4 бита. Затем использовалась заранее подготовленная таблица подстановки (например, рис. 4.4), названная Файстелем S-Box (от substitution – в английском языке обозначающего подстановку или замену) и окрещенная в русской терминологии S-блоком и узлом (иногда еще говорят, блоком) замены.

Подставляя значение входных данных в левую колонку таблицы, получаем соответствующее значение подстановки в правой колонке. Как в левой, так и в правой колонках все значения должны быть различны, иначе, заменив однажды данные в соответствии с таблицей, мы не сможем однозначно их восстановить позже.

Читатель, ознакомившийся со второй главой руководства, возможно, сразу предложит способ взлома шифра, использующего таблицу замен, – это простой частотный анализ. В роли букв латинского алфавита из классических примеров здесь выступят всевозможные двоичные последовательности – комбинации из четырех битов. Чтобы сделать схему с таблицей замен стойкой к анализу, требуется значительно увеличить размер обрабатываемых двоичных последовательностей, чтобы во много раз усложнить частотный анализ. Для этого надо будет использовать например 128-битовую таблицу замен, а следовательно, хранить все 128 значений 128-битовых векторов. Для этого понадобится 16 kb памяти только для одной таблицы. Кроме того, возникает вопрос об использовании такой таблицы в качестве ключа – она все-таки слишком громоздка. Это означает, что необходимо придумать способ расширить небольшой по размеру ключ до необходимого размера и модифицировать постоянную таблицу в соответствии с ним. В силу явных трудностей с реализацией метода сотрудники Bell Laboratories обратили внимание еще и на таблицы перестановок (рис. 4.5).

Таблица перестановок была названа P-Box (от permutation – перемешивание) или узел (блок) перестановки по аналогии с узлом (блоком) замены. С ее помощью в блоке данных биты переставляются так, чтобы затруднить частотный анализ. При этом даже для сравнительно небольших блоков мы получаем очень большое пространство возможных ключей, равное по мощности N! Например, для 16 битового блока 16! = 20922789888000). Впечатляющее число, не правда ли?

Однако для блока перестановки легко придумать криптографическую атаку, которая позволит быстро (всего за N-1 операций, если блок перестановки состоит из N элементов) раскрыть структуру его содержимого. Немного присмотревшись к рис. 4.5, читатель может увидеть, что для этого достаточно подать на вход строки битов, содержащие одну единицу и остальные нули: то есть последовательность.

После этого единица на выходе будет соответствовать тому элементу, на место которого переставляется исходный единичный бит.

Если криптоаналитик получит доступ к шифровальной машине (или программе), то, просто подставив все векторы, легко получит формулу преобразования данных и сможет раскрывать все тексты, зашифрованные с ее помощью.

Таким образом, у нас есть два различных способа преобразования данных, каждый из которых уязвим к определенному виду криптоатак. При этом мы знаем, что с точки зрения формального подхода наиболее эффективным шифром из всех возможных блочных шифров является тот, который может преобразовать любой возможный блок открытого текста в любой возможный блок шифрованного текста. И естественно, это преобразование должно быть обратимым. Такой шифр можно отнести к шифрам на основе простой подстановки, который в упрощенном варианте был описан S-блоком.

Теперь вернемся к реальности и проведем простой расчет. Если блок шифра имеет длину n битов, то имеется 2n различных двоичных блоков и (2n)! способов, с помощью которых можно зашифровать один блок текста. Количество битов ключа, необходимых для выбора одного из этих способов, огромно – оно равно log2{2n)!}. Это неприемлемо большое число даже при небольших значениях n. Например, при n, равным 8, нам потребуется хранить ключ длиной почти в 2000 битов. Плюс ко всему простые подстановки на малых алфавитах можно эффективно раскрывать посредством составления частотных таблиц для знаков шифрованного текста. Мы оказываемся перед дилеммой – нам нужны блоки больших размеров, но мы не сможем эффективно их использовать из-за слишком большой длины ключа.

Разрешить ее можно, пойдя по стопам сотрудников лаборатории IBM. Почти все первые криптосистемы IBM базируются на работе Шеннона и его композиционных шифрах. Для построения сильной системы из слабых по отдельности компонент используется произведение шифров, а точнее, их многократное последовательное применение над данными. Понятно, что последовательное применение, например, двух блоков замены равносильно применению одного третьего блока замены. Поэтому применение замен и перестановок необходимо чередовать между собой. Именно так и поступили в IBM.

Несмотря на незначительные различия в реализациях, почти во всех системах фирмы IBM в основном использовалась перестановка внутри блока для некоторого фиксированного перемешивающего преобразования и подстановка для 4-битовых подблоков (рис. 4.6). Кстати, название «узел замены» появилось именно отсюда, поскольку оно наглядно демонстрирует позицию блока замены в архитектуре шифра как некоторую узловую операцию, в которой своего рода узлом сходятся линии, обозначающие поступление данных.

Файстелем была описана такая схема в качестве примера эффективной криптосистемы. В ней блок из 128 битов открытого текста разбивается на 32 4 битных подблока, каждый из которых подвергается действию различных S-блоков, которые управляются частью заданного пользователем ключа. Затем полученные 128 битов перемешиваются с помощью фиксированной перестановки, и процесс повторяется. Перестановка перемешивает биты различных S-блоков и необходима для того, чтобы предотвратить вырождение всего преобразования в подстановку 4-битовых блоков. Расшифрование происходит аналогично, за исключением того, что в качестве S-блоков используются их обратные подстановки.

К сожалению, в данной схеме есть существенные недостатки. Дело в том, что в данном случае S блоки являются секретной частью алгоритма шифрования. Все они должны быть различными, следовательно, для их хранения понадобится целых битов.

Чтобы преодолеть данные трудности, Файстель использовал только два различных S блока (S0 и S1), структура которых известна вместе с алгоритмом. Тогда каждый из S блоков на рис. 4.6 будет заменен либо S0, либо S1, в зависимости от значения одного бита ключа. Это снижает требования к памяти для S-блоков до 128 битов и к длине ключа до 512 битов. Дальнейшее уменьшение размера ключа до 128 битов было достигнуто за счет использования алгоритма разворачивания ключа (key shedule), который просто повторяет каждый бит ключа четыре раза.
Каждый 4-битовый S-блок можно реализовать в виде массива в памяти объемом в шестнадцать 4-битовых слов. Поскольку S-блок должен быть обратимым, все слова должны быть разными. Следовательно, простейшая реализация одного 4-битового S-блока потребует от нас наличия 64 битов памяти, для 8-битового S-блока потребуется уже 2048 битов памяти, а 16-битовый S-блок «отъест» приличный кусок в один мегабайт. В IBM выбрала размер в 4 бита, выдержав своего рода компромисс между стоимостью и надежностью.

Если бы был выбран 2 битовый вариант, то вся система могла быть раскрыта за несколько секунд работ персонального компьютера. Это произошло бы потому, что все 4! = 24 обратимых отображения 2 битов в 2 бита являются линейными (или, если быть точным – аффинными) и могут быть представлены в виде линейного уравнения, в котором вся арифметика выполняется по модулю 2. Факт того, что перестановка является линейной операцией, а композиция аффинных отображений дает аффинное отображение, показывает, что использование S-блоков в этом случае было бы равносильно одному линейному преобразованию. В этом случае, даже не пытаясь найти ключ, можно было бы получить открытый текст из решения системы линейных уравнений методом, описанным в начале раздела.

Следовательно, при создании S-блоков аффинных отображений следует избегать. Отображений, «близких» к аффинным, тоже следует избегать, что, по-видимому, и отразилось в решении не использовать 3 битовые узлы замены, хотя в данном случае аффинными будут всего лишь 3% обратимых отображений 3 битов в 3 бита. Вместо этого были созданы и использованы 4-битовые S-блоки.

 

Шифр DES.

DES (Data Encryption Standart) — Симметричный алгоритм шифрования, в котором один ключ используется, как для шифрования, так и для расшифрования данных. DES разработан фирмой IBM и утвержден правительством США в 1977 году как официальный стандарт (FTPS 46-3). DES имеет блоки по 64 бит и 16 цикловую структуру сети Фейстеля, для шифрования использует ключ с длиной 56 бит. Алгоритм использует комбинацию нелинейных (S-блоки) и линейных (перестановки E, IP, IP-1) преобразований. Для DES рекомендовано несколько режимов:

 режим электронной кодовой книги (ECB — Electronic Code Book),

 режим сцепления блоков (СВС — Cipher Block Chaining),

 режим обратной связи по шифротексту (CFB — Cipher Feed Back),

 режим обратной связи по выходу (OFB — Output Feed Back).

Блочный шифр

Входными данными для блочного шифра служат блок размером n бит и k-битный ключ. На выходе, после применения шифрующего преобразования, получается n-битный зашифрованный блок, причём незначительные различия входных данных как правило приводят к существенному изменению результата. Блочные шифры реализуются путём многократного применения к блокам исходного текста некоторых базовых преобразований.
Базовые преобразования:

 Сложное преобразование на одной локальной части блока.

 Простое преобразование между частями блока. Так как преобразование производится поблочно, как отдельный шаг требуется разделение исходных данных на блоки необходимого размера. При этом вне зависимости от формата исходных данных, будь то текстовые документы, изображения или другие файлы, они должны быть интерпретированы в бинарный вид и только после этого разбиты на блоки. Все вышеперечисленное может осуществляться программными, так и аппаратами средствами.

Преобразования Сетью Фейстеля

Это преобразование над векторами (блоками) представляющими собой левую и правую половины регистра сдвига. В алгоритме DES используются прямое преобразование сетью Фейстеля в шифровании (см. Рис.1) и обратное преобразование сетью Фейстеля в расшифрование (см. Рис.2).