шифр Хилла

Шифр замены на основе линейной алгебры

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

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

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

Шифрование

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

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

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

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

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

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

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

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

${\displaystyle {\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», или:

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

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

${\displaystyle {\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 обратная матрица, использованная в предыдущем примере, равна:

${\displaystyle {\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» из предыдущего примера, мы получаем:

${\displaystyle {\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 или имеет общие множители с модульной базой, то матрицу нельзя использовать в методе Хилла. шифр, и необходимо выбрать другую матрицу (иначе расшифровать будет невозможно). К счастью, матрицы, удовлетворяющие условиям шифра Хилла, довольно распространены.

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

${\displaystyle {\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 не имеет общих делителей с 26, и эту матрицу можно использовать для шифра Хилла. ${\displaystyle 25=5^{2}}$ ${\displaystyle 26=2\times 13}$

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

Пример

Позволять

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

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

${\displaystyle 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}}}$

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

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

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

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

${\displaystyle {\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 можно вычислить по формуле ${\displaystyle K^{-1}}$ ${\displaystyle KK^{-1}=K^{-1}K=I_{2}}$ ${\displaystyle {\begin{pmatrix}a&b\\c&d\end{pmatrix}}^{-1}=(ad-bc)^{-1}{\begin{pmatrix}d&-b\\-c&a\end{pmatrix}}}$

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

${\displaystyle 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}}}$

${\displaystyle 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}}}$

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

${\displaystyle {\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}},}$и

${\displaystyle {\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}}}$

Поэтому,

${\displaystyle {\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}$.

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

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

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

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

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

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

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

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

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

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

${\displaystyle 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}).}$

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

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

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

Шифр Хилла размерности 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» реализует шифр Хилла и показывает задействованные матрицы.
• «Объяснение шифра Хилла» иллюстрирует линейную алгебру, лежащую в основе шифра Хилла.
• «Калькулятор шифров Хилла» описывает шифр Хилла на веб-странице.