Теория связи в секретных системах: различия между версиями

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску
Интерактивная навигация по истории
[непроверенная версия][непроверенная версия]
← Предыдущая правкаСледующая правка →
Содержимое удалено Содержимое добавлено
ВизуальныйВики-текст
см. Обсуждение
Строка 29: Строка 29:


==Содержание==
==Содержание==

===Математическая структура секретных систем===
[[Файл:Модель Шеннона криптосистемы.jpg|мини|450x450пкс|Модель Шеннона для криптосистемы. ]]
В первой части статьи введено формальное определение [[Криптосистема|криптосистемы]] ([[Симметричные криптосистемы|симметричной криптосистемы]]), состоящей из источника сообщений, источника ключей, шифровальщиков, сообщения, ключа, криптограммы и шифровальщика противника. Затем определяется функция шифрования, зависящая от исходного сообщения и ключа. Процесс дешифрования для получателя сообщения состоит в вычислении отображения, обратного шифрованию, а процесс дешифрования для противника - в попытке определить исходное сообщение, зная только криптограмму и априорные вероятности различных ключей и сообщений. <ref name=":8" /><ref>{{Статья|автор=Siu-Wai Ho, Terence H. Chan, Alex Grant, Chinthani Uduwerelle|заглавие=Error-Free Perfect-Secrecy Systems|ссылка=http://ieeexplore.ieee.org/document/6033797/|язык=en|издание=Information Theory Proceedings (ISIT), 2011 IEEE International Symposium on|тип=статья|год=2011|месяц=|число=|том=|номер=|страницы=1|issn=978-1-4577-0596-0|doi=10.1109/ISIT.2011.6033797}}</ref> <ref>{{Книга|автор=Тилборг ван Х.К.А.|заглавие=Основы криптологии. Профессиональное руководство и интерактивный учебник.|ответственный=|издание=1-е изд|место=М.|издательство=Мир|год=2006|страницы=11|страниц=471|isbn=5-03-003639-3}}</ref> <ref name=":1">{{Книга|автор=Аграновский А.В., Хади Р.А.|заглавие=Практическая криптография: алгоритмы и их программирование|ответственный=|издание=|место=М.|издательство=Солон-Пресс|год=2009|страницы=15—19, 69—73|страниц=256|isbn=5-98003-002-6}}</ref>

Автор также предлагает представление криптосистемы в виде [[Двудольный граф|двудольного графа]], в вершинах которого расположены возможные сообщения и возможные криптограммы, а каждому ключу шифрования поставлено в соответствие множество ребер, соединяющих каждое возможное сообщение с соответствующей ему криптограммой. <ref>{{Статья|автор=M. E. Hellman|заглавие=An Extension of the Shannon Theory Approach to Cryptography|ссылка=http://www-ee.stanford.edu/~hellman/publications/25.pdf|язык=en|издание=IEEE Trans. on Info. Theory|тип=статья|год=1977|месяц=5|число=|том=|номер=IT-23|страницы=289—290|issn=}}</ref> <ref name=":2">{{Статья|автор=Tatiana Diyachenko|заглавие=STATISTICAL ANALYSIS OF THE UNIFORMITY OF CRYPTOGRAMS IN THE DYNAMIC CRYPTOSYSTEMS|ссылка=https://publications.theseus.fi/bitstream/handle/10024/101276/Thesis_Tatiana_Diyachenko.pdf?sequence=2|язык=en|издание=Thesis CENTRIA UNIVERSITY OF APPLIED SCIENCES|тип=статья|год=2015|месяц=11|число=|том=|номер=|страницы=10, 11|issn=}}</ref>
[[Файл:Пример графа Шеннона совершенно секретной системы 2.jpg|мини|300x300пкс|Пример графа Шеннона совершенно секретной системы. M<sub>i</sub>, i = 1..4 - исходные сообщения; E<sub>i</sub>, i = 1..4 криптограммы; нумерация дуг графа соответствует нумерации ключей (1..4).]]
Приведено математическое описание ранее известных шифров. Рассматривается [[Шифр подстановки|шифр простой подстановки]], [[Шифр Виженера|шифр Виженера]], [[Шифр подстановки|диграммная, триграммная и n-граммнная подстановки]], [[Шифр Плейфера|шифр Плэйфера]], шифр с автоключом и дробные шифры. <ref>{{Книга|автор=Бабаш А.В., Шанкин Г.П.|заглавие=Криптография|ответственный=|издание=|место=М.|издательство=Солон-Пресс|год=2007|страницы=82|страниц=512|isbn=5-93455-135-3}}</ref><ref name=":9">{{Книга|автор=В. В. Ященко, Н. П. Варновский, Ю. В. Нестеренко, Г. А. Кабатянский, П. Н. Девянин, В. Г. Проскурин, А. В. Черемушкин, П. А. Гырдымов, А.Ю. Зубов, А. В. Зязин, В. Н. Овчинников, М. И. Анохин|заглавие=Введение в криптографию|ответственный=под ред. В. В. Ященко|издание=4|место=М.|издательство=МЦНМО|год=2012|страницы=13, 17—18|страниц=348|isbn=978-5-4439-0026-1}}</ref>

Введены основные критерии оценки криптосистем: количество секретности (оценка возможности дешифрования сообщения противником единственным способом), объём ключа, сложность операции шифрования и дешифрования, разрастание числа ошибок при шифровании и передаче, увеличение объёма сообщения в результате шифрования. <ref>{{Статья|автор=Gabriela Moise|заглавие=Knowledge-Based Schema for S-box Design|ссылка=http://www.arpapress.com/Volumes/Vol8Issue3/IJRRAS_8_3_04.pdf|язык=en|издание=International Journal of Research and Reviews in Applied Sciences|тип=статья|год=2011|месяц=9|число=|том=|номер=8(3)|страницы=296|issn=}}</ref><ref name=":5">{{Статья|автор=Τσιάκης, Θεοδόσιος|заглавие=Η εφαρμοσμένη κρυπτογραφία ως τυπική μέθοδος και μοντέλο για την ασφάλεια των ηλεκτρονικών συναλλαγών|ссылка=https://dspace.lib.uom.gr/handle/2159/229|язык=gr|издание=Πανεπιστήμιο Μακεδονίας, Θεσσαλονίκη|тип=диссертация|год=2005|месяц=|число=|том=|номер=|страницы=153—154|issn=}}</ref> В конце статьи отмечается, что перечисленные в первой части требования к криптосистемам (критерии оценки секретных систем) не могут выполняться одновременно. <ref name=":5" />

Предложена структура алгебры секретных систем (алгебры шифров), с двумя основными операциями комбинирования шифров: взвешенная сумма (сложение шифров с весами в виде вероятностей выбора шифра) и произведение (последовательное применение). Новые шифры предлагается получать комбинированием взвешенной суммы и произведения различных шифров. <ref name=":1" />

=== Теоретическая секретность ===
Во второй части статьи определено понятие [[Криптографическая стойкость|совершено секретной криптосистемы]], как системы, где исходное сообщение и криптограмма [[Независимость (теория вероятностей)|статистически независимы]]. <ref name=":3">{{Книга|автор=Варфоломеев А.А.|заглавие=Современная прикладная криптография: Учеб. пособие.|ссылка=http://web-local.rudn.ru/web-local/uem/iop_pdf/32-Varfolomeev.pdf|ответственный=|издание=|место=М.|издательство=РУДН|год=2008|страницы=8, 51—56|страниц=218|isbn=}}</ref><ref name=":8" /> Указано, что у графа совершенно секретной системы равны числа сообщений, ключей и криптограмм, причем каждое сообщение соединено с каждой криптограммой только одной линией и все ключи равновероятны. <ref name=":2" />

Доказана совершенная секретность [[Шифр Вернама|шифра Вернама]] ([[Шифр Вернама|одноразового шифроблокнота]]). <ref name=":8" />

Показана ненадежность некоторых шифров на примере [[Шифр Цезаря|шифра Цезаря]], в котором частоты появления символов, соответствующих символам сообщения не зависят от ключа. <ref name=":10" />

При рассмотрении случайного шифра было введено понятие [[Расстояние единственности|расстояния единственности]] как минимальное число символов криптограммы, с помощью которых ключ может быть определен однозначно. <ref name=":3" /><ref name=":6">{{Книга|автор=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}}</ref>

Отмечена проблема [[Избыточность языка|избыточности языка]], состоящая в том, что избыточность, представляющая собой набор условий, наложенных на символы сообщения, дает дополнительные возможности при дешифровке криптограммы противником. <ref name=":0" /><ref name=":4" />

Введено понятие идеальной секретной системы, которая имеет бесконечное [[расстояние единственности]]. Частным (более строгим) случаем таких систем являются совершено секретные системы. Характерной особенностью является то, что идеальная криптосистема сохраняет неопределенность даже при успешной операции дешифрования противником.<ref name=":6" />

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

В третьей части статьи определена рабочая характеристика системы как функция, зависящая от числа известных символом криптограммы и равная среднему объему работы, затраченному на нахождение ключа шифрования. <ref name=":3" /> Эта функция имеет некоторые сходства с понятием [[Вычислительная сложность|вычислительной сложности алгоритма]]. <ref>{{Книга|автор=Dominic Welsh|заглавие=Codes and Cryptography|ответственный=|издание=|место=Oxford|издательство=Clarendon Press|год=1988|страницы=121—122|страниц=257|isbn=0 19 853287 3}}</ref>

Рассмотрена возможность раскрытия шифра с помощью [[Статистика|статистического анализа]] символов и метода вероятных слов. Согласно описанной в статье теории, противник в процессе дешифрования может использовать некоторые статистические свойства языка. Показано, что при знании языка исходного сообщения для некоторых шифров возможно раскрыть текст, состоящий из нескольких десятков символов. В качестве примера часто встречающихся в [[Английский язык|английском языке]] слов автор приводит "[[Артикль|the]]", "[[:en:Conjunction_(grammar)|and]]", "[[:en:That|that]]" и слог "[[:en:Suffix|-tion]]", а в качестве сочетания символов "[[Qu (диграф)|qu]]". Это напрямую связанно с вопросом об [[Избыточность языка|избыточности языка]], рассмотренным во второй части статьи. <ref name=":0" /> <ref name=":4">{{Книга|автор=В. В. Иванов|заглавие=Избранные труды по семиотике и истории культуры.|ответственный=|издание=|место=М.|издательство=Языки славянских культур|год=2007|том=4: Знаковые системы культуры, искусства и науки|страницы=21—33|страниц=792|isbn=5-9551-0207-8}}</ref>

Предложено использовать несколько слоев (циклов) замен и перестановок, что впоследствии было использовано при построении [[Блочный шифр|блочных шифров]]. В оригинальной статье Шеннон называет эти методы "confusion" (запутывание) соответствует замене и "diffusion" (рассеивание) ответствует перестановке. <ref name=":8" />


== См. также ==
== См. также ==

Версия от 14:37, 4 ноября 2016

Теория связи в секретных системах
Communication Theory of Secrecy Systems
Автор Шеннон К.
Жанр Криптология
Язык оригинала английский
Оригинал издан 1949
Издатель John Wiley & Sons, США
Страниц 59
Текст на стороннем сайте

Теория связи в секретных системах (англ. Communication Theory of Secrecy Systems, 1949 год) — статья Клода Шеннона, опубликованная в журнале «The Bell System Technical Journal» в 1948 году. Данная статья послужила началом обширных исследований в теории кодирования и передачи информации, и, по всеобщему мнению, придала криптографии статус науки, а также ознаменовала наступление эры научной криптологии с секретными ключами. В статье определены фундаментальные понятия теории криптографии.

Об авторе

Клод Э́лвуд Ше́ннон (англ. Claude Elwood Shannon) — американский математик и инженер, основатель теории информации, автор многих книг и статей по кибернетике.

История

В 1940-х годах Клод Шеннон проводил исследования в Лабораториях Белла, связанные с изучением и совершенствованием процессов управления огнем и сглаживанию данных. Работы Шеннона были акцентированы на теории информации и криптографии. [1][2]

В процессе этих исследований 1 сентября 1945 года выходит секретный доклад Шеннона "Математическая теория криптографии" (англ. A Mathematical Theory of Cryptography [1]). Среди тех, кому был доступен данный доклад, были L. Espenschied, H. S. Black, F. B. Llewellyn, Гарри Найквист, D. M. Oliver, R. K. Potter, C. B. H. Feldman, R. C. Mathes, Ральф Хартли, Джон Робинсон Пирс, H. W. Bode, R. L. Dietzold, L. A. MacCall, Уолтер Шухарт и S. A. Schelkunoff. [3][4]

В 1948 году была опубликована работа Шеннона "Математическая теория связи" (англ. A Mathematical Theory of Communication) , которая считается основополагающей для теории информации. [1]

Автор характеризовал свои работы "Математическая теория криптографии" и «"Математическая теория связи" так [5]:

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

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

Содержание

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

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

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

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

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

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

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

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

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

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

Доказана совершенная секретность шифра Вернама (одноразового шифроблокнота). [6]

Показана ненадежность некоторых шифров на примере шифра Цезаря, в котором частоты появления символов, соответствующих символам сообщения не зависят от ключа. [17]

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

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

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

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

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

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

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

См. также

Примечания

  1. ↑ 1 2 3 4 В.И. Левин. К.Э. ШЕННОН И СОВРЕМЕННАЯ НАУКА (рус.) // Вестник ТГТУ : статья. — 2008. — Т. 14, № 3. — С. 703-725. — ISSN 0136-5835.
  2. ↑ Eugene Chiu, Jocelyn Lin, Brok Mcferron, Noshirwan Petigara, Satwiksai Seshasai. Mathematical Theory of Claude Shannon (англ.).
  3. ↑ Whitfield Diffie. Preface to Claue Shannon’s A Mathematical Theory of Cryptography (англ.) // IACR : статья. — 2015. — December.
  4. ↑ Claude Shannon. A Mathematical Theory of Cryptography (англ.). — 1945. — 1 September.
  5. ↑ David Khan. The Godebreakers. — MacMillan. — 1967. — ISBN 0722151497.
  6. ↑ 1 2 3 4 Ошибка в сносках?: Неверный тег <ref>; для сносок :8 не указан текст
  7. ↑ Siu-Wai Ho, Terence H. Chan, Alex Grant, Chinthani Uduwerelle. Error-Free Perfect-Secrecy Systems (англ.) // Information Theory Proceedings (ISIT), 2011 IEEE International Symposium on : статья. — 2011. — P. 1. — ISSN 978-1-4577-0596-0. — doi:10.1109/ISIT.2011.6033797.
  8. ↑ Тилборг ван Х.К.А. Основы криптологии. Профессиональное руководство и интерактивный учебник.. — 1-е изд. — М.: Мир, 2006. — С. 11. — 471 с. — ISBN 5-03-003639-3.
  9. ↑ 1 2 Аграновский А.В., Хади Р.А. Практическая криптография: алгоритмы и их программирование. — М.: Солон-Пресс, 2009. — С. 15—19, 69—73. — 256 с. — ISBN 5-98003-002-6.
  10. ↑ M. E. Hellman. An Extension of the Shannon Theory Approach to Cryptography (англ.) // IEEE Trans. on Info. Theory : статья. — 1977. — May (no. IT-23). — P. 289—290.
  11. ↑ 1 2 Tatiana Diyachenko. STATISTICAL ANALYSIS OF THE UNIFORMITY OF CRYPTOGRAMS IN THE DYNAMIC CRYPTOSYSTEMS (англ.) // Thesis CENTRIA UNIVERSITY OF APPLIED SCIENCES : статья. — 2015. — November. — P. 10, 11.
  12. ↑ Бабаш А.В., Шанкин Г.П. Криптография. — М.: Солон-Пресс, 2007. — С. 82. — 512 с. — ISBN 5-93455-135-3.
  13. ↑ В. В. Ященко, Н. П. Варновский, Ю. В. Нестеренко, Г. А. Кабатянский, П. Н. Девянин, В. Г. Проскурин, А. В. Черемушкин, П. А. Гырдымов, А.Ю. Зубов, А. В. Зязин, В. Н. Овчинников, М. И. Анохин. Введение в криптографию / под ред. В. В. Ященко. — 4. — М.: МЦНМО, 2012. — С. 13, 17—18. — 348 с. — ISBN 978-5-4439-0026-1.
  14. ↑ Gabriela Moise. Knowledge-Based Schema for S-box Design (англ.) // International Journal of Research and Reviews in Applied Sciences : статья. — 2011. — September (no. 8(3)). — P. 296.
  15. ↑ 1 2 Τσιάκης, Θεοδόσιος. Η εφαρμοσμένη κρυπτογραφία ως τυπική μέθοδος και μοντέλο για την ασφάλεια των ηλεκτρονικών συναλλαγών (gr) // Πανεπιστήμιο Μακεδονίας, Θεσσαλονίκη : диссертация. — 2005. — С. 153—154.
  16. ↑ 1 2 3 Варфоломеев А.А. Современная прикладная криптография: Учеб. пособие.. — М.: РУДН, 2008. — С. 8, 51—56. — 218 с.
  17. ↑ Ошибка в сносках?: Неверный тег <ref>; для сносок :10 не указан текст
  18. ↑ 1 2 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.
  19. ↑ 1 2 В. В. Иванов. Избранные труды по семиотике и истории культуры.. — М.: Языки славянских культур, 2007. — Т. 4: Знаковые системы культуры, искусства и науки. — С. 21—33. — 792 с. — ISBN 5-9551-0207-8.
  20. ↑ Dominic Welsh. Codes and Cryptography. — Oxford: Clarendon Press, 1988. — С. 121—122. — 257 с. — ISBN 0 19 853287 3.

Ссылки

Источник — https://ru.wikipedia.org/w/index.php?title=Теория_связи_в_секретных_системах&oldid=81698968