Шифр Хілла – поліграмний шифр підстановки» для корпоративного доданку

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

Криптоаналіз тільки для зашифрованого шифрами Хілла тексту важкий. По-перше, атака грубої сили при шифрі Хілла надзвичайно складна, тому що матриця-ключ - . Кожен вхід може мати одно з 26 значень. По-перше, це означає розмір ключа  . Проте, не усі матриці мають мультиплікативну інверсію. Тому область існування ключів все ж не така величезна.

По-друге, шифри Хилла не зберігають статистику звичайного тексту. Неможливо провести аналіз частоти окремих букв з двох або трьох букв. Аналіз частоти слів розміру m міг би cработать, але дуже рідко початковий текст має багато однакових рядків розміру m. Можна провести атаку на шифр, використовуючи метод знання початкового тексту, якщо знати значення m і пари «початковий текст/зашифрований текст», принаймні m блоків. Блоки можуть належати тому ж самому повідомленню або різним повідомленням, але мають бути різні. Тому можна створити дві   матриці, P (звичайний текст) і C (зашифрований текст), в якому відповідні рядки представляють відомі пари звичайного/зашифрованого тексту. Оскільки C = PK, можна використати стосунки K = CP – 1, щоб знайти ключ, якщо P є оборотним. Якщо P не є оборотним, то повинно бути задіяно різні набори m пар звичайного/зашифрованого тексту.

Якщо не відоме значення m, можна спробувати різні значення за умови, що m не є дуже великим.

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

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

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

Крім того, буде розумно уникати занадто великої кількості нулів в матриці-ключі, оскільки вони зменшують дифузію. У результаті виходить, що ефективний простір ключів стандартного шифру Хілла складає близько 4. 64n2 − 1. 7. Для шифру Хилла 5 × 5 це складе приблизно 114 біт. Очевидно, повний перебір – не найефективніша атака на шифр Хілла [4].  

 

 

При запуску програми відкривається вікно, яке має вигляд:

 

Робота з інтерфейсом програми відбувається по наступному алгоритму:

• введення даних для зашифровування;
• знаходження ключа;
• розшифрування і отримання початкового тексту.

При запуску програми в полі тексту треба ввести повідомлення, яке треба зашифрувати. Текст можна завантажити з файлу натисненням кнопки «Завантажити». Поле «Ключ» містить ключ за умовчанням – криптолог.

Наступним блоком роботи програми є демонстрація зашифровування. Зашифровування виконується натисненням кнопки «Розшифрувати». Кожному символу початкового тексту зіставляється його порядний номер за алфавітом. Текст (вже представлений цифрами) розбивається на блоки по три символи (оскільки квадратна матриця ключа має розмірність 3*3) і записується послідовно по рядках в матрицю. Тобто кожен рядок представлятиме блок тексту. Кожен з таких блоків множиться на квадратну матрицю ключа, і ми отримуємо нову матрицю. Щоб замінити цифри символами назад і отримати шифротекст необхідно кожен елемент матриці розділити по модулю розмірності використовуваного алфавіту. Після цього отримаємо нову матрицю з номерами символів від 0 до 54 (алфавіт містить 55 символів). Кожна комірка матриці переводиться в символ згідно з порядковим номером її значення в алфавіті. Отриманий зашифрований текст відображається в новому полі.

Потім необхідно знайти ключ. Для цього треба клікнути по кнопці «Знайти ключ». Щоб знайти ключ необхідно знайти зворотну матрицю від матриці відкритого тексту і помножити її на матрицю шифротекста. Ми припускаємо, що вдається перехопити декілька блоків відкритого тексту, знаходимо детермінант такої матриці і будуємо транспоновану матрицю з доповнень алгебри кожного елементу. Якщо цю матрицю (транспоновану) розділити на детермінант матриці з блоків відкритого тексту і помножити на матрицю тієї ж розмірності шифротекста, ми отримаємо квадратну матрицю ключа. Після описаних дій на панель виводиться ключ згідно з цифрами в отриманій матриці.

Наступним етапом є розшифровка тексту, кнопка «Розшифрувати». Для цього множимо матрицю шифротекста на зворотну ключу матрицю, яку представляє транспонована матриця з доповнень алгебри кожного елементу цієї матриці, розділеної на її детермінант. Після виконання цих дій можна замінити цифри отриманоі при множенні матриці на символи з алфавіту і вивести расшифрованый текст.

При демонстрації програми, ми додамо текст із файла, зашифруемо текст, знайдемо ключ та розшифруемо текст:

 

Повний код програми поданий у додатку А.  

 

 

В процесі виконання роботи ми детальніше ознайомилися з методом шифрування Хілла, його програмною реалізацією. В порівнянні з деякими алгоритмами цей метод має хорошу криптостоійкість. Він не піддається взлому методом частотного аналізу. Але він має також і свої недоліки. Стандартний шифр Хілла уразливий до атаки за вибраним відкритим текстом, тому що він повністю лінійний. Перехопивши декілька пар символ повідомлення/символ шифротекста можна скласти систему лінійних рівнянь, яку можливо вирішити. Якщо виявиться, що система не вирішувана, то необхідно усього лише додати ще декілька пар символ повідомлення/символ шифротекста.

 

 

1. Основи криптографії: Навчальний посібник [Текст] / [Алфьоров А. П., Зубов А. Ю., Кузьмін А. С., Черьомушкін А. В. ] – М. : 2005. – 480 с.
2. Криптографічні засоби захисту інформації. – [ Електроний ресурс ] – Режим доступу:
3. http: //ua-referat. com/Криптографічні_засоби_захисту_інформації.
4. Шифр Хилла. – [ Електроний ресурс ] – Режим доступу:
5. http: //kriptografea. narod. ru/Hill. html
6. Разработка программы «Шифр Хилла». – [ Електроний ресурс ] – Режим доступу: http: //docus. me/d/414555/
7. Ященко В. В. Введення в криптографію [Текст] / Ященко В. В. – М. : 2000. -288 с.
8. Нечаєв В. І. Елементи криптографії (Основи теорії захисту інформації) [Текст] / Нечаєв В. І. – М. : Вищ. шк., 1999 – 109 с.
9. Архангельский А. Я. Delphi 2006. Справочное пособие [Текст] / Архангельский А. Я. – М. : – Бином-Пресс, 2006. -ISBN 5-9518-0138-9. -1152 c.
10. Галисеев Г. В. Компоненты в Delphi 7. Профессиональная работа [Текст] / Галисеев Г. В. – М. : Диалетика, 2004. – ISBN 5-8459-0555-9. -624 c.
11. Шифр Хілла. – [Електроний ресурс] – Режим доступу: https: //ru. wikipedia. org/wiki/Шифр_Хілла