Лабораторная работа №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