Материал: 08_ЛР

МИНИСТЕРСТВО ЦИФРОВОГО РАЗВИТИЯ

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ

УЧРЕЖДЕНИЕ ВЫСШЕГО ОБРАЗОВАНИЯ

«САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ТЕЛЕКОММУНИКАЦИЙ ИМ. ПРОФ. М.А. БОНЧ-БРУЕВИЧА»

(СПбГУТ)

_____________________________________________________________________________

Кафедра информационной безопасности телекоммуникационных систем

Дисциплина «Основы криптографии с открытыми ключами»

Лабораторная работа 8

«Изучение криптосистемы МАК-ЭЛИС»

Выполнила: студ. гр. .

. .

Проверил: проф. Яковлев В.А..

Санкт-Петербург

2021

Цель лабораторной работы

Изучить преобразования, выполняемые при шифровании и дешифровании сообщений в системе Мак-Элис, а также простейшие попытки ее взлома.

Ход работы

Генерирование порождающей матрицы

1. Выбираем следующие параметры криптосистемы Мак-Элис:

Длина кодового слова: бита

Длина информационного сообщения: бит

Число исправляемых ошибок:

Неприводимый полином:

Минимальное кодовое расстояние:

2. Генерируем порождающую матрицу в программе MAGMA.exe:

Рисунок 1. Генерация порождающей матрицы.

Рисунок 2. Сгенерированная матрица.

Генерация ключей

;

.

3. Запускаем программу McEliece.exe. Загружаем сгенерированную ранее порождающую матрицу G:

Рисунок 3. Загрузка порождающей матрицы G.

4. Генерируем не сингулярную (невырожденную) матрицу S:

Рисунок 4. Генерация матрицы S.

5. Генерируем перестановочную матрицу P:

Рисунок 5. Генерация матрицы P.

6. Получаем произведение матриц G*P:

Рисунок 6. Произведение G*P.

Рисунок 7. Проверка произведения матриц G и P.

7. Вычисляем матрицу путем произведения матриц S и (G*P):

Рисунок 8. Вычисление матрицы .

Рисунок 9. Проверка произведения матриц S и (G*P).

Шифрование

8. Выбираем сообщение в виде двоичной последовательности длиной k = 17 бит:

Сообщение: 00111001010100101

9. Переходим во вкладку «Шифрование». Вводим сообщение, генерируем случайный двоичный вектор Z длины n, и веса (т.е. числа единиц в нём) не более , вычисляем произведение сообщения и матрицы (S*G*P): . Вычисляем криптограмму .

Рисунок 10. Шифрование сообщения.

Полученная криптограмма: 10111100001110010101100110101001

Дешифрование

10. Переходим во вкладку «Дешифрование». Вычисляем вектор , а также получаем матрицу, обратную P:

Рисунок 11. Вычисление вектора .

11. Путем вычитания двоичного вектора ошибок Z исправим не более ошибок в , что даст некоторый двоичный вектор длины k:

Рисунок 12. Исправление ошибок в .

12. Восстанавливаем сообщение как , а также получаем матрицу, обратную S:

Рисунок 13. Восстановление сообщения.

Восстановленное сообщение: 00111001010100101

Исходное сообщение: 00111001010100101

Видим, что расшифрованное сообщение такое же, как двоичная последовательность, зашифрованное ранее.

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

13. Переходим во вкладку «Криптоанализ» и нажимаем кнопку «Атака»:

Рисунок 14. Атака на криптосистему.

Для рассматриваемого примера атака прошла успешно. Видно, что полученное сообщение совпадает с сообщением, которое зашифровывали ранее.

14. Рассчитаем вероятности успеха атаки на КС Мас-Элис при длине кодового слова n = 32 и различном количестве информационных символов k:

Вероятность атаки:

1. При k = 22:

При t = 1:

При t = 2:

2. При k = 17:

При t = 1:

При t = 2:

При t = 3:

3. При k = 12:

При t = 1:

При t = 2:

При t = 3:

При t = 4:

4. При k = 7:

При t = 1:

При t = 2:

При t = 3:

При t = 4:

При t = 5:

Таблица 1. Вероятности успеха криптоатаки при различном количестве искусственно вводимых ошибок.

k	t
	1	2	3	4	5
22	0,313	0,091	–	–	–
17	0,469	0,212	0,092	–	–
12	0,625	0,383	0,230	0,135	–
7	0,781	0,605	0,464	0,352	0,264

График 1. Зависимость вероятности успеха криптоатаки от количества информационных символов.

Из диаграммы видно, что при увеличении длины информационного сообщения k вероятность успешного проведения криптоатаки снижается.

Вывод

В ходе выполнения данной лабораторной работы были изучены преобразования, выполняемые при шифровании и дешифровании сообщений в системе Мак-Элис, а также разобран простейший способ атаки на неё.