5.2. Методы подстановки

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

Один из самых простейших методов замены был придуман еще Гаем Юлием Цезарем. Так называемый шифр Цезаря описан во всех учебниках по криптографии. В своих письмах Юлий Цезарь заменял каждую A на D, каждую B на E, и т. д. И его послание мог дешифровать только тот, кто знал правило «смещения на 3». Таким образом, шифр построен по алгоритму: читать четвертую букву вместо первой. При открытом тексте VENI VIDI VICI (пришел, увидел, победил) для алфавита, состоящего из 26 букв, получается шифротекст SBKF SFAF SFZF. Следует заметить, что алфавит замкнут на себя, то есть если при сдвиге не хватает букв слева, то смещение продолжается от крайнего правого знака алфавита.

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

Можно составить общую формулу моноалфавитной замены. Она выглядит следующим образом:

Y_i = chr(K₁ asc(X_i) +K₂) mod n, где

Y_i – символ шифротекста;

X_i – символ открытого текста;

K₁, K₂ – произвольные константы;

Chr(N) – функция, позволяющая определить символ, по его месту N в алфавите;

asc(S) – функция, позволяющая определить место символа S в алфавите (функция, обратная функции asc()).

r mod n – остаток от целочисленного деления r на n;

n – количество символов в алфавите.

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

Метод прямой замены. Опишем последовательность действий, характеризующих данный метод.

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

Рассмотрим пример.

Пусть

А₀=А,Б,В,Г,Д,Е,Ж,З,И,Й,К,Л,М,Н,О,П,Р,С,Т,У,Ф,Х,Ц,Ч,Ш,Щ,Ъ,Ы,Ь,Э,Ю,Я, _, где символом «_» обозначен пробел.

А₁=Ъ,Д,О,Ц,Н,В,Х,Й,Е,М,Ю,З,Ш,И,_,К,Ж,П,Р,Ь,Т,Г,С,Я,У,А,Ы,Э,Щ,Л,Ч,Б,Ф

Тогда получим соответствие: АЪ; БД; ВО; ГЦ; ДН; ЕВ; ЖХ; ЗЙ; ИЕ; ЙМ; КЮ; ЛЗ; МШ; НИ; О_; ПК; РЖ; СП; ТР; УЬ; ФТ; ХГ; ЦС; ЧЯ; ШУ; ЩА; ЪЫ; ЫЭ; ЬЩ; ЭЛ; ЮЧ; ЯБ; _Ф.

На основе имеющегося соответствия закодируем фразу: «СЕГОДНЯ У НАС НЕОБЫЧНО УДАЧНЫЙ ДЕНЬ».

Получим: «ПВЦ НИБФЬФИЪПФИВ ДЭЯИ ЬНЪЯИЭМФНВИЩ».

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

Таблица 3

Относительная частота букв русского алфавита

в осмысленных текстах

№ п/п	Буква	Относительная частота	№ п/п	Буква	Относительная частота	№ п/п	Буква	Относительная частота
1 2 3 4 5 6 7 8 9 10 11	А Б В Г Д Е Ж З И Й К	0,062 0,014 0,038 0,013 0,025 0,072 0,007 0,016 0,062 0,010 0,028	12 13 14 15 16 17 18 19 20 21 22	Л М Н О П Р С Т У Ф Х	0,035 0,026 0,053 0,090 0,023 0,040 0,045 0,053 0,021 0,002 0,009	23 24 25 26 27 28 29 30 31 32 33	Ц Ч Ш Щ Ъ Ы Ь Э Ю Я пробел	0,004 0,012 0,006 0,003 0,005 0,016 0,009 0,003 0,006 0,018 0,174

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

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

Однако заметим, что ни для каждой буквы можно однозначно определить ей соответствующую, так как в таблицах присутствуют одинаковые значения относительных частот символов. Например, одинаковое значение относительной частоты имеют такие буквы русского алфавита в осмысленном тексте, как Т и Н (0,053), И и А (0,062), Ю и Ш (0,006) и некоторые другие.

Таблица 4

Относительная частота букв русского алфавита

в закодированном тексте

№ п/п	Буква	Относительная частота	№ п/п	Буква	Относительная частота	№ п/п	Буква	Относительная частота
1 2 3 4 5 6 7 8 9 10 11	А Б В Г Д Е Ж З И Й К	0,003 0,018 0,072 0,009 0,014 0,062 0,040 0,035 0,053 0,016 0,023	12 13 14 15 16 17 18 19 20 21 22	Л М Н О П Р С Т У Ф Х	0,003 0,010 0,025 0,038 0,045 0,053 0,004 0,002 0,006 0,174 0,007	23 24 25 26 27 28 29 30 31 32 33	Ц Ч Ш Щ Ъ Ы Ь Э Ю Я пробел	0,013 0,006 0,026 0,009 0,062 0,005 0,021 0,016 0,028 0,012 0,090

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

Другим примером шифра простой замены может служить программа ROT13, которую обычно можно найти в операционной системе UNIX. С ее помощью буква "А" открытого текста на английском языке заменяется на букву "N", "В" — на "О" и так далее. Таким образом, ROT13 циклически сдвигает каждую букву английского алфавита на 13 позиций вправо. Чтобы получить исходный открытый текст надо применить функцию шифрования ROT 13 дважды:

Р = ROT13(ROT13(P))

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

Метод замены по таблице Вижинера (Метод Вижинера).

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

Y_i = chr(asc(X_i) + asc(Z_i)) mod n, где

Y_i – i-тый символ шифротекста;

X_i – i-тый символ открытого текста;

Z_i – i-тый символ ключа;

Chr(N) – функция, позволяющая определить символ, по его месту N в алфавите;

asc(S) – функция, позволяющая определить место символа S в алфавите (функция, обратная функции asc()).

r mod n – остаток от целочисленного деления r на n;

n – количество символов в алфавите.

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

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

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

А Б В Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ъ Ы Ь Э Ю Я

Б В Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ъ Ы Ь Э Ю Я А

В Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ъ Ы Ь Э Ю Я А Б

Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ъ Ы Ь Э Ю Я А Б В

Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ъ Ы Ь Э Ю Я А Б В Г

Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ъ Ы Ь Э Ю Я А Б В Г Д

Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ъ Ы Ь Э Ю Я А Б В Г Д Е

З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ъ Ы Ь Э Ю Я А Б В Г Д Е Ж

И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ъ Ы Ь Э Ю Я А Б В Г Д Е Ж З

Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ъ Ы Ь Э Ю Я А Б В Г Д Е Ж З И

К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ъ Ы Ь Э Ю Я А Б В Г Д Е Ж З И Й

Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ъ Ы Ь Э Ю Я А Б В Г Д Е Ж З И Й К

М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ъ Ы Ь Э Ю Я А Б В Г Д Е Ж З И Й К Л

Н О П Р С Т У Ф Х Ц Ч Ш Щ Ъ Ы Ь Э Ю Я А Б В Г Д Е Ж З И Й К Л М

О П Р С Т У Ф Х Ц Ч Ш Щ Ъ Ы Ь Э Ю Я А Б В Г Д Е Ж З И Й К Л М Н

П Р С Т У Ф Х Ц Ч Ш Щ Ъ Ы Ь Э Ю Я А Б В Г Д Е Ж З И Й К Л М Н О

Р С Т У Ф Х Ц Ч Ш Щ Ъ Ы Ь Э Ю Я А Б В Г Д Е Ж З И Й К Л М Н О П

С Т У Ф Х Ц Ч Ш Щ Ъ Ы Ь Э Ю Я А Б В Г Д Е Ж З И Й К Л М Н О П Р

Т У Ф Х Ц Ч Ш Щ Ъ Ы Ь Э Ю Я А Б В Г Д Е Ж З И Й К Л М Н О П Р С

У Ф Х Ц Ч Ш Щ Ъ Ы Ь Э Ю Я А Б В Г Д Е Ж З И Й К Л М Н О П Р С Т

Ф Х Ц Ч Ш Щ Ъ Ы Ь Э Ю Я А Б В Г Д Е Ж З И Й К Л М Н О П Р С Т У

Х Ц Ч Ш Щ Ъ Ы Ь Э Ю Я А Б В Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф

Ц Ч Ш Щ Ъ Ы Ь Э Ю Я А Б В Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х

Ч Ш Щ Ъ Ы Ь Э Ю Я А Б В Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц

Ш Щ Ъ Ы Ь Э Ю Я А Б В Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч

Щ Ъ Ы Ь Э Ю Я А Б В Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш

Ъ Ы Ь Э Ю Я А Б В Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ

Ы Ь Э Ю Я А Б В Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ъ

Ь Э Ю Я А Б В Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ъ Ы

Э Ю Я А Б В Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ъ Ы Ь

Ю Я А Б В Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ъ Ы Ь Э

Я А Б В Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ъ Ы Ь Э Ю

Рис 7. Таблица Вижинера, построенная на алфавите кириллицы

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

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

Поясним сказанное на примере.

Пусть в качестве исходного алфавита выбран алфавит кириллицы и имеется текст: «ИЗУЧАЕМ МЕТОДЫ ШИФРОВАНИЯ ТЕКСТОВ».

Для указанного алфавита таблица Вижинера уже построена (Рис. ). В качестве ключа шифрования, соблюдая обязательные требования, выберем слово «ВОЗРАСТ». Тогда, в соответствии с третьим шагом получим:

И

З

У

Ч

А

Е

М

М

Е

Т

О

Д

Ы

Ш

И

Ф

Р

О

В

А

Н

И

Я

Т

Е

К

С

Т

О

В

В

О

З

Р

А

С

Т

В

О

З

Р

А

С

Т

В

О

З

Р

А

С

Т

В

О

З

Р

А

С

Т

В

О

Следующий шаг предполагает непосредственное получение закодированного текста. Для этого каждый символ исходного текста заменяется на символ из таблицы Вижинера, стоящий на пересечении столбца, первый символ которого – символ исходного текста, и строки, первый символ которой – символ ключа, записанный под символом исходного текста. Например, первый символ исходного текста «И» заменится символом «К» так как именно этот символ стоит на пересечении столбца, начинающегося с символа «И» и строки, начинающейся с символа «В». Аналогичным образом находится символ, который заменит второй символ исходного текста – «З», под которой стоит символ «О» ключа шифрования. Это будет «Х».

Проделав замены с каждым символом исходного текста, получим следующий закодированный текст: «КХЪЗАЦЮ ОУЩЮДМ ККВЧЮВСЯКН».

Очевидным преимуществом этого метода замены перед методом прямой замены является то, что одинаковые символы исходного текста, как правило, заменяются на разные буквы. Так, например, символ «Е», встречающийся в слове «ИЗУЧАЕМ» исходного текста был заменен на символ «Ц», а символ «Е», встречающийся в слове «МЕТОДЫ» был заменен на символ «У».

Последовательность шагов при дешифровке очевидна.

1-й шаг: под символами закодированного текста записать символы ключа, повторяя ключ столько раз, сколько это необходимо.

2-ой шаг: в строке, начинающейся с символа ключа, найти соответствующий символ закодированного текста, определить столбец, в котором он стоит, и записать символ, с которого начинается этот столбец.

Суть криптоанализа при этом будет заключаться в поиске ключа шифрования.