Шифр перестановки, как видно из названия, осуществляет преобразование перестановки букв в открытом тексте. Типичным и древнейшим примером шифра перестановки является шифр «Сциталь». Обычно открытый текст разбивается на отрезки равной длины, и каждый отрезок шифруется (т.е. в нем переставляются буквы) независимо. Пусть, например, длина отрезков равна n и σ — взаимно-однозначное отображение множества {1,2, ..., n} в себя. Тогда шифр перестановки действует так: отрезок открытого текста x1...xn преобразуется в отрезок шифрованного текста xσ(1)...xσ(n).
Важной проблемой при практическом использовании шифров замены и перестановки является проблема удобного запоминания отображений g и σ. Ясно, что легко запоминать некоторые отображения: например, отображения «небольших» размеров, отображения, реализуемые каким-нибудь предметом (сциталь в шифре «Сциталь» и т.п.). Если же отображение «большого» размера, то процесс запоминания сильно усложняется. Например, широко известны биграммные шифры. В них преобразовывались биграммы (пары букв). Поскольку количество биграмм превышает 1000, то на практике биграммные шифры выглядят как специальные книжки.
Для облегчения запоминания отображений g и σ изобретались различные хитроумные способы. Правда, «расплатой» за это было упрощение используемых отображений и тем самым уменьшение стойкости шифров.
Популярным способом запоминания отображения σ, т.е. шифра перестановки, является следующий. Пусть, например, n=20. Берем прямоугольную таблицу размера 4x5, вписываем в нее открытый текст «по строкам», а шифрованный текст считываем «по столбцам». Возможны и более хитрые способы вписывания и считывания.
Подумайте сами:
1. Выпишите отображение g для шифра Цезаря.
2. Выпишите отображение σ для описанного шифра перестановки — прямоугольника 4×5.
2.5. Возможен ли абсолютно стойкий шифр
Да, и единственным таким шифром является какая-нибудь форма так называемой ленты однократного использования, в которой открытый текст «объединяется» с полностью случайным ключом такой же длины, Этот результат был доказан К. Шенноном с помощью разработанного им теоретико-информационного метода исследования шифров. Мы не будем здесь останавливаться на этом подробно, но заинтересованному читателю рекомендуем изучить работу К. Шеннона, она указана в списке литературы.
Обсудим особенности строения абсолютно стойкого шифра и возможности его практического использования. Типичным и наиболее простым примером реализации абсолютно стойкого шифра является шифр Вернама, который осуществляет побитовое сложение n-битового открытого текста и n-битового ключа: yi=x1⊕ki, i=1, ..., n.
Здесь x1, ..., xn — открытый текст, k1, ..., kn — ключ, y1, ..., yn — шифрованный текст; символы складываются по таким правилам: 0⊕0=0, 0⊕1=1⊕0=1, 1⊕1=0.
Подчеркнем теперь, что для абсолютной стойкости существенным является каждое из следующих требований к ленте однократного использования:
1) полная случайность (равновероятность) ключа (это, в частности, означает, что ключ нельзя вырабатывать с помощью какого-либо детерминированного устройства);
2) равенство длины ключа и длины открытого текста;
3) однократность использования ключа.
В случае нарушения хотя бы одного из этих условий шифр перестает быть абсолютно стойким и появляются принципиальные возможности для его вскрытия (хотя они могут быть трудно реализуемыми).
Но, оказывается, именно эти условия и делают абсолютно стойкий шифр очень дорогим и непрактичным. Прежде чем пользоваться таким шифром, мы должны обеспечить всех абонентов достаточным запасом случайных ключей и исключить возможность их повторного применения. А это сделать необычайно трудно и дорого. Как отмечал Д. Кан: «Проблема создания, регистрации, распространения и отмены ключей может показаться не слишком сложной тому, кто не имеет опыта передачи сообщений по каналам военной связи, но в военное время объем передаваемых сообщений ставит в тупик даже профессиональных связистов. За сутки могут быть зашифрованы сотни тысяч слов. Создание миллионов ключевых знаков потребовало бы огромных финансовых издержек и было бы сопряжено с большими затратами времени. Так как каждый текст должен иметь свой собственный, единственный и неповторимый ключ, применение идеальной системы потребовало бы передачи, по крайней мере, такого количества знаков, которое эквивалентно всему объему передаваемой военной информации».
В силу указанных причин, абсолютно стойкие шифры применяются только в сетях связи с небольшим объемом передаваемой информации, обычно это сети для передачи особо важной государственной информации.
2.6. Стойкость теоретическая и практическая
Теперь мы уже понимаем, что чаще всего для защиты своей информации законные пользователи вынуждены применять неабсолютно стойкие шифры. Такие шифры, по крайней мере теоретически, могут быть вскрыты. Вопрос только в том, хватит ли у противника сил, средств и времени для разработки и реализации соответствующих алгоритмов.
Обычно эту мысль выражают так: противник с неограниченными ресурсами может вскрыть любой неабсолютно стойкий шифр.
Как же должен действовать в этой ситуации законный пользователь, выбирая для себя шифр? Лучше всего, конечно, было бы доказать, что никакой противник не может вскрыть выбранный шифр, скажем, за 10 лет и тем самым получить теоретическую оценку стойкости. К сожалению, математическая теория еще не дает нужных теорем — они относятся к нерешенной проблеме нижних оценок сложности задач.
Поэтому у пользователя остается единственный путь — получение практических оценок стойкости. Этот путь состоит из следующих этапов:
— понять и четко сформулировать, от какого противника мы собираемся защищать информацию; необходимо уяснить, что именно противник знает или сможет узнать о системе шифра, какие силы и средства он сможет применить для его вскрытия;
— мысленно стать в положение противника и пытаться с его позиций атаковать шифр, т.е. разрабатывать различные алгоритмы вскрытия шифра; при этом необходимо в максимальной мере обеспечить моделирование сил, средств и возможностей противника;
— наилучший из разработанных алгоритмов использовать для практической оценки стойкости шифра.
Здесь полезно для иллюстрации упомянуть о двух простейших методах вскрытия шифра: случайного угадывания ключа (он срабатывает с маленькой вероятностью, зато имеет маленькую сложность) и перебора всех подряд ключей вплоть до нахождения истинного (он срабатывает всегда, зато имеет очень большую сложность).