Клод Шеннон - Теория связи в секретных системах, страница 3

Наше ограничение обычно в криптографических исследованиях. Оно являетсяпессимистичным, но безопасно, и в конечном счете реалистично, так как можно ожидать, чтопротивник рано или поздно раскроет любую секретную систему. Поэтому даже в томслучае, когда разработана совершенно новая система, так что противник не может приписатьей никаких априорных вероятностей, если только он ее уже не раскрыл, нужно иметь в видуего возможную осведомленность.Эта ситуация аналогична ситуации, возникающей в теории игр, где предполагается,что партнер «обнаруживает» используемую стратегию игры. В обоих случаях этопредположение служит для более четкого описания сведений, которыми располагаетпротивная сторона.Второе возможное возражение против нашего определения секретной системысостоит в том, что в нем не принимаются в расчет используемые обычно на практике вставкив сообщение посторонних нулевых знаков и использование многократных подстановок.

Втаких случаях для данного сообщения и ключа имеется не единственная криптограмма и7шифровальщик может выбрать по своему желанию одну из нескольких различныхкриптограмм. Эту ситуацию можно было бы рассмотреть, но это только внесло быдополнительные усложнения на данном этапе рассуждений без существенного изменениякаких-либо из основных выводов.Если сообщения создаются марковским процессом, то вероятности разныхсообщений определяются структурой этого марковского процесса. Однако подойдем квопросу с более общей точки зрения и будем трактовать сообщения просто как абстрактноемножество объектов, которым приписаны вероятности, причем эти объекты не обязательносостоят из последовательностей букв и не обязательно создаются марковским процессом.Следует подчеркнуть, что далее во всех случаях секретная система означает не одно,а целое множество отображений. После того как выбран ключ, используется только одно изэтих отображений и отсюда можно было бы прийти к определению секретной системы какединственного преобразования языка.

Однако противник не знает, какой ключ выбран, иостальные возможные ключи столь же важны для него, как и истинный. Именносуществование этих других возможных ключей и придает системе секретность. Так как мыинтересуемся в первую очередь секретностью, то вынуждены предпочесть данное намиопределение понятия секретной системы. Тип ситуации, когда остальные возможности также важны, как и осуществившаяся, часто встречается в стратегических играх. Ходшахматной игры в большой степени контролируется угрозами, которые не осуществляются.Нечто подобное представляет из себя «фактическое существование» нереализованныхвозможностей в теории игр.Следует отметить, что система, состоящая из единственной операции над языком,представляет собой при нашем определении вырожденный тип секретной системы.

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

Процесс дешифрования для противникапредставляет собой попытку определить сообщение (или конкретный ключ), имея враспоряжении только криптограмму и априорные вероятности различных ключей исообщений.Существует много трудных эпистемологических вопросов, связанных с теориейсекретности, или вернее с любой теорией, связанной с реальным применением вопросовтеории вероятностей (так обстоит дело, в частности, с априорными вероятностями, теоремойБайеса и т.д.). Трактуемая абстрактно теория вероятности может быть изложена на строгихлогических основах с использованием современной теории меры. Однако в применениях кфизическим ситуациям, особенно когда дело касается «субъективных» вероятностей инеповторимых экспериментов, возникают многочисленные вопросы, связанные с логическимобоснованием. Например, при нашем подходе к проблеме секретности допускается, чтоаприорные вероятности различных ключей и сообщений известны шифровальщикупротивника, но как он может определить их эффективным способом даже при использованиивсех своих сведений о данной обстановке?Можно создать искусственные криптографические ситуации типа «урны иигральной кости», в которых априорные вероятности имеют вполне определенный смысл иидеализация, использованная здесь, является наверняка подходящей.

Но в других случаях,которые можно себе представить, например, при перехвате сообщений, передаваемых между8собой марсианами, высадившимися на Землю, априорные вероятности были бы настольконеопределенными, что не имели бы никакого значения.Наиболее часто встречающиеся на практике криптографические задачи лежат где-томежду этими крайними пределами. Шифровальщик противника может иметь желаниеразделить возможные сообщения на категории «приемлемых», «возможных, номалоправдоподобных» и «неприемлемых», но чувствуется, что более подробноеподразделение не имело бы смысла.К счастью, на практике только очень большие ошибки в априорных вероятностяхключей и сообщений могут вызвать заметные ошибки в важных параметрах. Этопроисходит из-за того, что число сообщений и криптограмм ведет себя какэкспоненциальная функция, а измеряется логарифмической мерой.3.

Способы изображения систем.Секретная система, в том виде как она определена выше, может быть изображенаразличными способами. Один из них (удобный для целей иллюстрации) используетлинейные схемы, изображенные на рис. 2 и рис. 4. Возможные сообщения представляютсяточками слева, а возможные криптограммы – точками справа. Если некоторый ключ,скажем, ключ 1, отображает сообщение M2 в криптограмму Е2, то M2 и E2 соединяютсялинией, обозначенной значком 1 и т.д. Для каждого ключа из каждого сообщения должнавыходить ровно одна линия. Если это же верно и для каждой криптограммы, скажем, чтосистема является замкнутой.M11E13E12M22E21M133M331222E31M213E31 2M4E23E4Замкнутая системаНезамкнутая системаРис.2. Схемы простых систем.Более общий способ описания системы состоит в задании операции, с помощьюкоторой, применяя к сообщению произвольный ключ, можно получить криптограмму.Аналогично неявным образом можно определить вероятности различных ключей или спомощью задания способа выбора ключей, или с помощью описания сведений о том, какобычно выбирает ключи противник.

Вероятности сообщений определяются простопосредством изложения наших априорных сведений о языке противника, тактическойобстановке (которая будет влиять на возможное содержание сообщений) и любойспециальной информации, касающейся криптограммы.4. Примеры секретных систем.В данном разделе рассматриваются несколько примеров шифров. В дальнейшем вцелях иллюстрации будем часто ссылаться на эти примеры.9Шифр простой подстановки.В таком шифре производится замена каждой буквы сообщения на некоторыйопределенный символ (обычно также на букву). Таким образом, сообщениеМ = m1m2m3m4…,где m1,m2,...

– последовательные буквы, переходит вE = e1e2e3e4... = f (m1) f (m2) f (m3) f (m4)…,причем функция f (m) имеет обратную функцию. Ключ является просто перестановкойалфавита (если буквы заменяются на буквы), например,XGUACDTBFHRSLMQVYZWIEJOKNP.Первая буква – X заменяет букву A, G заменяет B и т.д.Перестановка с фиксированным периодом d.В этом случае сообщение делится на группы символов длины d и к каждой группеприменяется одна и та же перестановка. Эта перестановка является ключом; она может бытьзадана некоторой перестановкой первых d целых чисел.Таким образом, для d = 5 в качестве перестановки можно взять 23154.

Это будетозначать, чтоm1m2m3m4m5m6m7m8m9m10...переходит вm2m3m1m5m4m7m8m6m10m9...Последовательное применение двух или более перестановок будет называться составнойперестановкой. Если периоды этих перестановок равны d1,...,ds, то, очевидно, в результатеполучится перестановка периода d, где d – наименьшее общее кратное d1,...,ds.Шифр Виженера и его варианты.В шифре Виженера ключ задается набором из d букв. Такие наборыподписываются с повторением под сообщением и полученные две последовательностискладываются по модулю 26 (каждая буква рассматриваемого алфавита нумеруется отА = 0 до Z = 25).Таким образом,ei = mi + ki (mod 26),где ki – буква ключа, полученная сокращением числа i по модулю d.

Например, спомощью ключа GAH получаемСообщение NПовторяемый ключ GКриптограмма TOAOWHDIGOSASTHAHGNEAEШифр Виженера с периодом 1 называется шифром Цезаря. Он представляет собойпростую подстановку, в которой каждая буква сообщения М сдвигается вперед нафиксированное число мест по алфавиту. Это число и является ключом; оно может бытьлюбым от 0 до 25. Так называемый шифр Бофора (Beaufort) и видоизмененный шифрБофора подобны шифру Виженера. В них сообщения зашифровываются с помощьюравенствei = ki – mi (mod 26) иei = mi – ki (mod 26)соответственно. Шифр Бофора с периодом 1 называется обратным шифром Цезаря.10Повторное применение двух или более шифров Виженера будет называтьсясоставным шифром Виженера.