Сколько итераций Рабина-Миллера я должен использовать для криптографически безопасных простых чисел?

Question

Я генерирую 2048-битное безопасное простое число для ключа типа Диффи-Хеллмана, p такое, что p и (p-1) / 2 оба просты.

Сколько итераций Рабина-Миллера я могу использовать как для p, так и для (p-1) / 2 и при этом быть уверенным в криптографически надежном ключе? В исследовании, которое я провел, я слышал все от 6 до 64 итераций для 1024-битных простых чисел, поэтому я немного запутался в этом вопросе. И как только это будет установлено, изменится ли число, если вы генерируете безопасное простое число, а не обычное?

Время вычислений имеет первостепенное значение, поэтому это практический вопрос - я в основном задаюсь вопросом, как найти минимально возможное количество тестов, с которыми я могу справиться при одновременном поддержании в значительной степени гарантированной безопасности. *

Answer 1

Предположим, что вы выбираете простое p , выбирая случайные значения, пока не найдете одно, для которого Миллер-Рабин говорит: это выглядит как простое число. Вы используете n раундов максимум для теста Миллера-Рабина. (Для так называемого «безопасного простого числа» ничего не меняется, за исключением того, что вы запускаете два вложенных теста.)

Вероятность того, что случайное 1024-разрядное целое число является простым, составляет около 1/900. Теперь вы не хотите делать глупостей, поэтому генерируете только нечетные значения (четное 1024-битное целое число гарантировано не простое), и, в более общем случае, вы запускаете тест Миллера-Рабина, только если значение не является «явно» не простым, то есть может быть разделено на небольшое простое число. Таким образом, в итоге вы пробуете около 300 значений с Миллером-Рабином, прежде чем попасть в простое число (в среднем). Если значение не простое, Миллер-Рабин будет обнаруживать его с вероятностью 3/4 в каждом раунде, поэтому число раундов Миллера-Рабина, которое вы проведете в среднем для одного непростого значения, составляет 1+ (1/4 ) + (1/16) + ... = 4/3. Для 300 значений это означает около 400 раундов Миллера-Рабина, независимо от того, что вы выберете для n .

Таким образом, если вы выберете n , например, равным 40, тогда стоимость, подразумеваемая n , будет меньше 10% от общей вычислительной стоимости. В процессе случайного выбора простых чисел преобладает критерий не простых чисел, на который не влияет значение n , которое вы выберете. Я говорил здесь о 1024-битных целых числах; для больших чисел выбор n еще менее важен, так как простые числа становятся более разреженными с увеличением размера (для 2048-битных целых чисел "10%" выше становятся "5%").

Следовательно, вы можете выбрать n = 40 и быть довольны этим (или, по крайней мере, знать, что сокращение n в любом случае не даст вам большой выгоды). С другой стороны, использование n больше 40 не имеет смысла, потому что это приведет вас к вероятностям ниже, чем риск простого неправильного вычисления. Компьютеры являются аппаратными, они могут иметь случайные сбои. Например, функция проверки простоты может возвращать «истину» для непростого значения, потому что космический луч (высокоэнергетическая частица, несущаяся через Вселенную на высокой скорости), попадает в нужный транзистор в нужный момент, переворачивая возвращаемое значение от 0 («ложь») до 1 («истина»). Это очень маловероятно - но не менее вероятно, чем вероятность 2 ^-80 . См. этот ответ на стекопоток для получения дополнительной информации. Суть в том, что независимо от того, как вы убедитесь, что целое число является простым, у вас все еще есть неизбежный вероятностный элемент, и 40 раундов Миллера-Рабина уже дают вам лучшее, на что вы можете надеяться.

Чтобы подвести итог, используйте 40 раундов.

Answer 2

Бумага Оценки средней ошибки случая для сильного вероятного простого теста Дамгарда-Ландрока-Померанса указывают, что, если вы случайно выберете k -битное нечетное число n и последовательно применять t независимых тестов Рабина-Миллера, вероятность того, что n является составным, имеет гораздо более сильные границы.

Фактически для 3 <= t <= k/9 и k >= 21,

Для простого числа k=1024, итерации t=6 дают коэффициент ошибок меньше 10^(-40).

Answer 3

Каждая итерация Рабина-Миллера уменьшает вероятность того, что число составное в 1/4 раза.

Таким образом, после 64 итераций в 2 ^ 128 существует только 1 вероятность того, что число составное.

Предполагая, что вы используете их для алгоритма открытого ключа (например, RSA), и предполагая, что вы комбинируете это с симметричным алгоритмом, использующим (скажем) 128-битные ключи, злоумышленник может угадать ваш ключ с эта вероятность.

Суть в том, чтобы выбрать количество итераций, чтобы поместить эту вероятность в приблизительную область других размеров, которые вы выбираете для своего алгоритма.

[обновить, уточнить]

Ответ полностью зависит от того, для каких алгоритмов вы собираетесь использовать числа и каковы наиболее известные атаки против этих алгоритмов.

Например, согласно Википедия :

По состоянию на 2003 год RSA Security заявляет, что 1024-битные ключи RSA эквивалентны по силе 80-битным симметричным ключам, 2048-битные ключи RSA - 112-битным симметричным ключам и 3072-битные ключи RSA - 128-битным симметричным ключам.

Итак, если вы планируете использовать эти простые числа для генерации (скажем) 1024-битного ключа RSA, то нет причин запускать более 40 итераций Рабина-Миллера или около того. Зачем? Потому что к тому времени, когда вы нажмете сбой, злоумышленник все равно сможет взломать один из ваших ключей.

Конечно, нет никаких оснований , а не выполнять больше итераций, если позволяет время. Просто не так много очков для этого.

С другой стороны, если вы генерируете 2048-битные ключи RSA, тогда 56 (или около того) итераций Рабина-Миллера более уместны.

Криптография обычно состоит из примитивов, таких как простое поколение, RSA, SHA-2 и AES. Если вы хотите сделать один из этих примитивов в 2 900 раз прочнее, чем другие, вы можете это сделать, но это все равно, что поставить стальную дверь хранилища длиной 10 футов в бревенчатую хижину.

На ваш вопрос нет четкого ответа. Это зависит от силы других частей, входящих в вашу криптографическую систему.

Все, что сказано, 2 ^ -128 - смехотворно малая вероятность, поэтому я, вероятно, просто использовал бы 64 итерации: -).

Answer 4

Из источника libgcrypt: /* We use 64 Rabin-Miller rounds which is better and thus sufficient. We do not have a Lucas test implementaion thus we can't do it in the X9.31 preferred way of running a few Rabin-Miller followed by one Lucas test. */ cipher / primegen.c строка # 1295

Answer 5

Я бы выполнил две или три итерации теста Миллера-Рабина (т. Е. Сильное вероятное простое число Ферма), убедившись, что одно из оснований равно 2.

Тогда я бы выполнил сильный вероятный простой тест Лукаса, выбрав D, P и Q с помощью метода, описанного здесь: https://en.wikipedia.org/wiki/Baillie%E2%80%93PSW_primality_test

Нет известных композитов, которые прошли бы эту комбинацию тестов Ферма и Лукаса.

Это намного быстрее, чем 40 итераций Рабина-Миллера. Кроме того, как указывалось Pomerance, Selfridge и Wagstaff в https://math.dartmouth.edu/~carlp/PDF/paper25.pdf,, при многократных тестах Ферма доходность уменьшается: если N является псевдопригодностью к одной базе, то это более вероятно, чем среднее число псевдоприемник к другим основаниям. Вот почему, например, мы видим, что так много основ 2 для psp также являются основанием 3. psp *

Answer 6

Меньшая вероятность обычно лучше, но я бы взял фактическое значение вероятности с крошкой соли.Альбрехт и др. Простое и предубеждение: тестирование простоты в условиях состязательности нарушает ряд процедур простого тестирования в криптографических библиотеках.В одном примере опубликованная вероятность составляет 1/2 ^ 80, но число, которое они строят, объявляется простым 1 раз из 16.

В некоторых других примерах их число проходит 100% времени.

Answer 7

Имеет ли это значение? Почему бы не запустить 1000 итераций? При поиске простых чисел вы в любом случае прекращаете применять тест Рабина-Миллера в первый раз, когда он терпит неудачу, поэтому в течение времени, необходимого для поиска простого числа, на самом деле не имеет значения, какова верхняя граница числа итераций. Вы могли бы даже запустить алгоритм проверки детерминированной простоты после этих 1000 итераций, чтобы быть полностью уверенным.

При этом вероятность того, что число простое после n итераций, составляет 4 ^ -n.