Введение
Шифр подстановки на основе линейной алгебры
В классической криптографии шифр Хилла — это полиграфический шифр подстановки, основанный на линейной алгебре. Изобретённый Лестером С. Хиллом в 1929 году, он стал первым полиграфическим шифром, в котором стало практически осуществимым (хотя и с трудом) оперировать более чем с тремя символами одновременно. Дальнейшее обсуждение предполагает базовые знания матриц.
Безопасность
Основной шифр Хилла уязвим к атаке с известным открытым текстом, поскольку он полностью линеен. Злоумышленник, перехвативший пары символов открытого и зашифрованного текста, может составить систему линейных уравнений, которую (обычно) можно легко решить; если эта система оказывается неопределённой, достаточно добавить несколько дополнительных пар открытого и зашифрованного текста. Вычисление решения с помощью стандартных алгоритмов линейной алгебры занимает очень мало времени. Хотя само по себе матричное умножение не обеспечивает надёжное шифрование, оно остаётся полезным шагом в сочетании с другими нелинейными операциями, поскольку матричное умножение обеспечивает диффузию. Например, правильно подобранная матрица может гарантировать, что небольшие различия во входных данных до умножения матрицы приведут к значительным различиям в выходных данных после умножения. Фактически, некоторые современные шифры используют шаг матричного умножения для обеспечения диффузии. Например, шаг MixColumns в AES является матричным умножением. Функция g в Twofish представляет собой комбинацию нелинейных S-блоков с тщательно подобранным матричным умножением (MDS).
Размер ключевого пространства
Ключевое пространство – это множество всех возможных ключей. Размер ключевого пространства – это количество возможных ключей. Эффективный размер ключа, выраженный в битах, является двоичным логарифмом размера ключевого пространства. Существует матриц размера n × n. Таким образом, или приблизительно является верхней границей размера ключа шифра Хилла, использующего матрицы n × n. Это лишь верхняя граница, поскольку не каждая матрица обратима и, следовательно, может быть использована в качестве ключа. Количество обратимых матриц можно вычислить с помощью китайской теоремы об остатках. То есть, матрица обратима по модулю 26 тогда и только тогда, когда она обратима как по модулю 2, так и по модулю 13. Количество обратимых n × n матриц по модулю 2 равно порядку общей линейной группы GL(n,Z₂). Это равно
Аналогично, количество обратимых матриц по модулю 13 (то есть порядок GL(n,Z₁₃)) равно
Количество обратимых матриц по модулю 26 является произведением этих двух чисел. Следовательно, оно равно
Кроме того, представляется разумным избегать слишком большого количества нулей в матрице ключа, поскольку они снижают диффузию. Итоговый эффект заключается в том, что эффективное ключевое пространство базового шифра Хилла составляет около . Для шифра Хилла 5 × 5 это приблизительно 114 бит. Конечно, поиск ключей – не самая эффективная известная атака.
Механическое выполнение
При работе с двумя символами одновременно шифр Хилла не дает каких-либо особых преимуществ по сравнению с шифром Плейфера или бифидным шифром, а на самом деле он слабее обоих и немного более трудоемок при ручном использовании. С увеличением размерности шифр быстро становится непрактичным для ручной работы. Шифр Хилла размерности 6 был реализован механически. Хилл и его партнер получили патент на это устройство, которое выполняло умножение матриц 6 × 6 по модулю 26 с использованием системы шестерен и цепей. К сожалению, конструкция шестерен (и, следовательно, ключ) была фиксированной для каждой машины, поэтому для обеспечения безопасности рекомендовалось тройное шифрование: секретный нелинейный этап, за которым следовал широкий диффузионный этап, выполняемый машиной, и третий секретный нелинейный этап. (Более поздний шифр Even–Mansour также использует неключевой диффузионный промежуточный этап). Такая комбинация была весьма эффективной для 1929 года и свидетельствует о том, что Хилл, по-видимому, понимал концепции атаки "встреча посередине", а также перемешивания и диффузии. К сожалению, его машина не была коммерчески успешной.