ФЭНДОМ


В криптографии под случайным простым числом понимается простое число, содержащее в двоичной записи заданное количество битов 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 Править

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

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

Типовой алгоритм 2 Править

Этот алгоритм описан в книге «Введение в криптографию» под редакцией В. В. Ященко.[1]

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

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

Ссылки Править

  1. «Как строить большие простые числа», глава 4.5 из книги «Введение в криптографию» под редакцией В. В. Ященко.

en:Generating primes

Обнаружено использование расширения AdBlock.


Викия — это свободный ресурс, который существует и развивается за счёт рекламы. Для блокирующих рекламу пользователей мы предоставляем модифицированную версию сайта.

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

Также на ФЭНДОМЕ

Случайная вики