Шифрование методом перестановки

Требования к шифрам

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

Методы шифрования

Шифрование заменой (подстановкой)

В этом, наиболее простом методе символы шифруемого текста заменяются другими символами, взятыми из одного (одно- или моноалфавитная подстановка) или нескольких

(много- или полиалфавитная подстановка) алфавитов. Самой простой разновидностью является прямая замена, когда буквы шифруемого сообщения заменяются другими буквами того же самого или некоторого другого алфавита. Таблица замены может иметь следующий вид (таблица 1).

Таблица 1 - Таблица простой замены

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

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

Шифрование методом перестановки

Этот метод заключается в том, что символы шифруемого текста переставляются по определенным правилам внутри шифруемого блока символов. Если после замены символы сообщения превращались во что угодно, но сохраняли в шифровке свое исходное местоположение, после перестановки они там расположены еще и где угодно, что надежно защищает шифровку от атак криптологов.

Простейшим примером перестановки является запись исходного текста по строкам некоторой матрицы, а чтение его по строкам этой матрицы. Последовательность заполнения строк и чтения столбцов может быть любой и задается ключом. Таким образом, для матрицы размерностью 8? 8 (длина блока 64 символа) возможно 1,6? 10⁹ ключей, что позволяет на современных ЭВМ путем перебора расшифровать заданный текст. Однако для матрицы размерность 16? 16 (длина блока 64 символа) имеется 1,4? 10²⁶ ключей и перебор их с помощью современных средств практически неосуществим.

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

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

Рисунок 1 Пример усложненной перестановки по таблице

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

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

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

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

Рисунок 2 - Вариант схемы маршрутов Гамильтона