Лабораторна робота 3 Шифри Кардано і Ардженті

2. Опис методів шифрування

1.1. Шифр на основі поворотної решітки (XVI вік). Ідея поворотної решітки як засобу шифрування належить італійському математику Д. Кардано. Така решітка – це квадрат розміру (в якості значення обирається парне число, хоча це – необов’язкова вимога), в якому так вирізані квадратики розміру , що при поворотах решітки на кут кожна клітка квадрату розміру виявлялася під вирізом не більше одного разу. Для того, щоб забезпечити однозначність процесу перетворення інформації один з боків поворотної решітки позначався. Вихідним положенням решітки вважалось таке, при якому позначений бік мав фіксоване розташування (наприклад, внизу). Шифрування здійснювалось в такий спосіб. Решітка накладалася у вихідному положенні на аркуш паперу. В вирізи послідовно, літера за літерою, вписувалась інформація, яку необхідно передати адресату. Після заповнення всіх вирізів, решітка поверталася на кут (для забезпечення однозначності процесу перетворення інформації напрям повороту заздалегідь обговорювався відправником і адресатом) і описана процедура повторювалась. Після 3-х поворотів решітка знімалася і незаповнені позиції (якщо такі були) квадрату розміру заповнювались довільними символами алфавіту, який використовувався. Якщо місця для запису інформації не вистачало, то решітка накладалася на нове місце аркушу (поруч або нижче), і описана вище процедура повторювалась. Якщо при заповненні останнього квадрату розміру вся інформація виявлялась записаною, але не всі вирізи в решітці були повністю використані, то в вільні позиції записувалась заздалегідь обговорена послідовність символів алфавіту. Така послідовність грає рольфінального маркера, що фіксує закінчення інформаційної послідовності. Отриманий шифротекст відправлявся адресату. Адресат, що мав трафарет, повторював всі дії відправника з тією різницею, що замість «запису» інформації здійснював її «зчитування».

Приклад 3.1. В якості засобу шифрування обрана поворотна решітка розміру 4×4, зображена на рис. 3.1.а. В якості фінального маркера з послідовності АБВГДЕЖЗИЙКЛМНО, обирається початковий відрізок, що має довжину, необхідну для заповнення всіх вирізів, які не були використані. На рис. 3.1.б наведений шифротекст фрази:

МАТЕМАТИКА_–_ЭТО_“ГИМНАСТИКА”_УМА!

Рисунок 3.1. Шифр на основі поворотної решітки: а) поворотна решітка розміру

4×4 (Вирізані квадратики − заштриховані клітки); б) шифротекст.

Поворотна решітка розміру – повна, якщо після обробки за її допомогою квадрату розміру відсутні незаповнені позиції, якщо – парне число і є в точності одна незаповнена позиція, що розташована в центрі квадрату, якщо– непарне число.

Теорема 3.1. Кількість повних поворотних решіток розміру дорівнює

. (3.1)

Доведення. Зафіксуємо число . Розіб’ємо множину всіх кліток квадрату розміру на блоків так, що будь-який блок переходить на себе при повороті квадрату на кут . Знайдемо значення :

;

.

Повна поворотна решітка розміру характеризується тим, що:

1. в кожному 4-х елементному блоці вирізається в точності одна клітка;

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

Кількість способів вибору клітки, що вирізається у фіксованому блоці дорівнює 4. А оскільки вибір кліток, що вирізаються, в різних блоках здійснюється незалежно, то

,

,

звідки і витікає дійсність рівності (3.1).

Теорема доведена.

1.2. Шифр Ардженті (XVII вік). Заснований на таблиці Ардженті. В ній вперше були вдало сполучені наступні три ідеї:

1. для символів вихідного алфавіту, які найчастіше зустрічаються, використовувалось декілька шифр-позначень (що робило частотний аналіз шифротексту практично нездійсненим);

2. використовувались шифр-позначення різної довжини;

3. шифр-позначення застосовувались для сполучень літер, складів і цілих фраз, які часто зустрічались.

В результаті реалізації останньої ідеї «алфавіт» , що нумерував стовпці таблиці Ардженті, містив близько 1200 символів.

Шифрування здійснювалось за допомогою послідовної заміни кожного символу повідомлення будь-яким його шифр-позначенням. Такий підхід приводить до неоднозначності шифрування, оскільки для одного і того ж повідомлення можуть бути отримані різні шифротексти, причому різної довжини. Однак така неоднозначність не впливає ні на коректність, ні на складність процесу розшифровки. Адресат послідовно проглядав шифротекст, здійснюючи пошук чергового фрагменту в стовпцях таблиці Ардженті. Виявивши такий фрагмент, він замінював його символом , який нумерує цей стовпець.

Приклад 3.2. Таблиця 3.1 – це варіант таблиці Ардженті для російської мови.

Таблиця 3.1 (початок)

Таблиця 3.1 (закінчення)

Скористаємося цією таблицею і зашифруємо двома способами фразу:

МАТЕМАТИКА_–_ЭТО_“ГИМНАСТИКА”_УМА!

Спосіб 1.Послідовно шифруємо кожний символ. Отримаємо шифр текст: