Наиболее сложные перестановки осуществляются по гамильтоновым путям, которых в графе может быть несколько.

Лабораторная работа №1

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

В криптографии рассматриваются четыре типа подстановки (замены): моноалфавитная, полиалфавитная, гомофоническая и полиграммная.

Далее всюду в примерах использовано кодирование букв русского алфавита, приведенное в табл. 1.

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

Буква

Код

Буква

Код

Буква

_ (пробел)

Код

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

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

y_i=k₁*x_i+k₂(mod n) ,

где у _i — i-й символ алфавита k₁ и k₂ — константы, х _i — i-й символ открытого текста (номер буквы в алфавите), n — длина используемого алфавита.

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

Пример 1. Открытый текст «ШИФРОВАНИЕ_ЗАМЕНОЙ». Подстановка

задана табл. 2.

Таблица 2 Подстановка алфавита для шифрования заменой

Алфавит исходного текста	А	Б	В	Г	Д	…	Ь	Э	Ю	Я	_
Алфавит шифртекста	_	Я	Ю	Э	Ь	…	Д	Г	В	Б	А

Шифртекст «ИШМРТЮ_УШЫАЩ_ФЫУТЧ».

Шифр, задаваемый формулой

y_i=x_i+k_i(mod n) ,

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

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

Таблица 3 Подстановка шифра Вижинера

А М Е Н А

К Л Ю Ч К Л

y₁=8+11(mod 33)=19 ® Тy₂=1+12(mod 33)=13 ® Му₃=13+31(mod ЗЗ)=11® Кy₄=6+24(mod 33)=30 ® Эу₅=14+11(mod 33)=25 ® Шy₆=1+12(mod 33)=13 ® М
Шифртекст «ТМКЭШМ».

Шифры Бофора используют формулы у_i=k_i-x_i(mod n) и y_i=x_i-k_i(mod n).

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

x=x₁x₂...x_kx_k+1...x_2kx_2k+1...

заменяется шифртекстом
y=f₁(x₁)f₂(x₂)...f_k(x_k)f_k+1(x_k+1)...f_2k(x_2k)f_2k+1(x_2k+1)
где f_i(x_j) означает символ шифртекста алфавита i для символа открытого текста x_j.

Пример 3. Открытый текст: «ЗАМЕНА», k = 3. Подстановка задана табл. 4.

Шифртекст- «76 31 61 97 84 48».

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

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

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

Алфавит открытого текста	А	Б	…	Е	Ж		…	М	Н	…
Алфавит шифртекста	17 31 48	23 44 63	… …	97 51 15	47 67 33	19 59	… …	32 28 61	55 84 34	… …

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Пример 6. Открытый текст «ШИФРОВАНИЕ ЗАМЕНОЙ». Первичный ключ «КЛЮЧ». Схема шифрования с автоключом при использовании открытого текста представлена в табл. 6.

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

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

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

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

Пример 7. Открытый текст «ШИФРОВАНИЕ_ПЕРЕСТАНОВКОЙ»

Ключ (правило перестановки): группы из восьми букв с порядковыми номерами 1..2….8 переставить в порядок 3-8-1-5-2-7-6-4.

Шифртекст «ФНШОИАВР_СИЕЕЕРПННТВАОКО»

Можно использовать и усложненную перестановку. Для этого открытый текст записывается в матрицу по определенному ключу k₁. Шифртекст образуется при считывании из этой матрицы по ключу k₂.

Пример. 8. Открытый текст «ШИФРОВАНИЕ_ПЕРЕСТАНОВКОЙ»

Матрица из четырех столбцов приведена в табл 8, где запись по строкам в соответствии с ключом k₁ 5-3-1-2-4-6. а чтение по столбцам в соответствии с ключом k₂ 4-2-3-1.

Таблица 8. Матрица алфавита с перестановкой из четырех столбцов

	И	Е	_	П
	Е	Р	Е	С
	О	В	А	Н
	Т	А	Н	О
	Ш	И	Ф	Р
	В	К	О	Й
K₁/K₂

Шифртекст «ПСНОРЙЕРВАИК_ЕАНФОИЕОТШВ»

Наиболее сложные перестановки осуществляются по гамильтоновым путям, которых в графе может быть несколько.

Пример 9. Открытый текст «ШИФРОВАНИЕ_ПЕРЕСТАНОВКОЙ». Ключ — гамильтонов путь на графе (рис. 2).

Шифртекст «ШАОНИРФВИЕЕСЕП_РТОВИАОНК»

Чтение криптограммы (1-7-5-8-2-4-3-6)

Запись открытого текста (1-2-3-4-5-6-7-8)

Рис. 2. Гамильтонов путь на графе

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

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

В 1992—94 г.г. идея применения объемной перестановки для шифрования открытого текста получила дальнейшее развитие. Усовершенствованная схема перестановок по принципу кубика Рубика, в которой наряду с открытым текстом перестановке подвергаются и функциональные элементы самого алгоритма шифрования, легла в основу секретной системы «Рубикон». В качестве прообразов пространственных многомерных структур, на основании объемных преобразований которых осуществляются перестановки, в системе «Рубикон» используются трехмерный куб и тетраэдр

Лабораторная работа №2