Теорія зв'язку в секретних системах

«Теорія зв'язку в секретних системах»

Автор	Клод Шеннон
Мова	англійська
Видано	1949

«Теорія зв'язку в секретних системах» (англ. Communication Theory of Secrecy Systems) — стаття американського математика та інженера Клода Шеннона, опублікована в журналі англ. Bell System Technical Journal в 1949 році.

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

Історія

З початку 1940-х років Клод Шеннон працював на Національний дослідницький комітет оборони США (англ. National Defense Research Committee). В лабораторіях Белла — дослідному центрі в галузі телекомунікацій і електронних систем, серед інших питань, він займався дослідженнями в області теорії інформації та криптографії, зокрема, питаннями безпеки урядового зв'язку^[1][2].

1 вересня 1945 року, як результат його напрацювань, вийшла секретна доповідь «Математична теорія криптографії» (англ. A Mathematical Theory of Cryptography). Серед тих, кому вона була направлена, були Ллойд Еспеншід, Гарольд Стівен Блек, Фредерік Бріттон Ллевеллін, Гаррі Найквіст, Ральф Хартлі, Джон Робінсон Пірс, Хендрік Вейд Боде, Волтер Шухарт і Сергій Олександрович Щелкунов^[3][4].

Через три роки була опублікована робота Шеннона «Математична теорія зв'язку» (англ. A Mathematical Theory of Communication), яка вважається основоположною в теорії інформації. У жовтні 1949 року журнал Bell System Technical Journal опублікував статтю Клода Шеннона з криптографії «Теорія зв'язку в секретних системах» (англ. Communication Theory of Secrecy Systems). В останню, також як і раніше в «Математичну теорію зв'язку», увійшла значна частина концептуальних напрацювань, раніше викладених у секретній доповіді «Математична теорія криптографії». В обох статтях був розроблений математичний апарат для відповідних систем.

Лабораторії Белла працювали над секретними системами. Я працював над системами зв'язку й також був призначений в деякі комітети, які вивчали техніку криптоаналізу. Робота над обома математичними теоріями - зв'язку й криптографії - йшла одночасно з 1941 року. Не можна сказати, що одна завершилася раніше іншої - обидві були так близькі, що не могли бути розділені. (Клод Шеннон)

Зміст

Стаття складається з трьох частин: «Математична структура секретних систем», «Теоретична секретність» і «Практична секретність».

Математична структура секретних систем

У першій частині статті введено формальне визначення криптосистеми (симетричної криптосистеми), що складається з джерела повідомлень, джерела ключів, шифрувальників, повідомлення, ключа криптограми й шифрувальника противника. Визначено функцію шифрування, яка залежить від вихідного повідомлення і ключа, процес дешифрування для одержувача повідомлення, що складається в обчисленні відображення, зворотного шифруванню, і процес дешифрування для супротивника — спробі визначити початкове повідомлення, знаючи тільки криптограмму і апріорні ймовірності різних ключів та повідомлень^[5].

Автор також запропонував подання криптосистеми у вигляді двочасткового графа, у вершинах якого розташовані можливі повідомлення і можливі криптограми, а кожному ключу шифрування поставлено у відповідність множину ребер, що з'єднують кожне можливе повідомлення з відповідною йому криптограмою^[6][7].

Приклад графа Шеннона абсолютно секретної системи. M_i, i = 1..4 — вихідні повідомлення; E_i, i = 1..4 криптограми; нумерація дуг графа відповідає нумерації ключів (1..4)

Наведено математичний опис раніше відомих шифрів. Розглянуто шифр простої підстановки, шифр Віженер, діграмна, триграмна і n-граммна підстановки, шифр Плейфера, шифр з автоключем і дробові шифри^[8].

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

Запропонована структура алгебри секретних систем (алгебри шифрів) з двома основними операціями комбінування шифрів: зважена сума (додавання шифрів з вагами у вигляді ймовірностей вибору шифру) і витвір (послідовне застосування). Нові шифри запропоновано отримувати комбінуванням зваженої суми і комбінації різних шифрів^[5].

Теоретична секретність

У другій частині статті визначено поняття досконалої стійкості криптосистеми, системи, де вихідне повідомлення і криптограма статистично незалежні^[11].

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

При розгляді випадкового шифру було введено поняття відстані єдиності — мінімального числа символів криптограми, з допомогою яких ключ може бути визначений однозначно^[11][13]. Також відзначена проблема надмірності мови, яка полягає в тому, що надмірність, що являє собою набір умов, накладених на символи повідомлення, дає додаткові можливості при дешифруванні криптограми противником.

Введено поняття ідеально стійкої криптосистеми, яка має нескінченну відстань єдиності. Приватним (більш суворим) випадком таких систем є досконало секретні системи. Їх характерною особливістю є те, що ідеальна криптосистема зберігає невизначеність навіть при успішній операції дешифрування противником^[13].

Практична безпека

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

Розглянуто можливість розкриття шифру за допомогою статистичного аналізу частоти символів зашифрованого тексту і методу імовірних слів. Згідно описаної у статті теорії, противник в процесі дешифрування може використовувати деякі статистичні властивості мови. Показано, що, наприклад, за умови знання мови вихідного повідомлення, для деяких шифрів можливо розкрити текст, що складається з декількох десятків символів. В якості прикладу слів/словосполучень, які найчастіше зустрічаються в англійській мові, автор навів конструкції «the», «and», «that» і склад «-tion», а в якості поєднання символів «qu», що прямо пов'язано з питанням про надмірності мови, розглянутих у другій частині статті^[1][14].

Запропоновано використовувати кілька шарів (циклів) замін і змін, що згодом було використано при побудові блочних шифрів. В оригінальній статті Шеннон назвав ці методи «confusion» (заплутування, відповідає заміні) і «diffusion» (розсіювання, відповідає перестановці)^[12].

Оцінки впливу

У книзі «Зломщики кодів» Девіда Кана висловлено думку про те, що в той час, як стаття «Математична теорія зв'язку» послужила початком розвитку теорії інформації, у статті «Теорія зв'язку в секретних системах» розглянута наукова сутність криптографії. Відзначено великий внесок автора у вказівці на мовну надмірність як ґрунт для криптоаналізу, і що саме Шеннон вперше ввів фундаментальні принципи дешифрування. Іншою важливою ідеєю статті Шеннона в книзі Кана вважається введення відстані єдиності.

Вітфілд Діффі і Мартін Геллман у статті «Нові напрямки в криптографії» (англ. New Directions in Cryptography) констатували, що Шеннон в «Теорії зв'язку в секретних системах» довів досконалу секретність одноразового шифроблокнота, але його використання є практично нездійсненною задачею для більшості прикладних цілей. Існує думка, що ця стаття Діффі і Геллмана призвела до прориву в криптографії, тому що було показано, як сторони можуть отримати загальний секретний ключ, використовуючи незахищений від прослуховування канал зв'язку, чого не було в криптографії, описаної в статті Шеннона.

Брюс Шнайєр у книзі «Прикладна Криптографія» зазначив, що до 1967 року  література з криптографії була беззмістовною, за одним рідкісним винятком, яким є стаття «Теорія зв'язку в секретних системах»^[13].

У книзі Handbook of Applied Cryptography^[en] помічено, що стаття є однією з кращих основоположних статей із захисту інформації й важливо, що вона поєднує практичну та теоретичну сторону питання, вводить фундаментальні ідеї надмірності  і відстані єдиності.

В «Енциклопедії з криптографії та безпеки» вказано на вплив, запропонованої в даній роботі ідеї, про використання декількох циклів, що складаються із заміни та перестановки, на створення блочних шифрів і SP-мережі. Також особливо відзначена модель криптосистеми, описана Шенноном, і теорема про досконалої секретності шифру Вернама. Крім того, однією з найбільш цитованих максим в криптографії названо припущення з першої частини статті: «Противнику відома застосована система» (англ. The enemy knows the system being used)^[12].

Примітки

1. В.И. Левин. К.Э. ШЕННОН И СОВРЕМЕННАЯ НАУКА : [] // Вестник ТГТУ : статья. — 2008. — Т. 14, № 3. — С. 714—716. — ISSN 0136-5835.
2. 杉本, 舞. C.E.シャノンの暗号理論 : [арх. 22 квітня 2018] : [яп.] // 科学哲学科学史研究 : статья. — 京都大学文学部科学哲学科学史研究室, 2006. — Т. 1 (20 березня). — С. 139, 142—144. — DOI:10.14989/56970.
3. Whitfield Diffie. Preface to Claue Shannon’s A Mathematical Theory of Cryptography : [арх. 21 квітня 2018] : [англ.] // IACR : статья. — 2015. — Грудень.
4. Claude Shannon. A Mathematical Theory of Cryptography : [арх. 28 березня 2016] : [англ.]. — 1945. — 1 вересня.
5. Аграновский, Хади
6. Hellman An Extension of the Shannon Theory Approach to Cryptography // IEEE Trans. Inf. Theory
7. Davio, Goethals Elements of Cryptology // Secure Digital Communications
8. В. В. Ященко, Н. П. Варновский, Ю. В. Нестеренко, Г. А. Кабатянский, П. Н. Девянин, В. Г. Проскурин, А. В. Черемушкин, П. А. Гырдымов, А. Ю. Зубов, А. В. Зязин, В. Н. Овчинников, М. И. Анохин Введение в криптографию|ответственный
10. Β. Κάτος, Γ. Στεφανίδης (PDF). Архів оригіналу (PDF) за 29 листопада 2016. Процитовано 21 квітня 2018.
11. Варфоломеев А. А. Современная прикладная криптография: Учеб. пособие (PDF). Архів оригіналу (PDF) за 4 листопада 2016. Процитовано 21 квітня 2018. [Архівовано 2016-11-04 у Wayback Machine.]
12. Encyclopedia of Cryptography and Security / Henk C. A. van Tilborg. — 1. — Springer, 205. — С. 12, 41, 146, 161, 169, 206, 244, 289, 290, 323, 372, 480, 568, 601, 602. — 684 с. — ISBN 9781441959065.
13. B. Schneier Applied cryptography (2nd ed.): protocols, algorithms, and source code in C

Посилання

• Стаття Шеннона A Mathematical Theory of Cryptography [Архівовано 28 березня 2016 у Wayback Machine.] на сайті IACR
• Стаття Шеннона Communication Theory of Secrecy Systems [Архівовано 4 листопада 2016 у Wayback Machine.] на сайті Wiley Online Library
• Сторінка статті на Google Scholar [Архівовано 4 листопада 2016 у Wayback Machine.]
• Сторінка публікації на IEEE Xplore Digital Library [Архівовано 22 березня 2018 у Wayback Machine.]