Клод Шеннон. Теория связи в секретных системах. Рабочая характеристика.
После того как объем перехваченного текста превзойдет точку единственности, обычно будет существовать единственное решение криптограммы. Задача криптографического анализа и состоит в выделении этого единственного решения, имеющего высокую вероятность. До того как достигнута точка единственности, задача криптографического анализа состоит в выделении всех возможных решений с большой (по сравнению с остальными решениями), вероятностью и в определении вероятностей этих решений.
Хотя в принципе всегда можно найти эти решения (например, испытывая все возможные ключи), но для различных систем нужно будет затратить весьма различный объем работы. Средний объем работы, необходимой для определения ключа, если криптограмма имеет N букв, W(N) измеренное, скажем, в человеко-часах, можно назвать рабочей характеристикой системы. Это среднее значение берется по всем сообщениям и всем ключам с соответствующими им вероятностями. Функция W(N) измеряет количество "практической секретности" в данной системе.
Для простой подстановки, примененной к английскому языку, рабочая характеристика и характеристика ненадежности будут выглядеть примерно такими, как показано на рис. 12. Пунктирная часть кривой относится к области, где имеется несколько возможных решений и все они должны быть определены. Для сплошной части кривой после точки единственности существует, вообще говоря, только одно решение, но если необходимые данные имеются в минимальном количестве, то для нахождения этого решения нужно проделать большую работу. По мере увеличения количества данных объем необходимой работы быстро уменьшается, стремясь к некоторому асимптотическому значению, которое достигается, когда дополнительные данные уже не уменьшают объема работы.
По существу, такое же поведение кривых, как показано на рис. 12, можно ожидать для любого типа секретной системы, в которой ненадежность стремится к нулю. Однако масштаб количества требуемых человеко-часов будет сильно отличаться для разных типов шифров, даже тогда, когда кривые функции HE(M) почти совпадают. Например, шифр Виженера или составной шифр Виженера с тем же самым объемом ключа имели бы намного лучшие (т. е. более высокие) рабочие характеристики, чем простая подстановка. В хорошей (в практическом смысле) секретной системе график W(N) остается достаточно высоким вплоть до того числа букв, которое намереваются передавать с помощью данного ключа, что не дает противнику практической возможности найти решение или же задерживает нахождение решения до тех пор, пока содержащаяся в нем информация не устареет.
В следующем разделе будут рассмотрены способы, которые позволяют удерживать функцию W(N) на достаточно высоком уровне даже в тех случаях, когда значение HE(K) практически равно нулю. Эта проблема по существу относится к типу "минимаксных" проблем, как всегда бывает в случае борьбы двух разумных соперников. При создании хорошего шифра необходимо максимизировать минимальный объем работы, которую должен проделать противник для нахождения решения. Для этого недостаточно просто быть уверенным, что никаким из обычных криптографических методов нельзя раскрыть шифр. Надо быть уверенным, что этого нельзя добиться вообще никаким методом. И действительно, это оказалось слабой стороной многих секретных систем. Спроектированные так, чтобы быть недоступными для всех известных методов решения, они затем приводили к созданию новых криптографических методов, делавших возможным их раскрытие.
Проблема создания хорошего шифра является по существу проблемой нахождения наиболее сложных задач, удовлетворяющих определенным условиям. Это довольно нетривиальная ситуация, так как обычно в заданной области отыскивают простые и легко разрешимые задачи.
Как можно быть уверенным в том, что неидеальная система, которая необходимо имеет единственное решение для достаточно большого N, потребует большого объема работы для нахождения решения при любом методе анализа? Имеются два подхода к решению этого вопроса. 1) Можно изучить возможные методы решения, которыми пользуется противник, и попытаться описать их в достаточно общих терминах, с тем чтобы включить все методы, которые могли бы быть им использованы. Тогда наша система будет недоступной для этого "общего" метода решения. 2) Можно составить наш шифр таким образом, чтобы решение его было эквивалентно (или включало в себя) решению некоторой проблемы, про которую, известно, что для ее решения требуется большой объем работ. Так, если бы мы смогли показать, что нахождение решения некоторой секретной системы требует по меньшей мере столько же работы, сколько нужно для решения нераспадающейся системы уравнений с большим числом неизвестных, то можно получить некоторого рода нижнюю оценку для рабочей характеристики.
Следующие три раздела статьи посвящены этому вопросу. Трудно определить нужные понятия с точностью, достаточной для получения результатов в форме математических теорем, подумается, что выводы, полученные в форме общих принципов, остаются справедливыми.
[Титульный лист] [Предыдущий раздел] [Следующий раздел]
[Начало осмотра] [Что нового] [Статьи] [Выпуски в "Байтах"] [Что скачать] [Криптоалгоритмы] [Глоссарий] [Ссылки] [Гостевая книга] [Форум] [Напиши мне]Версия от 05.01.02. (c) 2002 Андрей Винокуров.
