Анализ криптосистем с открытым ключом

При анализе и построении асимметричных систем возникают задачи тестирования большого натурального числа п на простоту и построения больших простых чисел.

Распознавание простоты числа

Простейший метод распознавания простоты числа п — метод пробных делений. Если п = ah, то min{", /;} < yfn. Тогда для определения min{", h} достаточно проверить делимость п на d, где d — 2, 3, …, Lyfnj. Реализация метода требует менее 4п проверок, каждая из проверок требует выполнения конечного числа арифметических операций с целыми числами. Модификация метода связана с проверкой делимости п на 2 и на 3 и в случае отрицательного ответа — с проверкой делимости nmd только для чисел d вида 1 + 6/ и 5 + 6/, j = 1, 2, … Сложность метода примерно в три раза меньше и имеет также порядок 0(4п).

Для составления таблицы простых чисел из множества N_m используют метод решета Эратосфена. В порядке возрастания перебираются все простые числа. Из ряда чисел 2, 3,…, т сначала удаляются все числа, делящиеся на 2, кроме числа 2. Затем удаляются все числа, делящиеся на 3, кроме числа 3, и т. д. По вычислительной сложности метод является наилучшим, но при больших т реализация метода требует памяти большого размера.

Ряд тестов основан на малой теореме Ферма: если п простое, то а^п = = «(modп) для а е Z и «^w₁ = l (mod/z) при (а, п) = 1. Для проверки простоты числа п следует проверить второе сравнение для некоторого а е Z, что потребует 0(log») арифметических операций при использовании «быстрого» возведения числа в степень в кольце вычетов Z_n. Если сравнение неверно для взятого «, то п составное. В противном случае вывод не однозначен, например, для составного числа 341 = 11*13 выполнено 2340= (mod 341). Этот тест называют тестом Ферма по основанию а. Прошедшие тест числа называют псевдопростыми числами по основанию «, число а называют свидетелем того, что п составное.

При случайном выборе числа а вероятность выполнения сравнения _ап- = (mod п) для составного п меньше ½ [11]. Если тест применить к раз по различным независимо выбранным основаниям …, a_k, то при выполнении всех сравнений вывод формулируется так: число п составное с вероятностью нс более 2~^к.

Недостаток теста Ферма в том, что существуют составные числа, которые выдерживают тест по всем основаниям. Для бесконечного множества составных чисел п, названных числами Кармайкла (наименьшие числа Кармайкла равны 561 = 3−11−17, 1105 и 1729), сравнение выполнено при любых ае Z, где (а, п) = 1. Числа Кармайкла нечетны, имеют не менее трех простых делителей, свободны от квадратов и если простое р п, то (р — 1) | (г? — 1). Частоту встречаемости чисел Кармайкла характеризует пример: среди чисел, не превосходящих 10¹⁶, имеется примерно 2,7 • 10¹⁴ простых чисел и 246 683 числа Кармайкла.

Числа Кармайкла компрометируют тест Ферма. Дальнейшее усовершенствование теста Ферма достигнуто в широко используемом вероятностном тесте Соловея — Штрассеиа.

Пусть требуется распознать простоту нечетного натурального п. Выбираем случайно к натуральных чисел а, меньших п. Если п простое, то по утверждению 5.2.

Для каждого а вычисляем обе части равенства по модулю п, вычисления требуют порядка 0(log³w) двоичных операций. Если тождество (16.2) не выполнено хотя бы для одного а, то п составное. В противном случае п — составное число с вероятностью не более 2~^к, так как для любого составного п тождество (16.2) не выполнено, по меньшей мере, для половины всех возможных а.

Улучшением теста Соловея — Штрассена является вероятностный тест Миллера — Рабина. Нечетное составное число п = 2Ч + 1 (здесь t — нечетное) называется сильно псевдопростым по основанию а, если либо a^r= 1 (mod гг), либо имеется число г из диапазона 0 < г < 5 такое, что а²'¹ = -l (mod гг). Для простого п одно из этих условий выполнено, так как tf («^_1)/2(rnod/?) = ±1 в силу тождества (16.2). Если при вычислении бг/2 (mod /?) получено -1, то п — сильно псевдонростое. Если получено +1, то при простом гг число _a(w-i)/4 (modгг) = ±1. Повторяя процедуру не более s раз, получаем, что гг — сильно псевдопростое.

Реализация теста Миллера — Рабина заключается в проверке сильной псевдопростоты числа гг по к различным основаниям. Если гг не сильно псевдопростое хотя бы для одного я, то п составное. В противном случае число п составное с вероятностью не более 4~*, так как нечетное составное п является сильно псевдопростым не более чем для п / 4 оснований а из диапазона 0 < а < п [5]. Нередко при проверке простоты числа п с использованием основания а предварительно вычисляется (я, п) с помощью алгоритма Евклида. Дальнейшая проверка выполняется только в случае (а, гг) = 1.

Тест Миллера — Рабина сильнее теста Соловея — Штрассена; если при данных гг и а тест Миллера — Рабина не показывает, что число гг составное, то тест Соловея — Штрассена дает тот же результат. При условии справедливости обобщенной гипотезы Римана показано, что для составного n имеется свидетель а Миллера — Рабина, не больший 0(log^[1][2]w). Тест Миллера — Рабина применяется для генерации простых чисел в американском стандарте DSS.

В ряде случаев требуется проворить простоту числа п при известном полном или частичном разложении на множители п - 1 или п + 1. Приведем один метод, некоторые другие методы описаны в работе [10].

Теорема 16.2. Пусть п — 1 = р^х…р^к/ — каноническое разложение, где нечетное п > 2. Если найдется а_х такое, что af^-1 s l (modra), aⁿ~^^Pi Ф Ф l (modn), i=l,…, s, то n простое.

Ч Пусть ord cij (а, — элемент группы Z*), i = 1, …, s. По условию т, | (п — 1) и т, не делит (и — 1 )/р, тогда q, т,-, где q, = ру, i = 1,… s. Значит, в Z* число // = (modп) имеет порядок <�у, а число b = b…b_s(mod") ;

порядок q_v.q_s= n — 1. Тогда Z_n — поле, n простое. ?

Следствие. Число Ферма п = 2^[2]* +1 — простое при к > 0 з<�"-1)/^[2] = = -l (modw). D>

Известны алгоритмы, доказывающие простоту чисел. Наиболее успешный с точки зрения применения на практике алгоритм основан на эллиптических кривых и назван ЕСРР (Elliptic Curve Primality Prover), хотя ответ он выдаст не для всех чисел. Есть также алгоритм Адлемана и Хуанга, гарантирующий окончание работы и доказательство простоты данного простого числа. Ввиду сложности этот алгоритм не нашел практического применения.

Разработанный в начале 1980;х гг. детерминированный алгоритм Адлемана, Померанса и Румели¹, а также последовавшее его упрощение (алгоритм X. Ленстры^[2]) имеют неулучшаемую оценку сложности 0((log ft) ciogl°giogn), _с _ константа. Алгоритм Ленстры проверял простоту чисел п порядка 10¹⁰⁰ за несколько минут.

Индийские математики^[6] представили полиномиальный детерминированный алгоритм проверки простоты числа, имеющий сложность 0((log¹²w) (log log пУ).

• [1] Adleman L., Pomerance C., Rumely R. S. On distinguishing prime numbers from compositenumbers // Ann. Math. 1983. Vol. 117. P. 173−206.
• [2] Lenstra H. W. Primality testing algorithms (after Adleman, Rumely and Williams) //Bourbaki Seminar. Vol. 1980/81. 1981. (Lect. Notes in Math.; Vol. 901). P. 243—257.
• [3] Lenstra H. W. Primality testing algorithms (after Adleman, Rumely and Williams) //Bourbaki Seminar. Vol. 1980/81. 1981. (Lect. Notes in Math.; Vol. 901). P. 243—257.
• [4] Lenstra H. W. Primality testing algorithms (after Adleman, Rumely and Williams) //Bourbaki Seminar. Vol. 1980/81. 1981. (Lect. Notes in Math.; Vol. 901). P. 243—257.
• [5] Lenstra H. W. Primality testing algorithms (after Adleman, Rumely and Williams) //Bourbaki Seminar. Vol. 1980/81. 1981. (Lect. Notes in Math.; Vol. 901). P. 243—257.
• [6] Agrawal M., Kayal N., Saxena N. PRIMES is in P. Preprint, August 2002.