Применение перестановок

Все рассмотренные выше методы основывались на замещении по определенным правилам символов открытого текста на естественном языке различными символами специального алфавита (алфавитов), предназначенных для записи шифрованного текста. Принципиально иной класс преобразований строится на использовании перестановок букв открытого текста. Шифры, созданные с помощью перестановок, называют перестановочными шифрами.

Шифр «Лесенка». Простейший из перестановочных шифров использует преобразование “лесенки”, заключающееся в том, что открытый текст записывается вдоль наклонных строк определенной длины («ступенек»), а затем считывается построчно по горизонтали. Например, чтобы шифровать сообщение «meet me after the toga party» /встретьте меня после вечеринки в тогах/ по методу лесенки со ступеньками длиной 2 символа, запишем это сообщение в виде:

Шифрованное сообщение будет иметь следующий вид:

MEMATRHTGPRYETEFETEOAAT

Количество ступенек в «лесенке» рассматривается как ключ шифра. Такой шифр особой сложности для криптоанализа не представляет. Дешифровка может быть осуществлена на основе перебора вариантов количества ступенек в «лесенке».

При расшифровке необходимо определить количество символов в зашифрованной строке и разделить шифрованный текст на равные части в соответствии со значением ключа (количества ступенек в «лесенке»). Первая часть образует первую строку лесенки, вторая часть – вторую и т.д. Дальнейшая расшифровка не представляет труда. При делении с остатком необходимо иметь в виду, что последняя «лесенка» будет «не достроена» за счет нижних ступенек, что характерно для приведенного простого примера.

Шифр вертикальной перестановки. Более сложная схема предполагает запись текста сообщения в горизонтальные строки одинаковой длины и последующее считывание текста столбец за столбцом, но не по порядку, а в соответствии с некоторой перестановкой столбцов. Порядок считывания столбцов при этом становится ключом алгоритма. Рассмотрим пример шифрования следующей фразы: attack postponed until two am /атака отложена до двух ночи/. Первоначально фраза записывается построчно с помощью матрицы размером 4×7, затем с использованием ключа преобразуется в шифротекст:

Буквы x, y, z используются в данном случае как буквы-заполнители.

Простой перестановочный шрифт очень легко распознать, так как буквы в нем встречаются с той же частотой, что и в открытом тексте. Например, для только что рассмотренного способа шифрования с перестановкой столбцов анализ шифра выполнить достаточно просто – необходимо записать шифрованный текст в виде матрицы и перебрать возможные варианты перестановок для столбцов. Можно использовать также таблицы значений частоты биграмм и триграмм.

Перестановочный шифр можно сделать существенно более защищенным, выполнив шифрование с использованием перестановок несколько раз. Оказывается, что в этом случае примененную для шифрования перестановку воссоздать уже не так просто. Например, если предыдущее сообщение шифровать еще раз с помощью того же самого алгоритма, то результат будет следующим:

Чтобы нагляднее представить то, что мы получим в итоге повторного применения перестановки, сопоставим каждую букву исходного открытого текста с номером соответствующей ей позиции. Наше сообщение состоит из 28 букв, и исходной последовательностью будет последовательность:

После первой перестановки получим последовательность, которая все еще сохраняет некоторую регулярность структуры.

После второй перестановки получается следующая последовательность.

Регулярность этой последовательности уже совсем не просматривается, поэтому ее криптоанализ потребует значительно больше усилий.

Если известен ключ, расшифровка весьма проста и не требует пояснений.

Применение магических квадратов. В средние века для шифрования перестановкой применялись и магические квадраты. Магическими квадратами называют квадратные таблицы с вписанными в их клетки последовательными натуральными числами, начиная от 1, которые дают в сумме по каждому столбцу, каждой строке и каждой диагонали одно и то же число.

Шифруемый текст вписывали в магические квадраты в соответствии с нумерацией их клеток (первая буква записывалась в клетку под номером 1, вторая – в клетку под номером 2 и т.д.). Если затем выписать содержимое такой таблицы по строкам, то получится шифротекст, сформированный благодаря перестановке букв исходного сообщения. В те времена считалось, что созданные с помощью магических квадратов шифротексты охраняет не только ключ, но и магическая сила.

Пример магического квадрата и его заполнения сообщением ПРИЛЕТАЮ ВОСЬМОГО показан на рис. 2.24.

Рис. 2.24. Пример магического квадрата 4x4 и его заполнения сообщением ПРИЛЕТАЮ ВОСЬМОГО

Шифротекст, получаемый при считывании содержимого правой таблицы по строкам, имеет вполне загадочный вид:

ОИРМ ЕОСЮ ВТАЬ ЛГОП

Число магических квадратов быстро возрастает с увеличением размера квадрата. Существует только один магический квадрат размером 3x3 (если не учитывать его повороты). Количество возможных магических квадратов 4x4 составляет уже 880, а количество магических квадратов 5x5 – около 250 000. В связи с этим магические квадраты средних и больших размеров могли служить хорошей базой для обеспечения нужд шифрования того времени, поскольку практически нереально выполнить вручную перебор всех вариантов для такого шифра в целях его дешифровки.

Что касается расшифровки, то она при наличии ключа (то есть магического квадрата) чрезвычайно проста.

Метод гаммирования

Современный метод гаммирования базируется на методе одноразового блокнота Джозефа Моборна, который нами уже рассматривался. В годы Второй мировой войны этот метод был действительно труднореализуем, однако в условиях применения современных информационных технологий метод гаммирования стал одним из самых распространенных. Данный метод относится к категории методов замены (подстановки), но обычно его рассматривают отдельно.

Процесс шифрования заключается в данном случае в генерации гаммы шифра и наложении этой гаммы на исходный открытый текст. Наиболее часто на практике применяется двоичное гаммирование. В этом случае символы текста и гаммы представляются в двоичных кодах, а затем каждая пара двоичных разрядов складывается по модулю 2[7]. При необходимости двоичные коды можно преобразовать в обычный текст.

Процедура гаммирования на передаче и приеме представлена на рис. 2.25. При расшифровывании операция проводится повторно, в результате получается открытый текст. Символы текста и гаммы здесь также представляются первоначально в двоичных кодах.

Соответствие между буквенно-цифровыми символами и их двоичными кодами регулируется различными стандартами. В таблице 2.10 представлены коды буквенных символов русского языка в стандарте Windows 1251 и их двоичное представление. Этот стандарт представляет собой расширение стандарта ASCII для символов русского языка. В таблице 2.11 представлено кодирование латинских букв и некоторых других символов в ASCII.

Передатчик

Приемник

Рис.2.25. Процедура шифрования, основанная на «наложении» гамма-последовательности на открытый текст

Символы 0 – 31 ASCII (двоичные коды от 00000000 до 00011111) выполняют управляющие функции и не отображаются графическими знаками. В результате гаммирования может быть получен двоичный код, соответствующий этим символам. В этом случае при необходимости исключить в передаваемом сообщении двоичное отображение данных, восемь двоичных разрядов можно представить как две шестнадцатеричные цифры. Для общности с помощью двух шестнадцатеричных цифр можно отображать любой символ, соответствующий ASCII и Windows 1251. Соответствие между шестнадцатеричными и двоичными числами показано в табл. 2.12.

Приведем упрощенный пример шифрования / расшифровывания методом двоичного гаммирования. Необходимо зашифровать, а затем расшифровать короткую строку на русском языке РОССИЯ – 2018. В соответствии с таблицами 2.10 и 2.11 двоичное представление этой строки будет следующее:

1101 0000 1100 1110 1101 0001 1101 0001 1100 1000 1101 1111 0010 1101

0011 0010 0011 0000 0011 0001 0011 1000

С учетом таблицы 2.12 покажем шестнадцатеричное представление данного текста (два шестнадцатеричных символа соответствуют восьми бинарным):

D0 CE D1 D1 C8 DF 2D 32 30 31 38

В качестве случайно определенной гаммы, представляющей собой ключ для кодирования, принимается следующая строка, представленная в шестнадцатеричном виде: