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