Программная реализация блочных шифров

Краткая теоретическая часть

Описание шифров

Данный инструмент реализует два шифра:

1) Шифр Хилла

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

Открытый текст рассматривается как последовательность символов некоторого алфавита $A$ мощностью $m$, которые представляются элементами множества $\mathbb{Z}_{m}$. Перед зашифрованием открытый текст разбивается на блоки длины $n$, и каждый блок представляется в виде $n$-мерного вектора.

Ключом шифра является квадратная матрица размера $n \times n$, составленная из элементов множества $\mathbb{Z}_{m}$:

$$K = \left( k_{i,j} \right)_{i = 1,\ j = 1}^{n,\ n},\ k_{i,j} \in \mathbb{Z}_{m} \quad (1.1)$$

где:

• $m$ -- количество символов в алфавите,
• $K$ -- ключ,
• $k$ -- элемент ключа,
• $i$ -- номер строки,
• $j$ -- номер столбца.

Эта матрица должна быть обратима в $\mathbb{Z}_{m}$, чтобы была возможна операция расшифрования. Матрица будет являться обратимой только в том случае, если выполняется условие:

$$|K| \neq 0 \quad и \quad НОД\left( |K|,m \right) = 1 \quad (1.2)$$

где:

• $m$ -- количество символов в алфавите,
• $|K|$ -- определитель ключа.

Операция зашифрования заключается в том, что ключевая матрица умножается на вектор-столбец $X = \left( x_{1},...,x_{n} \right)^{T}$, соответствующий блоку открытого текста:

$$Y = E_{K}(X) = K\left( x_{1},...,x_{n} \right)^{T} = \left( y_{1},...,y_{n} \right)^{T} \quad (1.3)$$

где:

• $E_{K}(X)$ -- операция зашифрования, зависимая от ключа К и открытого текста Х с элементами х,
• $1...n$ - номера элементов открытого текста.

Для того, чтобы расшифровать шифртекст, необходимо разбить его на блоки длины $n$, представить каждый блок в виде вектора $Y = \left( y_{1},...,y_{n} \right)^{T}$ и выполнить обратное умножение:

$$X = D_{K}(Y) = K^{- 1}\left( y_{1},...,y_{n} \right)^{T} = \left( x_{1},...,x_{n} \right)^{T} \quad (1.4)$$

где:

• $D_{K}(Y)$ -- операция расшифрования, зависимая от ключа К и шифротекста Y с элементами y,
• $1...n$ - номера элементов шифротекста.

2) Рекуррентный шифр Хилла

В случае рекуррентного шифра Хилла для каждого блока открытого текста формируется своя ключевая матрица. Для этого задаются две обратимые матрицы $K_{1}$ и $K_{2}$, которые используются для зашифрования первых двух блоков открытого текста. После этого для каждого последующего блока вычисляется новая ключевая матрица на основе двух предыдущих.

$$K_{i} = K_{i - 1}K_{i - 2} \quad (1.5)$$

где $i$ -- порядковый номер ключа.

Для расшифрования шифртекста, полученного с помощью рекуррентного шифра Хилла, необходимо найти обратные матрицы для матриц $K_{1}$ и $K_{2}$, после чего все последующие обратные матрицы могут быть вычислены на основании предыдущих:

$$K_{i}^{- 1} = K_{i - 2}^{- 1}K_{i - 1}^{- 1} \quad (1.6)$$

где $i$ -- порядковый номер ключа.

Методы криптоанализа шифров

Атака на основе выбранного открытого текста и метод полного перебора используются для взлома обычного и рекуррентного шифров Хилла.

Атака при возможности выбора открытого текста (chosen-plaintext) -- криптоаналитик имеет доступ к шифрующему устройству и может зашифровать любой открытый текст. Целью криптоаналитика является определение ключа шифрования.