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

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

ОГЛАВЛЕНИЕ

Следующая >>

= - Е Е Р ( ^ = У)Р^^ = ^1^ = y)iog2P(^ = АУ = у)-
X у

Это та неопределенность в отношении величины X, которая оста­
ется после раскрытия значения У. Условная и совместная энтропии
связаны соотношением:
HiX,Y) = H{Y) + HiX\Y),
откуда получается оценка сверту
H{X\Y) ^ Н{Х),
где равенство достигается только в случае независимых случайных
величин X и ?. Доказательство этих формул мы также оставляем
читателю в качестве упражнения.

^Апостериорная мера неопределенности. — Прим. перев.
Глава 4' Теоретико-информационная стойкость

Возвращаясь к криптографии, выпишем несколько очевидных
утверждений, касающихся энтропии величин Р^ К т С,
- Н{Р\К^ С) = 0: при известных шифротексте и ключе мы пол­
ностью знаем соответствующий открытый текст. Этот факт,
очевидно, верен, поскольку в противном случае расшифрова­
ние будет работать неправильно.
- Н{С\Р^К) = 0: если мы знаем открытый текст и ключ, то
можем получить шифротекст. Это высказывание справедли­
во для всех шифров, с которыми мы уже знакомы, и остает­
ся в силе для симметричных криптосистем, описанных в сле­
дующих главах. Однако в современных схемах шифрования с
открытым ключом, при условии правильного их применения,
указанное свойство нарушается.
Кроме того, имеют место следующие тождества:
Н{К,Р,С)=^
= Н{Р,К) + Н{С\Р, К) = (т. к. Я ( Х , Y) = H{Y) + H{X\Y))
= Н{Р, К) = (т. к. Я ( С | Р , К) = 0)
= Н{К) -h Н{Р) (т. к. К и Р независимы);

Н{К,Р,С) =
= Н{К, С) + Н{Р\К, С) = (т. к. Я ( Х , У) = H{Y) + H{X\Y))
= Н{К, С) (т. к. Н{Р\К, С) = 0).
Следовательно,
Н{К,С)=Н{К)-^Н{Р),
Последняя формула имеет особое значение, поскольку она относит­
ся к условной энтропии Н{К\С)у называемой неопределенностью
ключа. Величина Н{К\С) — это то количество неопределенности
относительно истинного ключа, которое остается после прочтения
шифротекста. Напомним, что наша цель — определение ключа по
данной шифрограмме. Совмещая два предыдупщх равенства, находим
Н{К\С) = Н{К, С) - Н{С) = Н{К) + Н{Р) - Н{С), (4.4)
Иначе говоря, неопределенность в знании ключа при известном ши­
фротексте равна сумме неопределенностей относительно открытого
текста и ключа за вычетом неопределенности в отношении шифро­
текста.
На стр. 109 мы уже вычислили энтропию величин Р^ К и С для
«игрушечной» криптосистемы (соотношение (4.3)). Подставив эти
4-4' Лоэюные ключи и расстояние единственности

числа в формулу (4.4), получим
Н{К\С) ^ 1,9527 + 1,9944 - 1 , 5 ^ 1 , 4 5 8 3 .
Таким образом, после просмотра отдельного шифротекста нам оста­
ется найти около полутора бит информации об истинном ключе
шифровки. Этот пример объясняет, как криптосистема допускает
утечку информации, и показывает, почему ее нельзя считать стой­
кой. Как-никак, вначале у нас есть 1.9944 бита неопределенности
относительно ключа, а знание одной шифровки уменьшает неопре­
деленность до 1.4593 бита. То есть отдельный шифротекст сообп];ает
о ключе 1.9944 — 1.4593 ^ 0.535 бита информации.


4.4. Ложные ключи и расстояние единственности
Отдельный шифротекст выдает ненулевое количество информации
об истинном ключе криптосистемы, поскольку он исключает неко­
торое подмножество неподходящих ключей. Среди всех оставшихся
лишь один правилен. Для возможных, но отличных от истинного
ключей вводится термин лоэюный ключ.
Рассмотрим (немодифицированный) шифр сдвига, т. е. шифр, в
котором один ключ используется для замены любой буквы. Возьмем
шифрограмму WNAJW и предположим, что язык открытого тек­
ста — английский. Тогда есть только два разумных кандидата на
открытый текст: river и arena, соответствуюш;ие двум возможным
ключам: «ft и «w». Один из них истинный, а второй — ложный.
Обоснуем в очередной раз слабую криптостойкость шифра за­
мены, но на сей раз опираясь на понятие расстояния единственно­
сти. Мы подробно расскажем об этом термине несколько позже, а
сейчас более четко представим себе, что такое открытый текст. Во
многих компьютерных сетях открытый текст можно рассматривать
как случайную строку битов. Но довольно часто бывают исключе­
ния. В одних случаях шифруется обычный текст, а в других — не­
кий его образ. В наших обсуждениях мы рассматриваем ситуацию,
когда исходный открытый текст взят из английского языка, как в
шифре замены. Такой язык обычно называют естественным^ дабы
отличать его от строк битов, используемых в компьютерных сетях.
Сначала найдем энтропию (количество информации) HL^ кото­
рую несет одна буква естественного языка (в нашей ситуации — ан­
глийского). Отметим, энтропия случайной последовательности ан­
глийских букв равна
log2 26 ^ 4, 70.
Глава 4' Теоретико-информационная стойкость

Поэтому справедлива оценка HL ^ 4, 70. Случайная величина Р ,
принимающая значения букв в английском тексте, имеет распреде­
ление
р{Р = а) = 0,082, . . . , j9(P = е) = 0,127, ..., р{Р = z) =Q, 001
(сравните с табл. 3.1 на стр. 72). По стандартной формуле получаем
^ Н{Р) « 4,14.
HL

Следовательно, учитывая среднестатистическую частоту букв в ан­
глийском тексте, можно утверждать, что на каждую букву прихо­
дится 4,14 бит информации, а не 4,7, как мы предполагали после
грубой оценки.
Однако и это приближение далеко от истинного значения, по­
скольку буквы нельзя считать независимыми. Так, например, за «q»
всегда следует «и», а биграмма «th» наиболее популярна в англий­
ском языке. Возникает гипотеза, что р,ля лучшего приближения к
истинному значению энтропии HL СТОИТ изучить распределение би-
грамм. Итак, пусть Р^ — случайная биграмма. Обозначив через
р{Р = i^P' = j) вероятность появления биграммы «ij», найдем

Н{Р'') = -Т.Р{Р = hP' = j)log^p{P = г,Р' = j).

Эта величина вычислялась неоднократно разными авторами. Обыч­
но ее считают равной
Я(Р^) « 7.12
Отсюда энтропия отдельной буквы оценивается как

Яь^—у-^^3,56.
И опять нас не может удовлетворить такое ограничение, т.к. при
его вычислении мы не учитывали наиболее употребительных три­
грамм. Значит, р^ля ее улучшения надо исследовать совместное рас­
пределение трех букв Р^ и подсчитать Н{Р^)/3^ что увеличит ка­
чество оценки, но не до конца. Этот процесс последовательного со­
вершенствования подводит нас к следуюш;ему определению.

Определение 4.8. Энтропия естественного языка L определяется
по формуле

п—^оо fi

Точное значение этого предела найти крайне сложно, но его мож­
но аппроксимировать. Фактически пользуются экспериментальной
4-4' Лодюные ключи и расстояние единственности I 15


оценкой, которая в случае английского языка имеет вид
1,0 ^ Я ь ^ 1,5.
Так что каждая буква
- требует 5 битов для представления в компьютере,
- но содержит в себе не более 1,5 битов информации.
Это свидетельствует о том, что естественный язык имеет высокую
степень избыточности, в чем легко убедиться на следующем предло­
жении, из которого все еще можно извлечь заложенный в нем смысл,
хотя там и удалены по две из каждых четырех букв^.

On** ир^^ а ^**е ^**ге **5 а ^^г1 ^^ah^d S^^w W^^te.

Формально избыточность языка вычисляется по правилу


log2#P
Положив HL ˜ 1,25, получим, что избыточность английского языка
равна
- - '''' =0,75.
log2 26
Таким образом, теоретически мы можем сжать десятимегабайтный
файл с английским текстом до 2,5 MB
Вернемся к общему шифру и предположим, что с G С^, т.е. с —
шифротекст, состоящий из п знаков. Определим К{с) как множество
ключей, с помощью которых из шифрограммы с получаются подда­
ющиеся интерпретации тексты. Тогда #1К(с) — 1 — число ложных
ключей для данного с. Среднее число ложных ключей обозначается
символом 'Sn- Оно равно
sn= Y^piC = c)i#K{c)-l) =

= -Y,PiC = c) =
J2P(C = C)#K(C)
CGC^ CGC^


5^p(C = c ) # K ( c ) ) - l .


^Поскольку наивно предполагать совершенное знание английского у русскоязыч­
ного читателя, его вниманию предлагается следующая известная строчка: «Бу**
мг**ю **бо к**ет, **хри **ежн** кру**». — Прим. перев.
Глава 4' Теоретико-информационная стойкость

Для достаточно большого п при условии # Р = # С получаем
log2(5„ + 1) = log2 Yl Pi*^ = С)#К(С) ^

^ y ^ p{C = c) log2 #IK(c) > (неравенство Йенсена)

^ J2 P{C = c)H{K\c) =

= Я(7<'|С*) = (no определению)
= H{K) + HiP"") - HiC") и (формула (4.4))
« Н{К) + пНь - Я(С") = (т. к. п > 1)
= Н(К) - Н{С'')+
+ п(1 — /?i) log2 # Р ^ (по определению i?i,)
^F(K)-nlog2#C+
+ n ( l - i?b) log2 # P = ^ n log2 # C )
(T. K. Я ( С " ^ )

= H{K)- nRb log2 # P (T. K. # P = # C ) .
Итак, при больших n и # P = # C имеет место оценка:



При атаке на шифр нам хотелось бы понизить число ложных ключей
до нуля. Ясно, что с ростом длины шифротекста число ложных
ключей уменьшается. Расстоянием единственности шифра назы­
вают такую длину по шифротекста, начиная с которой число лож­
ных ключей становится равным нулю. Другими словами, это сред­
ний объем шифротекста, необходимый для точного вскрытия ключа
атакующим, имеюш;им неограниченные вычислительные ресурсы.
Для абсолютно стойких криптосистем щ = оо, но для других —
расстояние единственности может оказаться опасно малым. Оценим
По, положив в предыдуш;ей формуле Sn = 0:
,, log2#K
По ^ .
Rblog^W
Для шифра замены имеем
26
# Р = 26, # К - 26! « 4 . 10-
И используя значение RL = О, 75 для английского языка, получаем,
что расстояние единственности приблизительно равно
88,4
пп ^ ˜ 25.
° 0,75-4,7
4.4- Лооюные ключи и расстояние единственности

Таким образом, теоретически нам достаточно шифротекста из 25
букв ^1^ля взлома шифра замены, если у нас неограниченные вычисли­
тельные возможности. Во всяком случае мы ожидаем, что шифро-
текст, содержаш;ий свыше 25 букв, расшифровывается однозначно.
Предположим теперь, что у нас есть современный шифр, кото­
рый шифрует строку битов с помощью ключа, состоявшего из / би­
тов, тогда
# Р - 2, # К = 2К
Вновь считая, что RL = О, 75 (что не совсем верно, поскольку теперь
=
нам нужно какое-нибудь электронное представление языка, напри­
мер, код ASCn), находим расстояние единственности
I 41

Теперь рассмотрим ситуацию, когда перед передачей текст в фор­
мате ASCn сжимается. Если при этом пользоваться идеально ар-
хивируюш;им алгоритмом, то сжатый текст уже не будет обладать
избыточностью, т. е. значение М/ станет очень близким к 0. В этом
случае расстояние единственности будет выглядеть как
I
щ^ - = сх).
Возникает естественный вопрос: могут ли современные криптоси­
стемы зашифровать текст с нулевой избыточностью? Ответ — нет:
даже если современный шифр и сжимает данные, для увеличения
криптостойкости он добавляет некоторую избыточную информа­
цию к открытому тексту перед шифрованием.
Мы только что исследовали возможности так называемой пас­
сивной атаки, т. е. атаки на шифр, при которой атакуюш;ий может
исследовать только шифротекст и по нему должен восстановить се­
кретный ключ. Суш;ествуют атаки и другого типа. Их называют
активными. Следуя тактике активной атаки, нападаюш;ий генери­
рует открытый текст или шифрограмму по своему выбору и подсо­
вывает свой продукт законным пользователям для шифрования или
расшифрования, в зависимости от ситуации. Первая разновидность
активной атаки называется атакой с выбором открытого текста, а
вторая — с выбором шифротекста.
В криптосистемах с открытым ключом, с которыми мы позна­
комимся дальше, невозможно препятствовать атаке с выбором от­
крытого текста, поскольку там любому позволено шифровать все
что угодно. Поэтому там следует ставить преграды перед атаками
Глава 4' Теоретико-информационная стойкость

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

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

ОГЛАВЛЕНИЕ

Следующая >>