Криптоаналіз поліалфавітних шифрів

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

Історія створення поліалфавітного шифру

Шифр простої заміни довгий час був достатній для забезпечення секретності. Але до початку XV століття, коли багато криптоаналітиків того часу вже легко зламували будь-які повідомлення з шифром простої заміни, треба було шукати більш надійне шифрування. Розробкою стійкішого шифру зайнявся художник, композитор, поет і філософ Леон-Баттіста Альберті. З подачі свого друга Леонардо Дато, який служив секретарем у папи Римського, Альберті зацікавила ідея створення нового шифру. У своїй книзі «Трактат про шифри» (1466) Альберті запропонував використовувати для шифрування не один шифроалфавіт, а два або більше. При шифруванні один шифроалфавіт змінював інший.

Далі деякі доробки, ґрунтуючись на роботах Альберті, зробив німецький абат Йоганес Трісемус, автор першої друкованої книги з криптографії, виданої в 1518 році, яка носила назву «Поліграфія». Над шифром також потрудився італійський вчений Джованні Порта, який, крім створення шифрів, також займався і зломом поліалфавітних шифрів. Коли Порта було 28 років (1563), він написав свою книгу «Про таємне листування», в якій описав усі відомі системи шифрів.

Остаточний вид шифру, над яким працювали протягом століття в різний час Альберті,  Йоганес Трісемус і Порта, узагальнив французький дипломат Блез де Віженер. Сьогодні цей поліалфавітний шифр всім відомий як шифр Віженера. В силу своєї роботи, Віженеру доводилося постійно стикатися з шифровками, але впритул зайнятися вивченням криптографії у нього не було часу до виходу на пенсію. Так в 1586 році Віженер представив комісії Генріха III у Франції остаточний варіант шифру. Відомий письменник і математик Чарльз Лютвідж Доджсон назвав шифр Віженера незламним у своїй статті «Алфавітний шифр» (англ. The Alphabet Cipher); таким цей шифр вважали ще 300 років.

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

Криптоаналіз шифру Віженера

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

Шифр Віженера досить простий для використання в польових умовах, особливо якщо застосовуються шифрувальні диски. Наприклад, конфедерати використовували мідний шифрувальний диск для шифру Віженера в ході Громадянської війни в США. Послання Конфедерації були далекі від секретних, і їх противники регулярно зламували повідомлення. Основною вразливістю командування Конфедерації було те, що вони використовували лише три ключові словосполучення: «Manchester Bluff», «Complete Victory» і — так як війна підходила до кінця — «Come Retribution».

Аналіз Беббіджа і Казіскі

З різницею в кілька років над розробкою методу дешифрування працювали математики Чарльз Беббідж і Фрідріх Казіскі. Результати їх робіт майже однакові, за винятком того, що Казіскі дав суворе формулювання злому шифру Віженера, тоді як злом Беббіджа залишився тільки на сторінках його щоденника.

Беббідж

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

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

Успіху у зломі шифру Віженер Беббідж домігся в тому ж 1854 році, проте не опублікував своїх досліджень, і про відкриття ніхто не дізнався. Цей факт став відомий лише в XX столітті, коли вчені розбирали численні нотатки Беббіджа. Є дві версії, чому Беббідж не оголосив про своє досягнення. Перша версія полягає в тому, що британська секретна служба зажадала від Беббіджа збереження в таємниці своєї роботи, оскільки вона давала Британії явну перевагу над Росією — її противником в Кримській війні. Друга версія полягає в тому, що «була у нього така звичка — кидати незавершеними значні й перспективні починання і не повідомляти про свої відкриття».

Казіскі

Незалежно від Беббіджа аналогічний спосіб злому шифру Віженера був знайдений Фрідріхом Вільгельмом Казіскі, який опублікував його в 1863 рік у книзі «Die Geheimschriften und die Dechiffrirkunst» («Тайнопис і мистецтво дешифрування»). Дана публікація була на той час єдиною, в якій описувалися алгоритми злому поліалфавітних шифрів. Її можна вважати відправною точкою в історії злому даного типу шифрів. Алгоритм злому сьогодні відомий як метод Казіскі.

Аналіз Фрідмана

Полковник Фебіан після початку війни США проти Німеччини передав свою криптографічну лабораторію урядові в розпорядження. Вільям Фредерік Фрідман відповідав за підготовку розвідувальних військ, а одним із його асистентів була його дружина — криптограф Елізабет Фрідман. До кінця 1917 року Фрідманом вже був закладений фундамент у вигляді 7 монографій з криптографії, який став поштовхом для більш важливих відкриттів. Так, в 1920 році виходить робота The Riverbank Publications, яка вважається основоположною в цій дисципліні. У цьому ж році виходить одна з найбільш важливих публікації в історії криптографії The Index of Coincidence and Its Applications in Cryptography. У цій роботі Фрідман вводить поняття «індекс збігів» і пропонує методику розрахунку збігів. В суміжних публікаціях Фрідман описує метод визначення періоду гами в шифру Віженера, а також представляє безключовий метод дешифрування при використанні нерівноймовірної гами (тест Фрідмана, 1925). Це була перша успішна демонстрація ймовірнісно-статистичних методів в криптографії.

Література

• Кан, Дэвид. Взломщики кодов = The Codebreakers: The Story of Secret Writing / Перевод А. Ключевского. — М.: Центрполиграф, 2000. — 186 с. — ISBN 5-227-00678-4.
• Сингх, Саймон. Книга шифров: Тайная история шифров и их расшифровки = The Code Book / Перевод А. Галыгина. — М.: ООО «Издательство Астрель», 2006. — С. 62—110. — 447 с. — ISBN 978-5-271-14453-0.
• Kahate, Atuk. Cryptography and Network Security. — 8th ed. — Tata McGraw-Hill Publishing Company Ltd, 2006. — P. 36, 58. — ISBN 0-07-049483-5.

Посилання

• Alberti, Leone Battista. (1466). De Componendis Cyfris (PDF). Ars Cryptographica. Архів оригіналу (PDF) за 2 червня 2013. Процитовано 2 червня 2013.