Шифр Гілла

Шифр Гілла — поліграмний шифр підстановки, заснований на лінійній алгебрі. Лестер Гілл винайшов цей шифр в 1929, і це був перший шифр, який дозволяв на практиці (хоча і з труднощами) оперувати більш ніж з трьома символами за раз. Подальше обговорення шифру передбачає початкові знання матриць.

Шифрування

Кожній букві спершу зіставляється число. Для латинського алфавіту часто використовується найпростіша схема: A = 0, B = 1, …, Z = 25, але це не є істотною властивістю шифру. Блок з n букв розглядається як n-мірний вектор і множиться на n × n матрицю по модулю 26. (Якщо як основа модуля використовується число більше ніж 26, то можна використовувати іншу числову схему для зіставлення буквах чисел і додати прогалини і знаки пунктуації.) Матриця повністю є ключем шифру. Матриця повинна бути оборотною в $\mathbb {Z} _{26}^{n}$, щоб була можлива операція розшифрування.

У наступних прикладах використовуються латинські літери від A до Z, відповідні їм чисельні значення наведені в таблиці.

A	B	C	D	E	F	G	H	I	J	K	L	M	N	O	P	Q	R	S	T	U	V	W	X	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

Розглянемо повідомлення 'DOG' і представлений нижче ключ (GYBNQKURP в буквеному вигляді):

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

Оскільки букві 'D' відповідає число 3, 'O' — 14, 'G' — 6, то повідомлення — це вектор

${\begin{pmatrix}3\\14\\6\end{pmatrix}}$

Тоді зашифрований вектор буде

${\begin{pmatrix}6&24&1\\13&16&10\\20&17&15\end{pmatrix}}{\begin{pmatrix}3\\14\\6\end{pmatrix}}={\begin{pmatrix}360\\323\\388\end{pmatrix}}\equiv {\begin{pmatrix}22\\11\\24\end{pmatrix}}{\pmod {26}}$

що відповідає шифротексту 'WLY'. Тепер припустимо, що наше повідомлення було 'GOD' або

${\begin{pmatrix}6\\14\\3\end{pmatrix}}$

Тепер зашифрований вектор буде

${\begin{pmatrix}6&24&1\\13&16&10\\20&17&15\end{pmatrix}}{\begin{pmatrix}6\\14\\3\end{pmatrix}}\equiv {\begin{pmatrix}375\\332\\403\end{pmatrix}}\equiv {\begin{pmatrix}11\\20\\13\end{pmatrix}}{\pmod {26}}$

що відповідає шифротексту 'LUN'. Видно, що кожна буква шифротекста змінилася. Шифр Гілла досяг дифузії по Шеннону, і n-розмірний шифр Гілла може досягати дифузії n символів за раз.

Розшифрування

Для того, щоб розшифрувати повідомлення, необхідно звернути шифротекст назад в вектор і потім просто помножити на зворотню матрицю ключа (IFKVIVVMI в буквеному вигляді). (Існують стандартні методи обчислення зворотніх матриць, дивіться способи знаходження Оберненої матриці для подробиць.) В $\mathbb {Z} _{26}^{n}$ зворотна матриця до використаної в прикладі шифрування буде

${\begin{pmatrix}8&5&10\\21&8&21\\21&12&8\end{pmatrix}}$

Візьмемо шифротекст з попереднього прикладу 'WLY'. Тоді ми отримаємо

${\begin{pmatrix}8&5&10\\21&8&21\\21&12&8\end{pmatrix}}{\begin{pmatrix}22\\11\\24\end{pmatrix}}\equiv {\begin{pmatrix}471\\1054\\786\end{pmatrix}}\equiv {\begin{pmatrix}3\\14\\6\end{pmatrix}}{\pmod {26}}$

що повертає нас до повідомлення 'DOG', як ми й розраховували.

Необхідно обговорити деякі складнощі, пов'язані з вибором шифрувальної матриці. Не всі матриці мають обернену (див. Обернена матриця). Матриця матиме обернену в тому і тільки в тому випадку, коли її детермінант не дорівнює нулю і не має спільних дільників з основою модуля. Таким чином, якщо ми працюємо з основою модуля 26 як в прикладах вище, то детермінант повинен бути ненульовим і не ділитися на 2 і 13. Якщо детермінант матриці дорівнює нулю або має спільні дільники з основою модуля, то така матриця не може використовуватися в шифрі Гілла, і повинна бути обрана інша матриця (в іншому випадку шифротекст буде неможливо розшифрувати). Однак, матриці, які задовольняють вищенаведеним умовам, існують в достатку.

Детермінант матриці з прикладу:

${\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\equiv 25{\pmod {26}}$

Отже, детермінант дорівнює 25 по модулю 26. Так число 25 не має спільних дільників з числом 26, то матриця з таким детермінантом може використовуватися в шифрі Гілла.

Небезпека того, що детермінант матриці ключа буде мати загальні дільники з основою модуля може бути усунена шляхом вибирання простого числа як основи модуля. Наприклад, в більш зручному варіанті шифру Гілла в алфавіт додають 3 додаткових символи (такі як пробіл, крапка і знак питання), щоб збільшити основу модуля до 29.

Криптостійкість

На жаль, стандартний шифр Гілла вразливий до атаки по обраному відкритому тексту, тому що він повністю лінійний. Криптоаналітик, який перехопить $n^{2}$ пар символ повідомлення / символ шифротекста зможе скласти систему лінійних рівнянь, яку зазвичай не складно вирішити. Якщо виявиться, що система не вирішувана, то необхідно всього лише додати ще кілька пар символ повідомлення/символ шифротекста. Такого роду розрахунки засобами звичайних алгоритмів лінійної алгебри вимагає зовсім небагато часу.

Довжина ключа

Довжина ключа — це двійковий логарифм від кількості всіх можливих ключів. Існує $26^{n^{2}}$ матриць розміру n × n. Значить, $\log _{2}(26^{n^{2}})$ або приблизно $4.7n^{2}$ — верхня грань довжини ключа для шифру Гілла, що використовує матриці n × n. Це тільки верхня грань, оскільки не кожна матриця обернена, а тільки такі матриці можуть бути ключем. Кількість обернених матриць може бути розрахована за допомогою Китайської теореми про залишки. Тобто матриця обернена по модулю 26 тоді і тільки тоді, коли вона обернена і по модулю 2 і по модулю 13. Кількість обернених по модулю 2 матриць розміру n × n одно порядку лінійної групи GL (n, 'Z' ₂ ). Це

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

Аналогічно, кількість обернених по модулю 13 матриць (тобто Порядок GL (n,Z₁₃)) рівно

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

Кількість обернених по модулю 26 матриць дорівнює добутку цих двох чисел. значить,

$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}).$

Крім того, буде розумно уникати занадто великої кількості нулів у матриці-ключі, оскільки вони зменшують дифузію. У підсумку виходить, що ефективний простір ключів стандартного шифру Гілла становить близько $4.64n^{2}-1.7$. Для шифру Гілла 5 × 5 це складе приблизно 114 біт. Очевидно, повний перебір — не найефективніша атака на шифр Гілла.

Механічна реалізація

При роботі з двома символами за раз, шифр Гілла не надає ніяких конкретних переваг перед шифром Плейфера, і навіть поступається йому за криптостійкістю і простоті обчислень на папері. У міру збільшення розмірності ключа шифр швидко стає недоступним для розрахунків на папері людиною. Шифр Гілла розмірності 6 був реалізований механічно. Гілл з партнером отримали патент на цей пристрій (U.S. Patent 1,845,947), які виконувало множення матриці 6 × 6 по модулю 26 за допомогою системи шестерень і ланцюгів. Розташування шестерень (а значить і ключ) не можна було змінювати для конкретного пристрою, тому з метою безпеки рекомендувалося потрійне шифрування. Така комбінація була дуже сильною для 1929 року, і вона показує, що Гілл безсумнівно розумів концепції конфузії і дифузії. Його машина не мала успіху.