Обзор шифра Хилла

1. Введение

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

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

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

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

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

Пусть «p₁p₂p₃» – открытый текст, ключ – матрица размера 3 x 3 и шифротекст – вектор размерности – 3, «c₁c₂c₃» соответственно. В матричном виде эта система описывается так:

$\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 x 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, то всего существует 26^{n^2} таких матриц. Но не каждая матрица обратима, поэтому область несколько сужается. Количество обратимых матриц можно рассчитать с помощью китайской теоремы об остатках. Например, количество обратимых матриц по модулю 26 равно:

|K| = 26^{n^2}(1 – 1/2)(1 – 1/2²)…(1 – 1/2ⁿ) (1 – 1/13)(1 – 1/13²)…(1 – 1/13ⁿ)

В результате эффективное пространство ключей составляет около 4.64n² – 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, из которого формируется требуемая матрица ключей.

Generation of Key Matrix for Hill Cipher Encryption Using Classical Cipher

ieeexplore.ieee.org

3) Криптостойкость шифра Хилла можно повысить, если использовать меняющуюся длину ключа. Длина открытого текста меняется случайным образом: m = 2^k (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существует$