Современная криптография - Венбо Мао
ISBN 5-8459-0847-7
Скачать (прямая ссылка):
Пример 3.11. Как указано в главе 1, в книге рассматривается множество атак на криптографические алгоритмы и протоколы. В главе 14 мы опишем и изучим четыре разновидности атак на алгоритмы шифрования. Эти атаки имеют довольно длинные названия.
• Пассивная атака на основе неразличимых исходных текстов (passive plaintext indistinguishable attack).
• Активная атака на основе неразличимых подобранных исходных текстов (active plaintext indistinguishable attack in the chosen-plaintext mode).
• Активная атака на основе неразличимых подобранных зашифрованных текстов (active plaintext indistinguishable attack in the non-adaptive chosen-cipther-text mode).
Глава 3. Теория вероятностей и теория информации
115
• Активная атака на основе неразличимых адаптивно подобранных зашифрованных текстов (active plaintext indistinguishable attack in the adaptive chosen-ciphertext mode).
Полное описание этих атак будет дано в главе 14, а пока мы отметим два важных обстоятельства.
1. Использование длинных названий вполне обоснованно, поскольку они содержат большое количество информации.
2. В главе 14 будут рассмотрены только четыре атаки, перечисленные выше.
Поскольку в главе 14 мы опишем только эти четыре атаки, фактическая энтропия их названий равна как минимум 2 бит. Однако, так как в главе 14 будут использованы числа 0, 1, 2 и 3 и некоторые другие символы (например, буква "а", индексы "г" и "j", параметр к и т.п.), для однозначной идентификации атак нам придется использовать больше двух бит.
Обратите внимание на то, что в главе 14 мы не используем строки, имеющие вид аО, al, а2 и аЗ, хотя название каждой из атак можно было бы сократить именно так, не теряя однозначного соответствия. Следовательно, в рамках главы 14 энтропию названия атак можно было бы снизить до 4,7 + 2 = 6,7 бит на одно название. Здесь число 4,7 относится к букве "а", а два бит — к цифрам 0, 1, 2 и 3.
С другой стороны, путем простого подсчета читатели могут убедиться, что средняя длина четырех длинных названий перечисленных выше атак равна 62,75 буквы (в английском варианте. — Прим. ред.). Следовательно, среднее количество бит на букву в этих именах равно 6,7/67,75 = 0,107. Используя этот результат, мы можем вычислить избыточность длинных названий атак, изученных в главе 14.
Итак, указанные выше длинные названия атак чрезвычайно избыточны!
Однако отрасль науки, изучающей криптографические системы с доказуемой сильной стойкостью, намного шире, чем тема, рассмотренная в главе 14. Следовательно, имена аО, al, а2 и аЗ, использованные в примере 3.11, являются слишком короткими (их использование может привести в неоднозначному пониманию сущности атаки и создать неудобства). На самом деле сокращенные названия последних трех атак, перечисленных в примере 3.11, выглядят так: IND-CPA, IND-CCA и IND-CCA2 соответственно. Именно эти названия используются в главе 14.
В заключение отметим, что сокращения приняты только для последних трех атак, поскольку именно эти атаки изучаются чаще других. Первая атака известна под своим полным названием "passive (plaintext indistinguishable) attack", поскольку ее легко предотвратить и она рассматривается довольно редко.
6,7 - 0,107 6,7
> 98%.
?
116
Часть II. Математические основы
3.9 Резюме
В главе рассмотрены элементарные основы теории вероятностей и теории информации. Однако изложенного материала вполне достаточно для понимания остальной части книги.
Применяя теорию вероятностей, необходимо владеть основными понятиями, а также знать свойства и правила вычисления вероятностей. Следует подчеркнуть, что достичь хорошего знания теории вероятностей совсем не сложно — закон полной вероятности, закон больших чисел и парадокс дней рождений можно доказать на основе интуитивно понятных элементарных свойств и правил.
В остальной части книги мы будем широко использовать условную вероятность, закон полной вероятности, биномиальные распределения и парадокс дней рождений (в качестве яркого примера его применения мы описали Л-алгоритм Полларда).
В главе изложены основы теории информации. Теперь читатели знают, что энтропия источника сообщения представляет собой меру объема информации, содержащейся в сообщениях, порождаемых этим источником, или степени случайности (непредсказуемости) этих сообщений.
Упражнения
3.1. Предположим, игральные кубики выкидываются один за другим. Определите вероятность следующих событий.
а) Сумма очков равна 7, 1 или не превосходит 12.
б) Количество очков на первом игральном кубике меньше, чем количество очков на втором игральном кубике.
в) По крайней мере на одном из игральных кубиков выпало шесть очков.
г) На обоих игральных кубиках выпало по шесть очков.
3.2. Вычислите вероятность того, что в предыдущей задаче на первом игральном кубике выпало три очка, если сумма очков на обоих кубиках не меньше восьми.
3.3. Допустим, что 4,5% населения и 0,6% женщин являются дальтониками. Каков процент дальтоников среди мужчин, доля которых равна 49,9%? Подсказка: примените закон полной вероятности.
3.4. Предположим, что случайная величина в равномерно распределена на интервале [—7г/2,7г/2]. Найдите вероятность того, что в ^ 1/2, и того, что |sin0| ^ 1/2.
