Лекции по Теоретическим основам цифровой связи   

14. Шифрование и дешифрование

14.3.2. Подстановка

Технология шифрования с помощью подстановки, например использование шифра Цезаря и прогрессивного ключа шифрования Тритемиуса, широко используется в головоломках. Такие простые подстановочные шифры дают малую защищенность. Чтобы к подстановочной технологии можно было применить концепцию смешения, требуется более сложное соотношение. На рис. 14.6 изображен пример создания большей подстановочной сложности с помощью использования нелинейного преобразования. В общем случае п входных битов сначала представляются как один из 2n различных символов (на приведенном рисунке п=2). Затем множество из 2n символов перемешивается так, чтобы каждый символ заменялся другим символом множества. После этого символ снова превращается в n-битовый.

Можно легко показать, что существует (2n)! различные подстановки или связанные с ними возможные модели. Задача криптоаналитика становится вычислительно невозможной для больших n. Пусть п = 128, тогда 2n = 1038 и (2n)! представляет собой астрономическое число. Видим, что для n = 128 это преобразование с помощью блока подстановки (substitution block, S-блок) является сложным (запутывающим). Впрочем, хотя S-блок с п=128 можно считать идеальным, его реализация является невозможной, поскольку она потребует блока с 2n = 1038  контактами.

Вход

000

001

010

011

100

101

110

111

Выход

011

111

000

110

010

100

101

001

Рис. 14.6. Блок подстановки

Чтобы убедиться, что S-блок, приведенный на рис. 14.6, представляет собой нелинейное преобразование, достаточно использовать теорему о суперпозиции, которая формулируется ниже. Предположим, что

                                            С = Та + Tb                                                   (14.21)

                                            С’ = Т(а + b),

где а и bвходные элементы, С и С' - выходные элементы, а Т - преобразование. Тогда

Если T линейно, С = С’ для всех входных элементов.

Если Т нелинейно, СС.

Предположим, а = 001 и b = 010; тогда, используя преобразование Т, показанное на рис. 14.6, получим следующее.

С = T(001)Т(010) = 111000 = 111

С = T(001010) = T(011) = 110

Здесь символ  обозначает сложение по модулю 2. Поскольку СС,      S-блок является нелинейным.



*****
© Банк лекций Siblec.ru
Формальные, технические, естественные, общественные, гуманитарные, и другие науки.