Шифр Хилла




Главная
Новости
Статьи
Ремонт
Каркасный дом
Несущие конструкции
Металлические конструкции
Прочность дорог
Дорожные материалы
Стальные конструкции
Грунтовые основания
Опорные сооружения




26.02.2021


26.02.2021


25.02.2021


25.02.2021


24.02.2021


22.02.2021


22.02.2021


22.02.2021


20.02.2021


20.02.2021





Яндекс.Метрика
         » » Шифр Хилла

Шифр Хилла

19.01.2021

Шифр Хилла — полиграммный шифр подстановки, основанный на линейной алгебре и модульной арифметике. Изобретён американским математиком Лестером Хиллом в 1929 году. Это был первый шифр, который позволил на практике (хотя и с трудом) одновременно оперировать более чем с тремя символами. Шифр Хилла не нашёл практического применения в криптографии из-за слабой устойчивости ко взлому и отсутствия описания алгоритмов генерации прямых и обратных матриц большого размера.

История

Впервые шифр Хилла был описан в статье «Cryptography in an Algebraic Alphabet», опубликованной в журнале «The American Mathematical Monthly» в июне-июле 1929 года. В августе того же года Хилл расширил тему и выступил с речью о криптографии перед Американским математическим обществом в Боулдере, штат Колорадо. Позднее его лекция привела ко второй статье «Concerning Certain Linear Transformation Apparatus of Cryptography», которая была опубликована в журнале «The American Mathematical Monthly» в марте 1931 года. Дэвид Кан в своем труде «Взломщики кодов» так описал шифр Хилла и его место в истории криптографии:

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

Оригинальный текст (англ.) But Hill alone devised a method of power and generality. In addition, his procedure made polygraphic cryptography practical for the first time.

Описание шифра Хилла

Шифр Хилла является полиграммным шифром, который может использовать большие блоки с помощью линейной алгебры. Каждой букве алфавита сопоставляется число по модулю 26. Для латинского алфавита часто используется простейшая схема: A = 0, B = 1, …, Z = 25, но это не является существенным свойством шифра. Блок из n букв рассматривается как n-мерный вектор и умножается по модулю 26 на матрицу размера n × n. Если в качестве основания модуля используется число больше чем 26, то можно использовать другую числовую схему для сопоставления буквам чисел и добавить пробелы и знаки пунктуации. Элементы матрицы являются ключом. Матрица должна быть обратима в Z 26 n {displaystyle mathbb {Z} _{26}^{n}} , чтобы была возможна операция расшифрования.

Для n = 3 система может быть описана так:

{ c 1 = k 11 p 1 + k 12 p 2 + k 13 p 3 ( mod 26 ) , c 2 = k 21 p 1 + k 22 p 2 + k 23 p 3 ( mod 26 ) , c 3 = k 31 p 1 + k 32 p 2 + k 33 p 3 ( mod 26 ) , {displaystyle {egin{cases}c_{1}=k_{11}p_{1}+k_{12}p_{2}+k_{13}p_{3}{pmod {26}},c_{2}=k_{21}p_{1}+k_{22}p_{2}+k_{23}p_{3}{pmod {26}},c_{3}=k_{31}p_{1}+k_{32}p_{2}+k_{33}p_{3}{pmod {26}},end{cases}}}

или в матричной форме:

[ c 1 c 2 c 3 ] = [ k 11 k 12 k 13 k 21 k 22 k 23 k 31 k 32 k 33 ] [ p 1 p 2 p 3 ] ( mod 26 ) , {displaystyle {egin{bmatrix}c_{1}c_{2}c_{3}end{bmatrix}}={egin{bmatrix}k_{11}&k_{12}&k_{13}k_{21}&k_{22}&k_{23}k_{31}&k_{32}&k_{33}end{bmatrix}}{egin{bmatrix}p_{1}p_{2}p_{3}end{bmatrix}}{pmod {26}},}

или

C = K P ( mod 26 ) , {displaystyle C=KP{pmod {26}},}

где P {displaystyle P} и C {displaystyle C} — векторы-столбцы высоты 3, представляющие открытый и зашифрованный текст соответственно, K {displaystyle K} — матрица 3 × 3, представляющая ключ шифрования. Операции выполняются по модулю 26.

Для того, чтобы расшифровать сообщение, требуется получить обратную матрицу ключа K − 1 {displaystyle K^{-1}} . Существуют стандартные методы вычисления обратных матриц (см. способы нахождения обратной матрицы), но не все матрицы имеют обратную (см. обратная матрица). Матрица будет иметь обратную в том и только в том случае, когда её детерминант не равен нулю и не имеет общих делителей с основанием модуля. Если детерминант матрицы равен нулю или имеет общие делители с основанием модуля, то такая матрица не может использоваться в шифре Хилла, и должна быть выбрана другая матрица (в противном случае шифротекст будет невозможно расшифровать). Тем не менее, матрицы, которые удовлетворяют вышеприведенным условиям, существуют в изобилии.

В общем случае, алгоритм шифрования может быть выражен в следующем виде:

Шифрование: C = E ( K , P ) = K P ( mod 26 ) {displaystyle C=E(K,P)=KP{pmod {26}}} .

Расшифрование: P = D ( K , C ) = K − 1 C ( mod 26 ) = K − 1 K P ( mod 26 ) = P {displaystyle P=D(K,C)=K^{-1}C{pmod {26}}=K^{-1}KP{pmod {26}}=P} .

Пример

В следующем примере используются латинские буквы от A до Z, соответствующие им численные значения приведены в таблице.

Шифрование

Рассмотрим сообщение «ACT» и представленный ниже ключ (GYBNQKURP в буквенном виде):

K = [ 6 24 1 13 16 10 20 17 15 ] . {displaystyle K={egin{bmatrix}6&24&113&16&1020&17&15end{bmatrix}}.}

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

Так как букве «A» соответствует число 0, «C» — 2, «T» — 19, то сообщение — это вектор

P 1 = [ 0 2 19 ] . {displaystyle P_{1}={egin{bmatrix}0219end{bmatrix}}.}

Тогда зашифрованный вектор будет

C 1 = K P 1 ( mod 26 ) = [ 6 24 1 13 16 10 20 17 15 ] [ 0 2 19 ] ( mod 26 ) = [ 15 14 7 ] . {displaystyle C_{1}=KP_{1}{pmod {26}}={egin{bmatrix}6&24&113&16&1020&17&15end{bmatrix}}{egin{bmatrix}0219end{bmatrix}}{pmod {26}}={egin{bmatrix}15147end{bmatrix}}.}

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

P 2 = [ 2 0 19 ] . {displaystyle P_{2}={egin{bmatrix}219end{bmatrix}}.}

Теперь зашифрованный вектор будет

C 2 = K P 2 ( mod 26 ) = [ 6 24 1 13 16 10 20 17 15 ] [ 2 0 19 ] ( mod 26 ) = [ 5 8 13 ] . {displaystyle C_{2}=KP_{2}{pmod {26}}={egin{bmatrix}6&24&113&16&1020&17&15end{bmatrix}}{egin{bmatrix}219end{bmatrix}}{pmod {26}}={egin{bmatrix}5813end{bmatrix}}.}

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

Расшифрование

Обратная матрица ключа:

K − 1 ( mod 26 ) = [ 8 5 10 21 8 21 21 12 8 ] . {displaystyle K^{-1}{pmod {26}}={egin{bmatrix}8&5&1021&8&2121&12&8end{bmatrix}}.}

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

P 1 = K − 1 C 1 ( mod 26 ) = [ 8 5 10 21 8 21 21 12 8 ] [ 15 14 7 ] ( mod 26 ) = [ 0 2 19 ] . {displaystyle P_{1}=K^{-1}C_{1}{pmod {26}}={egin{bmatrix}8&5&1021&8&2121&12&8end{bmatrix}}{egin{bmatrix}15147end{bmatrix}}{pmod {26}}={egin{bmatrix}0219end{bmatrix}}.}

Этот вектор соответствует сообщению «ACT».

Криптостойкость

Стандартный шифр Хилла уязвим для атаки по выбранному открытому тексту, потому что в нём используются линейные операции. Криптоаналитик, который перехватит n 2 {displaystyle n^{2}} пар символ сообщения/символ шифротекста сможет составить систему линейных уравнений, которую обычно несложно решить. Если окажется, что система не решаема, то необходимо всего лишь добавить ещё несколько пар символ сообщения/символ шифротекста. Такого рода расчёты средствами обычных алгоритмов линейной алгебры требует совсем немного времени. В связи с этим для увеличения криптостойкости в него должны быть добавлены какие-либо нелинейные операции. Комбинирование линейных операций, как в шифре Хилла, и нелинейных шагов привело к созданию подстановочно-перестановочной сети (например, сеть Фейстеля). Поэтому с определённой точки зрения можно рассматривать современные блочные шифры как вид полиграммных шифров.

Длина ключа

Длина ключа — это двоичный логарифм от количества всех возможных ключей. Существует 26 n 2 {displaystyle 26^{n^{2}}} матриц размера n × n. Значит, log 2 ⁡ ( 26 n 2 ) ≈ 4 , 7 n 2 {displaystyle log _{2}(26^{n^{2}})approx 4{,}7n^{2}} — верхняя грань длины ключа для шифра Хилла, использующего матрицы n × n. Это только верхняя грань, поскольку не каждая матрица обратима, а только такие матрицы могут быть ключом. Количество обратимых матриц может быть рассчитано при помощи Китайской теоремы об остатках. Матрица обратима по модулю 26 тогда и только тогда, когда она обратима и по модулю 2 и по модулю 13.

Количество обратимых по модулю 2 и 13 матриц размера n × n равно порядку линейной группы GL(n, Z2) и GL(n, Z13) соответственно:

| K 1 | = 2 n 2 ( 1 − 1 / 2 ) ( 1 − 1 / 2 2 ) … ( 1 − 1 / 2 n ) , {displaystyle |K_{1}|=2^{n^{2}}(1-1/2)(1-1/2^{2})dots (1-1/2^{n}),} | K 2 | = 13 n 2 ( 1 − 1 / 13 ) ( 1 − 1 / 13 2 ) … ( 1 − 1 / 13 n ) . {displaystyle |K_{2}|=13^{n^{2}}(1-1/13)(1-1/13^{2})dots (1-1/13^{n}).}

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

| K | = 26 n 2 ( 1 − 1 / 2 ) ( 1 − 1 / 2 2 ) … ( 1 − 1 / 2 n ) ( 1 − 1 / 13 ) ( 1 − 1 / 13 2 ) … ( 1 − 1 / 13 n ) . {displaystyle |K|=26^{n^{2}}(1-1/2)(1-1/2^{2})dots (1-1/2^{n})(1-1/13)(1-1/13^{2})dots (1-1/13^{n}).}

Кроме того, будет разумно избегать слишком большого количества нулей в матрице-ключе, так как они уменьшают диффузию. В итоге получается, что эффективное пространство ключей стандартного шифра Хилла составляет около 4 , 64 n 2 − 1 , 7 {displaystyle 4{,}64n^{2}-1{,}7} . Для шифра Хилла 5 × 5 это составит приблизительно 114 бит. Очевидно, полный перебор — не самая эффективная атака на шифр Хилла.

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

При работе с двумя символами за раз шифр Хилла не предоставляет никаких конкретных преимуществ перед шифром Плэйфера и даже уступает ему по криптостойкости и простоте вычислений на бумаге. По мере увеличения размерности ключа шифр быстро становится недоступным для расчётов на бумаге человеком. Шифр Хилла размерности 6 был реализован механически. Хилл с партнёром получили патент на устройство (U.S. Patent 1 845 947), которое выполняло умножение матрицы 6 × 6 по модулю 26 при помощи системы шестерёнок и цепей. Расположение шестерёнок (а значит, и ключ) нельзя было изменять для конкретного устройства, поэтому в целях безопасности рекомендовалось тройное шифрование. Такая комбинация была очень сильной для 1929 года, и она показывает, что Хилл несомненно понимал концепции конфузии и диффузии. Однако устройство было довольно медленное, поэтому во Второй мировой войне машины Хилла были использованы только для шифрования трёхсимвольного кода радиосигналов.