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

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

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

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

Используя эту таблицу, зашифруем текст: In this book the reader will find a comprehensive survey... Получим следующее зашифрованное сообщение: At omiy pbbe omr nrsirn fadd zail s xbwgnrmrtjafr jcnfru... Однако такой шифр имеет низкую стойкость, так как зашифрованный текст имеет те же статистические характеристики, что и исходный. Например, текст на английском языке содержит символы со следующими частотами появления (в порядке убывания): Е — 0,13, Т — 0,105, А — 0,081, О — 0,079 и т. д. В зашифрованном тексте наибольшие частоты появления в порядке убывания имеют буквы R — 0,12, О-0,09, А и N по 0,07.

Естественно предположить, что символом R зашифрована буква Е, символом О — буква T и т. д. Это действительно соответствует таблице замены. Дальнейшая расшифровка не составляет труда. Эти методы дешифровки хорошо известны из классической литературы (см., например, Артур Конан Дойль, «Пляшущие человечки», или Алан Эдгар По, «Золотой жук»).

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

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

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

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

Схема шифрования Вижинера. Таблица Вижинера представляет собой квадратную матрицу с n² элементами, где n — число символов используемого алфавита. На рис. 3.2 показана таблица Вижинера для кириллицы. Каждая строка получена циклическим сдвигом алфавита на символ. Для шифрования выбирается буквенный ключ, в соответствии с которым формируется рабочая матрица шифрования.

Осуществляется это следующим образом. Из полной таблицы выбирается первая строка и те строки, первые буквы которых соответствуют буквам ключа. Первой размешается первая строка, а под нею — строки, соответствующие буквам ключа в порядке следования этих букв в ключе. Пример такой рабочей матрицы для ключа САЛЬЕРИ приведен в средней части рис. 3.3.

Процесс шифрования осуществляется следующим образом:

1) под каждой буквой шифруемого текста записываются буквы ключа. Ключ при этом повторяется необходимое число раз; 2) каждая буква шифруемого текста заменяется по подматрице буквами, находящимися на пересечении линий, соединяющих буквы шифруемого текста в первой строке подматрицы и находящихся под ними букв ключа; 3) полученный текст может разбиваться на группы по несколько знаков. Пусть, например, Требуется зашифровать сообщение: МАКСИМАЛЬНО ДОПУСТИМОЙ ЦЕНОЙ ЯВЛЯЕТСЯ ПЯТЬСОТ РУБ. ЗА ШТУКУ. В соответствии с первым правилом записываем под буквами шифруемого текста буквы ключа. Получаем:

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

сальерисаль ерисальери салье рисальер исальер иса ль ериса

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

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

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

число раз; 2) в строке подматрицы Вижинера, соответствующей букве ключа, отыскивается буква, соответствующая знаку зашифрованного текста. Находящаяся под ней буква первой строки подматрицы и будет буквой исходного текста; 3) полученный текст группируется в слова по смыслу.

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

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

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

С целью повышения стойкости шифрования можно использовать усовершенствованные варианты таблицы Вижинера. Приведем некоторые из них: 1) во всех (кроме первой) строках таблицы буквы располагаются в произвольном порядке; 2) в качестве ключа используются случайные последовательности чисел. Из таблицы Вижинера выбираются десять произвольных строк, которые кодируются натуральными числами от 0 до 10. Эти строки используются в соответствии с чередованием цифр в выбранном ключе. Известны и другие модификации метода.

Вариант системы подстановок Вижинера при т = 2 называется системой Вернама (1917 год). В то время ключ k = (k₀, k₁, ... , k_k - 1) записывался на бумажной ленте. Каждая буква исходного текста переводилась с использованием кода Бодо в пятибитовый символ. К исходному тексту Бодо добавлялся ключ (по модулю 2). Старинный телетайп фирмы AT&T со считывающим устройством Вернама и оборудованием для шифрования использовался корпусом связи армии США.

Монофоническая замена

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

руем монофоническим шифром тот же текст, который шифровался простой заменой:

In this book the reader will find a comprehensive survey...

Шифрованный текст имеет вид:

А(-,) VNG/LjpGZ+F.=hg...

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

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

Общий принцип шифрования подстановкой может быть представлен следующей формулой:

Ri=Si+w mod(k-1),

где R, — символ зашифрованного текста; S, — символ исходного текста; w — целое число в диапазоне 0—(k- I); k — число символов используемого алфавита.

Если w фиксировано, то формула описывает моноалфавитную , подстановку, если w выбирается из последовательности w^, w-^, ... w,„ ^ то получается полиадфавитная подстановка с периодом п.

Если в полиалфавитной подстановке п > т (где т — число знаков шифруемого текста) и любая последовательность w,, w;, ... w„ используется только один раз, то такой шифр является теоретически нераскрываемым, если, конечно, злоумышленник не имеет доступа к исходному тексту. Такой шифр получил название шифра Вермэна.

Поиск по сайту: