Введение в современную криптографию



Pdf көрінісі
бет245/249
Дата14.06.2023
өлшемі6.4 Mb.
#475029
1   ...   241   242   243   244   245   246   247   248   249
Криптография Катц

АЛГОРИТМ B.14
Выбор элемента однородной группы
Вход: (Описание) группы G; параметр длины A; параметр t
Выход: Однородный элемент группы G
for i = 1 to t:
Выбрать однородный if x ∈ G return x
return “fail”
Очевидно, что всякий раз, когда указанный выше алгоритм не выводит fail (ошиб-
ка), он выводит равномерно распределенный элемент G. Это просто потому, что 
каждый элемент G с равной вероятностью может быть выбран в любой итерации. С 
формальной точки зрения, если допустить, чтобы Fail было событием, при котором 
алгоритм выводит fail (ошибка), то для любого элемента g∈ G имеем
Pr[выход алгоритма равен g | Fail] =1/|G| 
Какова вероятность того, что алгоритм выводит fail (ошибка)? При любой 
итерации, в ероятность того, что x ∈ G равно точно |G|/2A, и вероятность того, 
что x не лежит в G при любой из t итераций равна
Существует компромисс между временем работы алгоритма B.14 и вероят-
ностью того, что алгоритм выводит fail (ошибка): увеличение t уменьшает ве-
роятность ошибки, но увеличивает время работы в худшем случае. Для крип-
тографических приложений нам нужен алгоритм, при котором время работы 
в худшем случае было бы полиномом в параметре безопасности n, тогда как 
вероятность ошибки пренебрежимо мала в n. Пусть K 2A/|G|. Если задать 
t := K • n, то вероятность того, что алгоритм выводит fail (ошибка) равна:
при использовании предположения A.2. Таким образом K = poly(n) (мы пред-
полагаем некий алгоритм групповой генерации, который зависит от параметра 
безопасности n, и, таким образом, как |G|, так и A являются функциями n), мы 
получаем алгоритм с нужными свойствами.
Случай ZN . Рассмотрим группу ZN , при n = ||N||. Проверка, является ли 
n-битная строка x (интерпретируется как положительное целое число длиной 
не более n) элементом ZN, просто требует проверки, что x < N . Кроме того,


331
и поэтому мы может отобрать однородный элемент ZN в течение времени 
poly(n) и с пренебрежимо малой вероятностью ошибки в n.
Случай ZN* . Рассмотрим следующую группу ZN* , при n = ||N|| , как и ра-
нее. Определить, является ли n-битная строка x элементом ZN* так же просто 
(см.пражнения). Более того,
Верхняя граница poly(n) является следствие приведенной ниже теоремы.
ТЕОРЕМА B.15 Для N ≥ 3 длиной n, имеем N/φ(N )< 2n.
(Известны более строгие ограничения, но для нашей цели достаточно указанных 
выше). Теорему можно доказать с помощью постулата Бертрана (теорема 8.32), но мы 
ограничимся доказательством двух особых случаев: когда N является простым числом 
и когда N является произведением двух (различных) простых чисел одинаковой длины.
Анализ прост, когда N – четное число. Здесь φ(N ) = N − 1, и таким образом
(используя тот факт, что N является нечетным для второго неравенства ). Рассмотри 
следующий случай N = pq для p и q различных, нечетных простых чисел. Тогда
Мы пришли к выводу, что когда N является простым или произведением двух 
различных нечетных простых чисел, существует алгоритм для генерации одно-
родного элемента ZN*, который действует в течение времени полинома в n = 
||N|| и выводит fail (ошибка) с вероятностью пренебрежимо малой в n.
На протяжении этой книги, когда мы говорим об отборе однородного элемен-
та из ZN или ZN* мы попросту игнорируем пренебрежимо малую вероятность 
вывода fail (ошибка), понимая, что это не оказывает существенного влияния на 
анализ.


Достарыңызбен бөлісу:
1   ...   241   242   243   244   245   246   247   248   249




©dereksiz.org 2024
әкімшілігінің қараңыз

    Басты бет