Клод Шеннон. Теория связи в секретных системах. Метод вероятных слов.

24. Метод вероятных слов.

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

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

Имеется мало шифров классического типа, которые при небольшом ключе могут оставаться долго не раскрытыми методом анализа вероятных слов. Рассмотрение этого метода позволяет выработать некоторый способ проверки качества шифров, который можно было бы назвать "проверкой кислотой", как в ювелирном деле. Он применим только к шифрам с малым ключом (меньше 50 десятичных единиц), причем лишь тогда, когда шифры применяются к естественным языкам и в них не используется идеальный метод увеличения секретности. Метод "проверки кислотой" состоит в следующем. Решается вопрос: насколько трудно определить ключ или часть ключа, зная небольшую выборку из сообщения и соответствующую ей криптограмму? Любая система, в которой это можно легко сделать, не может быть очень трудно раскрываемой, так как шифровальщик всегда может применять метод вероятных слов в сочетании с методом испытаний и ошибок, до тех пор, пока не будет получено правильное решение.

Условие, наложенное нами на объем ключа, делает количество испытаний малым, а условие относительно того, что система не должна быть идеальной, необходимо, так как идеальные системы автоматически дают методы проверки правильности решения. Наличие в криптограмме вероятных слов и фраз следует из предположения об использовании естественных языков.

Заметим, что требование, чтобы раскрытие шифра при этих условиях было трудным, само по себе не противоречит требованию простоты процессов зашифрования и расшифрования. Используя функциональные обозначения, запишем процесс зашифрования следующим образом:

E = f(K,M),

а процесс расшифрования –

M = g(K,E).

Обе эти операции могут быть простыми операциями над соответствующими аргументами, в то время как третья операция, записанная в виде

K = h(M,E),

может не быть простой.

Укажем, что при исследовании новых секретных систем один из наилучших методов их раскрытия состоит в рассмотрении того, как можно было бы определить ключ, если имеется достаточный объем сообщений M и соответствующа криптограмма E.

Идея метода запутывания может быть (и должна быть) использована для создания трудностей противнику, если он применит метод вероятных слов. Если шифровальщику противника даны (или он принял как данные) сообщение M = m₁m₂...m_s и криптограмма E = e₁e₂...e_s, то он может составить уравнения для различных элементов ключа k₁...k_r (а именно уравнение зашифрования):

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

С точки зрения повышения запутанности желательно, чтобы функции f_i содержали несколько m_i особенно если последние не являются смежными и, значит, менее коррелированы. Однако система при этом приобретает нежелательное свойство разрастания ошибок, так как тогда каждое e_i будет, вообще говоря, действовать на несколько m_i при расшифровании, и ошибка будет распространена на все эти m_i.

Таким образом, для того, чтобы рабочая характеристика секретной системы была высокой, для получения любой буквы криптограммы должна быть использована как можно большая часть ключа с применением метода запутывания. Далее, желательна зависимость от нескольких несвязанных m_i, если можно допустить некоторое разрастание ошибок. Все три соображения, разобранные в этих разделах, подводят нас к рассмотрению метода "перемешивания".

[Титульный лист] [Предыдущий раздел] [Следующий раздел]
[Начало осмотра] [Что нового] [Статьи] [Выпуски в "Байтах"] [Что скачать] [Криптоалгоритмы] [Глоссарий] [Ссылки] [Гостевая книга] [Форум] [Напиши мне]

Версия от 05.01.02. (c) 2002 Андрей Винокуров.