ставляет 1.3 бита. Значит, в каждом байте содержится 6.7 бита избыточной информации, что дает общую изб ы-точность 0.84 бита информации на бит ASCII-текста и энтропию 0.16 бита информации на бит ASCII-текста. То же сообщение, набранное кодом BAUDOT, с 5 битами на символ, имеет избыточность 0.74 бита на бит и энтр опию 0.26 бита на бит. Пробелы, пунктуация, числа и форматирование изменяют эти результаты.

Безопасность криптосистемы

Шеннон определил точную математическую модель понятия безопасности криптосистемы. Смысл работы криптоаналитика состоит в определении ключа К, открытого текста P или и того, и другого. Однако, его может устроить и некоторая вероятностная информация о P: является ли этот открытый текст оцифрованным звуком, немецким текстом, данными электронных таблиц или еще чем-нибудь.

В реальном криптоанализе у криптоаналитика есть некоторая вероятностная информация о P еще до начала работы. Он, скорее всего, знает язык открытого текста. Этот язык обладает определенной, связанной с ним и з-быточностью. Если это сообщения для Боба, оно, возможно, начинается словами "Дорогой Боб". Определенно, "Дорогой Боб" намного вероятнее, чем "e8T&.g [,m". Целью криптоаналитика является изменение вероятностей, связанных с каждым возможным открытым текстом. В конце концов, из груды возможных открытых текстов будет выбран один конкретный (или, по крайней мере, весьма вероятный).

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

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

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

Энтропия криптосистемы является мерой размера пространства ключей, K. Она приблизительно равна логарифму числа ключей по основанию 2:

Н(К) = log2 K

Энтропия криптосистемы с 64-битовым ключом равна 64 битам, энтропия криптосистемы с 56-битовым ключом равна 56 битам. В общем случае чем больше энтропия, тем тяжелее взломать криптосистему.

Расстояние уникальности

Для сообщения длиной n число различных ключей, которые расшифруют шифротекст сообщения в какой-то осмысленный открытый текст на языке оригинального открытого текста (например, английском), определяется следующей формулой [712, 95]:

Шеннон [1432] определил расстояние уникальности, U, называемое также точкой уникальности, как такое приближенное количество шифротекста, для которого сумма реальной информации (энтропия) в соответству ю-щем открытом тексте плюс энтропия ключа шифрования равняется числу используемых битов шифротекста. Затем он показал, что имеет смысл считать, что шифротексты, которые длиннее расстояния уникальности, мо ж-но расшифровать только одним осмысленным способом. Шифротексты, которые заметно короче расстояния уникальности, скорее всего, можно расшифровать несколькими способами, каждый из которых может быть правилен, и таким образом обеспечить безопасность, поставив противника перед выбором правильного откр ы-того текста.

Для большинства симметричных криптосистем расстояние уникальности определяется как энтропия крипт о-системы деленная на избыточность языка.

U = н(к)ю

Расстояние уникальности является не точным, а вероятностным значением. Оно позволяет оценить мин и-мальное количество шифротекста, при вскрытии которого грубой силой имеется, вероятно, только один разу м-ный способ дешифрирования. Обычно чем больше расстояние уникальности, тем лучше криптосистема. Для DES с 56-битовым ключом и англоязычного сообщения, записанного символами ASCII, расстояние уникальн о-

сти приблизительно равно 8.2 символа ASCII или 66 бит. В 1405-й приведены расстояния уникальности для различных длин ключа. Расстояния уникальности для некоторых классических криптосистем можно найти в [445].

Расстояние уникальности измеряет не количество криптотекста, нужного для криптоанализа, а количество криптотекста, необходимое для единственности результата криптоанализа. Криптосистема может быть вычи с-лительно неуязвима, даже если теоретически ее возможно взломать, используя малое количество шифротекста. (Уместно вспомнить о весьма эзотерической теории релятивистской криптографии [230, 231, 232, 233, 234, 235].) Расстояние уникальности пропорционально избыточности. Если избыточность стремится к нулю, даже тривиальный шифр может не поддаться вскрытию с использованием только шифротекста.

Табл. 11-1. Расстояния уникальности текста ASCII, зашифрованного алгоритмами с различной длиной ключа

Шеннон определил криптосистему с бесконечным расстоянием уникальности, как обладающую идеальной тайной. Обратите внимание, что идеальная криптосистема не обязательно является совершенной, хотя сове р-шенная криптосистема обязательно будет и идеальной. Если криптосистема обладает идеальной тайной, то даже при успешном криптоанализе останется некоторая неопределенность, является ли восстановленный открытый текст реальным открытым текстом.

Практическое использование теории информации

Хотя эти понятия имеют большое теоретическое значение, реальный криптоанализ использует их достаточно редко. Расстояние уникальности гарантирует ненадежность системы, если оно слишком мало, но его высокое значение не гарантирует безопасности. Несколько практических алгоритмов абсолютно не поддаются анализу, поведение параметров теории информации могло бы способствовать взлому некоторых шифрованных сообщ е-ний. Однако, подобные соображения теории информации иногда полезны, например, для определения в ко н-кретном алгоритме рекомендуемого интервала изменения ключей. Криптоаналитики также используют ряд те с-тов не базе статистики и теории информации, чтобы выбирать наиболее перспективные направления анализа. К сожалению, большинство литературы по применению теории информации в криптоанализе остается секретной, включая основополагающую работу Алана Тьюринга (Alan Turing), написа нную в 1940.

Путаница и диффузия

Двумя основными методами маскировки избыточности открытого текста сообщения, согласно Шеннону, служат путаница и диффузия [1432].

Путаница маскирует связь между открытым текстом и шифротекстом. Она затрудняет попытки найти в шифротексте избыточность и статистические закономерности. Простейшим путем создать путаницу является подстановка. В простом подстановочном шифре, например, шифре Цезаря, все одинаковые буквы открытого текста заменяются другими одинаковыми буквами шифротекста. Современные подстановочные шифры являю т-ся более сложными: длинный блок открытого текста заменяется блоком шифротекста, и способ замены меняе т-ся с каждым битом открытого текста или ключа. Такого типа подстановки обычно недостаточно - сложный а л-горитм немецкой Энигмы был взломан в ходе второй мировой войны.

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

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

мать (хотя шифры с двойной перестановкой оказываются поустойчивее, чем другие некомпьютерные системы).

11.2 Теория сложности

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

Сложность алгоритмов

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

Обычно вычислительная сложность алгоритма выражается с помощью нотации "О большого", т.е описыв а-ется порядком величины вычислительной сложности. Это просто член разложения функции сложности, быстрее всего растущий с ростом n, все члены низшего порядка игнорируются. Например, если временная сложность данного алгоритма равна 4 n2+7n+12, то вычислительная сложность порядка n2, записываемая как O( n2).

Временная сложность измеренная таким образом не зависит от реализации. Не нужно знать ни точное время выполнения различных инструкций, ни число битов, используемых для представления различных переменных, ни даже скорость процессора. Один компьютер может быть на 50 процентов быстрее другого, а у третьего шина данных может быть в два раза шире, но сложность алгоритма, оцененная по прядку величины, не изменится. Это не жульничество, при работе с алгоритмами настолько сложными, как описанные в этой книге, всем пр о-чим можно пренебречь (с точностью до постоянного множителя) в сравнении со сложностью по порядку вел и-чины.

Эта нотация позволяет увидеть, как объем входных данных влияет на требования к времени и объему пам яти. Например, если 7= O(n), то удвоение входных данных удвоит и время выполнения алгоритма. Если 7=О(2п), то добавление одного бита к входным данным удвоит время выполнения алгоритма.

Обычно алгоритмы классифицируются в соответствии с их временной или пространственной сложностью. Алгоритм называют постоянным, если его сложность не зависит от п: 0(1). Алгоритм является линейным, если его временная сложность 0( п). Алгоритмы могут быть квадратичными, кубическими и т.д. Все эти алгоритмы - полиномиальны, их сложность - 0(nm), где m - константа. Алгоритмы с полиномиальной временной сложностью называются алгоритмами с полиномиальным временем.

Алгоритмы, сложность которых равна О( f n)), где t - константа, большая, чем 1, а f(n) - некоторая полиномиальная функция от n, называются экспоненциальными. Подмножество экспоненциальных алгоритмов, сло ж-ность которых равна О( cf(n)), где где c - константа, а fn) возрастает быстрее, чем постоянная, но медленнее, чем линейная функция, называется суперполиномиальным.

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

С ростом n временная сложность алгоритмов может стать настолько огромной, что это повлияет на практ и-ческую реализуемость алгоритма. В 9-й показано время выполнения для различных классов алгоритмов при n равном одному миллиону. В таблице игнорируются постоянные величины, но показано, почему это можно д е-лать.

Табл. 11-2

Время выполнения для различных классов алгоритмов

КлассСложностьКоличество операций для n=106 Время при 106 операций в секунду