Статистичний опис джерела відкритих текстів

Сложность обработки.Время, нужное для проведения вскрытия. Часто называется коэффициентом работы.

3. Требования к памяти. Объем памяти, необходимый для вскрытия.

В качестве эмпирического метода сложность вскрытия определяется по максимальному из этих трех коэффициентов. Ряд операций вскрытия предполагают взаимосвязь коэффициентов: более быстрое вскрытие возможно за счет увеличения требований к памяти.

Сложность выражается порядком величины. Если сложность обработки для данного алгоритма составляет 2¹²⁸, то 2¹²⁸ операций требуется для вскрытия алгоритма. (Эти операции могут быть сложными и длительными.) Так, если предполагается, что ваши вычислительные мощности способны выполнять миллион операций в секунду, и вы используете для решения задачи миллион параллельных процессоров, получение ключа займет у вас свыше 10¹⁹ лет, что в миллиард раз превышает время существования вселенной.

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

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

Алиса на рис. 1.1 играет роль конечного или бесконечного источника открытых текстов над алфавитом, например, над. Источник можно описать как конечную (соответственно бесконечную) последовательность случайных переменных, т.е. как последовательность для некоторого фиксированного значения, причем для всех появляющихся событий заданы вероятности. Так, для каждой комбинации букв (-граммы) () над и каждой начальной точки определена вероятность

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

1. для всех текстов;

2.;

3. для всех.

Третье свойство называется условием совместности Колмогорова.

Дата добавления: 2013-12-12