Введение в современную криптографию
жүктеу/скачать 6.4 Mb. Pdf көрінісі
|
- Бұл бет үшін навигация:
- ТЕОРЕМА B.15
| АЛГОРИТМ 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 (ошибка), понимая, что это не оказывает существенного влияния на анализ. жүктеу/скачать 6.4 Mb. Достарыңызбен бөлісу:
|