Введение
В криптографии SP-сеть, или сеть подстановки-перестановки (SPN), представляет собой последовательность связанных математических операций, используемых в алгоритмах блочных шифров, таких как AES (Rijndael), 3 Way, Kalyna, Kuznyechik, PRESENT, SAFER, SHARK и Square. Такая сеть принимает блок открытого текста и ключ в качестве входных данных и применяет несколько чередующихся раундов или слоев ящиков подстановки (S-боксов) и ящиков перестановок (P-боксов) для получения блока зашифрованного текста. S-боксы и P-боксы преобразуют (под)блоки входных битов в выходные биты. Обычно эти преобразования представляют собой операции, эффективно выполняемые в аппаратном обеспечении, такие как исключающее ИЛИ (XOR) и побитовое вращение. Ключ вводится в каждом раунде, как правило, в виде "ключей раунда", производных от него. (В некоторых конструкциях сами S-боксы зависят от ключа.) Расшифровка выполняется путем простого обращения процесса (используя обратные S-боксы и P-боксы и применяя ключи раунда в обратном порядке).
In cryptography, an SP network, or substitution–permutation network (SPN), is a series of linked mathematical operations used in block cipher algorithms such as AES (Rijndael), 3 Way, Kalyna, Kuznyechik, PRESENT, SAFER, SHARK, and Square. Such a network takes a block of the plaintext and the key as inputs, and applies several alternating rounds or layers of substitution boxes (S boxes) and permutation boxes (P boxes) to produce the ciphertext block. The S boxes and P boxes transform (sub )blocks of input bits into output bits. It is common for these transformations to be operations that are efficient to perform in hardware, such as exclusive or (XOR) and bitwise rotation. The key is introduced in each round, usually in the form of "round keys" derived from it. (In some designs, the S boxes themselves depend on the key.) Decryption is done by simply reversing the process (using the inverses of the S boxes and P boxes and applying the round keys in reversed order).
Компоненты
S-блок заменяет небольшой блок битов (вход S-блока) другим блоком битов (выход S-блока). Эта замена должна быть взаимно однозначной, чтобы обеспечить обратимость (и, следовательно, дешифрование). В частности, длина выходного блока должна быть равна длине входного блока (на рисунке справа показаны S-блоки с 4 входными и 4 выходными битами), что отличается от S-блоков в общем случае, которые также могут изменять длину, например, в стандарте шифрования данных (DES). S-блок обычно не является простой перестановкой битов. Скорее, в хорошем S-блоке каждый выходной бит зависит от каждого входного бита. Более точно, в хорошем S-блоке каждый входной бит изменяет каждый выходной бит с вероятностью 50%. Поскольку каждый выходной бит изменяется с вероятностью 50%, примерно половина выходных битов изменится при изменении одного входного бита (см. строгий критерий лавины). 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-блоки были обратимыми (для выполнения дешифрования); внутренние функции Фейстеля не имеют такого ограничения и могут быть сконструированы как односторонние функции.