Сеть Фейстеля
Сеть Фейстеля — это общий метод преобразования произвольной функции F в перестановку на множестве блоков. , Она состоит из циклически повторяющихся ячеек — раундов. Внутри каждого раунда блок открытого текста разделяется на две равные части. Раундовая функция
Шифрование в ячейке Фейстеля |
|
берет одну половину (на рис. правую), преобразует её с использованием ключа Ki и объединяет результат с второй половиной посредством операции исключающее ИЛИ (XOR). Этот ключ задаётся первоначальным ключом K и различен для каждого раунда. Далее половинки меняются местами (иначе будет преобразовываться только одна половина блока) и подаются на следующий раунд. Преобразование сети Фейстеля является обратимой операцией.
Для функции F существуют определенные требования:
её работа должна приводить к лавинному эффекту
должна быть нелинейна по отношению к операции XOR
В случае невыполнения первого требования, сеть будет подвержена дифференциальным атакам (похожие сообщения будут иметь похожие шифры). Во втором случае действия шифра линейны и для взлома достаточно решения системы линейных уравнений. [3]
Подобная конструкция обладает ощутимым преимуществом: процедуры шифрования/расшифрования совпадают, только производные от первоначального ключи используются в обратном порядке. Это значит, что одни и те же блоки могут использоваться как для шифрования, так и для расшифрования, что, безусловно, упрощает реализацию шифра. Недостаток схемы заключается в том, что в каждом раунде обрабатывается только половина блока, что приводит к необходимости увеличивать число раундов.
Различные реализации шифра Фейстеля отличаются следующими параметрами.
Размер блока.
Размер ключа.
Число раундов обработки.
Алгоритм вычисления подключей.
Функция раунда.
Дешифрование шифра Фейстеля.
Процесс дешифрования шифра Фейстеля производится по той же схеме (не по обратной), что и шифрование. Применяется тот же алгоритм, но на вход подается шифрованный текст, а подключи Ki используются в обратной последовательности.
RnLn L0=Rn R0=Ln
L1 R1 L1=R0 =Ln=R(n-1) R1=L0+F(Kn,R0)=Rn+F(Kn,Ln)= L(n-1)+F(Kn,R(n-1))+F(Kn, R(n-1))=L(n-1)
L2 R2 L2=R1 =L(n-1)=R(n-2)
R2=L1+F(K(n-1),R1)=R(n-1)+F(K(n-1),L(n-1))=L(n-2)+F(K(n-1),R(n-1))+ F(K(n-1),R(n-1))=L(n-2)
…
Li Ri Li=R(i-1) Ri=L(i-1)+F(Ki,R(i-1))
…
Ln Rn Ln=R(n-1) Rn=L(n-1)+F(Kn,R(n-1))
Rn Ln
Обратим внимание, что не требуется обратимость функции F для обратимости шифра Фейстеля.
Криптоанализ
Как и все шифры, алгоритмы которых известны, блочные шифры подвергаются криптографическим атакам. Цель атаки — разработать алгоритм взлома более эффективный, чем полный перебор всех возможных ключей. В случае нахождения подобного решения, атака считается успешной. При этом шифр является взломанным, если существуют атака, позволяющая провести взлом за время, в течение которого информация сохраняет актуальность, и проведение подобной атаки выгодно злоумышленнику.
Атака полным перебором
англ. Вrute force attack. Благодаря такой характеристике блочного шифра, как обратимость функции, его вывод становится отличимым от истинной случайной последовательности . Эта особенность приводит к снижению безопасности шифра и необходимости брать во внимание размер блока. Таким образом, существует компромисс между большими, снижающими производительность шифра, и ненадежными маленькими блоками.
Не менее важную роль играет размер ключа. Ранний шифр DES характеризовался размером ключа в 56 бит, что, как показала практика, явно не достаточно для надежной пересылки данных. Именно атакой полным перебором впервые был вскрыт DES. Более современные алгоритмы, такие как AES и ГОСТ 28147-89 имеют размер ключа в 128 бит и 256 бит соответственно, что делает бессмысленным подобные атаки.
Дифференциальный криптоанализ
Рис.1 Схема взлома дифференциальным криптоанализом
англ. Differential cryptanalysis. В 1990 году Эли Бихам (Eli Biham) и Ади Шамир (Adi Shamir) определили идею дифференциального криптоанализа. Данный метод работает с парами шифротекстов, для которых известно различие соответствующих открытых текстов, и рассматривает эволюцию этих различий.
Линейный криптоанализ
англ. Linear cryptanalysis. Линейный криптоанализ — метод вскрытия шифра, основанный на поиске аффинных приближений для работы алгоритма.
Интегральный криптоанализ
англ. Intergal cryptanalysis. Интегральный криптоанализ — вид атак, особенно применимый к блочный шифрам, построенным на SP-сети. В отличие от дифференциального криптоанализа, использующего пару выбранного открытого текста с фиксированным разницей, вычисленной при помощи операции XOR, интегральный криптоанализ использует множества открытых текстов, в которых одни части удерживаются постоянными, в то время как другие варьируются среди всевозможных значений. Подобное множество с необходимостью имеет сумму по модулю 2 (XOR), равной 0, в то время, как соответствующая сумма шифротекста содержит информацию об операциях шифра.
@@@@@@@@@@@@@конец лекции
Модификации сети Фейштеля
Модификации сети Фейштеля для большего числа ветвей применяют гораздо чаще. Это в первую очередь связано с тем, что при больших размерах кодируемых блоков (128 и более бит) становится неудобно работать с математическими функциями по модулю 64 и выше. Как известно, основные единицы информации обрабатываемые процессорами на сегодняшний день – это байт и двойное машинное слово 32 бита. Поэтому все чаще и чаще в блочных криптоалгоритмах встречается сеть Фейштеля с 4-мя ветвями. Самый простой принцип ее модификации изображен на рисунке 4а. Для более быстрого перемешивания информации между ветвями (а это основная проблема сети Фейштеля с большим количеством ветвей) применяются две модифицированные схемы, называемые "type-2" и "type-3". Они изображены на рисунках 4б и 4в.
