ПРИМЕНЕНИЕ МАТРИЧНОГО ИСЧИСЛЕНИЯ В КРИПТОГРАФИИ: ИСПОЛЬЗОВАНИЕ МАТРИЦ ДЛЯ ШИФРОВАНИЯ И ДЕШИФРОВАНИЯ ДАННЫХ

​АННОТИЦИЯ

Показано, как линейная алгебра применяется к защите данных на примере шифра Хилла. Алгоритм - блочное кодирование: текст преобразуется умножением на матрицу. Указаны математические условия для обратного декодирования. Дана пошаговая схема перевода знаков в числа, прямое шифрование и выбор ключевой матрицы. Работоспособность продемонстрирована на примере шифрования и расшифровки. Отмечены уязвимости метода и границы его использования в современных криптосистемах.

Ключевые слова: матричное исчисление; криптография; шифр Хилла; модульная арифметика; обратимая матрица; блочное шифрование; линейная алгебра; определитель матрицы.

Развитие криптографии связано с матричными вычислениями. Криптография занимается поиском и исследованием методов преобразования информации с целью скрытия ее содержания. Сфера интересов криптоанализа - исследование возможности расшифровывания информации без знания ключей. [3, с. 4] Ключ - информация, необходимая для беспрепятственного шифрования и расшифрования текстов. [3, с. 4] Переход от простейших алгоритмов замены к блочному шифрованию возможен благодаря свойствам матриц. Блочные шифры - это шифры, в которых за одну операцию обрабатывается (шифруется или дешифруется) группа (блок) элементов данных. [4, с. 49]

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

Шифр Хилла опирается на квадратные матрицы - у них число строк и столбцов совпадает. Это даёт возможность использовать определители и обратные матрицы. Ключевая характеристика матрицы - её определитель det A. По нему судят об обратимости: если определитель не ноль (det A ≠ 0), матрица обратима. Если определитель равен нулю (det A = 0), обратной матрицы не существует. Тогда расшифровать сообщение однозначно не получится. Вся возможность обратного преобразования висит на существовании обратной матрицы (А^-1).

А · А^-1 = А^-1 · А = I

Шифрование на матрицах строится на двух вещах. Первое - умножение матриц. Зашифрованный блок C = A · B, каждый элемент считают так:

Второе - обратная матрица, но не как в обычной алгебре, а по модулю N. В шифре Хилла просто взять обратную матрицу нельзя - расшифровка не сойдётся. Нужно искать её по модулю. Роль модуля N играет размер алфавита: 26 для латиницы, 33 для кириллицы. Так результат остаётся в пределах алфавита.

Если при шифровании преобразуются более двух букв открытого текста, то шифр называется полиграммным. Первый полиграммный шифр предложил Лестер Хилл в 1929 году. [2, с. 41] В модели Хилла исходное сообщение разбивается на блоки по n букв. Каждый блок - это вектор-столбец p_i. Буквы предварительно переводят в числа - от 0 до m-1, по порядку в алфавите. Дальше шифрование сводится к умножению матриц

В шифре Хилла нужна квадратная матрица K размером n. Чтобы расшифровка работала, она должна быть обратимой по модулю m. Модулярная арифметика не даёт числам выйти за пределы алфавита. Это же и повышает криптостойкость шифра.

В шифре Хилла расшифровка сводится к решению уравнения в кольце вычетов. Берём обратную матрицу K^-1, чтобы выполнялось K · K^-1 = I (mod m). Условие обратимости: gcd(det(K), m) = 1. Разберём на примере слова «MATH» (m = 26). Разбиваем текст на векторы: p₁ = (12, 0)^T и p₂ = (19, 7)^T . Возьмём ключ K = . Считаем определитель: det(K) = -121 9 (mod 26) - условие выполняется. Умножаем ключ на блоки сообщения: получаем (8, 22)^T и (21, 8)^T, то есть строку «IWVI». Чтобы расшифровать, находим мультипликативную инверсию определителя. Для 9 по модулю 26 это 3, потому что 9 · 3 1. Дальше вычисляем обратную матрицу: K^-1 = 3 ·

Умножение K^-1 на вектор зашифрованного блока c₁ = (8, 22)^T дает результат (12, 0)^T («MA»). Это подтверждает точность выбранного математического аппарата и его устойчивость при соблюдении условий обратимости.

Таблица 1.

Свойства шифра Хилла и способы усиления

Стойкость криптоалгоритмов должна быть достаточной для того, чтобы обеспечить безопасность данных в течение некоторого срока, определяемого условиями эксплуатации информационной системы, использующей эти алгоритмы. [1, с. 46]

Шифр Хилла показывает, как линейная алгебра работает в задачах защиты данных. Алгоритм простой и математически чёткий, относится к классическим блочным шифрам. Но из-за линейности матричных преобразований он не даёт серьёзной стойкости на практике.

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

Если добавить динамическую ротацию ключей или нелинейные шаги, взломать шифр становится намного сложнее. Правда, растёт и вычислительная нагрузка.

Список литературы:

1. Гатченко Н. А., Исаев А. С., Яковлев А. Д. Криптографическая защита информации: учебное пособие / Н. А. Гатченко, А. С. Исаев, А. Д. Яковлев. - СПб.: НИУ ИТМО, 2012. - 142 с.
2. Габидулин Э. М. Защита информации: учебное пособие / Э. М. Габидулин, А. С. Кшевецкий, А. И. Колыбельников. - Москва: МФТИ, 2011. - 225 с. - ISBN 978-5-7417-0377-9
3. Баричев С. Г. Основы современной криптографии: учебное пособие / С. Г. Баричев, В. В. Гончаров, Р. Е. Серов. - 3‑е изд., перераб. и доп. - Москва: Горячая линия - Телеком, 2011. - 175 с. - ISBN 978-5-9912-0182-7
4. Карпов А. В., Ишмуратов Р. А. Введение в криптографию: учебное пособие / А. В. Карпов, Р. А. Ишмуратов. - Казань: Казан. ун-т, 2024. -128 с.