Європейська криптологія

Європейська криптологія

Історія спецзв'язку

Вадим Гребенніков

© Вадим Гребенніков, 2018

ISBN 978-5-4493-0715-6

Создано в интеллектуальной издательской системе Ridero

1. Поява шифрів

Взагалі всі шифри можуть бути розділені на два види: перестановка й заміна. При перестановці букви повідомлення просто переставляються, утворюючи анаграму. Для дуже короткого повідомлення, що складається, наприклад, з одного слова, такий спосіб досить ненадійний, оскільки існує вкрай обмежене число можливих способів перестановки жменьки букв. Так, 3 букви можуть бути розставлені всього лише 6 різними способами. Однак у міру збільшення чисельності букв кількість можливих перестановок стрімко зростає, і відновити вихідне повідомлення стає неможливо, якщо невідомий точний спосіб шифрування. Наприклад, якщо фраза складається з 35 букв, то кількість їхніх різних перестановок становить більше 50 000 000 000 000 000 000 000 000 000 000.

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

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

Першим шифрувальним пристроєм, який дійшов до нас та реалізовував шифр перестановки, була так звана «скитала» або «сцитала» (близько VI—V ст. до н.е.), що використовувалась в античний період спартанцями.

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

У 404 році до н.е. до спартанського полководця Лісандра привели вісника, який був закривавлений та ледве тримався на ногах, одного з 5-ти вісників, що залишився живим після вкрай небезпечної подорожі з Персії. Вісник передав свій пояс Лісандру, що намотав його навколо своєї скитали й прочитав, що перський воєначальник Фарнабаз збирається напасти на нього. Завдяки скиталі Лісандр встиг підготуватися до нападу й відбив його.

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

Це те ж саме, начебто букви писати не підряд, а через домовлене число по кільцю доти, поки весь текст не закінчиться. Повідомлення «ВИСТУПАЙТЕ» при окружності палички в 3 букви дасть шифровку «ВУТИПЕСАТЙ».

Для прочитання шифровки потрібно було не тільки знати систему засекречування, але й мати ключ у вигляді палички визначеного діаметра. Знаючи тип шифру, але не маючи ключа, розшифрувати повідомлення було би складно. Шифр був досить популярний у Спарті й багато разів удосконалювався в пізніші часи. Про його важливе значення й велике поширення говорить свідчення Плутарха в «Порівняльних життєописах», коли історик повідомляє про життя грецького полководця Алкивіада: «Однак Лісандр звернув увагу на ці слова не раніше, ніж одержав з будинку скиталу з наказом відскіпатися від Алкивіада…»

Цей нехитрий спосіб часто використовувався через свою простоту та можливість оперативного розшифрування повідомлення. У той же час стійкість даного шифру була невелика, тому пізніше Архімед запропонував пристрій («антискитала»), за допомогою якого розшифровка подібного повідомлення без потрібного циліндра була досить простою та швидкою. Ремінь намотували на конічний «спис» і зрушували нагору й униз доти, поки не знаходили потрібний діаметр і текст повідомлення ставав зрозумілим.

Альтернативним шифру перестановки був шифр заміни, у якому кожна буква у вихідному тексті замінялася іншою буквою. Один з перших описів шифру заміни був приведений у «Камасутрі», тексті, написаному в 4-му столітті н.е. священиком-браміном Ватсьяяною, але заснованому на манускриптах, що відносяться до 4-го століття до н.е.

Згідно з «Камасутрою», жінки повинні опанувати 64 мистецтва, такі як готування їжі й напоїв, мистецтво одягання, масажу, готування ароматів. У цей список також входили менш очевидні мистецтва: чаклунство, гра в шахи, палітурна справа й теслярство. Під номером 45 у списку знаходилося мистецтво тайнопису «mlecchita-vikalpa», призначене для того, щоб допомогти жінкам приховати подробиці своїх любовних зв'язків.

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

D A M H I K O Z R S U W Y

X B T. V G J. C L N E Q F. P

Тоді замість слова «UKRAINE» відправник напише слово «QJNBGRS».

На Близькому Сході один з перших шифрів заміни був розроблений древніми євреями та називався «темура» – «обмін». 22 букви єврейського алфавіту ділилися на дві частини, причому одна містилася над іншою; потім верхні букви замінялися на нижні або навпаки. Можна було встановити всілякі комбінації залежно від місця поділу алфавіту й напрямку переміщуваних букв.

Найпростіший спосіб полягав у поділі алфавіту посередині так, щоб перші дві букви, «А» і «Б», збігалися із двома останніми, «Т» і «Ш». Ці букви й дали назву методу шифрування – «Атбаш» (англ. Atbash). Це був простий шифр одно-алфавітної заміни для єврейського алфавіту. Таблиця (лінійка) шифрування цим методом для латинського алфавіту буде виглядати таким чином:

A B C D. E F G H I. J. K L M N O P Q R S T U V W X Y Z

Z Y X W V U T S R Q P O N M L K J. I. H G F E D. C B A

Бачимо, що у цьому шифрі заміна має симетричний вигляд. Так, наприклад, слово «UZHGOROD» перетворювалося у слово «FASTLILW».

Інший шифр «Альбам» полягав у розбивці алфавіту на дві частини та розташуванні однієї частини під іншою:

A. B C D E F G H I..J. K L M

N O P Q R S T U V W X Y Z

Слово «UZHGOROD» перетворювалося вже у слово «HMUTBEBQ».

Перше документально підтверджене використання шифру заміни у військових цілях з'явилося у «Записках про галльську війну» (лат. Commentarii de Bello Gallico) Гая Юлія Цезаря (I століття до н.е.). Цезар описував, як він послав повідомлення Цицерону, що перебував в облозі та був на грані капітуляції. У цьому листі латинські букви були замінені грецькими, тому ворог його не зміг би зрозуміти.

Цезар так часто користувався тайнописом, що Марко Валерій Проб написав цілий трактат про застосовувані ним шифри, який, на жаль, не дійшов до наших днів. Однак завдяки твору Гая Транквілла Светонія «Життя 12 Цезарів», написаному в 2-му столітті н.е., у нас є докладний опис одного з шифрів заміни, що застосовувалися Юлієм Цезарем. Він просто заміняв кожну букву в посланні буквою, що знаходилась в алфавіті на три позиції далі.

Ось як про це повідомляє Гай Светоній: «Існують і його листи Цицерону та листи до близьких про домашні справи: у них, якщо потрібно було повідомити що-небудь негласно, він користувався тайнописом, тобто міняв букви так, щоб з них не складалося жодного слова. Щоб розібрати й прочитати їх, потрібно читати щоразу четверту букву замість першої».

A B C D E F G H I. J. K. L M N O P Q R S T. U V W X Y Z

D E F G H I. J. K L M N O P Q R S T U V W X Y Z. A B C

Спочатку виписувався алфавіт у природному порядку, а потім під ним виписувався той же алфавіт, але зі зрушенням на 3 букви вліво. При зашифруванні буква «А» замінялася буквою «D», «B» замінялася на «E», «C» – на «F» й так далі. Так, наприклад, слово «UZHGOROD» перетворювалося у шифротекст «XCKJRURG», а «UKRAINE» – у «XNUDLQH». Одержувач зашифрованого повідомлення шукав ці букви в нижньому рядку та по буквах над ними відновлював вихідне слово. Ключем у шифрі Цезаря була величина зрушення нижнього рядка алфавіту, тобто цифра 3. Спадкоємець Юлія Цезаря – Цезар Август – використовував той же шифр, але з ключем зрушення 4.

Вже у IV столітті до н.е. робилися спроби «механізації» криптологічної справи, пов'язані насамперед з ім'ям давньогрецького полководця Енея Тактики, захисника Трої, друга Гектора. Він створив так званий «диск Енея», що одержав у Давній Греції широке застосування. У диску діаметром 10—15 см і товщиною 1—2 см висвердлювалися отвори, що відповідали буквам алфавіту, через які просмикувалася нитка відповідно до букв шифрованого тексту. Для розшифрування нитку витягали, одержуючи зворотню послідовність букв. Цей примітивний на перший погляд спосіб шифрування був досить ефективний, тому що супротивнику, який перехопив повідомлення, було невідомо, яка буква відповідає кожному отвору. Крім того, якщо виникала небезпека перехоплення повідомлення, нитку можна було легко порвати, тим самим знищивши його.

Ідея Енея була використана при створенні й інших оригінальних шифрів заміни. Зокрема, в одному з варіантів замість диска використовувалася лінійка з кількістю отворів, рівних кількості букв алфавіту. Кожний отвір позначався своєю буквою, а букви по отворах розташовувалися в довільному порядку. До лінійки була прикріплена котушка з намотаною на неї ниткою. Поруч із котушкою був проріз. При шифруванні нитка простягалася через проріз, а потім через отвір, що відповідав першій букві шифрованого тексту, при цьому на нитці зав'язувався вузлик у місці проходження її через отвір. Потім нитка поверталася в проріз й аналогічно зашифровувалася друга буква тексту й т. д. Після закінчення шифрування нитка витягалася й передавалася одержувачу повідомлення. Той, маючи ідентичну лінійку, простягав нитку через проріз до отворів, обумовлених вузлами, і відновлював вихідний текст по буквах отворів.

Цей пристрій одержав назву «лінійка Енея». Шифр, реалізований лінійкою Енея, був одним з прикладів шифру заміни: коли букви замінялися на відстані між вузликами з урахуванням проходження через проріз. Ключем шифру був порядок розташування букв по отворах у лінійці. Супротивник, що одержав нитку (навіть, маючи лінійку, але без нанесених на ній букв), не міг прочитати передане повідомлення. Аналогічне «лінійці Енея» «вузелкове письмо» отримало поширення в індіанців Центральної Америки. Свої повідомлення вони також передавали у вигляді нитки, на якій зав'язувалися різнобарвні вузлики, що визначали зміст повідомлення.

Ще один винахід стародавніх греків – так званий «квадрат Полібія». Грецький письменник Полібій (біля 200 – 120 до н.е.) використовував систему сигналізації, що була широко прийнята як метод шифрування. Він записував букви грецького алфавіту в квадратну таблицю та заміняв їх числовими координатами в таблиці номером рядка та номером стовпця. Пари чисел передавалися за допомогою смолоскипів. У варіанті з латинським алфавітом для передачі, наприклад, букви «U» потрібно було взяти 4 смолоскипи в праву руку та 5 – у ліву, або записати як цифру «45» (див. таблицю).

Наприклад, слово «UKRAINE» можна записати як цифровий шифротекст «45254211243315» або «54522411423351».

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

Із застосуванням цього шифру пов'язані деякі історичні казуси. Так, російські «декабристы», які були ув'язнені після невдалого повстання, не змогли встановити зв'язок з князем Одоєвським. Виявилося, що він (добре освічений за тих часів) не пам'ятав природний порядок розташування букв у російському та французькому алфавітах (іншими мовами він не володів). «Декабристы» для російського алфавіту використовували прямокутник розміру 5x6 (5 рядків та 6 стовпців) і скорочений до 30 букв алфавіт.

Пізніше букви стали розташовувати в квадраті хаотично, але це вимагало наявність такого квадрата у отримувача повідомлення, що також було небезпечно. Вихід був знайдений у застосуванні так званого ключового слова, що легко запам'ятовувалося. Обиралося недовге слово (наприклад, «UKRAINE»), з нього забиралися букви, що повторювалтся, а ті, що залишалися, записувалися в перші клітини квадрата по рядках. Порожні клітини заповнювалися буквами алфавіту, що залишилися, у природному порядку (див. таблицю).

В результаті такого шифрування слово «UZHGOROD» перетворюється у цифровий шифротекст «11553332414125».

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

Ледащі й тому винахідливі римляни в IV столітті до н.е., щоб спростити процедуру шифрування, почали застосовувати два шифрувальні диски. Кожний із дисків, розміщених на загальної вісі, містив на своєму ободі алфавіт у випадковій послідовності. Кожній букві першого диска відповідала буква другого, що й становило шифр. Знайшовши на одному диску букву тексту, з іншого диска зчитували відповідну їй букву шифру. Такі прилади, що породжували шифр простої заміни, використовувалися аж до епохи Відродження.

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

Із занепадом античної цивілізації та утворенням у Європі варварських держав, криптологія занепала. Велика шкода її розвитку була завдана в часи середньовічної інквізиції. Всі кращі досягнення цивілізації, а разом з ними й криптологія, були втрачені. За свідченням святого Джерома «увесь світ поринув у руїни». В умовах, коли грамотність була вкрай низька, зашифровувати повідомлення не було необхідності, тому й самих письмових повідомлень практично не було.

Так, король франків Карл Великий, засновавший у 800 році Священну Римську імперію, навчився читати й писати тільки у 50 років. Проте Карл Великий знав і використовував у листуванні зі своїми генералами шифр заміни букв алфавіту групою символів.

Освіта й грамотність у ті часи зосередилися в церкві, тому тайнопис став її монополією. Церква ухвалила, що простим парафіянам не можна приховувати таємниці від «Господа», а тайнопис – це «єресь». За використання тайнопису передбачалися жорстокі заходи покарання, аж до страти.

Крім вищеперерахованих причин, криптологія перебувала в занепаді ще й тому, що в ній бачили елементи чаклунства. Набір незрозумілих букв або символів, сам по собі схожий на заклинання, сприймався як щось магічне, а люди, що розуміли у цьому наборі символів зміст, розцінювалися як чаклуни або ворожки, що не могло не накласти свій відбиток на ставлення до них у християнській Європі.

З перших днів свого існування криптологія мала на меті сховати зміст важливих розділів письмових документів, що мали відношення до таких сфер магії, як гадання й заклинання. В одному з рукописів про магію, що датується III століттям н.е., був використаний шифр, щоб сховати важливі частини чаклунських рецептів. Криптографія часто була на службі магії в часи середньовіччя, і навіть в епоху Відродження за допомогою шифрів алхіміки засекречували важливі частини формул одержання «філософського каменя».

До шифрування інформації «призивалися» містичні сили. Так, наприклад, рекомендувалося використовувати «магічні квадрати». У квадрат розміром 4 х 4 вписувалися числа від 1 до 16. Його магія полягала в тому, що сума чисел по рядках, стовпцях і діагоналях дорівнювала одному й тому ж числу – 34. Уперше ці квадрати з'явилися в Китаї, де їм і була приписана деяка «магічна сила» (див. таблицю).

Для зашифрування слова «ЗАКАРПАТТЯ» букви вписувалися послідовно до квадрату згідно з записаними в них цифрами, а до пустих клітинок вписувалися будь-які букви (див. таблицю).

Після цього букви записувалися у рядок і отримувався такий шифротекст: ЖКАГРЯБТТПАВАЕДЗ. Даний шифр – це звичайний шифр перестановки, але вважалося, що особливу стійкість йому надають чари «магічного квадрата».

На перший погляд здається, начебто магічних квадратів дуже мало. Проте їхнє число дуже швидко зростає зі збільшенням розміру квадрата. Так, існує лише один магічний квадрат розміром 3х3, якщо не брати до уваги його повороти. Магічних квадратів 4х4 налічується вже 880, а число магічних квадратів розміром 5х5 близько 250000. Тому магічні квадрати більших розмірів могли бути гарною основою для надійної системи шифрування того часу, тому що ручний перебір всіх варіантів ключа для цього шифру був немислимий.

Подібність між магією та криптологією обумовлювалася й іншими факторами. Крім криптології, таємничі символи використовувалися в зрозумілих лише присвяченим сферах магічних знань – астрологія та алхімія, де подібно знакам відкритого тексту, кожна планета й кожна хімічна речовина мали спеціальний знак. Як і зашифровані слова, заклинання й магічні формули, начебто «абракадабри», нагадували нісенітницю, але в дійсності мали важливе значення.

Те, що писали або малювали астрологи та маги, було схоже на кодограму, де кожний символ або ієрогліф мав своє особисте як екзотеричне (матеріальне), так і езотеричне (духовне) значення. Наприклад, символ Сонця – це індивідуальність та духовність, Місяця – м'якість та душевність, Меркурія – мислення та інтелектуальність, Венери – жіночість та кохання, Марса – мужність та активність, Юпітера – законослухняність та релігійність, Сатурна – самотність та цілеспрямованість тощо. Навіть місця символів, де вони були намальовані, теж визначали їх вплив на події життя та взаємовідносини з іншими чинниками долі. А те, що одним малюнком (гороскопом) можна відобразити долю та все життя людини або країни, здавалося справжньою магією чи чаклунством.

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

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

В середньовічному Китаї у трактаті «Основи класичної військової науки», складеному в XI столітті нашої ери, були присутні лише кодувальні рекомендації. В них рекомендувалося співвіднести з різними простими повідомленнями перші 40 знаків якого-небудь вірша, відомого як відправнику, так і одержувачу. По першому знаку вірша, поставленому в домовленому місці цілком безневинного повідомлення, одержувач «зчитував» інформацію, наприклад, що потрібно послати більше провіанту. Такі коди практично не піддавалися розшифруванню, але вони могли використовуватися лише в дуже обмеженому масштабі.

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

У XVIII столітті франкмасонами використовувався для забезпечення таємності своїх документів так називаний шифр «Pigpen». У ньому кожна буква замінялася визначеним символом таким чином: щоб зашифрувати букву, визначалося її місцезнаходження в одній з чотирьох сіток, а потім малювалася та частина сітки, що відповідала цій букві.

2. Становлення криптології як науки

В арабському світі криптологія не тільки не занепала, але продовжувала успішно розвиватися, досягши значних успіхів. Про тайнопис і його значення говорилося навіть у казках «Тисячі й однієї ночі». У 855 році арабський письменник, алхімік і єгиптолог Абу Бакр Ахмед ібн Вахш (Ахмад Бін Абубекр Бін Вахіші) описав відомі йому класичні шифралфавіти у своїй «Книзі про велике прагнення людини розгадати загадки давньої писемності» (араб. Kitab Shawq al-Mustaham). Видання арабського тексту з англійським перекладом з'явилося лише у 1806 році.

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

Крім того, найбільш ранній із відомих описів методу використання частоти появи букв з метою «злому» шифрів належав перу арабського вченого Абу Юсуф Якуб ібн Ісхак ібн Сабах аль-Кінді (біля 800—879) та датований приблизно 850 роком. Відомий як «філософ арабського світу», аль-Кінді був автором 290 книг з медицини, астрономії, математики, лінгвістики й музики. Його найзнаменитіший трактат, що був виявлений заново лише у 1987 році в оттоманському архіві Сулайманія в Стамбулі, називався «Трактат про дешифрування криптографічних повідомлень аль-Кінді». Хоча в ньому був викладений докладний аналіз статистики, фонетики й синтаксису арабської мови, революційна система криптоаналізу аль-Кінді вміщається у два короткі абзаци:

«Один із способів прочитати зашифроване повідомлення, якщо ми знаємо мову, якою воно написано, – це взяти інший незашифрований текст на тій же мові, розміром приблизно на сторінку, і потім підрахувати появу в ньому кожної з букв. Назвемо букву, що найбільш часто зустрічається, «першою», букву, що за частотою появи знаходиться на другому місці, назвемо «другою», букву, що за частотою появи знаходиться на третьому місці, назвемо «третьою» і так далі, поки не будуть пораховані всі різні букви в незашифрованому тексті.