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

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

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

 

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

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

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

Буква

А

Б

В

Г

Д

Е

Ж

И

И

К

Л

Код

Буква

М

Н

О

П

Р

С

Т

У

Ф

X

Ц

Ч

Код

Буква

Ш

Щ

Ъ

Ы

Ь

Э

Ю

Я

_ (пробел)

Код

 

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

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

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. Схема шифрования с автоключом при ис­пользовании открытого текста

 

Ш

И

Ф

Р

О

В

А

Н

И

Е

_

А

М

Е

Н

О

Й

К

Л

Ю

Ч

Ш

И

Ф

Р

О

В

А

Н

И

Е

_

А

М

В

Ф

Т

Ж

Л

Х

Ю

Ч

И

А

Х

Й

Т

Е

X

П

Ц

 

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

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

 

Ш

И

Ф

Р

О

В

А

Н

И

Е

_

А

М

Е

Н

О

Й

К

Л

Ю

Ч

В

Ф

Т

С

Ч

У

Х

Ъ

Э

У

Э

Ы

И

В

Ф

Т

С

Ч

У

X

Ъ

Э

У

Э

Ы

Й

Щ

К

Й

У

 

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

 

Пример 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. Матрица алфавита с перестановкой из четырех столбцов

	И	Е	_	П
	Е	Р	Е	С
	О	В	А	Н
	Т	А	Н	О
	Ш	И	Ф	Р
	В	К	О	Й
K1/K2

 

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

 

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

 

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

 

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

 

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

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

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

 

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

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

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

 

 

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