Главная
«Теория связи в секретных системах» (англ. Communication Theory of Secrecy Systems) — статья американского математика и инженера Клода Шеннона, опубликованная в журнале Bell System Technical Journal в 1949 году.
В ней впервые были определены фундаментальные понятия теории криптографии, доказана совершенная криптостойкость шифра Вернама, определено понятие расстояния единственности, рассмотрена проблема избыточности языка и предложена идея создания шифров на основе нескольких циклов замены и перестановки. Считается, что именно с появлением этой статьи криптография, которая прежде считалась искусством, начала развиваться как наука.
История
С начала 1940-х годов Клод Шеннон работал на Национальный исследовательский комитет обороны США. В лабораториях Белла — исследовательском центре в области телекоммуникаций и электронных систем, среди прочих вопросов, он занимался исследованиями в области теории информации и криптографии, в частности, вопросами безопасности правительственной связи.
1 сентября 1945 года, как результат его наработок, вышел секретный доклад «Математическая теория криптографии» (англ. A Mathematical Theory of Cryptography). Среди тех, кому он был направлен, были Ллойд Эспеншид, Гарольд Стивен Блэк, Фредерик Бриттон Ллевеллин, Гарри Найквист, Ральф Хартли, Джон Робинсон Пирс, Хендрик Уэйд Боде, Уолтер Шухарт и Сергей Александрович Щелкунов.
Спустя три года была опубликована работа Шеннона «Математическая теория связи» (англ. A Mathematical Theory of Communication), которая считается основополагающей в теории информации. В октябре 1949 года журнал Bell System Technical Journal опубликовал статью Клода Шеннона по криптографии «Теория связи в секретных системах» (англ. Communication Theory of Secrecy Systems). В последнюю, также как и ранее в «Математическую теорию связи», вошла значительная часть концептуальных наработок, ранее изложенных в секретном докладе «Математическая теория криптографии». В обеих статьях был разработан математический аппарат для соответствующих систем.
Лаборатории Белла работали над секретными системами. Я работал над системами связи и также был назначен в некоторые комитеты, изучавшие технику криптоанализа. Работа над обеими математическими теориями – связи и криптографии – шла одновременно с 1941 г. Нельзя сказать, что одна завершилась раньше другой – обе были так близки, что не могли быть разделены.Клод Шеннон
Перевод статьи «Теория связи в секретных системах» на русский язык был выполнен профессором Владленом Федоровичем Писаренко и помещён в сборник переводов статей Клода Шеннона «Работы по теории информации и кибернетике», выпущенный по инициативе Андрея Николаевича Колмогорова в 1963 году.
Содержание
Статья Клода Шеннона «Теория связи в секретных системах» разделена на три основные части: «Математическая структура секретных систем», «Теоретическая секретность» и «Практическая секретность».
Математическая структура секретных систем
В первой части статьи введено формальное определение криптосистемы (симметричной криптосистемы), состоящей из источника сообщений, источника ключей, шифровальщиков, сообщения, ключа, криптограммы и шифровальщика противника. Определены функция шифрования, зависящая от исходного сообщения и ключа, процесс дешифрования для получателя сообщения, состоящий в вычислении отображения, обратного шифрованию, и процесс дешифрования для противника — попытке определить исходное сообщение, зная только криптограмму и априорные вероятности различных ключей и сообщений.
Автор также предложил представление криптосистемы в виде двудольного графа, в вершинах которого расположены возможные сообщения и возможные криптограммы, а каждому ключу шифрования поставлено в соответствие множество ребер, соединяющих каждое возможное сообщение с соответствующей ему криптограммой.
Приведено математическое описание ранее известных шифров. Рассмотрен шифр простой подстановки, шифр Виженера, диграммная, триграммная и n-граммнная подстановки, шифр Плэйфера, шифр с автоключом и дробные шифры.
Основными критериями оценки свойств (стойкости) криптосистем в статье названы: размер (длина) ключа, сложность операций шифрования и дешифрования, возможность или невозможность дешифрования сообщения противником единственным способом, степень влияния ошибок при шифровании и передаче на получаемое сообщение и степень увеличения размера сообщения в результате шифрования. В конце статьи отмечено, что в случае шифрования составленного на естественном языке сообщения нельзя улучшить общую оценку криптосистемы, улучшая её по всем перечисленным параметрам одновременно.
Предложена структура алгебры секретных систем (алгебры шифров) с двумя основными операциями комбинирования шифров: взвешенная сумма (сложение шифров с весами в виде вероятностей выбора шифра) и произведение (последовательное применение). Новые шифры предложено получать комбинированием взвешенной суммы и произведения различных шифров.
Теоретическая секретность
Во второй части статьи определено понятие совершеной стойкости криптосистемы, системы, где исходное сообщение и криптограмма статистически независимы.
Доказана совершенная стойкость шифра Вернама (одноразового шифроблокнота). Показана ненадежность некоторых шифров на примере шифра Цезаря, в котором частоты появления символов, соответствующих символам исходного сообщения, не зависят от ключа.
При рассмотрении случайного шифра было введено понятие расстояния единственности — минимального числа символов криптограммы, с помощью которых ключ может быть определён однозначно. Также отмечена проблема избыточности языка, состоящая в том, что избыточность, представляющая собой набор условий, наложенных на символы сообщения, дает дополнительные возможности при дешифровке криптограммы противником.
Введено понятие идеально стойкой криптосистемы, которая имеет бесконечное расстояние единственности. Частным (более строгим) случаем таких систем являются совершено секретные системы. Их характерной особенностью является то, что идеальная криптосистема сохраняет неопределённость даже при успешной операции дешифрования противником.
Практическая секретность
В третьей части статьи определена рабочая характеристика криптосистемы как функция, зависящая от числа известных символов криптограммы и равная среднему объёму работы, затраченному на нахождение ключа шифрования. Эта функция имеет некоторые сходства с понятием вычислительной сложности алгоритма.
Рассмотрена возможность раскрытия шифра с помощью статистического анализа встречаемости символов зашифрованного текста и метода вероятных слов. Согласно описанной в статье теории, противник в процессе дешифрования может использовать некоторые статистические свойства языка. Показано, что, например, при условии знании языка исходного сообщения, для некоторых шифров возможно раскрыть текст, состоящий из нескольких десятков символов. В качестве примера наиболее часто встречающихся в английском языке слов/словосочетаний автор привел конструкции «the», «and», «that» и слог «-tion», а в качестве сочетания символов «qu», что прямо связанно с вопросом об избыточности языка, рассмотренным во второй части статьи.
Предложено использовать несколько слоев (циклов) замен и перестановок, что впоследствии было использовано при построении блочных шифров. В оригинальной статье Шеннон назвал эти методы «confusion» (запутывание, соответствует замене) и «diffusion» (рассеивание, ответствует перестановке).
Оценки влияния
В книге «Взломщики кодов» Дэвида Кана высказано мнение о том, что в то время, как статья «Математическая теория связи» послужила началом развития теории информации, в статье «Теория связи в секретных системах» расcмотрена научная сущность криптографии. Отмечен большой вклад автора в указании на языковую избыточность как почву для криптоанализа, и что именно Шеннон впервые ввёл фундаментальные принципы дешифрования. Другой важной идеей статьи Шеннона в книге Кана считается введение расстояния единственности.
Уитфилд Диффи и Мартин Хеллман в статье «Новые направления в криптографии» (англ. New Directions in Cryptography) констатировали, что Шеннон в «Теории связи в секретных системах» доказал совершенную секретность одноразового шифроблокнота, но его использование является практически нереализуемой задачей для большинства прикладных целей. Существует мнение, эта статья Диффи и Хеллмана привела к прорыву в криптографии, потому что было показано, стороны могут получить общий секретный ключ, используя незащищенный от прослушивания канал связи, чего не было в криптографии, описанной в статье Шеннона.
Брюс Шнайер в книге «Прикладная Криптография» отметил, что до 1967 года литература по криптографии была бессодержательной за одним редким исключением, которым является статья «Теория связи в секретных системах».
В книге Handbook of Applied Cryptography замечено, что статья является одной из лучших основополагающих статей по защите информации и особенно примечательно, что она сочетает практическую и теоретическую сторону вопроса, вводит фундаментальные идеи избыточности и расстояния единственности.
В «Энциклопедии по криптографии и безопасности» указано на влияние предложенной в данной работе идеи о использовании нескольких циклов, состоящих из замены и перестановки, на создание блочных шифров и SP-cети. Также особо отмечена модель криптосистемы, описанная Шенноном, и теорема о совершенной секретности шифра Вернама. Кроме того, одной из наиболее цитируемых максим в криптографии названо предположение из первой части статьи: «Противнику известна используемая система» (англ. The enemy knows the system being used).