КОДИРОВАНИЕ КАК СРЕДСТВО КРИПТОГРАФИЧЕСКОГО ЗАКРЫТИЯ ИНФОРМАЦИИ

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

Во многих случаях хранимая и передаваемая информация может представлять интерес для лиц, желающих использовать ее в корыстных целях. Последствия от такого несанкционированного использования информации могут быть весьма серьезными. Поэтому уже в настоящее время возникла проблема защиты информации от несанкционированного доступа [3]. В данном разделе ограничимся рассмотрением методов защиты информации от несанкционированного доступа при передаче ее по каналам связи. Рассматриваемые методы защиты обеспечивают такое преобразование сообщений, при котором их исходное содержание становится доступным лишь при наличии у получателя некоторой специфической информации (ключа) и осуществления с ее помощью обратного преобразования. Эти методы называют методами криптографического закрытия информации. Они применяются как для защиты информации в каналах передачи, так и для защиты ее в каналах хранения.

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

Известно большое число различных методов криптографического закрытия информации. В настоящее время утвердились в практике следующие основные криптографические методы защиты: замены (подстановки); перестановки; использования генератора псевдослучайных чисел (гаммирование); перемешивания (алгоритмитические); использование систем с открытым ключом. Классификация методов преобразования информации приведена на рисунке 9.1. Рассмотрим некоторые из них в порядке возрастания сложности и надежности закрытия.

Метод замены

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

Пример 9.1. Зашифровать сообщение «ИНФОРМАЦИЯ», используя в качестве ключа для шифрования русского текста буквы русского алфавита в соответствии с таблицей 9.1.

Таблица 9.1 - Замена одних букв другими

Подставляя новые буквы, получаем криптограмму «ЦЭДЮАЬПЗЦО».

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

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

Таблица 9.2 - Частота появления букв английского языка в тексте

Таблица 9.3 - Частота появления букв русского языка в тексте

Ещё одна классическая система шифрования, изображенная на рисунке 9.2, называется квадратом Полибиуса (Polybius square).

Рисунок 9.2 – Квадрат Полибиуса

Вначале объединяются буквы I и J и трактуются как один символ ( в дешифрованном сообщении значение этой « двойной буквы» легко определяется из контекста). Получившиеся 25 символов алфавита размещаются в таблицу размером . Шифрование любой буквы производится с помощю выбора соответствующей пары числе – строки и столбца (или столбца и строки).

Пример 9.2.Зашифровать сообщение «now is the time» с помощью квадрата Полибиуса. Схема шифрования приведена в таблице 9.4.

Таблица 9.4 - Схема шифрования с помощью квадрата Полибиуса

Код изменяется путем перестановки букв в таблице .

Шифр Виженера (Vigener key method) – этот шифр является одним из наиболее распространенных. Степень надежности закрытия информации повышается за счет того, что метод шифрования предусматривает нарушение статистических закономерностей появления букв алфавита.

Каждая буква алфавита нумеруется. Например, буквам русского алфавита ставятся в соответствие цифры от 0 до 33 (таблица 9.5).

Ключ представляет собой некоторое слово или просто последовательность букв, которая подписывается с повторением под сообщением. Цифровой эквивалент каждой буквы криптограммы определяется в результате сложения с приведением по модулю 33 цифровых эквивалентов буквы сообщения и лежащей под ней буквы ключа , т.е.

Таблица 9.5 - Кодирование букв русского алфавита

Продолжение таблицы 9.5

Пример 9.3. Зашифруем сообщение «ИНФОРМАЦИЯ» кодом Виженера с ключом «НЕМАН».

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

Складывая верхние и нижние цифровые эквиваленты с приведением по модулю 33, получим следующую последовательность чисел

23 20 1 16 31 27 7 3 10 13 , что соответствует криптограмме

«Ц У А П Ю Ъ Ж В Й М» .

Шифр Вижинера обладает достаточно высокой надежностью закрытия только при использовании весьма длинных ключей.

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

Разновидностью шифра Вижинера является шифр Бофора, но при этом при определении цифрового эквивалента используют формулы

и

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

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

Пример 9.4. Открытый текст: «ШИФРОВАНИЕ ЗАМЕНОЙ».

Первичный ключ «КЛЮЧ» Схема шифрования с автоключом при использовании открытого текста представлена в таблице 9.6.

Таблица 9.6 - Схема шифрования с автоключом при использовании

открытого текста

Схема шифрования с автоключом при использовании криптограммы представлена в таблице 9.7

Таблица 9.7 - Схема шифрования с автоключом при использовании

криптограммы

Для шифрования используются и другие методы подстановки символов открытого текста в соответствии с некоторыми правилами.

Гомофоническая замена одному символу открытого текста ставит в соответствие несколько символов шифртекста. Этот метод применяется для искажения статистических свойств шифртекста.

Пример 9.5. Открытый текст «ЗАМЕНА». Подстановка задана таблицей 9.8.

Таблица 9.8 - Подстановка алфавита гомофонической замены

Шифртекст «76-17-32-97-55-31».

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

Полиалфавитная подстановка использует несколько алфавитов шифртекста. Пусть используется k алфавитов. Тогда открытый текст

заменяется шифртекстом

где означает символ шифртекста алфавита i для символа открытого текста

Пример 9.6. Открытый текст «ЗАМЕНА» k = 3 Подстановка задана таблицей из примера 9.5. Шифртекст «76 31 61 97 84 48».

Прогрессивный ключ Тритемиуса, который изображен на рисунке 9.3, является примером полиалфавитного шифра. Строка, обозначенная как сдвиг 0, совпадает с обычным порядком букв в алфавите. Буквы в следующей строке сдвинуты на один символ влево с циклическим сдвигом оставшихся позиций. Каждая последующая строка получается с помощью такого же сдвига алфавита на один символ влево относительно предыдущей строки. Это продолжается до тех пор, пока в результате циклических сдвигов алфавита не будет смещен на все возможные позиции. Один из методов использования такого алфавита заключается в выборе первого символа шифрованного сообщения из строки, полученной при сдвиге на 1 символ, второго символа – из строки, полученной при сдвиге на 2 символа, и т.д.

Пример 9.7. Зашифровать сообщение «NOWISTHETIME» ключом Тритемиуса. Результат шифрования приведен в таблице 9.9.

Рисунок 9.3 – Прогрессивный ключ Тритемиуса.

Таблица 9.9 - Подстановка алфавита гомофонической замены

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

В этом шифре алфавит располагается в матрице. Открытый текст разбивается на пары символов Каждаяпара символов открытого текста заменяется на пару символов из матрицы следующим образом:

–если символы находятся в одной строке, то каждый из символов пары заменяется на стоящий правее его (за последним символом в строке следует первый);

–если символы находятся в одном столбце, то каждый символ пары заменяется на символ расположенный ниже его в столбце (за последним нижним символом следует верхний);

–если символы пары находятся в разных строках и столбцах, то они считаются противоположными углами прямоугольника. Символ, находящийся в левом углу заменяется на символ, стоящий в другом левом углу. Замена символа, находящегося в правом углу осуществляется аналогично;

–если в открытом тексте встречаются два одинаковых символа подряд, то перед шифрованием между ними вставляется специальный символ (например, тире).

Пример 9.8. Открытый текст «ШИФР ПЛЭЙФЕРА» Матрица алфавита представлена в таблице 9.6

Таблица 9.8 - Матрица алфавита шифра Плэйфера

Шифртекст «РДЫИ,-СТ-И. ХЧС».

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

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

Рисунок 9.4 – Блок подстановки

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

(9.1)

где a и b – входные элементы, С и С’ – выходные элементы, а Т - преобразование. Тогда если T линейно, С=С’ для всех входных элементов, а если Т нелинейно,

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

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