Министерство науки и высшего образования Российской Федерации

Федеральное государственное бюджетное образовательное учреждение высшего образования

«ТОМСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ СИСТЕМ УПРАВЛЕНИЯ И РАДИОЭЛЕКТРОНИКИ» (ТУСУР)

Кафедра комплексной информационной безопасности электронно-вычислительных систем (КИБЭВС)

«ШИФР ХИЛЛА»

Отчет по индивидуальному домашнему заданию №2 по дисциплине «Криптографические методы защиты информации»

Студент гр. 739-1

_______Климанов М.Д.

25.12.2021

Преподаватель кафедры

КИБЭВС

_____ Полюга В.А.

__.__.2021

Томск 2021

1 Введение

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

2 Ход работы

2.1 Шифр Хилла

Зашифруем слово Лягуха и разобьем его по 3 буквы. Выберем ключ Альбатрос. Составим матрицу исходного слова, а также конечную матрицу ключа (либо 2х2, либо 3х3). Перемножим блоки матрицы на конечную матрицу ключа и получим шифротекст (рисунок 2.1).

Рисунок 2.1 - Пример работы таблицы

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

q	r	y	n	a	y2	y1
			37	25	0	1
1	12	-1	25	12	1	-1
2	1	3	12	1	-1	3
12	0	-37	1	0	3	-37
#ДЕЛ/0!	#ДЕЛ/0!	#ДЕЛ/0!	0	#ДЕЛ/0!	-37	#ДЕЛ/0!
#ДЕЛ/0!	#ДЕЛ/0!	#ДЕЛ/0!	#ДЕЛ/0!	#ДЕЛ/0!	#ДЕЛ/0!	#ДЕЛ/0!
#ДЕЛ/0!	#ДЕЛ/0!	#ДЕЛ/0!	#ДЕЛ/0!	#ДЕЛ/0!	#ДЕЛ/0!	#ДЕЛ/0!
#ДЕЛ/0!	#ДЕЛ/0!	#ДЕЛ/0!	#ДЕЛ/0!	#ДЕЛ/0!	#ДЕЛ/0!	#ДЕЛ/0!
#ДЕЛ/0!	#ДЕЛ/0!	#ДЕЛ/0!	#ДЕЛ/0!	#ДЕЛ/0!	#ДЕЛ/0!	#ДЕЛ/0!
#ДЕЛ/0!	#ДЕЛ/0!	#ДЕЛ/0!	#ДЕЛ/0!	#ДЕЛ/0!	#ДЕЛ/0!	#ДЕЛ/0!
#ДЕЛ/0!	#ДЕЛ/0!	#ДЕЛ/0!	#ДЕЛ/0!	#ДЕЛ/0!	#ДЕЛ/0!	#ДЕЛ/0!

Рисунок 2.2 – Обратное определителя равно единице

Поиск алгебраических дополнений представлены на рисунке 2.3.

Рисунок 2.3 – Расчет дополнений матрицы

Получившуюся матрицу из алгебраических дополнений нужно транспонировать и домножить на определитель (рисунок 2.4).

Рисунок 2.4 – Транспонирование и перемножение матрицы и определителя

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

Рисунок 2.5 – Успешно расшифрованное слово

2.2 Рекуррентный шифр Хилла

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

Зашифруем слово «банальный», где одним из ключей будет слово «жестянщик», а остальные – случайным набором цифр, которые привязаны к алфавиту (рисунки 2.6 - 2.8).

Рисунок 2.6 – Процесс шифрования (1)

Рисунок 2.7 – Процесс шифрования (2)

Рисунок 2.8 – Процесс шифрования (3)

Конечный шифротекст: «аэяуфьовё».

Расшифруем данное зашифрованное слово аналогичным способом, как делали это в обычном шифре Хилла. Найдем алгебраические дополнения матрицы и сразу сделаем дешифрацию блока (рисунок 2.9 – 2.11).

Рисунок 2.9 – Поиск алгебраических дополнений и его дешифрация (1)

Рисунок 2.10 – Поиск алгебраических дополнений и его дешифрация (2)

Рисунок 2.11 – Поиск алгебраических дополнений и его дешифрация (3)

3 Криптоанализ

Криптоанализ только для зашифрованного шифрами Хилла текста труден. Во-первых, атака грубой силы при шифре Хилла чрезвычайно сложна, потому что матрица-ключ – m*m. Каждый вход может иметь одно из 37 значений. Во-первых, это означает размер ключа 37^(m*m).

Во-вторых, шифры Хилла не сохраняют статистику обычного текста. Невозможно провести анализ частоты отдельных букв из двух или трех букв. Анализ частоты слов размера m мог бы сработать, но очень редко исходный текст имеет много одинаковых строк размера m. Можно провести атаку на шифр, используя метод знания исходного текста, если знать значение m и пары "исходный текст/зашифрованный текст", по крайней мере m блоков. Блоки могут принадлежать тому же самому сообщению или различным сообщениям, но должны быть различны. Поэтому можно создать две m*m матрицы, P (обычный текст) и C (зашифрованный текст), в котором соответствующие строки представляют известные пары обычного/зашифрованного текста.

Если не известно значение m, можно попробовать различные значения при условии, что m не является очень большим.

4 Заключение

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