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

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

ОГЛАВЛЕНИЕ

Следующая >>


4.2. Вероятность и шифры
Прежде чем дать формальное определение абсолютной стойкости,
нам необходимо в деталях осознать роль вероятности в понимании
простых шифров. Зафиксируем следующие обозначения:
Р — множество возможных открытых текстов, т. е. простран­
ство сообщений;
К — совокупность возможных ключей;
С — множество шифротекстов.
Каждое из этих множеств можно понимать как пространство собы­
тий, в котором вероятности обозначаются как р{Р = т ) , р{К = А;),
р{С = с).
Например, если наше пространство сообщений имеет вид Р =
= {а, 6, с} и сообщение а встречается с вероятностью 1/4, то мы
пишем р{Р = а) = | .
Будем считать, что любые события Р G Р и JC G К независимы,
т. е. пользователь не меняет ключ шифра в зависимости от содержа­
ния открытого текста, подлежащего шифрованию. Символом С{к)
4^2, Вероятность и шифры 99

обозначим множество всех криптограмм, полученных из простран­
ства сообщений шифрованием посредством ключа к:
C{k) = {Ek{x)\xeF},
где Ek — шифрующая функция. Имеет место соотношение
р{С = с)= J2 PiK = k)-p{P = Dkic)), (4.1)
А;: сеС{к)
где Dk — расшифровывающая функция.
В качестве базисного примера этого параграфа рассмотрим про­
странство сообщений Р = {а, Ь, с, d} с распределением вероятностей

р{Р = а) = 1 р{Р = Ь) = 10'

р ( Р = с) = 20,
^, р{Р = d) = ^.
Предположим, что пространство ключей имеет вид IK = {fci, к2ч к^}^
а вероятности их выбора равны

p{K = ki) = \ , р{К = к2) = \ , р{К = кг) = 1.

Пусть, наконец, С = {1, 2, 3, 4}, а функция шифрования предста­
влена таблицей:
abed
3421
A;i
к2 3 1 4 2
кг 4 3 1 2
Используя формулу (4.1), вычислим распределение вероятностей на
множестве С.
р{С = 1) = р{К = ki)p{P = d) +р{К = к2)р{Р = Ь)+
+ р{К = кз)р(Р = с) = 0,2625,
р{С = 2) = р{К = ki)p{P = с) + р{К = к2)р{Р = d)+
+ р{К = кз)р{Р = d) = 0,2625,
р(С = 3) = р{К = ki)p{P = а) +р{К = к2)р{Р = а)+
+ р{К = кг)р{Р = Ь) = 0,2625,
р(С = 4) = р{К = ki)p{P = b) + р{К = к2)р{Р = с)+
+ р{К = кг)р{Р = а) = 0,2125.
Отсюда видно, что шифротексты распределены почти однородно.
Глава 4- Теоретико-информационная стойкость

Для пары с Е С и т Е F можно вычислить условную вероятность
р(^С = с\Р = ш), т.е. вероятность выбора шифротекста с, если из­
вестно, что открытый текст — это т . Справедлива формула

р{С = с\Р = т)= Y1 Р(^ = ^)- (4-2)
к: m=dk{c)

Здесь сумма берется по всем ключам /с, для которых значение dk на
шифрограмме с совпадает с данным открытым текстом т. Вычи­
слим условные вероятности для базисного примера.

р{С = 1\Р = а) = О, р{С = 2|Р = а) = О,
р{С = 3|Р = а) = 0,75, р{С - 4|Р = а) = 0,25,

р(С = 1|Р = Ь) = 0,5, р{С = 2\Р = 6) = О,
р{С = 3\Р = Ь)=0,25, р{С = А\Р = Ь) = 0,25,

р{С = 1\Р = с)= 0,25, р{С = 2\Р = с)= 0,25,
р{С = 3\Р = с) = О, р(С = 4|Р = с) = 0,5,

р(С = 1|Р = d) = 0,25, р{С = 2|Р = d) = 0,75,
р(С = 3|Р = d)=0, р{С = 4|Р = d) = 0.

Однако при взломе шифра нам нужна условная вероятность дру­
гого сорта. То есть мы хотим знать вероятность открытого текста
при данном шифротексте. Вероятность того, что т — действитель­
но исходное сообп];ение для данной криптограммы, вычисляется по
формуле:
р{Р = т)р{С = с\Р = т)
р(Р = т\С = с) = ^^^--^ .

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

р{р = а\С = 1) = О, р{Р = Ь\С = 1) = 0,571,
р{р = с\С = 1) = 0,143, р{Р = d\C = 1) = 0,286,
4^2. Вероятность и шифры

р{Р = а\С = 2)= О, р{Р = Ь\С - 2) = О,
р{Р = с\С = 2)= 0,143, р{Р = d\C = 2) = 0,857,

р{Р = а\С = 3) = О, 714 р{Р = Ь\С - 3) = 0,286,
р{Р = с\С - 3) = О, р{Р = d\C = 3) = О,

р{Р = а\С = 4) = 0,294, р{Р = Ь\С = 4) = 0,352,
р{Р = с\С = 4) = 0,352, р{Р = d\C = 4) - 0.
Анализируя полученные результаты, можно сделать следующие вы­
воды:
- Если мы получили шифротекст 1, то точно знаем, что исходное
сообщение не может быть а. Более того, предположение о том,
что соответствующий открытый текст — Ь, более вероятно,
чем с или d,
- При получении шифротекста 2 мы уверены, что исходное со­
общение — не а и не Ь, а скорее всего — d,
- Увидев третью криптограмму, мы заключаем, что отправлен­
ное сообщение не может быть ни с и ни d, но имеет большие
шансы оказаться текстом а.
- Если у нас оказалась последняя шифрограмма, то отправлен­
ное сообщение отлично от d. Однако у нас очень мало основа­
ний предпочесть какое-либо из оставшихся.
Таким образом, шифротекст в нашем примере дает немало инфор­
мации относительно оригинального сообщения. Но именно этого мы
и хотим избежать. Мы стремимся к тому, чтобы по криптограмме
невозможно было получить какую-либо информацию об открытом
тексте.
Криптосистема, шифротекст в которой не дает никакой инфор­
мации о соответствующем открытом тексте, называется абсолютно
стойкой^ или совершенной.

Определение 4.1. Криптосистема обладает абсолютной стойко­
стью, если равенство
р{Р = т\С = с)= р{Р = т)
имеет место р^ля всех открытых текстов m G Р и всех криптограмм
CGC.
Иначе говоря, наличие шифрограммы никак не сказывается на
вероятности того, что открытый текст совпадает с т. Вновь под-
102 Глава 4- Теоретико-информационная стойкость

черкнем: абсолютная стойкость шифра означает, что шифротекст
не несет в себе сведений об открытом тексте^. Второй способ опре­
деления абсолютной стойкости дает следуюш;ая лемма.

Лемма 4.2. Криптосистема является абсолютно стойкой, если


р^ля всех т и с .
Доказательство. Утверждение леммы немедленно следует из опре­
деления абсолютной стойкости и формулы
р{Р = 7п)р{С = с\Р = т)
р{Р = т\С = с) =
р{С = с)


Первое свойство абсолютно стойких криптосистем сформулиро­
вано в лемме 4.3.

Лемма 4.3. Для абсолютно стойкой криптосистемы имеет место
неравенство:


где #1К — число возможных ключей, # С — количество возможных
шифрограмм и # Р — размер пространства сообщений.
Доказательство. Прежде всего заметим, что в любой криптоси­
стеме выполнено равенство:
# с ^ #р,
поскольку шифруюш;ая функция должна быть инъективной.
Предположим, что при шифровании может получиться любой
шифротекст с G С, т.е. Vc € С р{С = с) > 0. Если это не так, то
можно подправить определение множества С, выбросив из него лиш­
ние элементы. Тогда любое сообщение т и шифротекст с абсолютно
стойкой криптосистемы удовлетворяют соотношению
р{С = с\Р = т)= р{С - с) > 0.
Из него следует, что д,ля любой пары ттг и с найдется такой ключ А;,
что р{К = к) > О и 7п = dk{c) (см. (4.2)). Следовательно, зафикси­
ровав открытый текст т = т о , мы можем каждой шифрограмме с
поставить в соответствие такой ключ А;(с), что (1^(с){^) = ^ о - При
этом, естественно, разным шифротекстам будут отвечать разные
ключи, откуда # К ^ # С . •
^Если, конечно, не знать ключа. — Прим. перев.
4-2, Вероятность и шифры 103

Это подводит нас к основной теореме Шеннона, которая дает
критерий абсолютной стойкости шифра.

Теорема 4.4. (Шеннон.) Пусть набор
(Р, С, К, в,(.), dk{'))
обозначает симметричную криптосистему, в которой # Р = # С =
#1К. Она обладает абсолютной стойкостью тогда и только тогда,
когда
- использование всех ключей равновероятно, т. е. р{К = к) = J g
УкеК;
- для каждой пары m G Р и с G С существует единственный
ключ fc, такой что ek{m) = с.
Доказательство. Предположим, что криптосистема наделена аб­
солютной стойкостью. Тогда, как мы уже убедились при доказатель­
стве предыдущей леммы, для каждой пары m G Р и с Е С найдется
такой ключ А G К, при котором dk{c) = т. Ввиду симметрично­
;
сти криптосистемы это равенство влечет соотношение: ek{m) = с.
Отсюда, благодаря предположению # С = #1К, получаем
#{efc(m)|A;GK} = # K ,
Т. е. не существует таких двух ключей ki ик2, что Ck^ (m) = ek2 (^) =
с. Так что для всех ?тг G Р и с G С существует ровно один ключ А G К
;
со свойством ek{m) = с. В частности, тройка ( т , с, к) удовлетворяет
соотношению
Р{С = с\Р = т) = Р{К = к).

Покажем, что применение всех ключей равновероятно, т. е.

р{К = к) = щ Ук€К.

Пусть п = #1К и Р = {шг, 1 ^ г ^ п}. Фиксируем с G С и пронуме­
руем ключи fci, . . . , кп так, что
^kii^^i) = С при 1 ^ г ^ П.
Опираясь на абсолютную стойкость криптосистемы, т.е. на соот­
ношение
р{Р = ггц\С = с) = р{Р = ГПг),

получаем р{Р = rrii) = р{Р = т{\С = с) =
04 Глава 4- Теоретико-информационная стойкость


^ р{С = С\Р = тг)р{Р = ТПг) ^
р{С = с)
^ р{К = кг)р{Р = ГЩ)
р{С = с)
Следовательно, для всех 1 ^ г ^ п
р{С = с) = р{К = кг).
Из этого равенства, ввиду фиксированности с, вытекает, что все
ключи используются с одинаковой вероятностью

р{К = к) = р{С = с) = —rip для всех А G К.
;

Докажем вторую часть критерия, а именно, предположив, что
- # К = # С = #Р,
- использование ключей равновероятно,
- для любой пары m G Р и с G С существует единственный ключ
fc, А^ля которого ekipi) = с,
покажем справедливость равенства
р{Р = т\С = с) = р{Р = т ) .
Из равновероятности применения ключей получаем
р{С = с)= Y^PiK = к)р{Р = dk{c)) =
к


Кроме того, поскольку для каждой пары т и с существует един­
ственный ключ fc, переводящий ттг в с, имеем
J^piP = dk{c)) = ^р{Р = m) = 1.
fe т
Значит, р{С = с) = 1/#К. Если с = ek{in), то р{С = с\Р = т) =
= р{К = к) = 1/#К. Теперь из теоремы Байеса вытекает
р{Р = т)р{С = с\Р = т)
р{Р = т\С = с) =
р{С = с)

j_ -р{Р = т).

Теорема доказана.
4-2. Вероятность и шифры

Закончим параграф обсуждением двух систем с абсолютной стой­
костью.

4.2.1. Модифицированный шифр сдвига

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

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

ОГЛАВЛЕНИЕ

Следующая >>