Современная криптография - Венбо Мао
ISBN 5-8459-0847-7
Скачать (прямая ссылка):
Вероятность события Е
Условная вероятность события Е, т.е. вероятность того, что событие Е произойдет, если произошло событие F
Факториал числа п, равный п(п — 1)(п — 2)... 1, причем 0! = 1
Число сочетаний из п элементов по к, равное
хУ у
к\ (п - к)\
Биномиальное распределение к успехов среди п испытаний в схеме Бернулли, если вероятность успеха равна р
Функция д(п), такая что \д(п)\ ^ с|/(п)|, где с > 0 -некая константа, для всех достаточно больших чисел п
О () в поразрядных вычислениях
Логическая операция НЕ (х — булева переменная) либо побитовая операция: поразрядное отрицание (ж — битовая строка)
Логическая операция И (х, у — булевы переменные) либо побитовая операция: поразрядное И (х, у — битовые строки)
Логическая операция ИЛИ (х, у — булевы переменные) либо побитовая операция: поразрядное ИЛИ (х, у — битовые строки)
92
Часть II. Математические основы
Аргумент Описание
х®у Логическая операция ИСКЛЮЧАЮЩЕЕ ИЛИ (х, у — буле-
вы переменные) либо побитовая операция: поразрядное ИСКЛЮЧАЮЩЕЕ ИЛИ (х, у — битовые строки)
(*•--*) Комментарии в алгоритмах или протоколах
? Конец доказательства, замечания или примера
Глава 3
Теория вероятностей и теория информации
3.1 Введение
Теория вероятностей и теория информации образуют фундамент современных криптографических методов.
Вероятность — основное средство анализа безопасности. Часто возникает необходимость оценить, насколько вероятно некое опасное событие при определенных условиях. Например, рассматривая протокол "Подбрасывание монеты по телефону", описанный в главе 1, мы должны оценить вероятность того, что Алиса найдет коллизию однонаправленной функции / (желательно, чтобы эта вероятность была как можно меньше), а также вероятность того, что Боб распознает четность числа х при заданной функции f(x) (желательно, чтобы эта вероятность была как можно ближе к числу |).
Теория информации тесно связана с теорией вероятностей. Важным аспектом безопасности алгоритмов шифрования является "неопределенность шифров": алгоритм должен создавать текст, имеющий случайное распределение по всему пространству зашифрованных текстов. Шеннон (Shannon) дал количественную оценку неопределенности информации, введя понятие энтропии. С исторической точки зрения стремление достичь высокой энтропии шифров происходит от потребности максимально затруднить расшифровку, которая использует избыточность естественных языков и частое употребление распространенных устойчивых выражений.
В последнее время потребность обеспечить вероятностное поведение современных криптографических систем, в частности, криптосистем с открытым ключом, приняла еще более строгую форму — возникла необходимость обеспечить семантическую стойкость (semantic security). Это свойство можно описать следующим образом. Допустим, Алиса шифрует нуль и единицу с одинаковой вероятностью, используя семантически безопасный алгоритм шифрования, посылает зашифрованный текст Бобу и просит его ответить, чему равно зашифрованное число. Если Боб не имеет правильного ключа расшифровки, то не должен суще-
94
Часть II. Математические основы
ствовать алгоритм, который позволил бы ему выбрать один из двух возможных вариантов с вероятностью, выше, чем вероятность простого угадывания. Следует отметить, что многие учебные алгоритмы шифрования не обладают этим свойством.
3.1.1 Структурная схема главы
Основные понятия теории вероятностей, достаточные для понимания всей книги, изложены в разделах 3.2-3.6. Теория информации излагается в разделах 3.7-3.8.
3.2 Основные понятия теории вероятностей
Пусть S — произвольное, но фиксированное множество точек, называемое полем вероятностей (probability space) или выборочным пространством (sample space). Любая точка х G S называется выборочным элементом (sample point) или исходом (outcome), простым событием (simple event), а также неразложимым событием (indecomposable event). (Для краткости мы будем называть этот элемент просто точкой (point).) Событие (составное, или разложимое) является подмножеством множества S и обычно обозначается прописной буквой (например, Е). Эксперимент (experiment), или наблюдение, представляет собой извлечение точки из множества S. Событие Е происходит, если в результате эксперимента выясняется, что некоторая точка х из S принадлежит множеству Е.
Пример 3.1. Рассмотрим эксперимент, в ходе которого из "идеальной" колоды извлекается игральная карта (термин "идеальная" означает, что карта извлекается случайным образом). Перечислим некоторые примеры поля вероятностей, точек и событий.
1. Si: пространство состоит из 52 точек — по одной на каждую карту. Допустим, что событие Ei обозначает '*туз" (т.е. Е\ = {Tdfr, TV, ТО, ТО*}). Оно происходит, если из колоды извлекается туз любой масти.
2. §2 = {красная масть, черная масть}. Допустим, что Е2 = {красная масть}. Это событие происходит, если из колоды извлекается карта красной масти.
3. S3: пространство состоит из 13 точек — 2, 3,4,..., 10, В, Д, К, Т. Допустим, что Е3 = {числа}. Это событие происходит, если из колоды извлекается карта 2, или 3,..., или 10. ?
