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


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

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

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

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


1.1.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

1.1.2. Російський алфавіт [3]

Ідею формування таблиці шифрування проілюструємо для російської мови. Число букв в російській алфавіті відрізняється від числа букв у грецькому алфавіті, тому розмір таблиці вибрано інший (квадрат 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 Щ И Ь / виданню Е Ю Я

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


Або є такий варіант: Шифр ​​"Квадрат Полібія".

"Квадрат Полібія" являє собою квадрат 5x5, стовпці і рядки якого нумеруються цифрами від 1 до 5. В кожну клітину цього квадрата записується одна буква (в нашому алфавіті 31 літера, виданню і Е виключені, крім того в одну клітку помістіть букви е-е, і-й, ж-з, р-с, ф-х, ш-щ ). Букви розташовані в алфавітному порядку. В результаті кожній букві відповідає пара чисел, і шифрування повідомлення перетворюється в послідовність пар чисел. Розшифровується шляхом знаходження букви стоїть на перетині рядка і стовпця.


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

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

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

1.2.1. Метод 1

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

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

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

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

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

1.2.2. Метод 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

1.2.3. Метод 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

2. Додавання ключа [4]

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

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

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

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

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

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


2.1. Приклад

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

3. Історична довідка [5]

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

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

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

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

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


4. Стійкість до криптоаналіз [8]

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


Примітки

  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. Антонов А. К., Артюшенко В. М. Захист інформації. Методи захисту інформації. Ч.1.: Курс лекцій / М.: ГОУВПО МГУС, 2005-191 с.
  4. Баричев С. Г. Основи сучасної криптографії. М.: Гаряча Лінія - Телекому, 2001. 152 стр.
  5. Астрахан В. І., Гусєв В. В., Павлов В. В., Чернявський Б. Г. Становлення та розвиток урядового зв'язку в Росії, Орел: ВІПС, 1996.
  6. Дільс Г. Антична техніка. Під ред. С. І. Ковальова. М. - Л., Гостехиздат, 1934
  7. Полібій. Загальна історія в сорока книгах. Пер. з грец. Ф. Г. Міщенко. Т. 2, М., 1895, с. 282-284.
  8. Варфоломєєв О. О., Жуков А. Є., Пудовкіна М. А. Потокові крипто-системи. Основні властивості та методи аналізу стійкості. М.: "ПАИМС". 2000.