В криптографії під випадковим простим числом розуміється просте число, що містить в двійковій запису задану кількість бітів k , На алгоритм генерації якого накладаються певні обмеження. Отримання випадкових простих чисел є невід'ємною частиною процедур вироблення ключів у багатьох криптографічних алгоритмах, включаючи RSA і ElGamal.

З огляду на те, що тестування простоти великих чисел вимагає істотних тимчасових витрат, вимога простоти одержуваного числа часто послаблюють до сильною псевдопростоти по декількох різних випадковим підставах. Існуючі алгоритми тестування сильної псевдопростоти на порядки швидше кращих відомих алгоритмів тестування простоти. У той же час, числа, які успішно пройшли тестування сильної псевдопростоти по декількох випадковим підстав, з великою вірогідністю є простими, причому ця ймовірність зростає зі зростанням кількості підстав, за якими проводиться тестування.


1. Вимоги до алгоритму та його реалізації

Вимоги до алгоритмів генерації випадкових простих чисел зводяться до таких двох:

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

2. Типові алгоритми генерації випадкових простих чисел

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

2.1. Тестування простоти

Перевірити (ймовірну) простоту числа 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 є простим.


2.2. Пряме побудову

  1. Згенерувати k-1 випадкових бітів і скласти з них k-бітове число p зі старшим бітом рівним 1.
  2. Збільшити p на 1 і перевірити його простоту. Повторювати цей крок до тих пір, поки не буде знайдено просте число.

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

2.3. (N -1)-методи

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

Типовий представник цього класу методів описаний в книзі "Введення в криптографію" під редакцією В. В. Ященко. [2]

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

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

Примітки

  1. Черьомушкін А. В. Лекції з арифметичним алгоритмам в криптографії. - М .: МЦНМО, 2002. - 104 с. - ISBN 5-94057-060-7
  2. Ю. В. Нестеренко Глава 4.5. Як будувати великі прості числа - nature.web.ru / db / msg.html? mid = 1157083 & uri = node33.html / / Введення в криптографію - nature.web.ru / db / msg.html? mid = 1157083 & uri = book.html / Под ред. В. В. Ященко. - Пітер, 2001. - 288 с. - ISBN 5-318-00443-1