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

Больше того, даже тогда, когда у противника достаточно материала, требуется гораздобольший объем вычислительной работы, так как избыточность распылена по большомучислу индивидуальных статистик. Примером распыления статистик может служить«усреднение» сообщения M = m1m2m3…:syn = å mn + i (mod 26) ,i =1где складываются s последовательных букв сообщения для получения буквы yn.

Можнопоказать, что избыточность в последовательности y та же, что и в последовательности m,но ее структура распылена. Так, частоты разных букв в последовательности y меньшеразличаются, чем в последовательности m; то же самое можно сказать о частотах диграмм ит.д.. Конечно, любая обратимая операция, которая выдает на выходе одну букву на каждуюпоступающую букву и не имеет бесконечной «памяти», дает на выходе ту же избыточность,44что и на входе.

Статистические характеристики текста не могут быть устранены без егосжатия, но они могут быть размазаны.Метод «запутывания» состоит в том, что соотношения между простыми статистиками в пространстве криптограмм и простыми подмножествами в пространстве ключейделаются весьма сложными и беспорядочными. Для случая простой подстановки легкоописать ограничения на ключи, налагаемые частотами букв в криптограммах. Если этиограничения очень сложны и беспорядочны, то противник, может быть, еще и можетоценить, скажем, статистику S1, которая ограничивает некоторую область в пространствеключей. Однако эта статистика выделяет некоторую весьма сложную область R1 впространстве ключей, возможно «свернутую» несколько раз, так что противнику трудновоспользоваться полученными результатами статистического анализа. Далее, втораястатистика S2 ограничивает ключи областью R2 и, следовательно, пересечением этихобластей, но это не облегчает дела, так как трудно определить, что же именно представляетсобой это пересечение.Чтобы несколько уточнить эту мысль, предположим, что в пространстве ключейимеются некоторые «естественные координаты» k1,k2,…,kp, которые противник хочетопределить.

Он измеряет, скажем, множество статистик S1,…,Sn; пусть этого множествастатистик достаточно для определения ki. Однако при использовании метода запутыванияуравнения, связывающие эти переменные, очень сложны и зависят от многих параметров.Скажем, имеетсяf1 ( k1,..., k p ) = s1 ,...........................fn ( k1,..., k p ) = sn ,где каждая функция fi зависит от всех ki.

Требуется выполнить очень трудную работу:решить эту систему совместно. В простых случаях (без запутывания) все функции fi (илипо крайней мере некоторые из них) зависят лишь от небольшого числа ki. Тогда сначаларешают более простые уравнения, получая некоторые ki, а затем подставляют их в болеесложные уравнения.Вывод, который можно сделать из приведенных рассуждений, состоит в том, что дляулучшения секретной системы нужно применить тот или иной из рассмотренных методовили оба вместе.24. Метод вероятных слов.Один из наиболее результативных приемов раскрытия шифров заключается виспользовании вероятных слов. Вероятные слова – это слова или выражения, которыеможно ожидать в частном сообщении вследствие того, что они характерны для данногоисточника сообщений.

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

Если другие частикриптограммы становятся при этом понятными, то предположение подтверждается.Имеется мало шифров классического типа, которые при небольшом ключе могутоставаться долго не раскрытыми методом анализа вероятных слов. Рассмотрение этогометода позволяет выработать некоторый способ проверки качества шифров, который можнобыло бы назвать «проверкой кислотой», как в ювелирном деле. Он применим только кшифрам с малым ключом (меньше 50 десятичных единиц), причем лишь тогда, когда шифры45применяются к естественным языкам и в них не используется идеальный метод увеличениясекретности.

Метод «проверки кислотой» состоит в следующем. Решается вопрос:насколько трудно определить ключ или часть ключа, зная небольшую выборку из сообщенияи соответствующую ей криптограмму? Любая система, в которой это можно легко сделать,не может быть очень трудно раскрываемой, так как шифровальщик всегда может применятьметод вероятных слов в сочетании с методом испытаний и ошибок, до тех пор, пока не будетполучено правильное решение.Условие, наложенное нами на объем ключа, делает количество испытаний малым, аусловие относительно того, что система не должна быть идеальной, необходимо, так какидеальные системы автоматически дают методы проверки правильности решения.

Наличие вкриптограмме вероятных слов и фраз следует из предположения об использованииестественных языков.Заметим, что требование, чтобы раскрытие шифра при этих условиях было трудным,само по себе не противоречит требованию простоты процессов зашифрования и расшифрования. Используя функциональные обозначения, запишем процесс зашифрования следующимобразом:E = f(K,M),а процесс расшифрования –M = g(K,E).Обе эти операции могут быть простыми операциями над соответствующими аргументами, вто время как третья операция, записанная в видеK = h(M,E),может не быть простой.Укажем, что при исследовании новых секретных систем один из наилучших методових раскрытия состоит в рассмотрении того, как можно было бы определить ключ, еслиимеется достаточный объем сообщений M и соответствующая криптограмма E.Идея метода запутывания может быть (и должна быть) использована для созданиятрудностей противнику, если он применит метод вероятных слов.

Если шифровальщикупротивника даны (или он принял как данные) сообщение M = m1m2…ms и криптограммаE = e1e2…es, то он может составить уравнения для различных элементов ключа k1…kr (аименно уравнение зашифрования):e1 = f1 ( m1,..., ms ; k1 ,..., kr ),e2 = f2 ( m1 ,..., ms ; k1,..., kr ),...........................................e s = fs ( m1,..., ms ; k1 ,..., kr ).Предположим, что в этих уравнениях известно все, за исключением ki. Поэтомукаждое из этих уравнений должно зависеть сложным образом от ki и включать многие изних. В противном случае противник мог бы решить простые уравнения и, подставиврезультаты в более сложные уравнения, решить и их.С точки зрения повышения запутанности желательно, чтобы функции fi содержалинесколько mi особенно если последние не являются смежными и, значит, менее коррелированы.

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

Далее, желательна зависимость отнескольких несвязанных mi, если можно допустить некоторое разрастание ошибок. Все три46соображения, разобранные в этих разделах, подводят нас к рассмотрению метода «перемешивания».25. Перемешивание.В некоторых разделах теории вероятностей очень ценным оказалось понятиеперемешивания.

Пусть имеется пространство с мерой (или вероятностное пространство) Wи некоторое сохраняющее меру отображение F этого пространства в само себя, т.е. такоеотображение, что мера отображенной области FR равна мере исходной области R.Отображение называется перемешиванием, если для любой функции, определенной напространстве, и для любой области R интеграл от этой функции по области F nR стремитсяпри n ® ¥ к интегралу от функции по всему пространству W, умноженному на объемобласти R.

Это означает, что первоначальная область R перемешивается с равномернойплотностью по всему пространству, если F применяется большое число раз. В общемслучае F nR становится областью, состоящей из большого числа тонких волокон,распределенных по всему пространству W. При увеличении n волокна становятся тоньше,а их плотность приближается к постоянной.Перемешивание в этом точном смысле может осуществляться лишь в пространствахс бесконечным числом точек, так как в пространстве с конечным числом точек такоеотображение должно быть периодическим. Однако можно понимать под перемешиванием,грубо говоря, такое отображение, которое распределяет любую разумно расположеннуюобласть довольно равномерно по всему пространству.

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