Шифр Гілла

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

Шифрування

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

У наступних прикладах використовуються латинські літери від 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 в буквеному вигляді):

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

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

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

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

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

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

Для того, щоб розшифрувати повідомлення, необхідно звернути шифротекст назад в вектор і потім просто помножити на зворотню матрицю ключа (IFKVIVVMI в буквеному вигляді). (Існують стандартні методи обчислення зворотніх матриць, дивіться способи знаходження Оберненої матриці для подробиць.) В зворотна матриця до використаної в прикладі шифрування буде

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Примітки

    This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.