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

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

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

 

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

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

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

Буква А Б В Г Д Е Ж И И К Л
Код
Буква М Н О П Р С Т У Ф X Ц Ч
Код
Буква Ш Щ Ъ Ы Ь Э Ю Я _ (пробел)
Код

 

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

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

yi=k1*xi+k2(mod n),

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

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

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

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

 

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

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

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

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

yi=xi+ki(mod n),

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

 

 

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

 

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

А М Е Н А
К Л Ю Ч К Л

 

y1=8+11(mod 33)=19 ® Тy2=1+12(mod 33)=13 ® Му3=13+31(mod ЗЗ)=11® Кy4=6+24(mod 33)=30 ® Эу5=14+11(mod 33)=25 ® Шy6=1+12(mod 33)=13 ® М

Шифртекст «ТМКЭШМ».

 

Шифры Бофора используют формулы уi=ki-xi(mod n) и yi=xi-ki(mod n).

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

x=x1x2...xkxk+1...x2kx2k+1...

заменяется шифртекстом

y=f1(x1)f2(x2)...fk(xk)fk+1(xk+1)...f2k(x2k)f2k+1(x2k+1)

где fi(xj) означает символ шифртекста алфавита i для символа от­крытого текста xj.

 

Пример 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»

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

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

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

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

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

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

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

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

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

 

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

 

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

 

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

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

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

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

 

Ш И Ф Р О В А Н И Е _ А М Е Н О Й
К Л Ю Ч Ш И Ф Р О В А Н И Е _ А М
В Ф Т Ж Л Х Ю Ч И А Х Й Т Е X П Ц

 

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

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

 

Ш И Ф Р О В А Н И Е _ А М Е Н О Й
К Л Ю Ч В Ф Т С Ч У Х Ъ Э У Э Ы И
В Ф Т С Ч У X Ъ Э У Э Ы Й Щ К Й У

 

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

 

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

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

 

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

 

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

 

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

 

Матрица из четырех столбцов приведена в табл 8, где запись по строкам в соответствии с ключом k1 5-3-1-2-4-6. а чтение по столбцам в соответствии с ключом k2 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