Эта статья входит в число хороших статей

Теория связи в секретных системах

Перейти к навигацииПерейти к поиску
Теория связи в секретных системах
Communication Theory of Secrecy Systems
АвторКлод Шеннон
Жанр научная статья
Язык оригиналаанглийский
Оригинал издан1949
ИздательBell System Technical Journal
Страниц59
Текст на стороннем сайте

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

В ней впервые были определены фундаментальные понятия теории криптографии[1], доказана совершенная криптостойкость шифра Вернама, определено понятие расстояния единственности, рассмотрена проблема избыточности языка и предложена идея создания шифров на основе нескольких циклов замены и перестановки. Считается, что именно с появлением этой статьи криптография, которая прежде считалась искусством, начала развиваться как наука[2][3][4].

История

С начала 1940-х годов Клод Шеннон работал на Национальный исследовательский комитет обороны США[англ.]. В лабораториях Белла — исследовательском центре в области телекоммуникаций и электронных систем, среди прочих вопросов, он занимался исследованиями в области теории информации и криптографии, в частности, вопросами безопасности правительственной связи[5][6].

1 сентября 1945 года, как результат его наработок, вышел секретный доклад «Математическая теория криптографии» (англ. A Mathematical Theory of Cryptography). Среди тех, кому он был направлен, были Ллойд Эспеншид[англ.], Гарольд Стивен Блэк[англ.], Фредерик Бриттон Ллевеллин[англ.], Гарри Найквист, Ральф Хартли, Джон Робинсон Пирс, Хендрик Уэйд Боде[англ.], Уолтер Шухарт и Сергей Александрович Щелкунов[7][8].

Спустя три года была опубликована работа Шеннона «Математическая теория связи» (англ. A Mathematical Theory of Communication), которая считается основополагающей в теории информации[5]. В октябре 1949 года журнал Bell System Technical Journal опубликовал статью Клода Шеннона по криптографии «Теория связи в секретных системах» (англ. Communication Theory of Secrecy Systems). В последнюю, также как и ранее в «Математическую теорию связи», вошла значительная часть концептуальных наработок, ранее изложенных в секретном докладе «Математическая теория криптографии». В обеих статьях был разработан математический аппарат для соответствующих систем[5][7].

Лаборатории Белла работали над секретными системами. Я работал над системами связи и также был назначен в некоторые комитеты, изучавшие технику криптоанализа. Работа над обеими математическими теориями – связи и криптографии – шла одновременно с 1941 г. Нельзя сказать, что одна завершилась раньше другой – обе были так близки, что не могли быть разделены.Клод Шеннон[9][5]

Перевод статьи «Теория связи в секретных системах» на русский язык был выполнен профессором Владленом Федоровичем Писаренко и помещён в сборник переводов статей Клода Шеннона «Работы по теории информации и кибернетике», выпущенный по инициативе Андрея Николаевича Колмогорова в 1963 году[10].

Содержание

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

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

Модель Шеннона для криптосистемы

В первой части статьи введено формальное определение криптосистемы (симметричной криптосистемы), состоящей из источника сообщений, источника ключей, шифровальщиков, сообщения, ключа, криптограммы и шифровальщика противника. Определены функция шифрования, зависящая от исходного сообщения и ключа, процесс дешифрования для получателя сообщения, состоящий в вычислении отображения, обратного шифрованию, и процесс дешифрования для противника — попытке определить исходное сообщение, зная только криптограмму и априорные вероятности различных ключей и сообщений[4][11][12][13].

Автор также предложил представление криптосистемы в виде двудольного графа, в вершинах которого расположены возможные сообщения и возможные криптограммы, а каждому ключу шифрования поставлено в соответствие множество ребер, соединяющих каждое возможное сообщение с соответствующей ему криптограммой[14][15].

Пример графа Шеннона совершенно секретной системы. Mi, i = 1..4 — исходные сообщения; Ei, i = 1..4 криптограммы; нумерация дуг графа соответствует нумерации ключей (1..4)

Приведено математическое описание ранее известных шифров. Рассмотрен шифр простой подстановки, шифр Виженера, диграммная, триграммная и n-граммнная подстановки, шифр Плэйфера, шифр с автоключом и дробные шифры[16][2].

Основными критериями оценки свойств (стойкости) криптосистем в статье названы: размер (длина) ключа, сложность операций шифрования и дешифрования, возможность или невозможность дешифрования сообщения противником единственным способом, степень влияния ошибок при шифровании и передаче на получаемое сообщение и степень увеличения размера сообщения в результате шифрования[17]. В конце статьи отмечено, что в случае шифрования составленного на естественном языке сообщения нельзя улучшить общую оценку криптосистемы, улучшая её по всем перечисленным параметрам одновременно[18].

Предложена структура алгебры секретных систем (алгебры шифров) с двумя основными операциями комбинирования шифров: взвешенная сумма (сложение шифров с весами в виде вероятностей выбора шифра) и произведение (последовательное применение). Новые шифры предложено получать комбинированием взвешенной суммы и произведения различных шифров[13].

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

Во второй части статьи определено понятие совершеной стойкости криптосистемы, системы, где исходное сообщение и криптограмма статистически независимы[3][4].

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

При рассмотрении случайного шифра было введено понятие расстояния единственности — минимального числа символов криптограммы, с помощью которых ключ может быть определён однозначно[3][19]. Также отмечена проблема избыточности языка, состоящая в том, что избыточность, представляющая собой набор условий, наложенных на символы сообщения, дает дополнительные возможности при дешифровке криптограммы противником[5][20].

Введено понятие идеально стойкой криптосистемы, которая имеет бесконечное расстояние единственности. Частным (более строгим) случаем таких систем являются совершено секретные системы. Их характерной особенностью является то, что идеальная криптосистема сохраняет неопределённость даже при успешной операции дешифрования противником[19].

Практическая секретность

В третьей части статьи определена рабочая характеристика криптосистемы как функция, зависящая от числа известных символов криптограммы и равная среднему объёму работы, затраченному на нахождение ключа шифрования[3]. Эта функция имеет некоторые сходства с понятием вычислительной сложности алгоритма[21].

Рассмотрена возможность раскрытия шифра с помощью статистического анализа встречаемости символов зашифрованного текста и метода вероятных слов. Согласно описанной в статье теории, противник в процессе дешифрования может использовать некоторые статистические свойства языка. Показано, что, например, при условии знании языка исходного сообщения, для некоторых шифров возможно раскрыть текст, состоящий из нескольких десятков символов. В качестве примера наиболее часто встречающихся в английском языке слов/словосочетаний автор привел конструкции «the», «and», «that» и слог «-tion», а в качестве сочетания символов «qu», что прямо связано с вопросом об избыточности языка, рассмотренным во второй части статьи[5][20].

Предложено использовать несколько слоев (циклов) замен и перестановок, что впоследствии было использовано при построении блочных шифров. В оригинальной статье Шеннон назвал эти методы «confusion» (запутывание, соответствует замене) и «diffusion» (рассеивание, соответствует перестановке)[4].

Оценки влияния

В книге «Взломщики кодов» Дэвида Кана высказано мнение о том, что в то время, как статья «Математическая теория связи» послужила началом развития теории информации, в статье «Теория связи в секретных системах» расcмотрена научная сущность криптографии. Отмечен большой вклад автора в указании на языковую избыточность как почву для криптоанализа, и что именно Шеннон впервые ввёл фундаментальные принципы дешифрования. Другой важной идеей статьи Шеннона в книге Кана считается введение расстояния единственности[9].

Уитфилд Диффи и Мартин Хеллман в статье «Новые направления в криптографии» (англ. New Directions in Cryptography) констатировали, что Шеннон в «Теории связи в секретных системах» доказал совершенную секретность одноразового шифроблокнота, но его использование является практически нереализуемой задачей для большинства прикладных целей[22]. Существует мнение, эта статья Диффи и Хеллмана привела к прорыву в криптографии, потому что было показано, стороны могут получить общий секретный ключ, используя незащищенный от прослушивания канал связи, чего не было в криптографии, описанной в статье Шеннона[4].

Брюс Шнайер в книге «Прикладная Криптография» отметил, что до 1967 года литература по криптографии была бессодержательной за одним редким исключением, которым является статья «Теория связи в секретных системах»[19].

В книге Handbook of Applied Cryptography замечено, что статья является одной из лучших основополагающих статей по защите информации и особенно примечательно, что она сочетает практическую и теоретическую сторону вопроса, вводит фундаментальные идеи избыточности и расстояния единственности[23].

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

Примечания

  1. ↑ Габидулин Э. М., Кшевецкий А. С., Колыбельников А. И. Защита информации: учебное пособие — М.: МФТИ, 2011. — С. 17. — 225 с. — ISBN 978-5-7417-0377-9
  2. ↑ 1 2 В. В. Ященко, Н. П. Варновский, Ю. В. Нестеренко, Г. А. Кабатянский, П. Н. Девянин, В. Г. Проскурин, А. В. Черемушкин, П. А. Гырдымов, А.Ю. Зубов, А. В. Зязин, В. Н. Овчинников, М. И. Анохин. Введение в криптографию / под ред. В. В. Ященко. — 4. — М.: МЦНМО, 2012. — С. 13, 17—18. — 348 с. — ISBN 978-5-4439-0026-1.
  3. ↑ 1 2 3 4 Варфоломеев А.А. Современная прикладная криптография: Учеб. пособие.. — М.: РУДН, 2008. — С. 8, 51—56. — 218 с. Архивировано 4 ноября 2016 года.
  4. ↑ 1 2 3 4 5 6 7 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.
  5. ↑ 1 2 3 4 5 6 В.И. Левин. К.Э. ШЕННОН И СОВРЕМЕННАЯ НАУКА (рус.) // Вестник ТГТУ : статья. — 2008. — Т. 14, № 3. — С. 714—716. — ISSN 0136-5835.
  6. ↑ 1 2 杉本, 舞. C.E.シャノンの暗号理論 (яп.) // 科学哲学科学史研究 : статья. — 京都大学文学部科学哲学科学史研究室, 2006. — 20 3月 (第1巻). — 第139, 142—144 頁. — doi:10.14989/56970. Архивировано 22 апреля 2018 года.
  7. ↑ 1 2 Whitfield Diffie. Preface to Claue Shannon’s A Mathematical Theory of Cryptography (англ.) // IACR : статья. — 2015. — December. Архивировано 21 апреля 2018 года.
  8. ↑ Claude Shannon. A Mathematical Theory of Cryptography (англ.). — 1945. — 1 September. Архивировано 28 марта 2016 года.
  9. ↑ 1 2 Kahn D. The Codebreakers (англ.): The Story of Secret Writing — Macmillan, 1967. — P. 403, 439—440, 444—446. — 1164 p. — ISBN 978-0-684-83130-5
  10. ↑ В.Ф. Писаренко. О Роланде Львовиче Добpушине. История института. Институт проблем передачи информации им. А.А. Харкевича РАН. Дата обращения: 4 ноября 2016. Архивировано 4 ноября 2016 года.
  11. ↑ Ho S., Chan T., Uduwerelle C. Error-free perfect-secrecy systems (англ.) // 2011 IEEE International Symposium on Information Theory Proceedings — IEEE, 2011. — ISBN 978-1-4577-0596-0 — ISSN 2157-8095 — doi:10.1109/ISIT.2011.6033797 — arXiv:1207.1860
  12. ↑ Тилборг Х. К. А. в. Основы криптологии: Профессиональное руководство и интерактивный учебник — М.: Мир, 2006. — С. 11. — 471 с. — ISBN 978-5-03-003639-7
  13. ↑ 1 2 Аграновский А. В., Хади Р. А. Практическая криптография: Алгоритмы и их программирование — М.: Солон-пресс, 2002. — С. 15—19, 69—73. — 256 с. — (Аспекты защиты) — ISBN 978-5-98003-002-5, 978-5-93455-184-2
  14. ↑ Hellman M. E. An Extension of the Shannon Theory Approach to Cryptography (англ.) // IEEE Transactions on Information Theory / F. Kschischang — IEEE, 1977. — Vol. 23, Iss. 3. — P. 289—294. — ISSN 0018-9448; 1557-9654 — doi:10.1109/TIT.1977.1055709
  15. ↑ Davio M., Goethals J. Elements of Cryptology (англ.) // Secure Digital Communications / G. O. Longo — Springer Vienna, 1983. — P. 1—7. — (International Centre for Mechanical Sciences; Vol. 279) — ISBN 978-3-211-81784-1 — ISSN 0254-1971; 2309-3706 — doi:10.1007/978-3-7091-2640-0_1
  16. ↑ Бабаш А. В., Шанкин Г. П. Криптография — М.: Солон-пресс, 2007. — С. 82. — 512 с. — (Аспекты защиты) — ISBN 978-5-93455-135-4
  17. ↑ Moise G. Knowledge-Based Schema for S-box Design (англ.) // International Journal of Research and Reviews in Applied Sciences — 2011. — Vol. 8, Iss. 3. — P. 296—300. — ISSN 2076-734X; 2076-7366
  18. ↑ Β. Κάτος, Γ. Στεφανίδης. Εισαγωγή // Τεχνικές Κρυπτογραφίας και Κρυπτανάλυσης. — Θεσσαλονίκη: ΖΥΓΟΣ, 2003. — С. 12. — 14 с. — ISBN 960-8065-40-2.
  19. ↑ 1 2 3 B. Schneier. Applied cryptography (2nd ed.): protocols, algorithms, and source code in C. — 2-е изд. — Inc. New York, NY, USA: John Wiley & Sons, 1995. — С. 235—236. — 758 с. — ISBN 0-471-11709-9.
  20. ↑ 1 2 Иванов В. В. Избранные труды по семиотике и истории культуры — М.: Языки славянских культур, 2007. — Т. 4. Знаковые системы культуры, искусства и науки. — С. 21—33. — 792 с. — (Язык. Семиотика. Культура) — ISBN 978-5-9551-0207-8
  21. ↑ Welsh D. Codes and Cryptography (англ.) — Oxford: OUP, 1988. — P. 121—122. — 257 p. — ISBN 978-0-19-853287-3
  22. ↑ Diffie W., Hellman M. E. New Directions in Cryptography (англ.) // IEEE Transactions on Information Theory / F. Kschischang — IEEE, 1976. — Vol. 22, Iss. 6. — P. 644—654. — ISSN 0018-9448; 1557-9654 — doi:10.1109/TIT.1976.1055638
  23. ↑ Menezes A. J., Oorschot P. v., Vanstone S. A. Handbook of Applied Cryptography (англ.) — Boca Raton: CRC Press, 1997. — P. 49. — 816 p. — (Discrete Mathematics and Its Applications) — ISBN 978-0-8493-8523-0

Ссылки