Випадкове просте число

У криптографії під випадковим простим числом розуміється просте число, що містить у двійковому записі задану кількість бітів $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. Згенерувати $k-1$ випадкових бітів і скласти з них k-бітове число p зі старшим бітом рівним 1.
2. Збільшити p на 1 і перевірити його простоту. Повторювати цей крок доти, поки не буде знайдено просте число.

Другий крок можна прискорити, якщо розглядати тільки непарні числа або числа, порівнянні з 1 і 5 за модулем 6 тощо.

(n-1)-методи

(n-1)-методи побудови простих чисел використовують знання про прості дільники числа n-1 для тестування простоти n за допомогою тесту простоти Люка.

Типового представника цього класу методів описано в книзі «Вступ до криптографії» під редакцією В. В. Ященко.

Генерування простих чисел Софі Жермен

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