Європейська криптологія
Потім подивимося на зашифрований текст, що ми хочемо прочитати, і таким же способом проведемо сортування його символів. Знайдемо символ, що найбільш часто зустрічається, і замінимо його «першою» буквою незашифрованого тексту, другий за частотою появи символ замінимо «другою» буквою, третій за частотою появи символ замінимо «третьою» буквою й так далі, поки не будуть замінені всі символи зашифрованого повідомлення, що ми хочемо дешифрувати».
Але по-справжньому характеризує пізнання арабів у сфері криптології енциклопедія з 14-ти томів «Шауба аль-Аша» (Світоч для незрячого в ремеслі писаря), що була написана вченим Шихабом ад-Дін Абу-л-Абас Ахмад ібн Алі ал-Калкашанді (1335—1418) у 1412 році. У розділі «Щодо приховання букв таємних повідомлень», автор виклав всі відомі йому на той час існуючі в арабському світі криптосистеми. Він містив дві частини: одна стосувалася символічних дій і натяків, а інша була присвячена симпатичному чорнилу та криптології.
У роботі пропонувалося сім систем шифрування, що повторювали неопубліковані ідеї його попередника Ібн ад-Дурайхима (1312—1361), який був першим, хто використав частотний аналіз букв:
– замінювати одну букву іншою;
– писати слово у зворотному порядку;
– переставляти у зворотному порядку букви слів;
– замінювати букви на цифри згідно з прийнятою заміною арабських букв на числа;
– замінювати кожну букву відкритого тексту на дві арабські букви, які використовуються і як числа й сума яких дорівнює цифровій величині букви відкритого тексту, що шифрується;
– замінювати кожну букву на ім'я якої-небудь людини;
– використовувати словник заміни, що описує положення Місяця, назви країн (у певному порядку), назв фруктів, дерев тощо.
Першого разу за всю історію шифрів в енциклопедії приводився список як систем перестановки, так і систем заміни. Більше того, у п'ятому пункті списку вперше згадувався шифр, для якого була характерна більш ніж одна заміна букв відкритого тексту. Однак яким би чудовим та важливим цей факт не був, він затьмарюється першим в історії описом криптоаналітичного дослідження шифротекста.
Його джерела, мабуть, варто шукати в інтенсивному й скрупульозному вивченні Корану численними школами арабських граматиків. Поряд з іншими дослідженнями вони займалися підрахунком частоти появи слів, намагаючись скласти хронологію глав Корана, вивчали фонетику слів, щоб установити, чи були вони справді арабськими або були запозичені з інших мов. Більшу роль у виявленні лінгвістичних закономірностей, що призвели до виникнення криптоаналізу в арабів, зіграв також розвиток лексикографії. Адже при складанні словників авторам фактично доводилося враховувати частоту появи букв, а також те, які букви можуть стояти поруч, а які ніколи не зустрічаються по сусідству.
Калкашанді писав у своїй книзі: «Якщо ви хочете прочитати повідомлення, що ви одержали в зашифрованому вигляді, то насамперед почніть підрахунок букв, а потім порахуйте, скільки разів повторюється кожен знак, і підбийте підсумок у кожному окремому випадку. Якщо винахідник шифру був дуже уважний та сховав у повідомленні всі границі між словами, то перша задача, що повинна бути вирішена, полягає в перебуванні знака, що розділяє слова. Це робиться так: ви берете букву та працюєте, виходячи з припущення, що наступна буква є знаком, що поділяє слова. І в такий спосіб ви вивчаєте все повідомлення з урахуванням різних комбінацій букв, з яких можуть бути складені слова… Якщо виходить, тоді усе в порядку; якщо ні, то ви берете наступну букву і т.д., поки ви не зможете установити знак розділу між словами. Потім потрібно знайти, які букви найчастіше трапляються у повідомленні, та порівняти їх зі зразком частоти появи букв, про яке згадувалося колись. Коли ви побачите, що одна буква трапляється частіше, ніж інші у даному повідомленні, ви припускаєте, що це буква „аліф“. Потім ви припускаєте, що наступна за частотою появи буде буквою „лам“. Точність вашого припущення повинна підтверджуватися тим фактом, що в більшості контекстів буква „лам“ випливає за буквою „аліф“… Потім перші слова, що ви спробуєте розгадати у повідомленні, повинні складатися з двох букв. Це робиться шляхом оцінки найбільш ймовірних комбінацій букв доти, поки ви не переконаєтеся в тому, що ви знаходитеся на правильному шляху. Тоді ви дивитеся на їхні знаки і виписуєте їхні еквіваленти кожного разу, коли вони трапляються у повідомленні. Потрібно застосовувати точно такий же принцип стосовно трибуквених слів цього повідомлення, поки не переконаєтеся, що на щось натрапили. Ви виписуєте еквіваленти з усього повідомлення. Цей же принцип застосовується стосовно слів, що складають з чотирьох і п'яти букв, причому метод роботи такий же. Коли виникає який-небудь сумнів, потрібно висловити два-три припущення або ще більше і виписати кожне з них, поки воно не підтвердиться на підставі іншого слова».
Давши це чітке пояснення, Калкашанді наводить приклад розкриття шифру. Дешифрована криптограма складається з двох віршованих рядків, зашифрованих за допомогою умовних символів. На закінчення Калкашанді відзначив, що вісім букв не було використано і що це саме ті букви, що знаходяться наприкінці переліку, складеного за частотою появи. Він підкреслив: «Однак це проста випадковість: буква може бути поставлена не на те місце, що вона повинна займати у вищезгаданому переліку». Таке зауваження свідчить про наявність великого досвіду в сфері криптоаналізу. Щоб розставити всі крапки над «і», Калкашанді приводить другий приклад криптоаналізу досить довгої криптограми. Цим прикладом він і закінчив розділ із криптології.
Араби першими звернули увагу на можливість використання стандартних слів і виразів для дешифрування. Так, перший широко відомий філолог серед арабів Ха-ліль ібн Ахмад аль-Фарахіді (біля 718—791), дешифрувавши криптограму грецькою мовою, надіслану йому візантійським імператором, заявив: «Я сказав собі, що лист повинен починатися зі слів „В ім'я Бога“ або як-небудь у цьому роді. Отже, я склав на основі цього перші букви, і все виявилося правильним». На основі відкритого ним методу дешифрування він написав книгу «Кітаб аль-маумма» (Книга таємної мови).
Історія замовчує те, як араби використали свої блискучі криптоаналітичні здібності, продемонстровані Калкашанді, для розкриття військових і дипломатичних криптограм, або який вплив це зробило на мусульманську історію. Однак зрозуміло, що незабаром ці знання перестали застосовуватися на практиці та були забуті. Один епізод, що відбувся майже 200 років по тому, яскраво демонструє ту деградацію у сфері криптоаналізу, що відбулася за той час.
У 1600 році мароканський султан Ахмед аль-Мансур направив до англійської королеви Єлизавети I посольство на чолі з довіреною людиною – міністром Абдель Вахід ібн Масуд ібн Мухамед Ануном. Посольство повинне було укласти з Англією союз, спрямований проти Іспанії. Анун відправив на батьківщину зашифровану простою заміною депешу, яка незабаром після цього якимось чином потрапила в руки одного араба. Араб той був, можливо, розумною людиною, але, на жаль, він нічого не знав про велику арабську спадщину у сфері криптоаналізу. Свідчення тому -пам'ятна записка, у якій він написав:
«Хвала Аллаху! Щодо листа міністра Абдель Вахід ібн Масуд ібн Мухамед Ануна. Я знайшов лист, написаний його рукою, у якому він за допомогою таємних знаків виклав деякі відомості, призначені для нашого заступника Ахмеда аль-мансура. Ці відомості стосуються султанші християн (хай покарає їх Аллах!), що жила в країні за назвою Лондон… З того моменту, як цей лист потрапив до мене, я постійно час від часу вивчав знаки, що містилися в ньому. Пройшло приблизно 15 років, поки не настав той час, коли Аллах дозволив мені зрозуміти ці знаки, хоча ніхто не навчав мене цьому…».
Відмітимо, що для таке завдання Калкашанді виконав би не за 15 років, а за кілька годин!
Невідомо, чи був тісний зв'язок між розвитком європейської та східної криптології. Безумовно подібного роду контакти могли відбуватися в Іспанії й під час Хрестових походів, але стверджувати, що європейська криптологія в той час використала арабський досвід, не можна. Праці Калкашанді не були перекладені з арабської мови, тому прямого зв'язку європейської криптології зі східною немає. Крім того, якщо на сході криптологія була скоріше частиною лінгвістики, то в Європі вона була ближче до математики й природничих наук, що також визначило її специфіку.
Європейська цивілізація почала користуватися криптологією з часів середньовічного феодалізму. Правда, спочатку тайнопис знаходився в зародковому стані, його застосовували рідко і мінливо. Навіть, церковні системи шифрування були простими, хоча в ту епоху церква користувалася найбільшим впливом у суспільстві. Цікаво, що в той час, коли прості люди шифрування вважали чаклунством, основні роботи в сфері криптології виконувалися в лоні католицької церкви.
У X столітті чернець Герберт Орильякський (Аврилакський), що правив католицькою церквою під ім'ям папи Сильвестра II (біля 946—1003) і вивчав «магічні» знання, вів записи за стенографічною системою, створеною Марком Туллієм Тіроном (103—4 до н.е.), вільновідпущеним і другом відомого Цицерона.
У 1267 році англійський монах-францисканець, професор в Оксфорді, універсальний вчений, математик, оптик, астроном Роджер Бекон (1214—1294) написав першу європейську книгу, яка була присвячена криптології та називалася «Послання ченця Роджера Бекона про таємні дії мистецтва і природи та нікчемність магії» (лат. Epistola fratris Rogerii Baconis de secretis operibus artis et naturae, et de nullitate magiae). У передмові він помітив: «Дурень той, хто пише про таємницю яким-небудь способом, але не так, щоб приховати її від простолюду».
У розділі «Сім способів заховання таємниці» Бекон привів такі методи шифрування: повна заміна символів і знаків, використання загадкових і образних виразів, особливі способи запису, одночасне використання букв різних мов, застосування різних малюнків, скорочення голосних букв тощо. За свої наукові праці він був засуджений за «чорну магію» церковним судом і провів 14 років в ув'язненні.
У 1379 році антипапа Климент VII, який за рік до цього втік до французького Авіньону, звелів своїй канцелярії ввести в дію нові шифри. Секретар антипапи Габріель де Лавінда, що працював у його представництві в одному з північно-італійських міст-держав, виготовив індивідуальні ключі для всіх 24 кореспондентів антипапи. Ключі де Лавінда, що були найдавніші серед збережених на Заході, поєднували у собі елементи коду й шифру.
У своїй книзі «Трактат про шифри» Габріель де Лавінда описав новий тип шифру, що використовував «омофони», тобто припускав заміну букв декількома символами (знаками), кількість яких пропорційна появі букв у відкритому тексті. Імена, посади, географічні назви він рекомендував заміняти спеціальними знаками. Крім шифроалфавіту заміни з «пустишками» майже кожен такий ключ включав невеликий список з десятка широко розповсюджених слів або імен, яким приводилися у відповідність двобуквені кодові еквіваленти. Це самий ранній зразок «Номенклатора» – гібридної системи шифрування, який у наступні 450 років поширився по всій Європі.
Розвитку європейської криптології сприяло те, що середньовічні вчені, зробивши відкриття, аж ніяк не поспішали описати його в листах колегам, як це було тоді прийняте за відсутності періодичних наукових видань. Нерідко ту частину відкриття, що тепер називають «know how», вони шифрували анаграмою, переставляючи букви повідомлення за відомим тільки їм ключем. Наприклад, назви древньої та сучасної столиць Японії в російському написанні теж являють собою анаграму: КІОТО – ТОКІО.
Пояснюючи широке поширення тайнопису серед вчених середньовіччя, О.І.Герцен писав: «Гнані, блукачі із країни в країну, оточені небезпеками, вони не зарили з розсудливого страху істини, про яку були покликані свідчити; вони висловлювали її скрізь, де не могли висловлювати прямо – одягали її в маскарадне плаття, наділяючи алегоріями. Ховали під умовними знаками, прикривали тонким флером, що для когось проникливого нічого не приховувало, але приховувало від ворога: любов догадлівіша й проникливіша ненависті. Іноді вони це робили, щоб не злякати боязкі душі сучасників; іноді – щоб не потрапити на багаття».
Найбільшого розквіту криптологія досягла в період Епохи Відродження. Творчі періоди життя таких великих людей, як Леонардо да Вінчі, кардинала Рішельє, Лю-овиків XII—XIV й інших дали поштовх до зародження наукового підходу до проблем тайнопису. Саме в ці роки виникло поняття «кодування» повідомлень, тобто заміни букв і цифр відкритого тексту на букви, цифри, знаки, згідно із заздалегідь обумовленим правилом, законом.
Леонардо да Вінчі (1452—1519) також шифрував більшість своїх особистих записів. Найпростіший вид шифру, яким він користувався, це зворотнє (дзеркальне) написання тексту так, що прочитати його можна було лише у відбитті дзеркала, наприклад: слово «UKRAINE» перетворюється у шифротекст «ENIARKU». Однак Леонардо іноді використовував й більш серйозні шифри, тому далеко не всі його замітки та записи розшифровані й вивчені до цього часу. Невипадково вийшли в світ книга та фільм з назвою «Код да Вінчі».
Одним із провідних європейських криптологів був відомий англійський письменник, астроном-аматор, митний чиновник Джеффрі Чосер (1343—1400). В 1370-х роках він виконував секретні дипломатичні доручення свого короля в Італії й Франції. Все таємне листування Чосер здійснював, використовуючи шифр простої заміни. Його книга «Екватор Планет», що вийшла у 1390 році, містила окремі шифровані глави.
У 1401 році в Мантуанському герцогстві був знайдений шифр із використанням «омофонів» для голосних букв. Той факт, що «омофони» застосовувалися не для всіх букв, а тільки для голосних, свідчив про знання криптоаналітичних методів, заснованих на частоті появи знаків шифротекста.
Широкий розвиток торгівлі в середині століття спровокував появу специфічних шифрів, дуже простих і зручних, якими могли б користуватися купці для передачі, наприклад, дати приїзду або ціни товару. Це були прості шифри заміни цифр на букви, засновані на ключовому слові. Торговці заздалегідь домовлялися про використання загального ключового слова, букви якого відповідали б цифрам.
Наприклад, для ключа «ШИФРОВАНИЙ» цифра 0 означає букву «Ш», цифра 1 означає «И», 2 – «Ф», 3 – «Р» тощо. Тому одержавши від кореспондента повідомлення «ПРИБУВАЮ ИФШАЙР», вони його читали як «ПРИБУВАЮ 12/06/93». Простота та зручність цієї системи шифрування дозволили їй дожити до початку минулого століття без усяких змін. Крім цих шифрів, найчастіше використовувався шифр простої заміни, що полягав у заміні кожної букви повідомлення на відповідну їй букву шифру.
У ручних шифрах того часу часто використовувалися таблиці, які давали прості шифри перестановки. Ключем у них служив розмір таблиці та фраза, що задавала перестановку або спеціальну особливість таблиць. Проста перестановка без ключа – один із найпростіших методів шифрування, родинний шифру «скитала».
Наприклад, повідомлення «ЗУСТРІЧАЙ У ДЕСЯТЬ» записувалося в таблицю розміром 4х4 по стовпцях (див. таблицю).
Після того, як відкритий текст був записаний по стовпцях, для утворення шифровки він зчитувався по рядках. В результаті виходив шифротекст: «ЗРЙСУ-ІУЯСЧДТТАЕЬ». Для використання цього шифру відправнику та одержувачу потрібно було домовитися про загальний ключ у вигляді розміру таблиці. Об'єднання букв у групи не входило у ключ шифру та використовувалося лише для зручності запису тексту.
Більш практичним був метод шифрування, який був названий одиночною перестановкою за ключем. Він відрізнявся від попереднього лише тим, що стовпці таблиці переставлялися за ключовим словом, фразою або набором чисел довжиною в рядок таблиці. Ключове слово (наприклад, «ШИФР») вписувалося у перший рядок таблиці, та здійснювалася перестановка стовпців відповідно до порядкових номерів букв ключа (див. таблицю).
В результаті зчитування по рядках повідомлення «ЗУСТРІЧАЙ У ДЕСЯТЬ» перетворялося у шифротекст «РСЙЗІЯУУЧТДСАЬЕТ».
Крім одиночних перестановок використовувалися ще подвійні перестановки стовпців і рядків таблиці з повідомленням згідно з попередньо визначеним порядком нумерування рядків і стовпців таблиці, що й було ключем шифру. При цьому перестановки визначалися окремо для стовпців та окремо для рядків. У таблицю вписувався текст по стовпцях, після чого здійснювалися перестановки стовпців та рядків (див. таблицю).
В результаті кінцевого зчитування по рядках повідомлення «ЗУСТРІЧАЙ У ДЕСЯТЬ» перетворялося у такий шифротекст: ЯІУУСРЗЙЬАТЕТЧСД. При розшифруванні порядок перестановок був зворотнім. Однак навіть шифри подвійної перестановки були слабким видом шифру, тому що легко читалися при будь-якому розмірі таблиці шифрування.
Новий етап розвитку криптології розпочався у другій половині XV століття з введенням у практику криптології багатоалфавітних шифрів заміни. Батьком цього шифру виявився теоретик мистецтва Леон Батіста Альберті (1404—1472), який узагальнив досвід гуманістичної науки у вивченні античної спадщини, написав трактати «Про статую», «Про живопис», «Про зодчество», десять книг про зодчество, побудував палац Ручеллаї, церкву Іль Джезу та ряд інших чудових здобутків зодчества середньовічної Італії.
У 1466 році Альберті надав до папської канцелярії також і трактат про шифри, де здійснив аналіз частот букв, дослідив шифри заміни та перестановки, торкнувся питань стійкості шифрів. Підмічена Альберті різночастотність появи букв в осмислених текстах дала поштовх вивченню синтаксичних властивостей письмових повідомлень. При цьому основна увага приділялясь буквам, що частіше зустрічались у тексті.
Альберті вперше висунув ідею «подвійного» шифрування – текст, отриманий в результаті першого шифрування, піддавався повторному зашифруванню. Він запропонував використовувати два або більше шифралфавітів, переходячи від одного до іншого в процесі зашифровування й заплутуючи цим можливих криптоаналітиків.
Наприклад, обравши два шифралфавіти, можемо зашифрувати повідомлення, використовуючи по черзі то один, то інший. Таким чином, щоб зашифрувати слово «UKRAINE», зашифруємо першу букву за допомогою першого шифроалфавіту, так що «U» перетвориться в «Z», другу ж букву ми зашифруємо, використовуючи другий шифралфавіт, при цьому «K» стане «E». Для зашифровування третьої букви ми повернемося знову до першого шифроалфавіту (R → U), а щоб зашифрувати четверту букву, ми знову звернемося до другого шифроалфавіту (A → U) і так далі: I → M, N → H, E → H. В результаті отримаємо такий шифротекст: ZEUUMHH.
Основна перевага системи Альберті полягала в тому, що однакові букви у відкритому тексті не обов'язково залишалися однаковими у шифротексті. Точно так повторювані букви у шифротексті були різними буквами відкритого тексту.
В своїй книзі Альберті запропонував також свій власний шифр із нескромною назвою «шифр, гідний королів», який зробив шифровку дуже стійкою до «злому». Реалізація шифру забезпечувалась за допомогою механічного шифрувального диску, що було також одним з найважливіших винаходів Альберті.
Шифрувальний диск складався з великого зовнішнього диска та рухомого внутрішнього диска. Окружність зовнішнього диска була розділена на 24 рівні сектори, до яких були вписано 20 букв латинського алфавіту в їхньому природному порядку та 4 цифри. При цьому з алфавіту були вилучено 6 букв, без яких можна було обійтися – H, J, K, U, Y, W. Окружність внутрішнього диска була розділена також на 24 сектори, до яких були вписані букви змішаного латинського алфавіту.
Маючи два такі прилади, кореспонденти домовлялися про першу індексну букву на рухомому диску. При шифруванні повідомлення відправник ставив індексну букву проти будь-якої букви великого диска. Він інформував кореспондента про таке положення диска, записуючи цю букву зовнішнього диска як першу букву шифротекста. Чергова буква відкритого тексту відшукувалася на нерухомому диску, і буква меншого диска, що стояла проти неї, була результатом її шифрування. Після того, як були зашифровані декілька букв тексту, положення індексної букви змінювалося, про що також повідомлялося кореспонденту.
A B C D E F G I L M N O P Q R S T V X Z. 1…2 3. 4
L G A Z E N B O S F C H T Y. Q I. X K V P ET M R D
Так, наприклад, для індексної букви «L» одним з багатьох варіантів шифрування слова «PRESIDENT» може бути «ATQEIOZECX», а іншим – «BHYZQBAZFI» тощо.
B C D E F G I L M N O P Q R S T V X Z 1. 2..3. 4 A
L G A Z E N B O S F C H. T Y Q I X K V P ET M R D
Такий шифр мав дві особливості, що робили винахід Альберті важливою подією в історії криптології. По-перше, на відміну від шифрів простої заміни шифродиск використовував не один, а декілька алфавітів для зашифрування. Такі шифри одержали назву багатоалфавітних. По-друге, шифродиск дозволяв використовувати так звані коди з перешифруванням, що одержали широке поширення лише наприкінці XIX століття, тобто через чотири століття після винаходу Альберті.
Для цієї мети на зовнішньому диску малися цифри. Альберті склав код, що складався з 336 кодових груп, занумерованих від 11 до 4444. Кожному кодовому позначенню відповідала деяка закінчена фраза. Коли така фраза траплялася у відкритому повідомленні, вона замінялася відповідним кодовим позначенням, а за допомогою диска цифри зашифровувалися як звичайні знаки відкритого тексту, перетворюючись у букви.
У 1474 році був написаний перший у світі трактат, присвячений винятково криптоаналізу. Це зробив Чико Сімонетті, один із секретарів правителів Мілана – герцогів Сфорца. У ньому він виклав удосконалені шифри заміни, у тому числі шифр багатозначної заміни, у якому одній букві (голосній) відповідало декілька шифропозначень. Він розробив 13 правил розкриття шифрів простої заміни, у яких збережені роздільники слів. Рукопис, написаний на трьох шматках пергаменту, починався зі слів: «Перша необхідна умова полягає в з'ясуванні того, чи написаний документ латинською або місцевою мовою, а це можна установити в такий спосіб: з'ясуєте, чи мають слова в даному документі тільки п'ять різних закінчень, менше або більше. Якщо їх тільки п'ять або менше, ви праві, вважаючи, що документ написаний місцевою мовою…».
Сімонетті у своєму трактаті докладно описав шифри заміни, у яких для вирівнювання частоти появи букв у шифротексті голосним буквам ставився у відповідність не один знак, а декілька. Тут же вперше був наведений опис так званого «гаслового» шифру, що у різних модифікаціях буде застосовуватися й кілька століть пізніше. Правило заміни букв у ньому визначалося таким чином: під алфавітом писалася ключова фраза – гасло (наприклад, «Ukraine») без повторюваних букв, а потім букви, що у гаслі не зустрічалися, у природному порядку.
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
U K R A I N E B C D F G H. J. L M O P Q S T V W X Y Z
В результаті слово «UZHGOROD» перетворюється у шифротекст: «TZBELPLA».
У 1518 році з'явилася перша друкована праця з криптології «Поліграфія» (лат. Polygraphia). Вона була написана Йоганом Гейденбергом (1462—1516), або Тритемієм (Трисемусом), абатом бенедиктинського монастиря Святого Мартіна (м. Вюрцбург, Німеччина), якого багато істориків вважають батьком європейської криптології. «Поліграфія» являла собою збірник з 6 книг і містила стовпці латинських термінів, слів, поставлених у відповідність буквам відкритого тексту, та першу квадратну таблицю, основу багатоалфавітної заміни.
Хоча у праці Тритемія було описано багато шифрів – як існуючих у той час, так і винайдених самим автором, вона була пронизана кабалістичними й окультними алюзіями.
В результаті книга викликала гнів багатьох монархових дворів Європи, які думали, що Тритемій видав у ній занадто багато таємниць. Крім того, Римська католицька церква вважала праці Тритемія єретичними та у 1609 році внесла його книги до списку заборонених. Ця заборона тривала 250 років.
У 1541 році книга була перевидана французькою мовою, а незабаром був зроблений її переклад на німецьку мову. У цій книзі Тритемій зробив дві нові пропозиції в криптології: він запропонував шифр «Аве Марія» і шифр, побудований на основі ключа, що періодично зрушується.