Шифрование методом замены

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

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

При моноалфавитной замене каждой букве алфавита открытого текста ставится в соответствие одна и та же буква шифротекста из этого же алфавита одинаково на всем протяжении текста.

Рассмотрим наиболее известные шифры моноалфавитной замены.

Шифрование методом Цезаря

Свое название данный шифр получил по имени римского императора Гая Юлия Цезаря, который использовал этот шифр при переписке с Цицероном (около 50 г. до н.э).

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

Общая формула шифра Цезаря имеет следующий вид:

где P – номер символа открытого текста, С – соответствующий ему номер символа шифротекста, K – ключ шифрования (коэффициент сдвига), M – размер алфавита (для русского языка M=32)

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

Пример 6.1.

Таблица подстановок для символов русского текста при ключе K=3 представлена в таблице 6.1. Данной таблице соответствует формула

Табл. 6.1. Табл. подстановок шифра Цезаря для ключа K=3

Согласно формуле (6.2.) открытый текст «БАГАЖ» будет преобразован в шифротекст «ДГЖГЙ».

Дешифрование закрытого текста, зашифрованного методом Цезаря согласно (6.1), осуществляется по формуле

Простая моноалфавитная замена

Шифр простой моноалфавитной замены является обобщением шифра Цезаря и выполняет шифрование по следующей схеме:

,

(6.4.)

где - ключ шифрования, .

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

(6.5.)

Пример 6.2.

Пусть M=26, a=3, K=6, НОД(3,26) = 1. Тогда получаем следующую таблицу подстановок для шифра простой моноалфавитной замены (в таблице указаны коды букв русского алфавита).

Тогда открытый текст «HOME» будет преобразован в шифротекст «BWQS».

Шифрующие таблицы Трисемуса

Данный шифр был предложен в 1508 году аббатом из Германии Иоганом Трисемусом [18] Для получения данного шифра замены им было предложено использовать таблицу для записи букв алфавита и ключевого слова или фразы. В таблицу сначала вписывалось по строкам ключевое слово, причем повторяющиеся буквы отбрасывались. Затем эта таблица дополнялась не вошедшими в нее буквами алфавита по порядку. При шифровании в построенной таблице находят очередную букву открытого текста и записывают в шифротекст букву, расположенную ниже ее в том же столбце. Если буква открытого текста оказывается в нижней строке таблицы, тогда для шифротекста берут самую верхнюю букву из того же столбца.

Для русского алфавита шифрующая таблица может иметь размер 4х8.

Пример 6.3.

Выберем в качестве ключа слово ПАМЯТНИК. Шифрующая таблица с данным ключом представлена в таблице 6.2.

Табл. 6.2. Шифрующая таблица Трисемуса

Тогда открытый текст «НЕРУКОТВОРНЫЙ» будет преобразован в закрытый текст «ЖУЩЫЙШЕОШЩЖТЦ».

Достоинством методов моноалфавитной замены является простота шифрования и дешифрования.

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

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

Многоалфавитные шифры замены предложил и ввел в практику криптографии Леон Батист Альберти. Рассмотрим ряд примеров шифров многоалфавитной замены.

Шифр Гронсфельда

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

Пример 6.4.

Пусть необходимо зашифровать исходное сообщение «НОЧЕВАЛА ТУЧКА ЗОЛОТАЯ», в качестве ключа возьмем К=193431.

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

Дешифрование шифротеста предполагает сдвиг его символов на необходимое число позиций в обратную сторону.

Система шифрования Вижинера

Отличие системы Вижинера от шифра Гронсфельда заключается в том, что элементами ключа в данном случае могут быть не только цифры от 0 до 9, но и произвольные символы некоторого алфавита.

При шифровании исходного сообщения его, как и в шифре Гронсфельда, выписывают в строку, а под ним записывают ключевое слово или фразу. Если ключ оказался короче сообщения, то его циклически повторяют. Все символы используемого алфавита пронумерованы от 0 до M-1, где M – размер алфавита. Преобразование символа открытого текста осуществляется по формуле

где P_i - номер символа открытого текста, K_i – номер расположенного под ним символа ключа, С_i – номер символа шифротекста.

Преобразование символа закрытого текста в символ открытого осуществляется по формуле

P_i=C_i -K_i (mod M)

Пример 6.6.

Рассмотрим пример шифрования сообщения ПРИЛЕТАЮ ДНЕМ по методу Вижинера с помощью ключевого слова СИСТЕМА

В данном случае буквы русского алфавита пронумерованы от 0 до 31: А-0, Б-1, В-2, ... , Я-31.

Шифрование методом Вернама

Система шифрования Вернама является частным случаем системы шифрования Вижинера при значении модуля M=2 [8].

При шифровании открытого текста, каждый его символ представляется в двоичном виде. Ключ шифрования также представляется в двоичной форме. Шифрование исходного текста осуществляется путем сложения по модулю 2 двоичных символов открытого текста с двоичными символами ключа согласно (6.7).

Дешифрование состоит в сложении по модулю 2 символов шифротекста с ключом.

Общая схема системы шифрования Вернама представлена на рис. 6.2.

Рис. 6.2. Схема системы шифрования Вернама

Модификация системы шифрования Вернама используется для криптографической защиты информации в архиваторе ARJ. Формула (6.7) в этом случае преобразуется в следующую:

где VALUE – фиксированное значение.

Пример 6.7.

Зашифруем с помощью системы Вернама открытый текст «БЛАНК» с помощью ключа «ОХ».

Преобразуем открытый текст «БЛАНК» в ASCII коды: Б=193, Л=203, A=192, Н=205, К=202. В двоичном виде последовательность 193, 203, 192, 205, 202 представится в виде 11000001 11001011 11000000 11001101 11001010.

Преобразуем ключ «ОХ» в ASCII коды: О=206, Х=213. В двоичном виде последовательность 206, 213 представится в виде 11001110 11010101.

Подпишем циклически ключ под открытым текстом и выполним сложение по модулю 2 соответствующих битов.

G-контурная многоалфавитная замена

Данный метод шифрования предполагает многократное использование системы шифрования Вижинера при использовании различных ключей. n-контурная многоалфавитная замена предполагает наличие n различных ключей – K₁, K₂,..., K_n. Открытый текст T вначале шифруется с помощью ключа K₁, затем результат шифрования обрабатывается с помощью ключа K₂ и.т.д. до ключа K_n. Полученный в результате шифрования на ключе K_n текст и является искомым шифротекстом.