Клод Шеннон. Теория связи в секретных системах. Общие замечания о решении криптограмм.

22. Общие замечания о решении криптограмм.

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

Предположим, например, что имеется ключ с 26! возможностями, (что составляет около 26.3 десятичных единиц), т.е. того же самого объема, что и для простой подстановки в английском языке. Этот ключ при любом приемлемом способе измерения является малым ключом. Он может быть выписан на клочке бумаги, и его можно выучить в течение пяти минут. Его можно записать на 27-разрядном десятичном регистре или же на 88-ми разрядном двоичном регистре.

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

210²⁶/2 60²2436510⁶ =  3 10¹² лет.

Другими словами, даже для малого ключа метод полной системы испытаний и ошибок не может быть использован на практике для решения криптограмм, исключая тот случай, когда ключ крайне мал, например, в шифре Цезаря, где имеются только 26 возможностей (или 1,4 десятичных единицы). Метод испытаний и ошибок, обычно используемый в криптографии, несколько отличен от описанного выше, или же при использовании такого метода его дополняют с помощью других средств. Если бы кто-либо имел секретную систему, которая требует для раскрытия применения полной системы испытаний и ошибок, то он мог бы чувствовать себя в полной безопасности. Такая система получается, если исходные смысловые сообщения, состоящие все, скажем, из 1000 букв, выбираются случайным образом из множества всех 1000-буквенных последовательностей. Если к такому языку применить любой из простых шифров, то окажется, что нельзя было бы существенно улучшить метод полной системы испытаний и ошибок.

Методы, фактически используемые в криптографии, часто включают в себя метод испытаний и ошибок, но несколько отличного типа. Во-первых, испытания проводятся, начиная с более вероятных гипотез, и, во-вторых, каждое испытание относится к большой группе ключей, а не к единственному ключу. Так, пространство ключей можно разделить, скажем, на 10 подмножеств, содержащих примерно по одинаковому числу ключей. С помощью не более чем десяти испытаний находят правильное подмножество. Это подмножество делится на несколько вторичных подмножеств и процесс повторяется. Для нашего примера с объемом ключа 26!210²⁶ можно ожидать около 265 = 130 испытаний вместо 10²⁶ при полной системе испытаний и ошибок. Этот результат может быть улучшен, если выбирать сначала наиболее вероятные из подмножеств. Если разделение производить на два подмножества (наилучший способ минимизировать число испытаний), то потребуется только 88 испытаний. В то время как метод полной системы испытаний и ошибок требует числа испытаний, равного по порядку числу ключей, испытания с разделением на подмножества требуют только число испытаний по порядку, равное объему ключа в битах.

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

.

Если каждая проверка имеет S возможных исходов, каждый из которых соответствует нахождению ключа в одном из S равновероятных подмножеств, то

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

,

или приблизительно 10^–25 бит информации. Разделение на S равновероятных подмножеств увеличивает количество информации, получаемой от одного испытания, до log S, и среднее число испытаний равно полной информации, которая должна быть получена, т.е. H(K), деленной на log S.

Вопрос, затронутый здесь, имеет много общего с различными задачами о взвешивании монет, рассматривавшимися в последнее время. Типичным является следующий пример. Известно, что среди 27 монет одна фальшивая и она немного легче остальных. Требуется найти фальшивую монету с помощью ряда взвешиваний на аптекарских весах. Чему равно наименьшее число необходимых для этого взвешиваний? Правильный ответ – 3. Он получается, если сначала разделить все монеты на 3 группы по 9 в каждой. Две из этих групп сравниваются на весах. Три возможных результата определяют те 9 монет, среди которых находится фальшивая. Эти 9 монет снова делятся на 3 группы по 3 монеты и процесс продолжается. Множество монет соответствует множеству ключей, фальшивая монета – правильному ключу, а процесс взвешивания – испытанию или проверке. Первоначальная неопределенность равна 27 бит, и каждое испытание дает log₂3 бит информации. Таким образом, когда нет "диофантовых трудностей", то достаточно log₂27/log₂3 испытаний.

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

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

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

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

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