стр. 17 |
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 |