Каталог@Mail.ru - каталог ресурсов интернет HitMeter - счетчик посетителей сайта, бесплатная статистика

Шифр Хилла

Другие шифры На главную Хеш-функции

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

см. также дополнение.

1. Алфавит и ключ шифра Хилла

Есть некоторый алфавит A, состоящий из n символов, символы пронумерованы от 0 до n-1.
Имеется матрица C размера m * m (квадратная матрица), являющаяся ключом шифра. Элементы матрицы состоят из чисел от 0 до n-1, при этом одинаковые числа не запрещены.
Произведение матриц в шифре Хилла несколько отличается от обычного: вместо элементов традиционного произведения берутся их остатки от деления на n.

Матрица C в шифре Хилла должна быть обратима. В данном случае обратимость матрицы проверяется по переопределённому, а не традиционному умножению. Пусть D - обратная матрица. Тогда матрицы CD и DC должны быть единичными, но используется новый вариант умножения.

Приведём пример: пусть n = 7, C - следующая матрица

23
14
В этом случае обратной будет матрица D вот такая:

55
46
Тогда получаем следующее:

"Традиционное" умножение
CDDC
2228
2129
1535
1436


Итак, обе полученные матрицы не единичные. Но теперь вспоминаем, что у нас другое умножение, а именно - вместо имеющихся элементов нужны остатки от деления на n = 7. Тогда всё в порядке: 22, 29, 15, 36 делятся на 7 с остатком 1, а 28, 21, 35, 14 кратны 7.

В шифре Хилла матрица C нужна для шифрования, матрица D - для расшифрования.

2. Алгоритм шифра Хилла

Шифр Хилла (можно также криптосистема Хилла) работает по следующему алгоритму:
1.Открытый текст разбивается на блоки размером m. Если длина текста не кратна m, в хвост текста что-нибудь добавляется.
2.Каждый блок представляется в виде вектора v. Если i-ый символ блока имеет номер k в алфавите, то v(i) = k. Например, если алфавит - ABC...Z, A = 0, B = 1, ..., то DB = (3, 1). Далее ищется произведение Cv так, как было описано выше (по модулю n). В результате получается некоторый вектор w.
По вектору w восстанавливаем блок шифрованного текста: если w(i) = k, то i-ым символом блока шифрованного текста является символ, имеющий номер k в алфавите.
3.Блоки шифрованного текста сцепляются в единый текст.

Если термины открытый текст и шифрованный текст поменять местами, а вместо матрицы C применить D, будет выполнено расшифрование.

Действительно, Dw = D(Cv) = (DC)v = v, то есть мы пользуемся ассоциативностью умножения матриц и определением обратной матрицы.

Поскольку C(Dv) = (CD)v = v, то шифр Хилла обладает вот каким забавным свойством:
если одновременно можно использовать C для шифрования и D для расшифрования, то одновременно можно использовать D для шифрования и C для расшифрования.

3. Шифр Хилла: пример

Покажем, как действует шифр Хилла, на несложном примере.
Алфавит - английский, A = 0, B = 1, ..., Z = 25 (n = 26). Длина блока: m = 3, матрицы:

C (для шифрования)D (для расшифрования)
6241
131610
201715
8510
21821
21128


Зашифруем слово ROCKET. В данном случае открытый текст имеет 2 блока: ROC, KET. Блоку ROC соответствует вектор v = (17, 14, 2); Cv = (440 mod 26, 465 mod 26, 608 mod 26) = (24, 23, 10) => YXK.
Блок KET: v = (10, 4, 19), Cv = (175 mod 26, 384 mod 26, 553 mod 26) = (19, 20, 7) => TUH.
Таким образом, вместо ROCKET получаем YXKTUH.
Расшифрование: w = (24, 23, 10), тогда Dw = (407 mod 26, 898 mod 26, 860 mod 26) = (17, 14, 2) => ROC.
w = (19, 20, 7), тогда Dw = (322 mod 26, 706 mod 26, 695 mod 26) = (10, 4, 19) => KET.

4. Особенности шифра Хилла

Нетрудно заметить, что шифр Хилла применяется для шифрования полиграмм, то есть выделяются группы символов. Если сравнить с классическими шифрами, это явный шаг вперёд, ибо предшественники в основном оперировали одиночными символами или биграммами (из последних на данном сайте можно изучить шифры Уитстона и Плейфера).

Если текст делить на блоки по 1-2 символа, шифр, который это делает, оказывается уязвимым к атакам, основанным на использовании частоты встречаемости символов и биграмм. То есть для наиболее известных языков уже посчитано, насколько часто встречается тот или иной символ (биграмма) в текстах, где этот язык используется. Так, статистически в русскоязычных текстах 17,5% символов составляют пробелы, ещё 9% - буква О. Соответственно весьма полезно прятать статистику вхождения символов в открытый текст. Не следует забывать о стремлении частоты к вероятности - эта аксиома теории вероятностей даёт о себе знать в случае длинных открытых текстов.

Шифр Хилла можно применять для биграмм (то есть m = 2), но тогда он даже уступает шифру Плейфера. Ясно, что чем больше размер блока, тем сложнее вскрыть криптосистему Хилла.

5. Рекомендации по подбору шифрующей матрицы

Чтобы матрица C имела обратную нужно, чтобы определитель был отличен от нуля и не имел общих делителей с молудем n, кроме единицы. Определитель вычисляется по модулю n , где n - количество символов в алфавите. Если "привычный" определитель detC от нуля до n-1, всё нормально; если detC > n-1, ищем detC mod n; если detC < 0, ищем наименьшее натуральное число k такое, что detC + kn неотрицательное.
Для простоты проверим при n = 7 вот такую матрицу C:

55
46


detC = 5 * 6 - 4 * 5 = 10; detC mod n = 3. Легко проверить, что у 7 и 3 есть единственный общий делитель - 1. Таким образом, матрица C имеет обратную. Какую именно - нетрудно понять, если снова вернуться к примерам.

Чтобы избавиться от ситуации НОД(detC, n) > 1, где НОД - наибольший общий делитель, легче всего взять n простым числом. Если количество символов алфавита не является простым числом, нужно дополнить его какими-либо символами, чтобы новое n стало простым, то есть делящимся только на 1 и на само себя. Так, русский алфавит + 4 знака препинания = 37 символов, английский алфавит + 3 знака препинания = 29 символов.

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

Шифр Хилла онлайн

Алфавит и матрица шифрования - как рассмотренные в примере из пункта 3. Если длина текста не кратна 3, добавляются символы A.

Открытый текст

Шифрованный текст

copyright © Исканцев Н.В., 2012

На главную
X