<< Предыдущая

стр. 16
(из 82 стр.)

ОГЛАВЛЕНИЕ

Следующая >>

Напомним, что шифром сдвига считается тот шифр, при котором
шифрование заключается в «прибавлении» фиксированной буквы к
каждому знаку открытого текста. Модифицируем его, выбирая свой
ключ А^ля каждой буквы сообщения. Например, для шифрования сло­
ва «hello» мы возьмем 5 случайных ключей, скажем fuiat. Затем
прибавим по модулю 26 ключевое слово к открытому тексту и по­
лучим шифрограмму MYTLH. Обратите внимание, что буква «1»
открытого текста переходит в разные символы шифровки.
При использовании в шифре сдвига разных равномерно распре­
деленных случайных ключей для каждой буквы текста получает­
ся абсолютно стойкая криптосистема. Чтобы проверить это, рас­
смотрим шифрование сообп1;ения из п букв. Тогда количество всех
ключей, криптограмм и открытых текстов равно
# К = # С = # Р = 26^.
К тому же каждый ключ будет применяться с одной и той же ве­
роятностью р{К = к) = 2 ^ , а для любой пары тис выделен
единственный ключ к = с — т (mod26) со свойством ek{m) = с.
В результате, благодаря теореме Шеннона, можно заключить, что
описанная криптосистема обладает абсолютной стойкостью.

4.2.2. Шифр Вернама
Главная операция описанного в предыдуш;ем подпараграфе модифи­
цированного шифра сдвига — сложение по модулю 26, что с точки
зрения вычислительной техники является слишком дорогостояш;им,
в то время как двоичная арифметика сравнительно легка. В первую
очередь нас интересует сложение по модулю 2, которое равносиль­
но логической операции «исключаюп];ее ИЛИ», обозначаемой обычно
«XOR»:
©01
0 01
1 10
в 1917 г. Гильберт Вернам запатентовал шифр, основанный на
этой операции, который теперь называют шифром Вернама или од­
норазовым шифр-блокнотом. Для пересылки строки битов необхо-
Глава 4- Теоретико-информационная стойкость

ДИМ ключ, состоящий из того же количества двоичных знаков, что и
сообщение. Каждый бит посылаемой строки складывается по моду­
лю 2 с соответствующим знаком 1слюча и получается криптограмма.
Любой ключ разрешается использовать для шифрования толь­
ко один раз, отсюда и название: одноразовый шифр-блокнот. Та­
ким образом, распределение ключей здесь — основная проблема, к
которой мы будем возвращаться снова и снова. Чтобы убедиться
в неизбежности неприятностей при шифровании нескольких тек­
стов одним ключом, рассмотрим атаку с выбором открытого тек­
ста. Предположим, что Алиса всегда пользуется одним ключом р,ля
шифрования данных. Ева пытается определить этот ключ и пред­
принимает следующую атаку:
- генерирует сообщение т и подсовывает его Алисе для шифро­
вания,
- получает с = т®к^
- вычисляет к = с®т.
Вы можете возразить, что Алиса не настолько глупа, чтобы ши­
фровать сообщение Евы. Но при разработке криптосистемы мы обя­
заны учесть любые ситуации, в том числе и глупого пользователя,
т.е. создать «защиту от дураков».
Другая проблема, возникающая при двойном употреблении ключа,
состоит в следующем. Допустим, Ева перехватила два сообщения,
зашифрованные одним ключом
ci = mi © fc, С2 = m2 © к.
Тогда она может получить частичную информацию о сообщениях,
сложив шифрограммы:
ci © С2 = (mi © /и) © {7П2 ®к) = mi® m2.
Несмотря на проблемы, связанные с распределением ключей, од­
норазовый шифр-блокнот применялся как в минувших войнах, так
и в дипломатической почте.


4.3. Энтропия
Криптосистема, требующая ключа той же длины, что и сообще­
ние, вместе с условием однократного использования каждого ключа,
крайне неудобна при интенсивной эксплуатации, например для осу­
ществления сделок через Интернет. Происходит это потому, что
4'S. Энтропия


передача секретного ключа в рамках одной криптосистемы от од­
ного пользователя к другому становится неразрешимой задачей.
Действительно, скрытая передача необходимого ключа требует оче­
редного ключа, тот - следуюш;его, и т. д. Возникающую проблему
называют проблемой распределения ключей.
В целях преодоления указанной трудности абсолютно стойкие
криптографические алгоритмы заменяются системами, будем наде­
яться, вычислительно заш;иш;енными. В этом состоят задачи совре­
менных криптографов, одна из которых — изобретение системы,
удовлетворяющей следующим требованиям:
- один ключ используется несколько раз,
- небольшим ключом шифруются длинные сообщения.
Такие схемы не будут совершенными ввиду теоремы Шеннона. В луч­
шем случае они будут вычислительно защищены.
Нам потребуются некоторые разделы теории информации, ка­
сающиеся вычислительно стойких криптосистем. Основные резуль­
таты здесь вновь принадлежат Шеннону и относятся к концу 40-ых
годов прошлого века. В частности, мы будем эксплуатировать идею
Шеннона об энтропии^ как о способе измерения количества инфор­
мации.
«Энтропия»— синоним слова «неопределенность». Основной прин­
цип теории информации состоит в таком наблюдении: информа­
ция, по существу, то же самое, что и неопределенность. На пер­
вый взгляд, такое отождествление довольно странно, но специали­
сты приводят в его пользу следующий аргумент: если Вы сомневае­
тесь в значении чего-либо, то его уточнение дает Вам информацию.
В применении к криптографии основной принцип можно пояснить
так. Предположим, что Вы хотите извлечь информацию из шифро-
текста, другими словами, хотите знать, каково его истинное значе­
ние. При этом:
- Вам неясно, что означает данная криптограмма.
- Вы могли бы что-то предположить относительно соответству­
ющего открытого текста.
- Уровень неизвестности, содержащийся в Вашем предположе­
нии, соответствует количеству информации, находящейся в
шифротексте.

^В русскоязычных книгах по криптографии вместо термина «энтропия» упо­
требляется термин «мера неопределенности». — Прим. перев.
Глава 4' Теоретико-информационнал стойкость

Количество энтропии, ассоциированной со случайной перемен­
ной X, обозначается через Н{Х). Отложив формальное определение
этой величины на будущее, обратимся к простому примеру, прояс­
няющему основные идеи этого понятия.
Предположим, что X — ответ на какой-то вопрос, т. е. нет или
да. Если Вам известно, что я на любой вопрос всегда говорю (9а, то
мой ответ Вам ничего не дает. Стало быть, количество информа­
ции, содержащейся в X, равно О, т.е. Н{Х) — 0. Поскольку ответ
известен заранее, он не несет в себе информации, поэтому нет и
энтропии.
Если Вам заранее неизвестна моя реакция на вопрос, а я говорю
да с той же вероятностью, что и wem, то своим ответом даю Вам
один бит информации. В терминах энтропии это можно записать
как Н{Х) = 1.
Заметим, что энтропия не зависит от длины фактического со­
общения. В предыдущем случае сообщение состояло либо из двух,
либо из трех букв ((9а, wem), а количество информации не превыша­
ло одного бита.
Теперь дадим строгое определение.

Определение 4.5. Пусть X — случайная величина, принимающая
значения xi {1 ^ г ^ п) с вероятностями р{Х = Xi) = pi. Ее энтро­
пией^ называется величина

п


г=1
При этом считается, что pi log2 Pi = О как только pi = 0.
Вернемся к нашему примеру с вопросами и покажем, что инту­
итивное понятие об энтропии, которое там присутствует, соответ­
ствует формальному определению. Напомним, X — мой ответ да
или нет на некий вопрос. Если известно, что я всегда тупо повто­
ряю (9а, то pi = 1, р2 = О и, согласно определению,
Н{Х) = - 1 • log2 1 - о • log2 0 - 0 .
Это означает, что мой ответ не дает Вам ни малейшей информации.
Во второй ситуации, когда мои ответы да или нет. равновероятны,
т. е. pi = Р2 = 1/2, получаем

я(х) =-!5|i - !2|i = 1.
Априорной мерой неопределенности. — Прим. перев.
4'S. Энтропия

Здесь мой ответ сообщает Вам один бит информации.
Из определения энтропии следуют несколько ее элементарных
свойств.
- Энтропия всегда неотрицательна: Н{Х) ^ 0.
- Энтропия Н{Х) равна нулю тогда и только тогда, когда jpi = 1
для некоторого г, а при j "^ i имеем pj = 0.
- Если Pi = ^ для всех г, то Н{Х) = log2 п.
С другой точки зрения энтропия измеряет степень сжатия ин­
формации. Посылая ответы да или нет с помощью одного символа
в коде ASCII, например, «Y» вместо да и «N» вместо wem, я передаю
8 битов данных, однако, фактически, только один бит информации.
Таким образом, при желании посылаемые данные можно было бы
сжать до 1/8 их первоначального размера. Следовательно, говоря
наивно, сообщение длины п, сжатое с коэффициентом ? от исходно­
го размера, содержит е • п битов информации.
Обратимся к нашей «детской» криптосистеме из предыдущего
параграфа. Напомним, там были пространства исходов
Р = { а , Ь, с, d } , K={A;i, А:2, ^з} и С = {1, 2, 3, 4}
с распределением вероятностей
р(р = а) = 0 , 2 5 , p{P = b)=p{P = d)=0,3, р ( Р = с) = 0,15,
р{К = ki) = р(К = ks) = 0,25, р{К = к2) = 0,5,
р{С = 1) = р{С = 2) = р{С = 3) = 0,2625, р{С = 4) = 0,2125.
Соответствующие энтропии имеют значения
Н{Р) « 1,9527, Н{К) « 1,9944, Н{С) ^ 1,5. (4.3)
Следовательно, шифротекст в нашем примере «дает утечку» в 1,5
бита информации о ключе и соответствующем открытом тексте,
поскольку ровно столько неопределенности содержится в отдельной
шифрограмме. Позже мы выясним, какая доля из этой «утечки» при­
ходится на ключ, а какая — на открытый текст.
Хотелось бы получить какую-нибудь оценку сверху для энтропии
случайной величины, поскольку нижняя ее граница нам известна:
Н{Х) ^ 0. Для этого нам потребуется следующий частный случай
неравенства Иенсена

Теорема 4.6. (Неравенство Иенсена.) Предположим, что

п


г=1
I 10 Глава 4- Теоретико-информационная стойкость

где а^ > О при 1 ^ г ^ п. Тогда для положительных чисел ж^ > О
имеет место неравенство
п /^ \
^ аг log2 Xi ^ log2 f ^ аг^г 1 ,
г=1 \г=1 /
равенство в котором достигается тогда и только тогда, когда xi =
Х2 = " ' = Хп-

Опираясь на этот факт, докажем следуюы]ую теорему.

Теорема 4.7. Энтропия случайной величины X, принимающей п
различных значений, удовлетворяет неравенству
О ^ Н{Х) ^ log2 п.
Нижняя граница неравенства достигается на случайной величине,
принимающей одно из своих значений с вероятностью 1, а верхняя —
на равномерно распределенной, т. е. принимающей все свои значения
равновероятно.
Доказательство. Мы уже обсудили все, касающееся нижней гра­
ницы энтропии, так что сконцентрируем свои усилия на верхней.
Пусть X — случайная величина с распределением вероятностей pi,
.., ^ Рп^ причем все pi > 0. Тогда
п п ^
^ ( ^ ) = " ^Pi 1^ё2Рг = ^Pi log2 — ^


^ 1^ё2 ij2\P''˜)) = ^^S2 ^•
Неравенство в этих преобразованиях следует из теоремы 4.6. В си­
лу неравенства Иенсена, знак «^» меняется на «=» тогда и только
тогда, когда все р^ = ^, т. е. случайная величина X распределена
равномерно. •
Основы теории энтропии близки к основам теории вероятностей.
Например, А,ЛЯ двух случайных величин в теории вероятностей опре­
деляется совместное распределение:
Tij = р{Х = XiHY = yi)
при 1 ^ г ^ п , 1 ^ ^ ^ 7 т г . По нему можно вычислить их совместную
энтропию
п т
H{X,Y) = -Y;^'?n,jlog,ri,j.
1=1 j=l
4.3. Энтропия

Совместную энтропию Н{Х^ Y) можно понимать как количество ин­
формации, которое получается из наблюдения пары значений (х^у)
этих случайных величин.
Имеет место неравенство


превращающееся в равенство только при независимых X и?. Оста­
вим его доказательство читателю в качестве упражнения.
Точно так же, как совместное распределение в теории вероятно­
стей ассоциировано с условной вероятностью, понятие совместной
энтропии связано с понятием энтропии условной^. Последнее — важ­
нейший инструмент исследования неидеальных шифров, описанных
в конце главы.
Пусть X и? — случайные величины. Напомним, что р{Х = х\? = у)
показывает вероятность равенства X = х при условии У = у. Пред­
положим, нам известно, что значение случайной величины ? рав­
но у. В этом случае энтропия случайной величины X определяется
формулой:
Н{Х\у) = - J2piX = x\Y = у) log2p(X = x\Y = у).
X


Используя это, определим условную энтропию случайной величины
X при данной величине ? как
я ( х | У ) = -Y,p{y = y)H{x\y) =
у

<< Предыдущая

стр. 16
(из 82 стр.)

ОГЛАВЛЕНИЕ

Следующая >>