Кітаб аль-Муамма (книга) — Вікіпедія

«Кітаб аль-Муамма» (араб. كتاب المُعَمَّى‎ — «Книга таємної мови») — арабська книга, складена у VIII столітті Халілем Ахмадом ібн аль-Фарахіді на основі його власного методу шифрування.

З VIII століття н. е. розвиток криптографії відбувається в основному в арабських країнах — саме араби першими почали використовувати статистику й теорію ймовірностей в тій чи іншій формі. Вважається, що відомий арабський філолог VIII століття ібн Ахмад Халіль аль-Фарахіді першим звернув увагу на можливість використання стандартних фраз відкритого тексту для дешифрування текстів.

На основі відкритого ним методу дешифрування, він написав книгу «Кітаб Аль-Муамма».

Передісторія[ред. | ред. код]

Одного разу Халілю ібн Ахмаду потрібно було дешифрувати криптограмму на грецькій мові, яку переслав йому візантійський імператор. Він пояснив свій метод розшифровки так:

Я сказав собі, що лист повинен починатися зі слів «В ім'я Аллаха» або як-небудь в цьому роді. Отже, я склав на основі цього перші літери, і все виявилося правильним.

Іншими словами, його рішення було засноване на відомій (вірно увгаданій) частині тексту повідомлення, яка почалася: «В ім'я Аллаха перед усім …» (англ. His solution was based on known (correctly guessed) plaintext at the message which began: “In the name of Allah before all things…”.).

Цей метод атаки був використаний у Великій Вітчизняній війні[перевірити], щоб зламати німецькі комунікації.[1]

Будова книги[ред. | ред. код]

Метод шифрування, придуманий Аль-Фарахіді, являє собою звукову частину вже відомої мови (в оригіналі — арабської). Словник включає в себе деякі складові вихідної мови. Застосовується правило відбору слів і букв, згідно з яким перераховане вище не повинно підкорятися правилам фонологічних досліджень, яке Аль-Фарахіді отримав раніше у своїх працях. Для цього він використовував свої знання з музики.

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

Пізніше арабські криптографи вдаються до частотного аналізу тексту, запропонованого аль-Фарахіді, для розрахунку частоти слів у своїх роботах.[3]

Інші праці на основі запропонованого методу[ред. | ред. код]

На жаль, книга «Кітаб аль-Муамма» не збереглася, до читача дійшла згадками в роботах інших вчених. Найвідоміша праця, на основі медоту дешифрування Халіля ібн Ахмада — це праця Абу Юсуф Якуб ібн Ісхак ібн Сабба аль-Кінді, відомого філософа, математика й астронома, який називається «Трактат про дешифрування криптографічних повідомлень».

Перша сторінка рукопису «Трактат про дешифрування криптографічних повідомлень»

Метод, запропонований Халілем Ахмадом Ібн, містить багато нововведень, в тому числі використання перестановок і комбінацій різних слів (для того, щоб перерахувати всі можливі арабські слова без використання голосних літер у них).[4]

Але вся революційна й допрацьована система криптоаналізу, запропонована Аль-Кінді, вміщається в два коротких абзаци:

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

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


Крім трактату Аль-Кінді є не менш відома робота — це енциклопедія з 14 томів «Шауб аль-Аша» («Світоч для незрячого в ремеслі писаря»), яка була написана вченим Шіхабом ад-Дін Абу-л-Аббас Ахмад ібн Алі ал-Калкашанді в 1412 році. Всі наступні роботи з криптоаналізу в арабських країнах до X століття були на основі одного з цих двох трактатів — «Трактат про дешифрування криптографічних повідомлень» або «Шауб аль-Аша», оскільки робота Халіля Ібн Ахмада не збереглася, то автор виклав всі відомі йому на той час криптосистеми. В роботі пропонувалося сім систем шифрування, які повторювали неопубліковані ідеї його попередника Ібн ад-Дурайхіма, який вперше використав частотний аналіз літер. Ось ці системи шифрування:

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

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

Перший раз за всю історію шифрів в цій енциклопедії наводився список систем перестановки й заміни систем. Та найголовніше, що вперше було представлено опис криптоаналітичного дослідження шифротекста. Мабуть, він був складений після інтенсивного й скрупульозного вивчення Корану арабськими граматиками. Вони займалися підрахунком частоти появи слів, вивчали фонетику слів (для встановлення морфологічного походження того чи іншого слова — арабське або воно чи було запозичене з іншої мови). При складанні словників, авторам доводилося враховувати частоту появи літер, а також те, які букви можуть стояти поруч, а які ніколи не зустрічаються по сусідству. Зібравши всю накопичену інформацію разом і відштовхнувшись від ідеї Халіля ібн Ахмада, Калкашанді описав у своїй книзі спосіб розшифровки повідомлення: [5]

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

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

Потім Ви припускаєте, що наступна по частоті буде буквою «Лям». Точність вашого припущення повинна підтверджуватися тим фактом, що в більшості контекстів буква «Лям» слідує за буквою «Аліф».

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

[6]

Іншими словами, Калкашанді починає виклад з того, що криптоаналітик має знати мову, на якій написана криптограма. Далі складається докладний опис його лінгвістичних характеристик (Калкашанді використовує арабську мову, як «найблагороднішу і найпрекраснішу з усіх мов»). Після цього наводяться перелік літер, які ніколи не можуть стояти разом в одному слові, і букв, які рідко з'являються по сусідству. Розглядаються також літерні комбінації, які в словах зустріти неможливо. Останнім йде список літер у порядку частоти їх використання в арабській мові у світлі результатів вивчення священного Корану". Автор навіть зазначає, що «в творах, не пов'язаних з Кораном, частота використання може бути іншою».[7]

Калкашанді навів приклад розкриття шифру: дешифрована криптограма складається із двох віршованих рядків, зашифрованих за допомогою умовних символів. На закінчення Калкашанді зазначив, що вісім букв не було використано і що це саме ті букви, які знаходяться в кінці переліку, складеного за частотою появи. Він підкреслив: «Однак це проста випадковість: літера може бути поставлена не на те місце, яке вона повинна займати у вищезгаданому переліку». Так Калкашанді привів наочний приклад використання статистичного аналізу тексту шифрування повідомлень. Примітно, що даний метод успішно застосовується в розшифровці повідомлень, зашифрованих методом використання одного алфавіту (моноалфавітний метод), по цей день, але він не є криптостійким.[8]

Примітки[ред. | ред. код]

Література[ред. | ред. код]