SP-сеть
В криптографии SP-сеть, или сеть замещения-пермутации (SPN), представляет собой ряд связанных математических операций, используемых в алгоритмах блочного шифрования, таких как AES (Rijndael), 3-Way, Kalyna, Kuznyechik, PRESENT, SAFER, SHARK, и Square.
Такая сеть берет блок чистого текста и ключ в качестве входных данных и применяет несколько чередующихся "круглых" или "слоев" блоков подстановок (S-боксов) и перестановки (P-боксов) для создания блока шифрованного текста. S-боксы и P-боксы преобразуют (суб)блоки входных битов в выходные. Обычно эти преобразования представляют собой операции, которые эффективно выполняются в аппаратном обеспечении, такие как эксклюзивное или (XOR) и битовое вращение. Ключ вводится в каждом раунде, обычно в виде производных от него "круглых ключей". (В некоторых конструкциях сами S-боксы зависят от ключа).
Дешифровка выполняется простым реверсированием процесса (используя инверсы S-боксов и P-боксов и применяя круглые клавиши в обратном порядке).
S-box заменяет небольшой блок битов (вход S-бокса) на другой блок битов (выход S-бокса). Эта замена должна быть один на один, чтобы обеспечить инвертируемость (отсюда и расшифровка). В частности, длина выходного блока должна совпадать с длиной входного блока (на рисунке справа S-боксы с 4 входными и 4 выходными битами), что отличается от S-боксов в целом, которые также могут изменять длину, как, например, в DES (Data Encryption Standard - Стандарт шифрования данных). S-box обычно не является просто перестановкой битов. Скорее, хороший S-box будет иметь свойство, что изменение одного входного бита изменит примерно половину выходных битов (или лавинный эффект). У него также будет свойство, что каждый бит вывода будет зависеть от каждого входного бита.
P-бокс - это перестановка всех битов: он берет выходы всех S-боксов одного раунда, перехватывает биты и подает их в S-боксы следующего раунда. Хороший P-box имеет свойство, что выходные биты любого S-box распределяются на как можно большем количестве входов S-box.
На каждом раунде круглый ключ (полученный из ключа с помощью некоторых простых операций, например, с помощью S-боксов и P-боксов) комбинируется с помощью некоторой групповой операции, обычно XOR.
Одиночный типичный S-бокс или одиночный P-бокс не обладает большой криптографической силой: S-бокс можно рассматривать как заменяющий шифр, в то время как P-бокс можно рассматривать как шифр транспозиции. Тем не менее, хорошо продуманная сеть SP с несколькими чередующимися раундами S- и P-боксов уже удовлетворяет Шеннон путаницы и диффузионных свойств:
- Причина диффузии следующая: Если изменить один бит чистого текста, то он подается в S-бокс, выход которого изменится на несколько бит, то все эти изменения распределяются P-боксом между несколькими S-боксами, следовательно, выходы всех этих S-боксов снова меняются на несколько бит, и так далее. Делая несколько раундов, каждый бит меняется несколько раз туда и обратно, поэтому к концу шифрованный текст изменился полностью, псевдослучайным образом. В частности, для случайно выбранного входного блока, если переворачивать i-й бит, то вероятность того, что j-й выходной бит изменится, составляет примерно половину, для любого i и j, что является Строгим Лавинным Критерием. И наоборот, если изменить один бит шифрованного текста, а затем попытаться его расшифровать, то в результате получится сообщение, совершенно отличное от исходных шифров чистого текста-SP, которые нелегко поддаются расшифровке.
- Причина путаницы точно такая же, как и для диффузии: изменение одного бита ключа меняет несколько круглых клавиш, и каждое изменение в каждой круглой клавише диффундирует по всем битам, изменяя шифрованный текст очень сложным образом.
- Даже если злоумышленник каким-то образом получает один обычный текст, соответствующий одному шифрованному тексту - атака по известному обычному тексту или, что еще хуже, атака по выбранному обычному тексту или атака по выбранному шифрованному тексту - путаница и диффузия затрудняют злоумышленнику восстановление ключа.
Хотя сеть Feistel, использующая S-boxes (например, DES), довольно похожа на сети SP, есть некоторые различия, которые делают то или иное более применимым в определенных ситуациях. При заданной степени путаницы и диффузии, сеть SP имеет более "присущий параллелизм", и поэтому - при наличии процессора с большим количеством исполнительных модулей - может быть вычислена быстрее, чем сеть Feistel. Процессоры с небольшим количеством единиц исполнения, такие как большинство смарт-карт, не могут воспользоваться преимуществами присущего им параллелизма. Кроме того, шифры SP требуют, чтобы S-boxes были инвертируемыми (для выполнения расшифровки); внутренние функции Feistel не имеют такого ограничения и могут быть сконструированы как односторонние функции.
