Шифр холма

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

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

Расшифровка [ править ]

Чтобы расшифровать, мы превращаем зашифрованный текст обратно в вектор, а затем просто умножаем на обратную матрицу ключевой матрицы (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. Не все матрицы имеют обратную (см. Обратимую матрицу ). Матрица будет иметь обратную тогда и только тогда, когда ее определитель не равен нулю.
2. Определитель матрицы шифрования не должен иметь общих множителей с модульной базой.

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

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

${\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. Поскольку у него нет общих множителей с 26, эту матрицу можно использовать для шифра Хилла.

Риск того, что определитель имеет общие множители с модулем, можно исключить, сделав модуль простым . Следовательно, полезный вариант шифра Хилла добавляет 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}$

Хотя умножение матриц само по себе не приводит к созданию безопасного шифра, оно по-прежнему является полезным шагом в сочетании с другими нелинейными операциями, поскольку умножение матриц может обеспечить распространение . Например, правильно выбранная матрица может гарантировать, что небольшие различия до умножения матриц приведут к большим различиям после умножения матриц. Действительно, некоторые современные шифры используют шаг матричного умножения для обеспечения распространения. Например, шаг 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}$

Механическая реализация [ править ]

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

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

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

См. Также [ править ]

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

• Шифр playfair
• Бифидный шифр
• Трехзначный шифр

Ссылки [ править ]

• Лестер С. Хилл, Криптография в алгебраическом алфавите, 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 Web App " реализует шифр Хилла и показывает задействованные матрицы
• " Hill Cipher Explained " иллюстрирует линейную алгебру, лежащую в основе Hill Cipher.
• « Калькулятор шифров Хилла » описывает шифр Хилла на веб-странице