Норма языка
Энтропия и неопределенность
Часть III Криптографические алгоритмы
Глава 11 Математические основы
11.1 Теория информации
Современная теория информации впервые была опубликована в 1948 году Клодом Э. Шенноном (Claude Elmwood Shannon) [1431, 1432]. (Его работы были переизданы в IEEE Press [1433].) С математической точки зрения эта тема хорошо рассмотрена в [593]. В этой главе я только схем атично излагаю основные идеи.
Теория информации определяет количество информациив сообщении как минимальное количество бит, необходимое для кодирования всех возможных значений сообщения, считая все сообщения равновероятными. Например, для поля дня недели в базе данных достаточно использовать три бита информации, так как вся и н-формация может быть закодирована 3 битами:
0 - Воскресенье
1 -Понедельник
10 -Вторник
11 -Среда
100 -Четверг
101 -Пятница ПО-Суббота
111 - Не используется
Если эта информация была бы представлена соответствующими строками ASCII символов, она заняла бы больше места в памяти, но не содержала бы больше информации. Аналогично, поле базы данных "пол" соде р-жит только один бит информации, хотя эта информация может храниться как одно из двух 7-байтовых ASCII строк: "МУЖЧИНА" или "ЖЕНЩИНА".
Формально, количество информации в сообщении М измеряется энтропиейсообщения, обозначаемое как Н(М). Энтропия сообщения, определяющего пол, составляет! бит, а энтропия сообщения, определяющего день недели, немного меньше, чем 3 бита. В общем случае энтропия сообщения, измеряемая в битах, равна log 2 п, где п - это количество возможных значений. При этом предполагается, что все значения равновероятны.
Энтропия сообщения также является мерой его неопределенности.Это количество битов открытого текста, которое нужно раскрыть в шифротексте сообщения, чтобы узнать весь открытый текст. Например, если блок шифротекста "QHP*5M " означает либо "МУЖЧИНА", либо "ЖЕНЩИНА", то неопределенность сообщения равна 1. Криптоаналитику нужно узнать только один правильно выбранный бит, чтобы раскрыть с ообщение.
Для данного языка норма языкаравна
г =H(M)/N
где N - это длина сообщения. При больших N норма обычного английского языка принимает различные зн а-чения от 1.0 бит/буква до 1.5 бит/буква. Шеннон в [1434] говорит, что энтропия зависит от длины текста. Ко н-кретно он показал, что норма для 8-буквенных блоков равна 2.3 бит/буква, но ее значение падает и находится между 1.3 и 1.5 для 16-буквенных блоков. Томас Кавер (Thomas Cover) использовал игровую методику оценки и обнаружил, что энтропия равна 1.3 бит/символ [386]. (В этой книге я буду использовать значение 1.3.) Абсолютная нормаязыка равна максимальному количеству битов, которое может быть передано каждым символом при условии, что все последовательности символов равновероятны. Если в языке L символов, то абсолютная норма равна:
R = log2 L
Это максимум энтропии отдельных символов.
Для английского языка с 26 буквами абсолютная норма равна log 2 26, или около 4.7 бит/буква. Вас не должно удивлять, что действительная норма английского языка намного меньше, чем абсолютная - естественные языки обладают высокой избыточностью. Избыточностьязыка, обозначаемая D, определяется как:
D=R - r
Считая, что норма английского языка равна 1.3, избыточность составит 3.4 бит/буква. Это означает, что к а-ждая английская буква содержит 3.4 бита избыточной информации.
У сообщения ASCII, состоящего только из английских букв, количество информации на каждый байт с о-
ставляет 1.3 бита. Значит, в каждом байте содержится 6.7 бита избыточной информации, что дает общую изб ы-точность 0.84 бита информации на бит ASCII-текста и энтропию 0.16 бита информации на бит ASCII-текста. То же сообщение, набранное кодом BAUDOT, с 5 битами на символ, имеет избыточность 0.74 бита на бит и энтр о-пию 0.26 бита на бит. Пробелы, пунктуация, числа и форматирование изменяют эти результаты.
Безопасность криптосистемы
Шеннон определил точную математическую модель понятия безопасности криптосистемы. Смысл работы криптоаналитика состоит в определении ключа К, открытого текста Р или и того, и другого. Однако, его может устроить и некоторая вероятностная информация о Р: является ли этот открытый текст оцифрованным звуком, немецким текстом, данными электронных таблиц или еще чем-нибудь.
В реальном криптоанализе у криптоаналитика есть некоторая вероятностная информация о Р еще до начала работы. Он, скорее всего, знает язык открытого текста. Этот язык обладает определенной, связанной с ним и з-быточностью. Если это сообщения для Боба, оно, возможно, начинается словами "Дорогой Боб". Определенно, "Дорогой Боб" намного вероятнее, чем "e8T&.g [,m". Целью криптоаналитика является изменение вероятностей, связанных с каждым возможным открытым текстом. В конце концов, из груды возможных открытых текстов будет выбран один конкретный (или, по крайней мере, весьма вероятный).
Существуют криптосистемы, достигающие совершенной безопасности.Такой является криптосистема, в которой шифротекст не дает никакой информации об открытом тексте (кроме, возможно, его длины). Шеннон теоретически показал, что такое возможно только, если число возможных ключей также велико, как и число возможных сообщений. Другими словами, ключ должен быть не короче самого сообщения и не может испол ь-зоваться повторно. Это означает, что единственной системой, которая достигает идеальной безопасности, может быть только криптосистема с одноразовым блокнотом (см. раздел 1.5).
За исключением идеально безопасных систем, шифротекст неизбежно дает определенную информацию о с о-ответствующем шифротексте. Хороший криптографический алгоритм сохраняет минимум этой информации, хороший криптоаналитик пользуется этой информацией для определения открытого текста.
Криптоаналитики используют естественную избыточность языка для уменьшения числа возможных откр ы-тых текстов. Чем избыточнее язык, тем легче его криптоанализировать. По этой причине многие криптограф и-ческие реализации перед шифрованием используют программы сжатия для уменьшения размера текста. Сжатие уменьшает избыточность сообщения вместе с объемом работы, необходимым для его шифрования и дешифр и-рования.
Энтропия криптосистемы является мерой размера пространства ключей, К. Она приблизительно равна логарифму числа ключей по основанию 2:
Н(К) = log2 К
Энтропия криптосистемы с 64-битовым ключом равна 64 битам, энтропия криптосистемы с 56-битовым ключом равна 56 битам. В общем случае чем больше энтропия, тем тяжелее взломать криптосистему.
Расстояние уникальности
Для сообщения длиной п число различных ключей, которые расшифруют шифротекст сообщения в какой-то осмысленный открытый текст на языке оригинального открытого текста (например, английском), определяется следующей формулой [712, 95]:
Шеннон [1432] определил расстояние уникальности,U, называемое также точкой уникальности, как такое приближенное количество шифротекста, для которого сумма реальной информации (энтропия) в соответству тощем открытом тексте плюс энтропия ключа шифрования равняется числу используемых битов шифротекста. Затем он показал, что имеет смысл считать, что шифротексты, которые длиннее расстояния уникальности, мо ясно расшифровать только одним осмысленным способом. Шифротексты, которые заметно короче расстояния уникальности, скорее всего, можно расшифровать несколькими способами, каждый из которых может быть правилен, и таким образом обеспечить безопасность, поставив противника перед выбором правильного откр ы-того текста.
Для большинства симметричных криптосистем расстояние уникальности определяется как энтропия крипт о-системы деленная на избыточность языка.
U = H(K)/D
Расстояние уникальности является не точным, а вероятностным значением. Оно позволяет оценить мин и-мальное количество шифротекста, при вскрытии которого грубой силой имеется, вероятно, только один разу м-ный способ дешифрирования. Обычно чем больше расстояние уникальности, тем лучше криптосистема. Для DES с 56-битовым ключом и англоязычного сообщения, записанного символами ASCII, расстояние уникальн о-
ста приблизительно равно 8.2 символа ASCII или 66 бит. В 1405-й приведены расстояния уникальности для различных длин ключа. Расстояния уникальности для некоторых классических криптосистем можно найти в [445].
Расстояние уникальности измеряет не количество криптотекста, нужного для криптоанализа, а количество криптотекста, необходимое для единственности результата криптоанализа. Криптосистема может быть вычи с-лительно неуязвима, даже если теоретически ее возможно взломать, используя малое количество шифротекста. (Уместно вспомнить о весьма эзотерической теории релятивистской криптографии [230, 231, 232, 233, 234, 235].) Расстояние уникальности пропорционально избыточности. Если избыточность стремится к нулю, даже тривиальный шифр может не поддаться вскрытию с использованием только шифротекста.
Табл. 11-1.