Шифр Хилла

Введение

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

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

Шифр Хилла

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

В случае латинского алфавита всем буквам должно быть сопоставлено число, к примеру, A – 0, B – 1, C – 2, …, Z – 25. В общем варианте соответствие «буква – число» может выбираться в произвольном порядке.

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

Предположим, имеется следующий открытый текст:

p1p2p3,

а ключом является матрица, имеющая размер три на три и шифротекст, являющийся вектором с размерностью три, то есть:

c1c2c3.

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

Рисунок 1. Система. Автор24 — интернет-биржа студенческих работ

Или в виде системы уравнений система может быть представлена так:

Рисунок 2. Система. Автор24 — интернет-биржа студенческих работ

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

Приведем конкретный пример. Предположим, что отправитель сообщения по имени Алиса желает переслать получателю по имени Боб сообщение «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 открытый текст, то его можно представить следующим образом:

Рисунок 3. Представление открытого текста. Автор24 — интернет-биржа студенческих работ

Для того чтобы выполнить шифровку данного сообщения, следует сделать выбор ключа, например, в виде матрицы, имеющей размер пять на пять (mod 26). Далее сделаем выбор следующей матрицы:

Рисунок 4. Матрица. Автор24 — интернет-биржа студенческих работ

Эта матрица является соответствием следующему ключевому слову:

GYBCHNQKNBURPVOSCXPHJELQV.

Теперь шифротекст C можно получить в виде произведения K • P:

Рисунок 5. Шифротекст. Автор24 — интернет-биржа студенческих работ

C является зашифрованным сообщением в виде «JGUAU».

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

Определим детерминант ключ-матрицы K, приведенной выше, он будет:

det(K) = 413965,

то есть, не равняется нулю.

Делителями детерминанта (413965) являются следующие числа:

5, 82, 793, 413965.

Делителями основания модуля (26) являются следующие числа:

2, 13, 26.

Таким образом, получается, что эта ключ-матрица обладает обратной матрицей $K^{-1}$ (mod 26), представленной ниже:

Рисунок 6. Ключ-матрица. Автор24 — интернет-биржа студенческих работ

Далее можно взять зашифрованный ранее текст C = «JGUAU» и расшифровать его:

Рисунок 7. Расшифровка. Автор24 — интернет-биржа студенческих работ

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

С точки зрения криптостойкости, шифр Хилла обладает следующими достоинствами и недостатками:

1. Взломать шифр Хилла при помощи грубой силы необычайно сложно. Если размерностью матрицы–ключа будет n x n, то всего может существовать $26n^2$ подобных матриц. Правда следует отметить, что не каждая из матриц является обратимой, по этой причине допустимая область будет несколько уже. Количество обратимых матриц может быть определено при помощи китайской теоремы об остатках. К примеру, количество обратимых матриц по модулю 26 равняется $|K| = 26n^2(1 – 1/2)(1 – 1/22)…(1 – 1/2n) (1 – 1/13)(1 – 1/132)…(1 – 1/13n)$.
2. Кроме того шифр Хилла не поддается частотному анализу, поскольку все символы открытого текста участвуют в процессе шифрования. Тем не менее имеется возможность осуществления анализа частоты слов размера n, и это означает, что не следует использовать шифр Хилла для информации, имеющей подобное строение.
3. Шифр Хилла является очень уязвимым для атаки по открытому тексту, поскольку в нем применяются линейные операции.

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