Сеть замены-перестановки
В криптографии SP -сеть , или сеть подстановки-перестановки ( SPN ), — это серия связанных математических операций, используемых в алгоритмах блочного шифрования , таких как AES (Rijndael) , 3-Way , Kalyna , Kuznyechik , PRESENT , SAFER , SHARK , и Площадь .
Такая сеть принимает блок открытого текста и ключа в качестве входных данных и применяет несколько чередующихся раундов или слоев блоков подстановки (S-блоков) и блоков перестановки (P-блоков) для создания блока зашифрованного текста . S-блоки и P-блоки преобразуют (суб)блоки входных битов в выходные биты. Обычно эти преобразования представляют собой операции, которые эффективно выполнять аппаратно, например исключающее или (XOR) и побитовое вращение . Ключ вводится в каждом раунде, обычно в форме « ключей раунда », полученных на его основе. (В некоторых конструкциях сами S-блоки зависят от ключа.)
Дешифрование выполняется путем простого обратного процесса (с использованием инверсий S-блоков и P-блоков и применения раундовых ключей в обратном порядке).
Компоненты
[ редактировать ]заменяет S-блок небольшой блок битов (вход S-блока) другим блоком битов (выход S-блока). Эта замена должна быть взаимно однозначной , чтобы обеспечить обратимость (следовательно, расшифровку). В частности, длина вывода должна быть такой же, как длина ввода (на рисунке справа изображены S-блоки с 4 входными и 4 выходными битами), что отличается от S-блоков в целом, которые также могут меняться. длина, как в стандарте шифрования данных например, (DES). S-блок обычно представляет собой не просто перестановку битов. Скорее, в хорошем S-блоке на каждый выходной бит будет влиять каждый входной бит. Точнее, в хорошем S-блоке каждый выходной бит будет изменен с вероятностью 50% каждым входным битом. Поскольку каждый выходной бит изменяется с вероятностью 50%, около половины выходных битов фактически изменятся при изменении входного бита (см. Строгий лавинный критерий ). [1]
P -блок — это перестановка всех битов: он принимает выходные данные всех S-блоков одного раунда, переставляет биты и передает их в S-блоки следующего раунда. Хороший P-блок обладает тем свойством, что выходные биты любого S-блока распределяются по как можно большему количеству входов S-блока.
В каждом раунде ключ раунда (полученный из ключа с помощью некоторых простых операций, например, с использованием S-блоков и P-блоков) объединяется с помощью некоторой групповой операции, обычно XOR .
Характеристики
[ редактировать ]Один типичный S-блок или один P-блок сам по себе не обладает большой криптографической стойкостью: S-box можно рассматривать как шифр подстановки , а P-box можно рассматривать как шифр перестановки . Однако хорошо спроектированная сеть SP с несколькими чередующимися раундами S- и P-блоков уже удовлетворяет Шеннона замешательства и диффузии свойствам :
- Причина диффузии следующая: если изменить один бит открытого текста, то он подается в S-блок, вывод которого изменится на несколько бит, тогда все эти изменения распределяются P-блоком между несколькими S-блоками. блоков, следовательно, выходные данные всех этих S-блоков снова изменяются на несколько битов и так далее. Делая несколько раундов, каждый бит меняется несколько раз туда и обратно, поэтому к концу шифртекст меняется полностью, псевдослучайным образом . В частности, для случайно выбранного входного блока, если перевернуть i -й бит, то вероятность того, что j -й выходной бит изменится, равна примерно половине, для любых i и j , что является строгим лавинным критерием . И наоборот, если изменить один бит зашифрованного текста, а затем попытаться его расшифровать, результатом будет сообщение, полностью отличающееся от исходного открытого текста — шифры SP нелегко поддаются изменению .
- Причина путаницы точно такая же, как и при диффузии: изменение одного бита ключа приводит к изменению нескольких раундовых ключей, и каждое изменение в каждом раундовом ключе распространяется на все биты, меняя зашифрованный текст очень сложным образом.
- Если злоумышленник каким-то образом получает один открытый текст, соответствующий одному зашифрованному тексту ( атака по известному открытому тексту или, что еще хуже, атака по выбранному открытому тексту или выбранному зашифрованному тексту) , путаница и распространение затрудняют атакующему восстановление ключа.
Производительность
[ редактировать ]Хотя сеть Фейстеля , использующая S-блоки (например, DES ), очень похожа на сети SP, существуют некоторые различия, которые делают ту или иную сеть более применимой в определенных ситуациях. При заданной степени путаницы и рассеяния сеть SP имеет больший «внутренний параллелизм». [2] и поэтому — при наличии процессора с множеством исполнительных блоков — можно вычислять быстрее, чем сеть Фейстеля. [3] Процессоры с небольшим количеством исполнительных блоков (например, большинство смарт-карт ) не могут воспользоваться преимуществами этого присущего параллелизма. Также шифры SP требуют, чтобы S-блоки были обратимыми (для выполнения дешифрования); Внутренние функции Фейстеля не имеют такого ограничения и могут быть построены как односторонние функции .
См. также
[ редактировать ]Ссылки
[ редактировать ]- ^ Вебстер, AF; Таварес, Стаффорд Э. (1985). «О проектировании S-box». Достижения в криптологии – Crypto '85 . Конспекты лекций по информатике. Том. 218. Нью-Йорк, штат Нью-Йорк: Springer-Verlag New York, Inc., стр. 523–534. ISBN 0-387-16463-4 .
- ^ «Принципы и производительность криптографических алгоритмов» Барта Пренила, Винсента Реймена и Антуна Босселерса.
- ^ "Семейство хеш-функций Skein". Архивировано 15 января 2009 г. на Wayback Machine, 2008 г. Нильс Фергюсон , Стефан Лакс , Брюс Шнайер , Даг Уайтинг, Михир Белларе , Тадаёши Коно, Джон Каллас , Джесси Уокер страница 40.
Дальнейшее чтение
[ редактировать ]- Кац, Джонатан; Линделл, Иегуда (2007). Введение в современную криптографию . ЦРК Пресс. ISBN 9781584885511 .
- Стинсон, Дуглас Р. (2006). Криптография. Теория и практика (Третье изд.). Чепмен и Холл/CRC. ISBN 1584885084 .
