An algorithm for generating a pair of special primes.pdf В 2006 г. М. Дж. Хинек предложил вариант криптосистемы RSA, устойчивой к атакам на малую секретную экспоненту, которая была названа Common Prime RSA. Простые сомножители p и q модуля Common Prime RSA выбираются такими, чтобы числа g = 1(p - 1,q- ^ h = (pq- 1) (1) были также простыми, причём число g должно быть достаточно большим. Система Common Prime RSA не получила распространения. Этот факт связан с малым количеством публикаций по её анализу. Большинство атак на данную разновидность RSA были также предложены М. Дж. Хинеком (см., например, [2]). Не способствует распространению и отсутствие острой необходимости использовать малые секретные экспоненты; другим сдерживающим фактором использования Common Prime RSA является долгая генерация ключей. Простейшая версия алгоритма генерации простых сомножителей модуля криптосистемы Common Prime RSA, предложенная в [1], описана ниже. Алгоритм 1. (Хинек, [1]) Вход: натуральные n и m, m < n Выход: пара n-битовых простых чисел p и q, таких, что g и h, определяемые равенствами (1), простые, а g имеет битовый размер m 1: Выбрать случайное простое m-битовое число g. 2: Повторять 3: Выбрать случайные положительные целые (n - m - 1)-битовые числа а и b; 4: p := 2gа + 1, q := 2gb +1, h := 2gab + а + b 5: Пока p, q, h - не простые или (а, b) = 1; 6: Вывести p, q. В работе [1] отмечается, что алгоритм 1 не оптимизирован. Отметим, что простые числа можно генерировать в двух независимых подциклах. Кроме того, эксперименты показывают, что неудачный выбор простого числа g может привести к тому, что время работы алгоритма будет существенно больше среднего времени работы для заданных параметров n и m. Отсюда целесообразно генерировать простое число g внутри цикла. Заметим, что самой частой и трудоёмкой операцией алгоритма является тест на простоту. На его первом этапе проверяется, что число не делится на малые простые. Этот этап можно ускорить, учитывая специальный вид простых. Например, вместо проверки условия r|(2ga+1) нужно проверять условие а = (-2g)-1 (mod r) для малого простого r. Алгоритм 2 Вход: натуральные n и m, m < n; натуральный параметр метода k Выход: пара n-битовых простых чисел p и q, таких, что g и h, определяемые равенствами (1), простые, а g имеет битовый размер m 1: Построить k первых простых чисел p1,... , . 2: Повторять 3: Используя технику просеивания, выбрать случайное простое m-битовое число g. 4: Вычислить gi := (-2g)-1 mod pi для всех i = 1,... , k. 5: Повторять 6: Используя технику просеивания, выбрать случайное (n - m - 1)-битовое положительное целое а, такое, что gi = а mod pi, i = 1,..., k. 7: Вычислить p := 2ga + 1 8: Пока p не простое 9: Вычислить hi := a(-2ga - 1)-1 mod pi для всех i = 1,..., k. 10: Повторять 11: Используя технику просеивания, выбрать случайное (n - m - 1)-битовое положительное целое b, такое, что gi = b mod pi, hi = b mod pi, i = 1, . . . , k. 12: Вычислить q := 2gb + 1 13: Пока q не простое и (a, b) = 1 14: Вычислить h := 2gab + а + b 15: Пока h не простое 16: Вывести p, q Алгоритмы реализованы на языке программирования C++ с использованием библиотеки NTL [3]. В таблице проводятся результаты экспериментов на компьютере с процессором Intel core i7 с тактовой частой 3,33 ГГц при значении параметра k = 100. Время работы алгоритмов варьируется в пределах, отличающихся на порядок. В связи с этим в таблице указано худшее время в трёх случайных экспериментах. Результаты экспериментов с 1024-битовым модулем p и q, биты g, биты Время алг. 1, с Время алг. 2, с 256 46 24 512 320 51 31 384 58 19 512 1082 213 1024 640 908 660 768 794 98 Из таблицы видно, что, несмотря на предложенное ускорение метода построения специальных простых, выработка модуля криптосистемы Common Prime RSA занимает неприемлемо большое время. Отметим, что выработка пары случайных простых чисел без дополнительных свойств занимает десятые доли секунды.

Скачать электронную версию публикации