Processing math: 100%

Случайное простое число

 В криптографии под случайным простым числом понимается простоечисло, содержащее в двоичной записи заданное количество битов k, наалгоритм генерации которого накладываются определенные ограничения.Получение случайных простых чисел является неотъемлемой частью процедурвыработки ключей во многих криптографических алгоритмах, включая RSA иElGamal.
 Ввиду того, что тестирование простоты больших чисел требует существенныхвременных затрат, требование простоты получаемого числа часто ослабляютдо сильной псевдопростоты по нескольким различным случайным основаниям.Существующие алгоритмы тестирования сильной псевдопростоты на порядкибыстрее лучших известных алгоритмов тестирования простоты. В то жевремя, числа, успешно прошедшие тестирования сильной псевдопростоты понескольким случайным основаниям, с большой вероятностью являютсяпростыми, причём эта вероятность растет с ростом количества оснований,по которым проводится тестирование.

Требования к алгоритму и егореализации


 Требования к алгоритмам генерации случайных простых чисел сводятся кследующим двум:

  • Распределение получаемых простых чисел должно быть близко к равномерному на множестве всех k-битных простых чисел. Существует несколько способов обеспечить выполнимость этого требования.
  • Процесс генерации конкретного случайного простого числа нельзя воспроизвести, даже зная детали алгоритма и его реализации. Обычно выполнение этого требования обеспечивается использованием криптостойкого ГПСЧ, проинициализированного некоторым ключом, получаемым извне (т. е. не являющимся частью алгоритма или его реализации). В качестве ключа может выступать, например, значение криптографической хеш-функции от секретной фразы, запрашиваемой у пользователя.

Типовые алгоритмы генерации случайных простыхчисел


 Везде далее предполагается использование криптографически стойкого ГПСЧ,проинициализированного с помощью секретного ключа (детали зависят отиспользуемого ГПСЧ и способа получения и представления ключа).

Тестированиепростоты


 Проверить (вероятную) простоту числа p, содержащего kбитов, можно так:

  1. Убедиться, что p не делится на небольшие простые числа 3, 5, 7, 11, и т.д. до некоторого небольшого предела (например, 256). Такая проверка позволяет эффективно отсечь множество заведомо составных чисел, прежде чем проверять их посредством более трудоёмких алгоритмов. Так, проверка делимости p на простые числа 2, 3, 5 и 7 отсеивает все четные числа и 54 делимости p на все простые числа до 100 отсеивает 76 чисел, а проверка делимости p на все простые числа до 256 отсеивает 80
  2. Выполнить тест Миллера — Рабина с количеством раундов не меньше k.

 Если число p не проходит хотя бы одной проверки — оно неявляется простым. В противном случае с большой вероятностью (зависящейот количества раундов) число p является простым.

Прямоепостроение



  1. Сгенерировать k1 случайных битов и составить из них k-битное число p со старшим битом равным 1.
  2. Увеличить p на 1 и проверить его простоту. Повторять этот шаг до тех пор, пока не будет найдено простое число.

 Второй шаг можно ускорить, если рассматривать только нечетные числа иличисла сравнимые с 1 и 5 по модулю 6 и т.п.

(n

—1)-методы
 (n—1)-методы построения простых чисел используют знание опростых делителях числа n—1 для тестирования простоты nс помощью теста простоты Люка.
 Типичный представитель этого класса методов описан в книге «Введение вкриптографию» под редакцией В. В. Ященко.

Генерация простых чисел СофиЖермен


 Простые числа Софи Жермен — такие простые p, что 2p + 1 тоже простое.