Шифр холма - Hill cipher

Шифровальная машина Хилла, из рисунка 4 патента

В классическая криптография, то Шифр холма это шифр полиграфической замены на основе линейная алгебра. Изобретенный Лестер С. Хилл в 1929 году это был первый полиграфический шифр, в котором было практично (хотя и почти не) оперировать более чем тремя символами одновременно.

Следующее обсуждение предполагает элементарные знания матрицы.

Шифрование

Каждая буква представлена числом по модулю 26. Хотя это не является существенной особенностью шифра, часто используется эта простая схема:

Письмо	А	B	C	D	E	F	грамм	ЧАС	я	J	K	L	M	N	О	п	Q	р	S	Т	U	V	W	Икс	Y	Z
Число	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25

Чтобы зашифровать сообщение, каждый блок п буквы (рассматриваются как п-компонент вектор ) умножается на обратимый п × п матрица, против модуль 26. Чтобы расшифровать сообщение, каждый блок умножается на матрицу, обратную матрице, используемой для шифрования.

Матрица, используемая для шифрования, - это шифр ключ, и его следует выбирать случайным образом из множества обратимых п × п матрицы (по модулю 26). Конечно, шифр можно адаптировать к алфавиту с любым количеством букв; вся арифметика просто должна быть сделана по модулю количество букв вместо по модулю 26.

Рассмотрим сообщение "ACT" и ключ ниже (или GYB/NQK/URP буквами):

{ displaystyle { begin {pmatrix} 6 & 24 & 1 13 & 16 & 10 20 & 17 & 15 end {pmatrix}}}

Поскольку 'A' равно 0, 'C' равно 2, а 'T' равно 19, сообщение является вектором:

{ displaystyle { begin {pmatrix} 0 2 19 end {pmatrix}}}

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

{ displaystyle { begin {pmatrix} 6 & 24 & 1 13 & 16 & 10 20 & 17 & 15 end {pmatrix}} { begin {pmatrix} 0 2 19 end {pmatrix}} = { begin {pmatrix} 67 222 319 end {pmatrix}} Equiv { begin {pmatrix} 15 14 7 end {pmatrix}} { pmod {26}}}

что соответствует зашифрованный текст из «ПОН». Теперь предположим, что наше сообщение вместо «CAT» или:

{ displaystyle { begin {pmatrix} 2 0 19 end {pmatrix}}}

На этот раз зашифрованный вектор имеет следующий вид:

{ displaystyle { begin {pmatrix} 6 & 24 & 1 13 & 16 & 10 20 & 17 & 15 end {pmatrix}} { begin {pmatrix} 2 0 19 end {pmatrix}} Equiv { begin {pmatrix} 31 216 325 end {pmatrix}} Equiv { begin {pmatrix} 5 8 13 end {pmatrix}} { pmod {26}}}

что соответствует зашифрованному тексту «FIN». Каждая буква изменилась. Шифр Хилла достиг Шеннон с распространение, а n-мерный шифр Хилла может полностью распространяться по n символам одновременно.

Расшифровка

Чтобы расшифровать, мы превращаем зашифрованный текст обратно в вектор, а затем просто умножаем его на обратную матрицу ключевой матрицы (IFK/VIV/ДМС буквами). (Видеть инверсия матриц для методов вычисления обратной матрицы.) Мы находим, что, по модулю 26, матрица, обратная к предыдущему примеру:

{ displaystyle { begin {pmatrix} 6 & 24 & 1 13 & 16 & 10 20 & 17 & 15 end {pmatrix}} ^ {- 1} { pmod {26}} Equiv { begin {pmatrix} 8 & 5 & 10 21 & 8 & 21 21 & 12 & 8 конец {pmatrix}}}

Взяв зашифрованный текст POH из предыдущего примера, мы получаем:

{ displaystyle { begin {pmatrix} 8 & 5 & 10 21 & 8 & 21 21 & 12 & 8 end {pmatrix}} { begin {pmatrix} 15 14 7 end {pmatrix}} Equiv { begin {pmatrix} 260 574 539 end {pmatrix}} Equiv { begin {pmatrix} 0 2 19 end {pmatrix}} { pmod {26}}}

что, как и ожидалось, возвращает нас к "ACT".

При выборе матрицы шифрования существуют две сложности:

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

Таким образом, если мы работаем по модулю 26, как указано выше, определитель должен быть ненулевым и не должен делиться на 2 или 13. Если определитель равен 0 или имеет общие множители с модульной базой, то матрица не может использоваться в матрице Хилла. cipher, при этом необходимо выбрать другую матрицу (иначе расшифровать не удастся). К счастью, матрицы, удовлетворяющие условиям, используемым в шифре Хилла, встречаются довольно часто.

Для нашего примера ключевой матрицы:

{ displaystyle { begin {vmatrix} 6 & 24 & 1 13 & 16 & 10 20 & 17 & 15 end {vmatrix}} Equiv 6 (16 cdot 15-10 cdot 17) -24 (13 cdot 15-10 cdot 20) + 1 (13 cdot 17-16 cdot 20) Equiv 441 Equ 25 { pmod {26}}}

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

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

Пример

Позволять

${ displaystyle K = { begin {pmatrix} 3 & 3 2 & 5 end {pmatrix}}}$

будет ключом, и предположим, что текстовое сообщение - HELP. Тогда этот открытый текст представлен двумя парами

${ displaystyle HELP to { begin {pmatrix} H E end {pmatrix}}, { begin {pmatrix} L P end {pmatrix}} to { begin {pmatrix} 7 4 end {pmatrix}}, { begin {pmatrix} 11 15 end {pmatrix}}}$

Затем мы вычисляем

${ displaystyle { begin {pmatrix} 3 & 3 2 & 5 end {pmatrix}} { begin {pmatrix} 7 4 end {pmatrix}} Equiv { begin {pmatrix} 7 8 end { pmatrix}} { pmod {26}},}$ и

${ displaystyle { begin {pmatrix} 3 & 3 2 & 5 end {pmatrix}} { begin {pmatrix} 11 15 end {pmatrix}} Equiv { begin {pmatrix} 0 19 end { pmatrix}} { pmod {26}}}$

и продолжаем шифрование следующим образом:

${ displaystyle { begin {pmatrix} 7 8 end {pmatrix}}, { begin {pmatrix} 0 19 end {pmatrix}} to { begin {pmatrix} H I end {pmatrix}}, { begin {pmatrix} A T end {pmatrix}}}$

Матрица K обратима, поэтому ${ displaystyle K ^ {- 1}}$ существует такое, что ${ displaystyle KK ^ {- 1} = K ^ {- 1} K = I_ {2}}$ Обратное к K может быть вычислено с помощью формула ${ displaystyle { begin {pmatrix} a & b c & d end {pmatrix}} ^ {- 1} = (ad-bc) ^ {- 1} { begin {pmatrix} d & -b - c & a end {pmatrix}}}$

Эта формула остается верной после модульной редукции, если модульный мультипликативный обратный используется для вычисления ${ displaystyle (ad-bc) ^ {- 1}}$ . Следовательно, в этом случае мы вычисляем

${ Displaystyle К ^ {- 1} Equiv 9 ^ {- 1} { begin {pmatrix} 5 & 23 24 & 3 end {pmatrix}} Equ 3 { begin {pmatrix} 5 & 23 24 & 3 end {pmatrix }} Equiv { begin {pmatrix} 15 и 17 20 и 9 end {pmatrix}} { pmod {26}}}$

${ displaystyle HIAT to { begin {pmatrix} H I end {pmatrix}}, { begin {pmatrix} A T end {pmatrix}} to { begin {pmatrix} 7 8 end {pmatrix}}, { begin {pmatrix} 0 19 end {pmatrix}}}$

Затем мы вычисляем

${ displaystyle { begin {pmatrix} 15 & 17 20 & 9 end {pmatrix}} { begin {pmatrix} 7 8 end {pmatrix}} Equiv { begin {pmatrix} 7 4 end { pmatrix}} { pmod {26}},}$ и

${ displaystyle { begin {pmatrix} 15 & 17 20 & 9 end {pmatrix}} { begin {pmatrix} 0 19 end {pmatrix}} Equiv { begin {pmatrix} 11 15 end { pmatrix}} { pmod {26}}}$

Следовательно,

${ displaystyle { begin {pmatrix} 7 4 end {pmatrix}}, { begin {pmatrix} 11 15 end {pmatrix}} to { begin {pmatrix} H E end {pmatrix}}, { begin {pmatrix} L P end {pmatrix}} to HELP}$ .

Безопасность

Базовый шифр Хилла уязвим для атака с известным открытым текстом потому что это полностью линейный. Противник, который перехватывает ${ displaystyle n}$ Пары символов открытого текста / зашифрованного текста могут создать линейную систему, которая (обычно) легко решается; если случится так, что эта система не определена, необходимо только добавить еще несколько пар открытый текст / зашифрованный текст. Вычисление этого решения с помощью стандартных алгоритмов линейной алгебры занимает очень мало времени.

Хотя умножение матриц само по себе не приводит к созданию безопасного шифра, оно все же является полезным шагом в сочетании с другими нелинейный операций, потому что умножение матриц может обеспечить распространение. Например, правильно выбранная матрица может гарантировать, что небольшие различия до умножения матрицы приведут к большим различиям после умножения матриц. Действительно, некоторые современные шифры используют шаг матричного умножения для обеспечения распространения. Например, шаг MixColumns в AES - матричное умножение. Функция грамм в Twofish представляет собой комбинацию нелинейных S-блоков с тщательно подобранным матричным умножением (MDS).

Размер ключевого пространства

В ключевое пространство - это набор всех возможных ключей. Размер ключевого пространства - это количество возможных ключей. размер ключа в количестве бит двоичный логарифм размера ключевого пространства.

Есть ${ displaystyle 26 ^ {п ^ {2}}}$ матрицы размерности n × n. Таким образом ${ Displaystyle журнал _ {2} (26 ^ {п ^ {2}})}$ или о ${ displaystyle 4.7n ^ {2}}$ - это верхняя граница размера ключа шифра Хилла с использованием матриц размера n × n. Это только верхняя граница, потому что не каждая матрица обратима и, следовательно, может использоваться в качестве ключа. Количество обратимых матриц можно вычислить с помощью Китайская теорема об остатках. То есть, матрица обратима по модулю 26 тогда и только тогда, когда она обратима как по модулю 2, так и по модулю 13. Число обратимых матриц размера n × n по модулю 2 равно порядку общая линейная группа GL (п,Z₂). это

{ displaystyle 2 ^ {n ^ {2}} (1-1 / 2) (1-1 / 2 ^ {2}) cdots (1-1 / 2 ^ {n}).}

Точно так же количество обратимых матриц по модулю 13 (т. Е. Порядок GL (n,Z₁₃)) является

{ displaystyle 13 ^ {n ^ {2}} (1-1 / 13) (1-1 / 13 ^ {2}) cdots (1-1 / 13 ^ {n}).}

Количество обратимых матриц по модулю 26 является произведением этих двух чисел. Следовательно, это

{ displaystyle 26 ^ {n ^ {2}} (1-1 / 2) (1-1 / 2 ^ {2}) cdots (1-1 / 2 ^ {n}) (1-1 / 13) (1-1 / 13 ^ {2}) cdots (1-1 / 13 ^ {n}).}

Кроме того, кажется разумным избегать слишком большого количества нулей в ключевой матрице, поскольку они уменьшают распространение. В результате эффективное пространство ключей базового шифра Хилла составляет примерно ${ displaystyle 4.64n ^ {2} -1.7}$ . Для шифра Хилла 5 × 5 это примерно 114 бит. Конечно, поиск по ключу - не самая эффективная из известных атак.

Механическая реализация

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

Шифр Хилла размерности 6 был реализован механически. Хилл и его партнер были награждены патент (Патент США 1845947 ) для этого устройства, которое выполнило матричное умножение 6 × 6 по модулю 26 с использованием системы шестерен и цепей.

К сожалению, механизмы передачи (и, следовательно, ключ) были фиксированы для любой данной машины, поэтому для безопасности было рекомендовано тройное шифрование: секретный нелинейный шаг, за которым следует широкий диффузный шаг от машины, за которым следует третий секретный нелинейный шаг. (Значительно позже Шифр Эвен-Мансура также использует неключевой диффузионный средний шаг). Такая комбинация на самом деле была очень сильной для 1929 года и указывает на то, что Хилл, очевидно, понимал концепции атака встречей посередине а также путаница и расплывчатость. К сожалению, его машина не продавалась.^{[нужна цитата ]}

Смотрите также

Другие практические "карандашно-бумажные" полиграфические шифры включают:

внешняя ссылка

"Веб-приложение Hill Cipher "реализует шифр Хилла и показывает задействованные матрицы
"Объяснение Hill Cipher "иллюстрирует линейную алгебру, лежащую в основе Hill Cipher.
"Калькулятор шифров Хилла "описывает Hill Cipher на веб-странице