шифр Хилла

Шифровальная машина Хилла, из рисунка 4 патента.

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

Следующее обсуждение предполагает элементарное знание матриц .

Шифрование

Каждая буква представлена ​​числом по модулю 26. Хотя это не является существенной особенностью шифра, часто используется эта простая схема:

Письмо	А	Б	С	Д	И	Ф	Г	ЧАС	я	Дж	К	л	М	Н	ТО	П	вопрос	Р	С	Т	В	V	В	Х	И	С
Число	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25

Чтобы зашифровать сообщение, каждый блок из n букв (рассматриваемый как n -компонентный вектор ) умножается на обратимую размера n × n матрицу по модулю 26. Чтобы расшифровать сообщение, каждый блок умножается на обратную матрицу, используемую для шифрования сообщения. шифрование.

Матрица, используемая для шифрования, является ключом шифрования , и ее следует выбирать случайным образом из набора обратимых матриц размера n × n ( по модулю 26). Шифр, конечно, можно адаптировать к алфавиту с любым количеством букв; всю арифметику нужно выполнять по модулю количества букв, а не по модулю 26.

Рассмотрим сообщение «ACT» и ключ ниже (или GYB / NQK / буквами URP):

${\begin{pmatrix}6&24&1\\13&16&10\\20&17&15\end{pmatrix}}$

Поскольку «A» равно 0, «C» равно 2 и «T» равно 19, сообщение является вектором:

${\begin{pmatrix}0\\2\\19\end{pmatrix}}$

Таким образом, зашифрованный вектор имеет вид:

${\begin{pmatrix}6&24&1\\13&16&10\\20&17&15\end{pmatrix}}{\begin{pmatrix}0\\2\\19\end{pmatrix}}={\begin{pmatrix}67\\222\\319\end{pmatrix}}\equiv {\begin{pmatrix}15\\14\\7\end{pmatrix}}{\pmod {26}}$

что соответствует зашифрованному тексту «POH». Теперь предположим, что вместо этого наше сообщение — «CAT», или:

${\begin{pmatrix}2\\0\\19\end{pmatrix}}$

На этот раз зашифрованный вектор имеет вид:

${\begin{pmatrix}6&24&1\\13&16&10\\20&17&15\end{pmatrix}}{\begin{pmatrix}2\\0\\19\end{pmatrix}}={\begin{pmatrix}31\\216\\325\end{pmatrix}}\equiv {\begin{pmatrix}5\\8\\13\end{pmatrix}}{\pmod {26}}$

что соответствует зашифрованному тексту «FIN». Каждая буква изменилась. Шифр Хилла достиг , диффузии Шеннона n и - мерный шифр Хилла может полностью распространяться по n символам одновременно.

Расшифровка

Чтобы расшифровать, мы превращаем зашифрованный текст обратно в вектор, затем просто умножаем на обратную матрицу ключевой матрицы (IFK / VIV / VMI в буквах). Мы находим, что по модулю 26 обратная матрица, использованная в предыдущем примере, равна:

${\begin{pmatrix}6&24&1\\13&16&10\\20&17&15\end{pmatrix}}^{-1}{\pmod {26}}\equiv {\begin{pmatrix}8&5&10\\21&8&21\\21&12&8\end{pmatrix}}$

Взяв зашифрованный текст «POH» из предыдущего примера, мы получаем:

${\begin{pmatrix}8&5&10\\21&8&21\\21&12&8\end{pmatrix}}{\begin{pmatrix}15\\14\\7\end{pmatrix}}={\begin{pmatrix}260\\574\\539\end{pmatrix}}\equiv {\begin{pmatrix}0\\2\\19\end{pmatrix}}{\pmod {26}}$

что возвращает нас к «ACT», как и ожидалось.

При выборе матрицы шифрования существует одна сложность:

1. Не все матрицы имеют обратную . Матрица будет иметь обратную тогда и только тогда, когда ее определитель обратим по модулю n, где n — модульное основание.

Таким образом, если мы работаем по модулю 26, как указано выше, определитель должен быть отличен от нуля и не должен делиться на 2 или 13. Если определитель равен 0 или имеет общие множители с модульной базой, то матрицу нельзя использовать в методе Хилла. шифр, и необходимо выбрать другую матрицу (иначе расшифровать будет невозможно). К счастью, матрицы, удовлетворяющие условиям шифра Хилла, довольно распространены.

Для нашего примера ключевой матрицы:

${\begin{vmatrix}6&24&1\\13&16&10\\20&17&15\end{vmatrix}}=6(16\cdot 15-10\cdot 17)-24(13\cdot 15-10\cdot 20)+1(13\cdot 17-16\cdot 20)=441\equiv 25{\pmod {26}}$

Итак, по модулю 26 определитель равен 25. Поскольку $25=5^{2}$ и $26=2\times 13$, 25 не имеет общих делителей с 26, и эту матрицу можно использовать для шифра Хилла.

Риск того, что определитель будет иметь общие множители с модулем, можно устранить, сделав модуль простым . Следовательно, полезный вариант шифра Хилла добавляет 3 дополнительных символа (например, пробел, точку и вопросительный знак), чтобы увеличить модуль до 29.

Пример

Позволять

$K={\begin{pmatrix}3&3\\2&5\end{pmatrix}}$

быть ключом и предположим, что открытое текстовое сообщение — «ПОМОЩЬ». Тогда этот открытый текст представляется двумя парами

$HELP\to {\begin{pmatrix}H\\E\end{pmatrix}},{\begin{pmatrix}L\\P\end{pmatrix}}\to {\begin{pmatrix}7\\4\end{pmatrix}},{\begin{pmatrix}11\\15\end{pmatrix}}$

Затем мы вычисляем

${\begin{pmatrix}3&3\\2&5\end{pmatrix}}{\begin{pmatrix}7\\4\end{pmatrix}}\equiv {\begin{pmatrix}7\\8\end{pmatrix}}{\pmod {26}},$ и

${\begin{pmatrix}3&3\\2&5\end{pmatrix}}{\begin{pmatrix}11\\15\end{pmatrix}}\equiv {\begin{pmatrix}0\\19\end{pmatrix}}{\pmod {26}}$

и продолжите шифрование следующим образом:

${\begin{pmatrix}7\\8\end{pmatrix}},{\begin{pmatrix}0\\19\end{pmatrix}}\to {\begin{pmatrix}H\\I\end{pmatrix}},{\begin{pmatrix}A\\T\end{pmatrix}}$

Матрица K обратима, следовательно $K^{-1}$ существует такое, что $KK^{-1}=K^{-1}K=I_{2}$.Обратное значение K можно вычислить по формуле ${\begin{pmatrix}a&b\\c&d\end{pmatrix}}^{-1}=(ad-bc)^{-1}{\begin{pmatrix}d&-b\\-c&a\end{pmatrix}}$

Эта формула по-прежнему сохраняется после модульного сокращения, если модульное мультипликативное обратное . для вычисления используется $(ad-bc)^{-1}$. Следовательно, в данном случае мы вычисляем

$K^{-1}\equiv 9^{-1}{\begin{pmatrix}5&23\\24&3\end{pmatrix}}\equiv 3{\begin{pmatrix}5&23\\24&3\end{pmatrix}}\equiv {\begin{pmatrix}15&17\\20&9\end{pmatrix}}{\pmod {26}}$

$HIAT\to {\begin{pmatrix}H\\I\end{pmatrix}},{\begin{pmatrix}A\\T\end{pmatrix}}\to {\begin{pmatrix}7\\8\end{pmatrix}},{\begin{pmatrix}0\\19\end{pmatrix}}$

Затем мы вычисляем

${\begin{pmatrix}15&17\\20&9\end{pmatrix}}{\begin{pmatrix}7\\8\end{pmatrix}}={\begin{pmatrix}241\\212\end{pmatrix}}\equiv {\begin{pmatrix}7\\4\end{pmatrix}}{\pmod {26}},$ и

${\begin{pmatrix}15&17\\20&9\end{pmatrix}}{\begin{pmatrix}0\\19\end{pmatrix}}={\begin{pmatrix}323\\171\end{pmatrix}}\equiv {\begin{pmatrix}11\\15\end{pmatrix}}{\pmod {26}}$

Поэтому,

${\begin{pmatrix}7\\4\end{pmatrix}},{\begin{pmatrix}11\\15\end{pmatrix}}\to {\begin{pmatrix}H\\E\end{pmatrix}},{\begin{pmatrix}L\\P\end{pmatrix}}\to HELP$.

Безопасность

Базовый шифр Хилла уязвим для атаки с использованием известного открытого текста, поскольку он полностью линеен . Противник, который перехватывает $n^{2}$ Пары символов открытого текста/зашифрованного текста могут создать линейную систему, которую (обычно) легко решить; если же окажется, что эта система неопределенна, то необходимо лишь добавить еще несколько пар открытый текст/зашифрованный текст. Вычисление этого решения с помощью стандартных алгоритмов линейной алгебры занимает очень мало времени.

Хотя умножение матриц само по себе не приводит к созданию надежного шифра, оно все же является полезным шагом в сочетании с другими нелинейными операциями, поскольку умножение матриц может обеспечить диффузию . Например, правильно выбранная матрица может гарантировать, что небольшие различия до умножения матрицы приведут к большим различиям после умножения матрицы. Действительно, некоторые современные шифры используют этап матричного умножения для обеспечения диффузии. Например, шаг MixColumns в AES — это умножение матриц. Функция g в Twofish представляет собой комбинацию нелинейных S-блоков с тщательно выбранным матричным умножением (MDS).

Размер ключевого пространства

Ключевое пространство — это набор всех возможных ключей. Размер ключевого пространства — это количество возможных ключей. Эффективный размер ключа , выраженный в битах, представляет собой двоичный логарифм размера ключевого пространства.

Есть $26^{n^{2}}$ матрицы размерности n × n . Таким образом $\log _{2}(26^{n^{2}})$ или о $4.7n^{2}$ — это верхняя граница размера ключа шифра Хилла с использованием матриц размера n × n . Это только верхняя граница, поскольку не каждая матрица обратима и, следовательно, может использоваться в качестве ключа. Количество обратимых матриц можно вычислить с помощью китайской теоремы об остатках . То есть матрица обратима по модулю 26 тогда и только тогда, когда она обратима как по модулю 2, так и по модулю 13.Число обратимых матриц размера n × n по модулю 2 равно порядку общей линейной группы GL(n, Z ₂ ). Это

$2^{n^{2}}(1-1/2)(1-1/2^{2})\cdots (1-1/2^{n}).$

Аналогично, количество обратимых матриц по модулю 13 (т.е. порядок GL(n, Z ₁₃ )) равно

$13^{n^{2}}(1-1/13)(1-1/13^{2})\cdots (1-1/13^{n}).$

Количество обратимых матриц по модулю 26 является произведением этих двух чисел. Следовательно, это

$26^{n^{2}}(1-1/2)(1-1/2^{2})\cdots (1-1/2^{n})(1-1/13)(1-1/13^{2})\cdots (1-1/13^{n}).$

Кроме того, представляется разумным избегать слишком большого количества нулей в ключевой матрице, поскольку они уменьшают диффузию. Конечным результатом является то, что эффективное пространство ключей базового шифра Хилла составляет около $4.64n^{2}-1.7$. Для шифра Хилла 5×5 это около 114 бит. Конечно, поиск ключей — не самая эффективная из известных атак.

Механическая реализация

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

Шифр Хилла размерности 6 был реализован механически. Хилл и партнер получили патент ( патент США 1845947 ) на это устройство, которое выполняло умножение матрицы 6×6 по модулю 26 с использованием системы шестерен и цепей.

К сожалению, механизмы передачи (и, следовательно, ключ) были фиксированными для каждой конкретной машины, поэтому в целях безопасности рекомендовалось тройное шифрование: секретный нелинейный шаг, за которым следовал широкий диффузионный шаг от машины, за которым следовал третий секретный нелинейный шаг. (Намного более поздний шифр Эвена-Мансура также использует неключевой диффузный средний шаг). Такая комбинация на самом деле была очень мощной в 1929 году и указывает на то, что Хилл, очевидно, понимал концепции атаки «встреча посередине», а также путаницы и рассеяния. К сожалению, его машина не была продана.

См. также

Другие практические полиграфические шифры «карандашом и бумагой» включают:

• Шифр Плейфера
• Бифидный шифр
• Трехраздельный шифр

Ссылки

• Лестер С. Хилл, Криптография в алгебраическом алфавите, The American Mathematical Monthly Vol.36, июнь – июль 1929 г., стр. 306–312. ( PDF )
• Лестер С. Хилл, О некоторых устройствах линейного преобразования криптографии, The American Mathematical Monthly Vol.38, 1931, стр. 135–154.
• Джеффри Оверби, Уильям Трэвес и Ежи Войдило, В пространстве ключей шифра Хилла, Cryptologia , Том 29, № 1, январь 2005 г., стр. 59–72. ( CiteSeerX ) ( PDF )

Внешние ссылки

• « Веб-приложение Hill Cipher » реализует шифр Хилла и показывает задействованные матрицы.
• « Объяснение шифра Хилла » иллюстрирует линейную алгебру, лежащую в основе шифра Хилла.
• « Калькулятор шифров Хилла » описывает шифр Хилла на веб-странице.