Сеть подстановки-перестановки - Substitution–permutation network
В криптографии , SP-сеть , или замещение-перестановка сети ( SPN ), представляет собой ряд связанных математических операций , используемых в блочного шифра алгоритмов , таких как AES (Rijndael) , 3-Way , калина , Kuznyechik , НАСТОЯЩЕЕ , SAFER , SHARK , и площадь .
Такая сеть принимает блок открытого текста и ключ в качестве входных данных и применяет несколько чередующихся «раундов» или «слоев» блоков подстановки (S-блоков) и блоков перестановок (P-блоков) для создания блока зашифрованного текста . S-блоки и P-блоки преобразуют (под) блоки входных битов в выходные биты. Обычно эти преобразования представляют собой операции, которые эффективно выполнять аппаратно, например исключающее ИЛИ (XOR) и побитовое вращение . Ключ вводится в каждом раунде, обычно в форме полученных на его основе «ключей раунда». (В некоторых конструкциях сами S-блоки зависят от ключа.)
Расшифровка выполняется путем простого обращения процесса (используя инверсии S-блоков и P-блоков и применяя круглые ключи в обратном порядке).
Составные части
S-коробка заменяет небольшой блок битов ( на вход S-блока) с помощью другого блока битов (выходной сигнал S-поле). Эта замена должна быть взаимно однозначной , чтобы гарантировать обратимость (следовательно, расшифровку). В частности, длина вывода должна быть такой же, как длина ввода (изображение справа имеет S-блоки с 4 входными и 4 выходными битами), что отличается от S-блоков в целом, которые также могут изменяться. длина, например, как в DES (стандарт шифрования данных) . S-блок обычно не просто перестановка битов. Скорее, хороший S-блок будет обладать тем свойством, что изменение одного входного бита изменит примерно половину выходных битов (или лавинный эффект ). Он также будет иметь свойство, что каждый выходной бит будет зависеть от каждого входного бита.
P-бокс представляет собой перестановку всех бит: он принимает выходные сигналы всех S-блоки одного раунда, переставляют биты, и подают их в S-боксы следующего раунда. Хороший P-блок обладает тем свойством, что выходные биты любого S-блока распределяются по как можно большему количеству входов S-блока.
В каждом раунде ключ раунда (полученный из ключа с помощью некоторых простых операций, например, с использованием S-блоков и P-блоков) объединяется с использованием некоторой групповой операции, обычно XOR .
Характеристики
Один типичный S-блок или один P-блок сами по себе не обладают большой криптографической стойкостью: S-блок можно рассматривать как шифр замещения , а P-блок можно рассматривать как шифр транспозиции . Однако хорошо спроектированная сеть SP с несколькими чередующимися раундами S- и P-блоков уже удовлетворяет свойствам смешения и распространения Шеннона :
- Причина распространения заключается в следующем: если кто-то изменяет один бит открытого текста, он подается в S-блок, вывод которого будет изменяться на нескольких битах, тогда все эти изменения распределяются P-блоком между несколькими S-блоками. ящиков, следовательно, выходы всех этих S-блоков снова изменяются на несколько бит и так далее. Выполняя несколько циклов, каждый бит меняется несколько раз туда и обратно, поэтому к концу зашифрованный текст изменился полностью псевдослучайным образом. В частности, для случайно выбранного входного блока, если перевернуть i-й бит, то вероятность того, что j-й выходной бит изменится, составляет примерно половину для любых i и j , что является строгим критерием лавины . И наоборот, если изменить один бит зашифрованного текста, а затем попытаться его расшифровать, результатом будет сообщение, полностью отличное от исходного открытого текста - шифры SP нелегко подобрать .
- Причина путаницы в точности такой же , как для диффузии: изменение одного бита ключа меняется несколько круглых кнопки, и каждое изменение в каждом раунде ключевыми диффундируешь по всем битам, меняя зашифрованный в очень сложным образе.
- Даже если злоумышленник каким-то образом получает один открытый текст, соответствующий одному зашифрованному тексту - атака с известным открытым текстом или, что еще хуже, выбранный открытый текст или атака с выбранным зашифрованным текстом - путаница и распространение затрудняют для злоумышленника восстановление ключа.
Представление
Хотя сеть Фейстеля, в которой используются S-блоки (такие как DES ), очень похожа на сети SP, есть некоторые отличия, которые делают то или иное более применимым в определенных ситуациях. При заданном количестве путаницы и распространения сеть SP имеет больше «присущего параллелизма», и поэтому - при наличии ЦП с множеством исполнительных блоков - может быть вычислена быстрее, чем сеть Фейстеля. ЦП с небольшим количеством исполнительных блоков, например, с большинством смарт-карт, не могут воспользоваться этим присущим параллелизмом. Также шифры SP требуют, чтобы S-блоки были обратимыми (для выполнения дешифрования); Внутренние функции Фейстеля не имеют такого ограничения и могут быть построены как односторонние функции .
Смотрите также
использованная литература
дальнейшее чтение
- Кац, Джонатан; Линделл, Иегуда (2007). Введение в современную криптографию . CRC Press. ISBN 9781584885511 .
- Стинсон, Дуглас Р. (2006). Криптография. Теория и практика (Третье изд.). Чепмен и Холл / CRC. ISBN 1584885084 .