Журнал фильтра правок

''''Сеть Фе́йстеля''' (конструкция [[Фейстель, Хорст|Фейстеля]]) — один из методов построения [[блочный шифр|блочных шифров]]. Сеть представляет собой определённую многократно повторяющуюся ([[итерация|итерированную]]) структуру, называющуюся ячейкой Фейстеля. При переходе от одной ячейки к другой меняется ключ, причём выбор ключа зависит от конкретного алгоритма. Операции [[Шифрование|шифрования]] и расшифрования на каждом этапе очень просты, и при определённой доработке совпадают, требуя только обратного порядка используемых [[Ключ (криптография)|ключей]]. Шифрование при помощи данной конструкции легко реализуется как на программном уровне, так и на аппаратном, что обеспечивает широкие возможности применения. Большинство современных блочных шифров используют сеть Фейстеля в качестве основы. Альтернативой сети Фейстеля является [[SP-сеть|подстановочно-перестановочная сеть]]. Херня это все! == История == В [[1971 год]]у [[Хорст Фейстель]] (Horst Feistel) запатентовал два устройства, реализовавшие различные [[алгоритмы]] [[шифрование|шифрования]], названные затем общим названием [[Lucifer (криптография)|«Люцифер»]] (Lucifer). Одно из устройств использовало конструкцию, впоследствии названную «сетью Фейстеля» («Feistel cipher», «Feistel network»). Работа над созданием новых криптосистем велась им в стенах [[IBM]] вместе с [[Дон Копперсмит|Доном Копперсмитом]] (Don Coppersmith). Проект «Люцифер» был скорее экспериментальным, но стал базисом для алгоритма [[DES|Data Encryption Standard]] (DES). В [[1973 год]]у [[Хорст Фейстель]] в журнале [[Scientific American]] опубликовал статью «Криптография и Компьютерная безопасность»<ref>[http://www.prism.net/user/dcowley/docs.html Horst Feistel. Cryptography and Computer Privacy] {{ref-en}}</ref><ref>[http://www.enlight.ru/crypto/articles/feistel/feist_i.htm Хорст Файстель. Криптография и компьютерная безопасность. Перевод Андрея Винокурова]</ref> («Cryptography and Computer Privacy»), в которой раскрыл ряд важных аспектов [[Шифрование|шифрования]] и привёл описание первой версии проекта [[Lucifer (криптография)|«Люцифер»]], не использовавшей сеть Фейстеля. В [[1977 год]]у DES стал стандартом в [[США]] на шифрование данных, и до последнего времени широко использовался в криптографических системах. Итеративная структура алгоритма позволяла упростить его реализацию в программных и аппаратных средах. Согласно некоторым данным<ref name="gost">А. Винокуров. [http://www.enlight.ru/crypto/articles/vinokurov/gost_i.htm Алгоритм шифрования ГОСТ 28147-89, его использование и реализация для компьютеров платформы Intel x86]</ref> уже в [[1970-е|1970-е годы]] в [[КГБ]] ([[СССР]]) разрабатывался блочный шифр, использовавший сеть Фейстеля, и, вероятно, именно он позднее был принят в качестве [[ГОСТ 28147-89]] в [[1990 год]]у. В [[1987 год]]у были разработаны алгоритмы [[FEAL]] и [[RC2]]. Широкое распространение сети Фейстеля получили в [[1990-е|1990-е годы]], когда появились такие алгоритмы, как: [[Blowfish]], [[CAST-128]], [[TEA]], [[XTEA]], [[XXTEA]], [[RC5]], [[RC6]] и др. [[2 января]] [[1997 год]]а [[NIST]] объявило [[AES (конкурс)|конкурс]] по созданию нового стандарта шифрования данных, пришедшего на замену [[DES]]. Новый блочный шифр был утверждён [[26 мая]] [[2002 год]]а под названием [[Advanced Encryption Standard]] и вместо сети Фейстеля использует [[SP-сеть]]. == Конструкция блочного шифра на основе сетей Фейстеля == {| border="0" align="right" |[[Файл:feistel encryption.png|frame|<center>Шифрование</center>|300x300px]] |[[Файл:feistel decryption.png|Сеть Фейстеля: расшифрование|frame|<center>Расшифрование</center>]] |} === Простое описание === ==== Шифрование ==== Рассмотрим случай, когда мы хотим зашифровать некоторую [[Информация|информацию]], представленную [[Единицы измерения информации|в двоичном виде]] в [[Компьютерная память|компьютерной памяти]] (например, [[файл]]) или электронике, как последовательность [[Двоичная система счисления|нулей и единиц]]. * Вся информация разбивается на блоки фиксированной длины. В случае, если длина входного блока меньше, чем размер, который шифруется заданным алгоритмом, то блок удлиняется каким-либо способом. Как правило длина блока является [[Возведение в степень|степенью]] двойки, например: 64 бита, 128 бит. Далее будем рассматривать операции происходящие только с одним блоком, так как с другими в процессе шифрования выполняются те же самые операции. * Выбранный блок делится на два равных подблока — «левый» (<math>L_0</math>) и «правый» (<math>R_0</math>). * «Левый подблок» <math>L_0</math> видоизменяется функцией <math>f(L_0, K_0)</math> в зависимости от раундового ключа <math>K_0</math>, после чего он [[Xor|складывается по модулю 2]] с «правым подблоком» <math>R_0</math>. * Результат сложения присваивается новому левому подблоку <math>L_1</math>, который будет половиной входных данных для следующего раунда, а «левый подблок» <math>L_0</math> присваивается без изменений новому правому подблоку <math>R_1</math> (см. схему), который будет другой половиной. * После чего операция повторяется N-1 раз, при этом при переходе от одного этапа к другому меняются раундовые ключи (<math>K_0</math> на <math>K_{1}</math> и т. д.) по какому-либо математическому правилу, где N — количество раундов в заданном алгоритме. ==== Расшифрование ==== Расшифровка информации происходит так же, как и шифрование, с тем лишь исключением, что ключи идут в обратном порядке, то есть не от первого к N-ному, а от N-го к первому. === Алгоритмическое описание === * блок открытого текста делится на 2 равные части <math>(L_0,\ R_0)</math> * в каждом раунде вычисляется (<math>i=1\ldots n</math> — номер раунда) <math>L_i\ =\ R_{i-1}\oplus f(L_{i-1},K_{i-1})</math> <math>R_i\ =\ L_{i-1}</math>, где <math>f</math> — некоторая функция, а <math>K_{i-1}</math> — ключ <math>i</math>-го раунда. Результатом выполнения <math>n</math> раундов является <math>(L_n,\ R_n)</math>. Но обычно в <math>n</math>-ом раунде перестановка <math>L_n</math> и <math>R_n</math> не производится, что позволяет использовать ту же процедуру и для расшифрования, просто инвертировав порядок использования раундовой ключевой информации: <math>L_{i-1}\ =\ R_{i}\oplus f(L_{i},\ K_{i-1})</math> <math>R_{i-1}\ =\ L_i</math>, Небольшим изменением можно добиться и полной идентичности процедур шифрования и расшифрования. Одно из преимуществ такой модели — обратимость алгоритма независимо от используемой функции <math>f</math>, и она может быть сколь угодно сложной. === Математическое описание === [[Инволюция (математика)|Инволюция]]<ref>[http://rain.ifmo.ru/cat/view.php/theory/coding/cryptography-2005/block ДИСКРЕТНАЯ МАТЕМАТИКА: АЛГОРИТМЫ. Симметричные системы и блочные шифры]</ref> — взаимно-однозначное преобразование, которое является обратным самому себе. Рассмотрим на примере: Пусть X — входной блок, а A — некоторое инволютивное преобразование, Y — результат. При однократном применении преобразования к входному блоку получится: <math>Y=AX</math>, при применении преобразования к результату предыдущего преобразования получится: <math>AY=A^2X=AAX=X, \forall X</math>. Пусть входной блок X=(L, R) состоит из двух подблоков (L и R) равной длины. Определим два преобразования <math>G(X, K)= G((L, R), K)=(L \oplus F(K, R), R)</math> (шифрование ключом K) и <math>T(L, R)=(R, L)</math> (перестановка подблоков). Введём обозначения: <math>\tilde{X} = (\tilde{L}, \tilde{R}) = GX,\ \tilde{\tilde{X}} = (\tilde{\tilde{L}}, \tilde{\tilde{R}}) = G^2X</math> Докажем их инволютивность: # Несложно заметить, что преобразование G меняет только левый подблок L, оставляя правый R неизменным. Поэтому далее будем рассматривать только подблок L. После того как преобразование G будет дважды применено к L получим:<math>\tilde{\tilde{L}} = \tilde{L}\oplus F(K, \tilde{R}) = \tilde{L}\oplus F(K, R) = L\oplus F(K, R) \oplus F(K, R) = L</math>. Таким образом <math>G^2X = X</math>, следовательно G — инволюция. # <math>T^2X = T^2(L, R) = T(R, L) = (L, R) = X</math>. Рассмотрим сам процесс шифрования. Определим X как входное значение. Пусть <math>G_i</math> — преобразование с ключом <math>K_i</math>, а <math>Y_i</math> — выходное значение после i-го раунда. Тогда преобразование на i+1-м раунде можно записать в виде <math>Y_{i+1} = TG_iY_i</math>, кроме первого, где <math>Y_1=TG_1X</math>. Следовательно, выходное значение после m раундов шифрования будет <math>Y_m = TG_mY_{m-1} = TG_mTG_{m-1}\ldots TG_1X</math>. Можно заметить, что на последнем этапе не обязательно выполнять перестановку T. Расшифрование ведётся применением всех преобразований в обратном порядке. В силу инволютивности каждого из преобразований обратный порядок даёт исходный результат: <math>X = G_1TG_2T\ldots G_{m-1}TG_mT(Y_m) = G_1TG_2T\ldots G_{m-1}T(Y_{m-1})= \ldots = G_1T(Y_1) = X</math>. === Функции, используемые в сетях Фейстеля === В своей работе «Криптография и Компьютерная безопасность» Хорст Фейстель описывает два различных блока преобразований (функций <math>f(L_{i},\ K_{i})</math>) — блок подстановок (S-блок) и блок перестановок (P-блок). Можно показать, что любое двоичное преобразование над двоичным блоком фиксированной длины, сводятся к S-блоку, но на практике в силу сложности строения n-разрядного S-блока при больших n, применяют более простые конструкции. Термин «блок» в оригинальной статье используется вместо функции вследствие того, что речь идёт о блочном шифре и предполагалось, что S- и P-блоки будут цифровыми микросхемами (цифровыми блоками). [[Файл:S-block.svg|Сеть Фейстеля: шифрование|frame|<center>Принципиальная схема 3-разрядного S-блока</center>]] [[Файл:Feistel Network P-Block.png|Сеть Фейстеля: шифрование|frame|<center>Принципиальная схема 8-разрядного P-блока</center>]] ==== S-блок (S-box) ==== Блок подстановок (S-блок) состоит из [[дешифратор]]а, преобразующего [[Числовой разряд|n-разрядный]] двоичный сигнал в одноразрядный сигнал по основанию <math>2^n</math>, системы коммутаторов внутренних соединений (всего возможных соединений <math>2^n!</math>) и [[Шифратор (электроника)|шифратора]], переводящего сигнал из одноразрядного <math>2^n</math>-ричного в n-разрядный двоичный. Анализ n-разрядного S-блока при большом n крайне сложен, однако реализовать такой блок на практике очень сложно, так как число возможных соединений крайне велико (<math>2^n!</math>). На практике блок подстановок используется как часть более сложных систем. В общем случае S-блок может иметь несовпадающее число входов/выходов, в этом случае в системе коммутации от каждого выхода дешифратора может идти не строго одно соединение, а 2 или более или не идти вовсе. То же самое справедливо и для входов шифратора. В электронике можно непосредственно применять приведённую справа схему, в программировании же генерируют таблицы замены. Оба этих подхода являются эквивалентными, то есть файл, зашифрованный на компьютере, можно расшифровать на электронном устройстве и наоборот. {| class="standard" |+ Таблица замены для приведённого 3-разрядного S-блока !№ комбинации ||0 ||1 ||2 ||3 ||4 ||5 ||6 ||7 |- !Вход |000 ||001 ||010 ||011 ||100 ||101 ||110 ||111 |- !Выход |011 ||000 ||001 ||100 ||110 ||111 ||010 ||101 |} ==== P-блок (P-box) ==== Блок перестановок всего лишь изменяет положение цифр и является линейным устройством. Этот блок может иметь очень большое количество входов-выходов, однако в силу линейности систему нельзя считать криптоустойчивой. Криптоанализ ключа для n-разрядного P-блока проводится путём подачи на вход n-1 различных сообщений, каждое из которых состоит из n-1 нуля («0») и 1 единицы («1») (или наоборот, из единиц и нуля). ==== Циклический сдвиг ==== {{main|Битовые операции|Битовый сдвиг}} [[Файл:Left shift 8 3.png|Циклический сдвиг влево|frame|<center>Циклический сдвиг влево на 3 разряда 8-битной шины</center>]] Можно показать, что циклический сдвиг является частным случаем P-блока. В простейшем случае (сдвиг на 1 бит), крайний бит отщепляется и перемещается на другой конец регистра или шины. В зависимости от того какой бит берётся, правый или левый, сдвиг называется вправо или влево. Сдвиги на большее число бит можно рассматривать, как многократное применение сдвига на 1. {| class="standard" |+Циклический сдвиг на m бит для n-разрядного входа (m &lt; n) !Направление сдвига |Порядок следования битов до сдвига |Порядок следования битов после сдвига |- !влево |<math>b_0,b_1,b_2, ... , b_{n-1}</math> |<math>b_m, b_{m+1}, ... b_{n-1}, b_0, b_1, ... , b_{m-1}</math> |- !вправо |<math>b_0,b_1,b_2, ... , b_{n-1}</math> |<math>b_{n-m}, b_{n-m+1}, ... b_{n-1}, b_0, b_1, ... , b_{n-m-1}</math> |} ==== [[Сравнение по модулю|Сложение по модулю <math>n</math>]] ==== Обозначение операции — (A + B) mod <math>n</math> — это [[Деление с остатком|остаток]] от деления [[Сумма (математика)|суммы]] A + B на <math>n</math>, где A и B — складываемые числа. Можно показать, что сложение двух чисел по модулю <math>n</math> представляется в двоичной системе счисления, как S-блок, у которого на вход подаётся число A, а в качестве системы коммутации S-блока используется циклический сдвиг влево на B разрядов. В [[компьютерная техника|компьютерной технике]] и [[электроника|электронике]] операция сложения, как правило, реализована как [[сложение]] по модулю <math>n = 2 ^ m</math>, где m — целое (обычно m равно разрядности машины). Для получения в двоичной системе A + B mod <math>2^m</math> достаточно сложить числа, после чего отбросить разряды начиная с m-того и старше. ==== Умножение по модулю <math>n</math> ==== Обозначение операции — (A * B) mod <math>n</math> — это остаток от деления произведения A * B на <math>n</math>, где A и B — перемножаемые числа. В персональных компьютерах на платформе [[x86]] при [[Умножение|перемножении]] двух m-разрядных чисел получается число разрядностью 2*m. Чтобы получить остаток от [[Деление (математика)|деления]] на <math>2^m</math> нужно отбросить m старших бит. === Пример реализации на языке [[Си (язык программирования)|Си]] === Общий вид алгоритма шифрования, использующего сеть Фейстеля: <source lang="C"> /* функция преобразования подблока по ключу (зависит от конкретного алгоритма) subblock - преобразуемый подблок key - ключ возвращаяемое значение - преобразованный блок*/ int f(int subblock, int key); /*Шифрование открытого текста left - левый входной подблок right - правый входной подблок * key - массив ключей (по ключу на раунд) rounds - количество раундов*/ void crypt(int *left, int *right, int rounds, int *key) { int i, temp; for(i = 0; i < rounds; i++) { temp = *right ^ f(*left, key[i]); *right = *left; *left = temp; } } /*Расшифрование текста left - левый зашифрованный подблок right - правый зашифрованный подблок*/ void decrypt(int *left, int *right, int rounds, int *key) { int i, temp; for(i = rounds - 1; i >= 0; i--) { temp = *left ^ f(*right, key[i]); *left = *right; *right = temp; } } </source> === Достоинства и недостатки === Достоинства: * Простота аппаратной реализации на современной электронной базе * Простота программной реализации в силу того, что значительная часть функций поддерживается на аппаратном уровне в современных компьютерах (например, [[Xor|сложение по модулю 2]], сложение по модулю <math>2^n</math>, умножение по модулю <math>2^n</math>, и т. д.) * Хорошая изученность алгоритмов на основе сетей Фейстеля<ref>Журнал Byte. № 8 (60), август 2003. [http://www.bytemag.ru/articles/detail.php?ID=6645 Современные алгоритмы шифрования], Сергей Панасенко</ref> Недостатки: * За один раунд шифруется только половина входного блока{{Источник:Основы современной криптографии}} == Теоретические исследования == Сети Фейстеля были широко изучены криптографами в силу их обширного распространения. В [[1988 год]]у Майкл Люби ([[:en:Michael Luby|Michael Luby]]) и Чарльз Ракофф ([[:en:Charles Rackoff|Charles Rackoff]]) провели исследования сети Фейстеля и доказали, что если раундовая функция является криптостойкой псевдослучайной, и используемые ключи независимы в каждом раунде, то 3-х раундов будет достаточно для того, чтобы блочный шифр являлся псевдослучайной перестановкой, тогда как четырёх раундов будет достаточно для того чтобы сделать сильную псевдослучайную перестановку. Псевдослучайной перестановкой Люби и Ракофф назвали такую, которая устойчива к атаке с адаптивным выбором открытого текста, а сильной псевдослучайной перестановкой — псевдослучайную перестановку устойчивую к атаке с использованием выбранного шифрованного текста. Иногда сеть Фейстеля в западной литературе называют «Luby-Rackoff block cipher» в честь Люби и Ракоффа, которые проделали большой объём теоретических исследований в этой области. В дальнейшем, в 1997 году, Мони Наор (Moni Naor) и Омер Рейнголд (Omer Reingold) предложили упрощённый вариант конструкции Люби — Ракоффа из четырёх раундов, где в качестве первого и последнего раунда используются две попарно-независимые [[перестановка|перестановки]]. Два средних раунда конструкции Наора — Рейнголда идентичны раундам в конструкции Люби — Ракоффа.<ref>On The Construction of Pseudo-Random Permutation: Luby-Rackoff Revisited</ref> Большинство же исследований посвящено изучению конкретных алгоритмов. Во многих блочных шифрах на основе сети Фейстеля были найдены те или иные уязвимости, однако в ряде случаев эти уязвимости являются чисто теоретическими и при нынешней производительности компьютеров использовать их на практике для взлома невозможно. == Модификации сети Фейстеля == При большом размере блоков шифрования (128 бит и более) реализация такой сети Фейстеля на 32-разрядных архитектурах может вызвать затруднения, поэтому применяются модифицированные варианты этой конструкции. Обычно используются сети с 4 ветвями. На рисунке показаны наиболее распространенные модификации. Также существуют схемы, в которых длины половинок <math>L_0</math> и <math>R_0</math> не совпадают. Они называются ''несбалансированными''. <gallery caption='Модификации сети Фейстеля'> Изображение:feistel type1.png|<center>Тип 1</center> Изображение:feistel type2.png|<center>Тип 2</center> Изображение:feistel type3.png|<center>Тип 3</center> </gallery> === Алгоритм IDEA{{Источник:Handbook of Applied Cryptography|часть=§7.6 IDEA|ссылка=http://www.cacr.math.uwaterloo.ca/hac/about/chap7.pdf|страницы=263}} === {{main|IDEA}} {| class="standard" align="right" ! Схема одной итерации<br />полного раунда алгоритма [[IDEA]] |- |[[Файл:International Data Encryption Algorithm InfoBox Diagram.svg|307px]] |- |[[Файл:Operations.png|center]] |} Примером алгоритма, использующим глубоко модифицированную сеть Фейстеля, является алгоритм [[IDEA]]. В нём 64-х битные входные блоки данных (обозначим за <math>X_0</math>) делятся на 4 подблока длиной 16 бит <math>X_0 = \{ X^{(0)}X^{(1)}X^{(2)}X^{(3)}\}</math>. На каждом этапе используется 6 16-ти битных ключей. Всего используется 8 основных этапов и 1 укороченный. Формулы для вычисления значения подблоков на i-м раунде (для раундов c 1-го по 8-й): Предвычисления: <math>A_{i} = ((X_{i-1}^{(0)}*K_{i}^{(1)}) \oplus (X_{i-1}^{(2)}+K_{i}^{(3)}))*K_{i}^{(5)}</math> <math>B_{i} = (((X_{i-1}^{(1)}+K_{i}^{(2)} ) \oplus (X_{i-1}^{(3)}*K_{i}^{(4)}) + A_{i})*K_{i}^{(6)})</math> <math>C_{i} = ((X_{i-1}^{(1)}+K_{i}^{(2)}) \oplus (X_{i-1}^{(3)}*K_{i}^{(4)}) + ((X_{i-1}^{(0)}*K_{i}^{(1)}) \oplus (X_{i-1}^{(2)}+K_{i}^{(3)}))*K_{i}^{(5)})*K_{i}^{(6)}</math> <math></math> Финальные вычисления: <math>X_{i}^{(0)}\ =\ ( X_{i-1}^{(0)}*K_{i}^{(1)} ) \oplus B_{i}</math> <math>X_{i}^{(1)}\ =\ ( X_{i-1}^{(2)}+K_{i}^{(3)} ) \oplus B_{i}</math> <math>X_{i}^{(2)}\ =\ ( X_{i-1}^{(1)}+K_{i}^{(2)} ) \oplus (A_{i}+C_{i})</math> <math>X_{i}^{(3)}\ =\ ( X_{i-1}^{(3)}*K_{i}^{(4)} ) \oplus (A_{i}+C_{i})</math> где <math>K_{i}^{(j)}</math> — j-й ключ на i-м раунде. Формула для вычисления 9-го раунда: <math>X_{9}^{(0)}\ =\ X_{8}^{(0)}*K_{9}^{(1)}</math> <math>X_{9}^{(1)}\ =\ X_{8}^{(2)}+K_{9}^{(2)}</math> <math>X_{9}^{(2)}\ =\ X_{8}^{(1)}+K_{9}^{(3)}</math> <math>X_{9}^{(3)}\ =\ X_{8}^{(3)}*K_{9}^{(4)}</math> Выходом функции будет <math>Y=\{X_{9}^{(0)}X_{9}^{(1)}X_{9}^{(2)}X_{9}^{(3)}\}</math> Как видно одной из особенностей является то, что не используются S- и P-блоки в чистом виде, в качестве основных операций используют умножение по модулю <math>2^{16} + 1 = 65537</math> и сложение по модулю <math>2^{16} = 65536</math>. == Шифры на основе сети Фейстеля == === Люцифер (Lucifer) === {{main|Lucifer (криптография)}} [[Файл:S-chooser.png|Выбор S-блока|frame|<center>Модуль, выбирающий используемую таблицу подстановок по битовому ключу</center>]] [[Файл:Lucifer v1.png|Упрощённая схема S- и P-слоёв в алгоритме «Люцифер» (июнь 1971)|frame|<center>Упрощённая схема S- и P-слоёв в алгоритме «Люцифер» (июнь 1971)</center>]] [[Файл:Ones Propagation.png|Схема генерации и распространения единиц|frame|<center>Схема генерации и распространения единиц</center>]] Исторически, первым алгоритмом, использующим сеть Фейстеля, был алгоритм [[Lucifer (криптография)|Люцифер]], при работе над которым Фейстелем и была, собственно, разработана структура, которую затем стали называть «сетью Фейстеля». В июне [[1971 год]]а Фейстелем был получен американский патент № 3798359.<ref>{{US patent|3,798,359}}</ref> Первая версия этого алгоритма использовала блоки и ключи длиной по 48 бит и не использовала конструкцию «сеть Фейстеля». Последующая модификация алгоритма была запатентована на имя Джона Л. Смитта (John Lynn Smith) в ноябре того же года (US Patent 3,796,830; Nov 1971)<ref>{{US patent|3,796,830}}</ref>, и в патенте содержится как описание собственно самой «сети Фейстеля», так и конкретной функции шифрования. В ней использовались 64-разрядные ключи и 32-битные блоки. И, наконец, последняя версия предложена в 1973 году и оперировала с 128-битными блоками и ключами. Наиболее полное описание алгоритма «Люцифер» было приведено в статье Артура Соркина (Arthur Sorkin) «Люцифер. Криптографический алгоритм» («Lucifer, A Cryptographic Algorithm») в журнале Криптология (Cryptologia) за январь 1984.<ref>Arthur Sorkin. Lucifer, A Cryptographic Algorithm. Cryptologia, Выпуск 8(1), Январь 1984, стр. 22—41, с дополнением в выпуске 8(3), стр. 260—261</ref> Хотя изначальная модификация «Люцифера» обходилась без «ячеек Фейстеля», она хорошо демонстрирует то, как только применением S- и P-блоков можно сильно исказить исходный текст. Структура алгоритма [[Lucifer (криптография)|Люцифер]] образца июня [[1971 год]]а представляет собой «сэндвич» из слоёв двух типов, используемых по очереди — так называемые [[SP-сеть|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-блок. === DES === {{main|DES}} Функция <math>f(L_i, K_i)</math> (где <math>L_i</math> — 32-разрядный входной блок на i-й итерации, <math>K_i</math> — 48-ми разрядный ключ на данной итерации) в алгоритме DES состоит из следующих операций: * Расширение входного блока L до 48 разрядов (некоторые входные разряды могут повторяться). * Сложение по модулю два с ключом <math>K_i</math>: <math>\tilde{L_i} = L_i \oplus K_i</math>. * Результат разбивается на 8 блоков длиной 6 бит каждый: <math>\tilde{L_i} = \{\tilde{L_i}^{(0)}\tilde{L_i}^{(1)}\tilde{L_i}^{(2)}\tilde{L_i}^{(3)}\tilde{L_i}^{(4)}\tilde{L_i}^{(5)}\tilde{L_i}^{(6)}\tilde{L_i}^{(7)}\}</math>. * Полученные блоки информации <math>\tilde{L_i^{(j)}}</math> подаются на блоки подстановок имеющие 6-ти разрядные входы и 4-разрядные выходы. * На выходе 4-х битные блоки объединяются в 32-х битный, который и является результатом функции <math>f(L_i, K_i)</math>. Полное число раундов в алгоритме DES — 16. === ГОСТ === {{main|ГОСТ 28147—89}} Функция <math>f(L_i, K_i)</math> (где <math>L_i</math> и <math>K_i</math> — 32-хбитные числа) вычисляется следующим образом: * Складываются <math>L_i</math> и <math>K_i</math> по модулю <math>2^{32}</math>: *: <math>\tilde{L_i} = (L_i + K_i)\ \bmod\ 2^{32}.</math> * Результат разбивается на 8 4-хбитных блоков, которые подаются на вход 4-хразрядных S-блоков (которые могут быть различными). * Выходы S-блоков объединяют в 32-хбитное число, которое затем сдвигается циклически на 11 битов влево. Полученный результат является выходом функции. Количество раундов в алгоритме ГОСТ 28147—89 равно 32. === Сравнительный список алгоритмов === Следующие блочные шифры используют классическую или модифицированную сеть Фейстеля в качестве своей основы: {| class="standard sortable" ! Алгоритм || Год || Число раундов || Длина ключа || Размер блока || Количество подблоков |- | [[Blowfish]] || 1993 || 16 || от 32 до 448 || 64 || 2 |- | [[Camellia (алгоритм)|Camellia]] || 2000 || 18/24 || 128/192/256 || 128 || 2 |- | [[CAST-128]] || 1996 || 12/16 || 40-128 || 64 || 2 |- | [[CAST-256]] || 1998 || 12×4=48 || 128/192/256 || 128 || 2 |- | [[CIPHERUNICORN-A]] || 2000 || 16|| 128/192/256|| 128 || 2 |- | [[CIPHERUNICORN-E]] || 1998 || 16|| 128|| 64 || 2 |- | [[CLEFIA]] || 2007 || 16|| 128/192/256|| 128 || 16 |- | [[DEAL]] || 1998 || 6 (8) || (128/192) 256 || 128 || 2 |- | [[DES]] || 1977 || 16 || 56 || 64 || 2 |- | [[DFC]] || 1998 || 8 || 128/192/256 || 128 || ? |- | [[FEAL]] || 1987 || 4-32 || 64 || 64 || 2 |- | [[ГОСТ 28147-89]] || 1989<ref name="gost"/> || 32/16 || 256 || 64 || 2 |- | [[IDEA]] || 1991 || 8+1 || 128 || 64 || 4 |- | [[KASUMI]] || 1999 || 8 || 128 || 64 || 2 |- | [[Khufu]] || 1990 || 16-32/64 || 512 || 64 || 2 |- | [[LOKI97]] || 1997 || 16 || 128/192/256 || 128 || 2 |- | [[Lucifer (криптография)|Lucifer]] || 1971 || 16 || 48/64/128 || 48/32/128 || 2 |- | [[MacGuffin]] || 1994 || 32 || 128 || 64 || 4 |- | [[MAGENTA]] || 1998 || 6/8 || 128/192/256 || 128 || 2 |- | [[MARS]] || 1998 || 32 || 128—1248 || 128 || 2 |- | [[Mercy]] || 2000 || 6 || 128 || 4096 || ? |- | [[MISTY1]] || 1995 || 4×n(8) || 128 || 64 || 4 |- | [[Raiden]] || 2006 || 16 || 128 || 64 || 2 |- | [[RC2]] || 1987 || 16+2 || 8-128 || 64 || 4 |- | [[RC5]] || 1994 || 1-255(12) || 0-2040(128) || 32/64/128 || 2 |- | [[RC6]] || 1998 || 20 || 128/192/256 || 128 || 4 |- | [[RTEA]] || 2007 || 48/64 || 128/256 || 64 || 2 |- | [[SEED]] || 1998 || 16 || 128 || 128 || 2 |- | [[Sinople]] || 2003 || 64 || 128 || 128 || 4 |- | [[Skipjack]] || 1998 || 23 || 80 || 64 || 4 |- | [[TEA]] || 1994 || 64 || 128 || 64 || 2 |- | [[Triple DES]] || 1978 || 32/48 || 112/168 || 64 || 2 |- | [[Twofish]] || 1998 || 16 || 128/192/256 || 128 || 4 |- | [[XTEA]] || 1997 || 64 || 128 || 64 || 2 |- | [[XTEA|XTEA-3]] || 1999 || 64 || 256 || 128 || 4 |- | [[XXTEA]] || 1998 || 12-64 || 128 || 64 || 2 |} == Примечания == {{примечания}} {{симметричные криптоалгоритмы}} {{Хорошая статья|Криптография|Математика}} [[Категория:Сеть Фейстеля| ]]'