Небольшой обзор на Шифр Хилла (Краткое пособие)13.12.2021 18:01

1.   Введение

В современном мире, полном информационных технологий, мы доверяем свои данные интернет — сервисам. Разумно предположить, что доступ к этим данным должен иметь только определенный круг лиц. Как раз для этого и существует шифрование. Шифрование — это кодирование информации, процесс использующийся для обеспечения конфиденциальности и безопасности данных, таких как тестовые сообщения, банковские реквизиты и т.д. Исходное сообщение (данные) называется открытым текстом, зашифрованное сообщение (данные) называется шифротекстом. Процедура шифрования обычно включает в себя использование определенного алгоритма и ключа. Алгоритм — это определенный способ засекречивания сообщения (список инструкций). Ключ же конкретизирует процедуру засекречивания.

В этой статье мы затронем такой вариант шифрования, как шифр Хилла, а именно алгоритм шифрования, расшифрования, криптостойкость и варианты различных модификаций.

Шифр Хилла — полиграммный шифр подстановки (элементы исходного открытого текста заменяются зашифрованным текстом в соответствии с некоторым правилом), в котором буквы открытого текста заменяются группами с помощью линейной алгебры. Для латинского алфавита каждой букве сопоставляется число, например, A — 0, B — 1, C — 2, …, Z — 25. В общем случае соответствия «буква — число» можно выбрать произвольно.

2.   Шифрование

Открытый текст представляет собой n-мерный вектор. Ключ — квадратная матрица размера n x n. Для получения шифротекста ключ умножается на открытый текст по модулю выбранной числовой схемы, в случае латинского алфавита — 26.

Пусть «p1p2p3» — открытый текст, ключ — матрица размера 3×3 и шифротекст — вектор размерности — 3, «c1c2c3» соответственно. В матричном виде эта система описывается так:

\begin{bmatrix} c_1\\ c_2\\ c_3\end{bmatrix} = \begin{bmatrix} k_{11}&k_{12}&k_{13}\\k_{21}&k_{22}&k_{23}\\k_{31}&k_{32}&k_{33} \end{bmatrix} * \begin{bmatrix} p_1\\p_2\\p_3 \end{bmatrix}

Или в качестве системы уравнений:

\begin{equation*}  \begin{cases} c_1 = k_{11}*p_1 + k_{12}*p_2+k_{13}*p_3 \\ c_2 = k_{21}*p1+k_{22}*p_2+k_{23}*p_3\\c_3=k_{31}*p_1+k_{32}*p_2+k_{33}*p_3\end{cases} \end{equation*}

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

Рассмотрим пример: Алиса хочет передать Бобу сообщение «hello», используя следующую числовую схему:

A

0

N

13

B

1

O

14

C

2

P

15

D

3

Q

16

E

4

R

17

F

5

S

18

G

6

T

19

H

7

U

20

I

8

V

21

J

9

W

22

K

10

X

23

L

11

Y

24

M

12

Z

25

Открытый текст, обозначим как P, будет выглядеть следующим образом:

P =\begin{bmatrix} 7\\4\\11\\11\\14\end{bmatrix}\\

Чтобы зашифровать данное сообщение нужно выбрать ключ — матрицу размером 5×5 (mod 26). Возьмем следующую матрицу:

K = \begin{bmatrix} 6&24&1&2&7\\13&16&10&13&1\\18&2&23&15&7\\9&24&11&16&21\\20&7&22&3&17\end{bmatrix}

что соответствует ключевому слову «GYBCHNQKNBURPVOSCXPHJELQV».

Тогда шифротекст C может быть получен, как K x P.

C = K*P = \begin{bmatrix}  6&24&1&2&7\\13&16&10&13&1\\18&2&23&15&7\\9&24&11&16&21\\20&7&22&3&17\  \end{bmatrix}*\begin{bmatrix} 7\\4\\11\\11\\14\ \end{bmatrix} = \begin{bmatrix} 9\\6\\20\\0\\20\ \end{bmatrix}

 C — зашифрованное сообщение («JGUAU»).

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

Чтобы Боб смог расшифровать сообщение, переданное Алисой, ключ — матрица должна иметь обратную матрицу. Такое возможно, если детерминант матрицы не равен нулю и не имеет общих делителей с основанием модуля. Именно это условие позволяет упростить задачу, можно выбрать в качестве основания модуля простое число, путем добавления в числовую схему новых элементов, например, знаков препинания. Таким образом детерминант любой матрицы не будет иметь общих делителей с основанием такого модуля.

Детерминант ключ — матрицы K, приведенной выше:

det (K) = -413965 — не равен 0.

Делители детерминанта = 413965: 5, 82, 793, 413965.

Делители основания модуля = 26: 2, 13, 26.

Следовательно, данная ключ — матрица имеет обратную матрицу K-1 (mod 26).

K^{-1} = \begin{bmatrix}  9&18&14&8&25\\10&7&15&18&15\\21&9&18&19&25\\7&2&4&13&24\\20&7&22&3&17\  \end{bmatrix}

Берем зашифрованный раннее текст C = » JGUAU» и расшифруем его:

P = K^{-1}*C = \begin{bmatrix} 9&18&14&8&25\\10&7&15&18&15\\21&9&18&19&25\\7&2&4&13&24\\20&7&22&3&17\ \end{bmatrix}*\begin{bmatrix} 9\\6\\20\\0\\20\ \end{bmatrix} =\begin{bmatrix} 7\\4\\11\\11\\14\ \end{bmatrix}

Таким образом Боб успешно расшифровал сообщение, переданное Алисой, которое содержало слово «hello».

4.   Криптостойкость шифра Хилла

1)     Атаковать грубой силой шифр Хилла сложно. Если размерность матрицы — ключа n x n, то всего существует 26n2 таких матриц. Но не каждая матрица обратима, поэтому область несколько сужается. Количество обратимых матриц можно рассчитать с помощью китайской теоремы об остатках. Например, количество обратимых матриц по модулю 26 равно:

               |K| = 26n2(1 — ½)(1 — 1/22)…(1 — 1/2n) (1 — 1/13)(1 — 1/132)…(1 — 1/13n)

В результате эффективное пространство ключей составляет около 4.64n2 — 1.7. Для ключа размера 5×5 этот параметр будет равен 114 битам, что делает вариант полного перебора неприменимым.

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

3)     Шифр Хилла очень уязвим для атаки по открытому тексту, так как в нем используются линейные операции. Если Ева знает m пар «открытое сообщение»/ «зашифрованное сообщение», то она может вычислить ключ. Предположим, что Ева перехватила 3 пары «открытое сообщение»/ «зашифрованное сообщение»:

\begin{bmatrix} 2&5&1 \end{bmatrix} \Leftrightarrow \begin{bmatrix} 3&17&21\end{bmatrix}\\\begin{bmatrix} 6&17&8 \end{bmatrix}\Leftrightarrow\begin{bmatrix} 4&13&25 \end{bmatrix}\\\begin{bmatrix} 25&0&13 \end{bmatrix}\Leftrightarrow\begin{bmatrix} 13&18&20 \end{bmatrix}

Если составить матрицы P и C из этих пар, то можно найти ключ K. Если матрица P не будет являться обратимой, то необходимо задействовать другие m наборов пар «открытое сообщение»/ «зашифрованное сообщение». В данном случае матрица P обратима.

P = \begin{bmatrix} 2&5&1\\6&17&8\\25&0&13 \end{bmatrix}\\C = \begin{bmatrix} 3&17&21\\4&13&25\\13&18&20\end{bmatrix}\\P^{-1} = \begin{bmatrix}13&13&25\\6&9&14\\23&7&10\end{bmatrix} \\K = P^{-1}*C =\begin{bmatrix} 0&8&6\\2&3&7\\19&12&0 \end{bmatrix}

Теперь Ева может расшифровать любое перехваченное сообщение.

5.   Вариации и модификации шифра Хилла

Оригинальный шифр Хилла не нашел практического применения в криптографии из-за слабой устойчивости ко взлому и отсутствия описания алгоритмов генерации прямых и обратных матриц большого размера. Большинство модифицированных криптосистем предполагают при шифровании/дешифровании использовать не одну пару ключей, а несколько, что многократно повышает стойкость системы. При шифровании каждый блок открытого текста обрабатывается отдельным ключом. Использование данного принципа позволяет в значительной степени скрыть статистические свойства открытого и шифрованного текста, а также взаимосвязь между ними. Несколько примеров ниже:

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

A triple hill cipher algorithm proposed to increase the security of encrypted binary dataand its implementation using FPGA

ieeexplore.ieee.org

2)     Мани и Вишвамбари предложили детерминированный метод генерации ключевой матрицы на основе магического прямоугольника. Матрица ключей более высокого порядка генерируется на основе m. Чтобы сгенерировать матрицу ключей, сначала магический прямоугольник порядка m × n преобразуется в магический квадрат порядка m × m, из которого формируется требуемая матрица ключей.

3)     Криптостойкость шифра Хилла можно повысить, если использовать меняющуюся длину ключа. Длина открытого текста меняется случайным образом: m = 2k (k = 3, 4, 5, …), вследствие чего меняются шифрующие и дешифрующие матрицы.

4)     Так же был предложен вариант генерации ключа с помощью LU разложения без фракций. Если взять случайно сгенерированную матрицу, получить LU разложение этой матрицы, то так как матрица L всегда обратима, она может быть использована в качестве ключа. Рассмотрим по подробнее этот процесс:

Генерация ключа с помощью LU разложения

Самой большой проблемой в шифре Хилла является поиск матрицы, соответствующей ключу, которая имеет обратную матрицу. Одним из способов разрешения является генерация ключ — матриц с помощью LU разложения (матрица L обратима всегда). Но матрицы L и U могут содержать дроби, следовательно, они не будут подходить для ключа. Однако это решается LU разложением без фракций. Мы можем получить LU разложение матрицы A без дробей в виде P x A = L x D-1 x U, где P — матрица перестановок, а D — диагональная матрица. Это очень сложная задача — вручную определить разложение LU без фракций с помощью ручки и бумаги. Но с помощью компьютера это можно легко вычислить. Так как матрицы L и U свободны от фракций, числа в матрице становятся довольно большими, а также имеют смешанные значения, такие как положительное целое число, отрицательное целое число и нули, что усложняет ключ.

Рассмотрим на примере:

В качестве разлагаемой матрицы можно взять симметричные, так и асимметричные. Рассмотрим случайную симметричную матрицу:

S = \begin{bmatrix} 71&80&2\\80&99&84\\2&84&22 \end{bmatrix} - симметричная\spaceматрица\\P = \begin{bmatrix} 1&0&0\\0&1&0\\0&0&1 \end{bmatrix} - матрица\spaceперестановок\\L = \begin{bmatrix}71&0&0\\80&629&0\\2&5804&1\end{bmatrix} - нижне-треугольная\spaceматрица\\D = \begin{bmatrix} 71&0&0\\0&44659&0\\0&0&629\end{bmatrix} - матрица\spaceидентичности\\U = \begin{bmatrix}71&80&2\\0&629&5804\\0&0&-460654 \end{bmatrix} - верхне-треугольная\spaceматрица\\K = L(mod \space26) = \begin{bmatrix} 19&0&0\\2&5&0\\2&6&1 \end{bmatrix}\\K^{-1} = \begin{bmatrix} 11&0&0\\6&21&0\\20&4&1\end{bmatrix} - обратная\spaceматрица\spaceсуществует

6.   Выводы

Достоинства шифра Хилла:

1)     Устойчивость к частотному анализу

2)     Устойчивость к полному перебору, даже при относительно небольших размерах ключа

3)     Простота и скорость применения

Недостатки:

1)     Уязвимость к атаке по открытому тексту

2)     Высокая сложность генерации ключ — матриц, особенно больших размерностей

© Habrahabr.ru