Современная криптография - Венбо Мао
ISBN 5-8459-0847-7
Скачать (прямая ссылка):
Пример 3.6. (В этом примере используются некоторые элементарные факты из теории чисел. Читатель, которому этот пример покажется слишком сложным, может вернуться к нему после изучения главы 6.)
Пусть р = 29 + 1, причем числа р и q являются простыми. Рассмотрим простой случайный выбор двух чисел g и h из множества S = {1,2,... ,р — 1} (с возвращением). Пусть событие А заключается в том, что "число h порождается числом д", иначе говоря, h = gK(modp) для некоторого числа х < р (т.е. существует число logfl h(mod(p— 1))/ Чему равна вероятность события А для случайных чисел g и h?
Можно непосредственно оценить вероятность РгоЬ[Л]. Однако намного легче сначала оценить несколько условных вероятностей, а затем применить теорему о полной вероятности.
Обозначим через ordp(g) мультипликативный порядок числа g(modp), т.е. наименьшее натуральное число г, такое что дг = l(modp). Величина РгоЬ[Л] зависит от вероятностей четырех взаимоисключающих событий.
1. Ei : ordp(g) = р— 1 = 2q. Кроме того, нам известна вероятность Prob[.Ei] = _ _ 2^1 (здесь ф _ функция Эйлера, а в множестве <S существует точно $(2д) = ?—1 элементов порядка 2q). В данном случае любое число h, удовлетворяющее условию h < р, должно порождаться числом д (число д является порождающим, или образующим элементом множества «S). Следовательно, Prob[j4|i?i] = 1.
2. Е2 : ordp(g) = q и (аналогично варианту 1) известна вероятность Probf-Cy = = В данном случае число h может порождаться числом д тогда и только тогда, когда ordp(h)\q. Поскольку в множестве «S существует ровно q элементов, порядки которых являются делителем числа q, получаем РгоЬ^-Ег] =
Глава 3. Теория вероятностей и теория информации
99
3. ?3 : ordp(g) = 2. Поскольку существует только один элемент порядка 2, а именно, число р — 1, получаем РгоЬ[?з] = Число р — 1 может порождать только числа 1 и р — 1, поэтому РгоЬ|А|Ез] = фу.
4. ?4 : ordp(g) = 1. Только число 1 имеет порядок 1, поэтому Probf-Ei] = = -~. Кроме того, число 1 может порождать только число 1, поэтому
РгоЬ[Л|Е4] - ф.
События, перечисленные выше, не являются взаимоисключающими, однако (они исчерпывают все варианты порядка, который может иметь число д. Следовательно, мы можем применить теорему о полной вероятности и вычислить вероятность РгоЬ[Л]:
Prob А = *—- +-- +---2 + ---тз-
р-1 2(р-1) (р-1)2 (р-1)2 ?
3.5 Случайные величины и распределения вероятностей
В криптографии, как правило, изучаются функции, определенные в дискретном пространстве (например, в качестве пространств криптографических ключей используются интервалы целых чисел либо конечные алгебраические структуры, такие как конечные группы или поля). Допустим, что дискретное пространство S содержит конечное или счетное количество изолированных точек х\, х2, ¦ ¦¦, x#s-Рассмотрим общий случай, когда пространство S содержит счетное количество точек, т.е. #5 = оо. Это позволит провести анализ асимптотической вычислительной сложности наших алгоритмов и протоколов (см. раздел 4.6).
Определение 3.5 (Дискретная случайная величина и ее функция распределения).
/. Дискретная случайная величина является числовым результатом эксперимента. Она представляет собой функцию, определенную на дискретном выборочном пространстве.
2. Пусть S — дискретное пространство вероятностей, а ? — случайная величина. Функция распределения дискретной случайной величины f представляет собой отображение § i—> R, заданное перечислением вероятностей
Prob[e = xi]=pg(« = l>2,...J#S)>
удовлетворяющих следующим условиям-a) Pi ^ 0;
100
Часть II. Математические основы
б) Еи = 1-
i=l
Рассмотрим теперь два дискретных распределения, которые часто используются в криптографии. В дальнейшем мы будем пропускать слою "дискретный", поскольку все изучаемые нами распределения являются дискретными.
3.5.1 Равномерное распределение
Наиболее часто в криптографии применяются случайные величины, имеющие равномерное распределение (uniform distribution):
Pn>bK = a:i] = ^(« = l12I...,#S).
Пример 3.7. Пусть S — множество неотрицательных чисел, состоящих из не более чем к бит (бинарных цифр). Выберем из множества S случайную точку х, придерживаясь равномерного распределения. Покажем, что вероятность извлечь число, состоящее из к бит, равна ^.
Множество S = {0,1,2,..., 2к - 1} можно разбить на два непересекающихся подмножества: Si = {0,1,2,...,2к- 1 - 1} и S2 = {2h~l,2k~l + 1,...,2к -— 1}, где множество 5г состоит из всех fc-разрядных чисел, #5i = = ^г. Применяя второе правило сложения вероятностей, получаем следующее.
2*-1
Prob[x € S2] = Prob (J {x = i} =
t=2fc-1
2fc-l
= Probfrc = г] =
t=2fc-l 2*-l
= У — =
1
~ 2" ?
Выражение "выберем из множества S случайную точку х, придерживаясь равномерного распределения" часто встречается в криптографии. Поскольку оно слишком многословно, мы будем использовать более короткое выражение "выберем из S равномерно распределенную величину р" или просто обозначение
Глава 3. Теория вероятностей и теория информации
101
3.5.2 Биномиальное распределение
Допустим, что эксперимент имеет только два исхода — успех или неудача (например, "ОРЕЛ" или "РЕШКА" при подбрасывании монеты), причем их вероятности постоянны. Повторяющиеся независимые эксперименты, удовлетворяющие этим условиям, называются испытаниями Бернулли (Bernoulli trials). Предположим, что в отдельном испытании
