Квадрат Полібія

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку

У криптографії квадрат Полібія (англ. Polybius square), також відомий як шахова дошка Полібія — оригінальний код простої заміни, одна з найдавніших систем кодування, запропонована Полібієм (грецький історик, полководець, державний діяч, III століття до н. е.). Цей спосіб кодування спочатку застосовувався для грецької абетки[1], але потім поширився на інші мови.

Спосіб шифрування

[ред. | ред. код]

Квадрат спочатку створювався для кодування, з його допомогою можна успішно шифрувати. Для того, щоб зашифрувати текст квадратом Полібія, потрібно зробити кілька кроків:

Крок 1: Формування таблиці шифрування[2]

[ред. | ред. код]

До кожної мови окремо складається таблиця шифрування з однаковою (не обов'язково) кількістю пронумерованих рядків та стовпців, параметри якої залежать від її потужності (кількості букв в абетці). Беруться два цілих числа, добуток яких найближче до кількості букв у мові — отримуємо потрібну кількість рядків і стовпців. Потім вписуємо в таблицю всі букви алфавіту поспіль — по одній на кожну клітину. При нестачі клітин можна вписати в одну дві букви (рідко вживані або схожі за вживанням).

Латинський алфавіт

[ред. | ред. код]

У сучасній латинській абетці 26 букв, отже таблиця повинна складатися з 5 рядків і 5 стовпців, оскільки 25=5*5 найбільш близьке до 26 число. При цьому літери I, J не розрізняються (J ототожнюється з буквою I), оскільки не вистачає 1 чарунки:

1 2 3 4 5
1 A B C D E
2 F G H I/J K
3 L M N O P
4 Q R S T U
5 V W X Y Z

Українська абетка

[ред. | ред. код]

Ідею формування таблиці шифрування проілюструємо для української мови. Число букв в українській абетці відрізняється від числа букв у грецькій абетці, тому розмір таблиці вибрано інший (квадрат 6*6=36, оскільки 36 найбільш близьке число до 33) :

1 2 3 4 5 6
1 А Б В Г Ґ Д
2 Е Є Ж З И І
3 Ї Й К Л М Н
4 О П Р С Т У
5 Ф Х Ц Ч Ш Щ
6 Ю Я Ь

Можливий також інший варіант складання, що передбачає об'єднання букв Г і Ґ, И і Й, видання І і Ї. В даному випадку отримуємо такий результат:

1 2 3 4 5 6
1 А Б В Г/Ґ Д Е
2 Є Ж З И/Й І/Ї К
3 Л М Н О П Р
4 С Т У Ф Х Ц
5 Ч Ш Щ Ю Я Ь

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

Крок 2: Принцип шифрування

[ред. | ред. код]

Існує кілька методів шифрування з допомогою квадрата Полібія. Нижче наведено три з них.

Метод 1

[ред. | ред. код]

Зашифруємо слово «SOMETEXT»:

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

Таблиця координат
Буква тексту: S O M E T E X T
Буква шифротексту: X T R K Y K C Y

Таким чином після шифрування отримуємо:

Результат
До шифрування: SOMETEXT
Після шифрування: XTRKYKCY

Метод 2

[ред. | ред. код]

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

Таблиця координат
Буква: S O M E T E X T
Координата горизонтальна: 3 4 2 5 4 5 3 4
Координата вертикальна: 4 3 3 1 4 1 5 4

Потім координати зчитують по рядках: 34 25 45 34 43 31 41 54 (*)

Далі координати перетворюються в літери з цього ж квадрату:

Таблиця координат
Координата горизонтальна: 3 2 4 3 4 3 4 5
Координата вертикальна: 4 5 5 4 3 1 1 4
Буква: S W Y S O C D U

Таким чином після шифрування отримуємо:

Результат
До шифрування: SOMETEXT
Після шифрування: SWYSOCDU

Метод 3

[ред. | ред. код]

Ускладнений варіант, який полягає в наступному: отриманий первинний шифротекст (*) шифрується вдруге. При цьому він виписується без розбиття на пари: 3425453443314154 Отримана послідовність цифр зсувається циклічно вліво на один крок (непарна кількість кроків) : 4254534433141543 Ця послідовність знову розбивається в групи по два: 42 54 53 44 33 14 15 43

і за таблицею замінюється на остаточний шифротекст:

Таблиця координат
Координата горизонтальна: 4 5 5 4 3 1 1 4
Координата вертикальна: 2 4 3 4 3 4 5 3
Буква: I U P T N Q V O

Таким чином після шифрування отримуємо:

Результат
До шифрування: SOMETEXT
Після шифрування: IUPTNQVO

Додавання ключа[3]

[ред. | ред. код]

На перший погляд шифр здається дуже нестійким, але для його реальної оцінки слід враховувати два фактори:

  1. Можливість заповнити квадрат Полібія буквами довільно, а не тільки строго за алфавітом;
  2. можливість періодично замінювати квадрати.

Тоді розбір попередніх повідомлень нічого не дає, оскільки до моменту розкриття шифру він може бути замінений.

Букви можуть вписуватися в таблицю в довільному порядку — заповнення таблиці в цьому випадку і є ключем. Для латинської абетки в першу клітку можна вписати одну з 25 букв, у другу — одну з 24, в третю — одну з 23 і т. д. Отримуємо максимальну кількість ключів для шифру на таблиці латинської абетки:

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

Приклад

[ред. | ред. код]

Зашифруємо слово «SOMETEXT», використовуючи ключ «DRAFT». Складемо попередньо таблицю шифрування з даним ключем, записуючи символи ключа по порядку в таблицю, після них решту абетки:

1 2 3 4 5
1 D R A F T
2 B C E G H
3 I K L M N
4 O P Q S U
5 V W X Y Z

Перетворимо повідомлення в координати по квадрату Полібія:

Таблиця координат
Буква: S O M E T E X T
Координата горизонтальна: 4 1 4 3 5 3 3 5
Координата вертикальна: 4 4 3 2 1 2 5 1

Рахуємо координати по рядках: 41 43 53 35 44 32 12 51

Перетворимо координати в літери з цього ж квадрату:

Таблиця координат
Координата горизонтальна: 4 4 5 3 4 3 1 5
Координата вертикальна: 1 3 3 5 4 2 2 1
Буква: F M N X S E B T

Таким чином після шифрування отримуємо:

Результат
До шифрування: SOMETEXT
Після шифрування: FMNXSEBT

Історична довідка[4]

[ред. | ред. код]

Ще в далекій давнині у людини виникла необхідність передачі сигналів на відстань. Для посилення голосу при подачі сигналів на полюванні стали застосовувати найпростіші рупори у вигляді рогів, раковин та ін. Цілями подачі служили тамтами, барабани і подібні їм пристрої, а трохи пізніше світлові засоби — смолоскипи, багаття. Навіть ці примітивні предмети світлової сигналізації дозволили різко збільшити відстань, на якому людям вдавалося підтримувати зв'язок.[5]

З розвитком суспільства виникла необхідність у передачі різноманітніших сигналів, в тому числі сигналів, зміст яких не був обумовлений заздалегідь. У книзі Полібія описаний спосіб[6] застосування водяних годинників, так званих клепсидр, у пристрої для далекої сигналізації. Клепсидри являли собою посудини з водою, на поверхні якої знаходилися поплавці з вертикальними стійками на них. Вода з посудин витікала з постійною швидкістю, і вони довжина видимої частини стійок була обернено пропорційна часу. Суть використання клепсидр для сигналізації полягала в тому, що їх вертикальні стійки мали однотипну розмітку: замість часових поділок на них були написані в однаковій послідовності різні слова, команди і т. ін. За умовного сигналу з передавального пункту обидві клепсидри одночасно запускалися, а з іншого сигналу зупинялися в той момент, коли на стійках була видно напис, яку потрібно було передати. Оскільки клепсидри були достатньо точними годинниками, то на передавальному і на приймальному пунктах вони показували один і той самий сигнал. У цьому способі зв'язку дальність визначалася умовами видимості сигналів, які могли подаватися будь-якими іншими відомими тоді сигнальними засобами.

Це був, мабуть, перший спосіб зв'язку з використанням технічних засобів (клепсидр), заснований на застосуванні принципу синхронізації приладів у часі.

Полібій описує також і другий спосіб сигналізації, заснований на іншому принципі, винахід якого він пов'язує з іменами Клеоксена і Демокліта з Александрії. За цим способом для сигналізації використовували смолоскипи, які виставляли на сигнальної стіні. При цьому існував певний код, складений наступним чином. Грецький алфавіт (24 букви) поділяли на 5 груп таким чином, що кожна буква визначалася номером групи та порядковим номером її в групі. Число смолоскипів в лівій частині сигнальної стіни означало номер групи, а число смолоскипів в правій частині стіни — номер місця в групі. Такий спосіб, хоча і вимагав багато часу на передачу кожного сигналу, однак давав можливість передавати буквеним текстом будь комюніке. Полібій, описуючи цей спосіб, як раз наводив таблицю такого коду (таблиця Полібія), яка розглядається в статті, в подальшому знайшла застосування в багатьох системах сигналізації. Це, мабуть, була одна з перших спроб використовувати код (п'ятірковий дворозрядний) для передачі інформації.

Цікаво зауважити, що в дещо зміненому вигляді код Полібія дійшов до наших днів і отримав цікаву назву «тюремний шифр». Для його застосування необхідно знати лише природний порядок розташування букв в абетці (як в зазначених вище прикладах для латинської та української абеток). Число 3, наприклад, передавалося шляхом триразового стуку. При передачі літери спершу відстукують число, відповідне рядку, в якому розташовувалася буква, а потім номер стовпця. Наприклад, літера «H» передавалася дворазовим стуком (другий рядок), а потім триразовим (третій стовпець). Достеменно відомо, що декабристи, ув'язнені після невдалого повстання 1825 року, не могли встановити зв'язок з Петропавлівської фортеці князем Одоєвським, що перебував в одиночній камері. Виявилося, що він не пам'ятав природний порядок розташування літер в російській і французькій абетках (іншими мовами він не володів). Декабристи для російської абетки використовували прямокутник розміру 5x6 і стиснутий до 30 букв алфавіт. Тому «Тюремний шифр», строго кажучи, не шифр, а спосіб модифікації повідомлення з метою його приведення до вигляду, зручному для передачі по каналу зв'язку (через стінку).

Стійкість до криптоаналізу[7]

[ред. | ред. код]

Одним з методів атак є частотний аналіз. Розподіл букв у криптотексті порівнюється з розподілом літер в абетці вихідного повідомлення. Букви з найбільшою частотою в криптотексті замінюються на букву з найбільшою частотою з абетки, якщо він відомий. Імовірність успішного розкриття підвищується із збільшенням довжини кріптотекста, оскільки розподіли статистичні. Існують безліч різних таблиць про розподіл букв в тій чи іншій мові, але жодна з них не містить остаточної інформації — навіть порядок букв може відрізнятися в різних таблицях. Розподіл дуже сильно залежить від типу тесту: проза, розмовна мова, технічну мову і т. ін. Квадрат Полібія є прикладом шифру заміни, тому нестійкий до частотної атаки.

Примітки

[ред. | ред. код]
  1. УДК 511 Коробейников А. Г, Ю. А. Гатчині. Математичні основи криптології. Навчальний посібник. СПб: СПб ГУ ІТМО, 2004.-106 с, іл. Ліцензія ВД в„– 00408 від 05.11.99
  2. Kahn D. The Codebreakers; The Comprehensive History of Secret Communication from Ancient Times to the Internet, N-Y: Macmillan Publ. Co. 1996.
  3. Баричев С. Г. Основи сучасної криптографії. М.: Гаряча Лінія — Телеком, 2001. 152 стр.
  4. Астрахан В. І., Гусєв В. В., Павлов В. В., Чернявський Б. Г. Становлення та розвиток урядового зв'язку в Росії, Орел: Віпс, 1996.
  5. Дільс Г. Антична техніка. Під ред. С. І. Ковальова. М. — Л., Гостехиздат, 1934
  6. Полібій. Загальна історія в сорока книгах. Пер. з грец. Ф. Г. Міщенко. Т. 2, М., 1895, з. 282—284.
  7. Варфоломєєв А. А., Жуков А. Е., Пудовкіна М. А. Потокові крипто- системи. Основні властивості та методи аналізу стійкості. М.: «ПАИМС». 2000.

Посилання

[ред. | ред. код]