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

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

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

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

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

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

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

У сучасній латинській абетці 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

Додавання ключа

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

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

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

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

$N=25*24*23*...*2*1=25!$

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

Приклад

Зашифруємо слово «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

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

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

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

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

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

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

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

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

Посилання

• Шифри Древности [Архівовано 13 Жовтня 2012 у Wayback Machine.] (рос.)
• Шифрування. Шифри заміни [Архівовано 8 Травня 2016 у Wayback Machine.] (рос.)
• Онлайн кодувальник квадратом Полібія [Архівовано 30 Квітня 2020 у Wayback Machine.] (англ.)