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

Ответ 1

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

Вероятность того, что случайное 1024-битное целое число составляет около 1/900. Теперь вы не хотите делать что-то глупое, чтобы вы генерировали только нечетные значения (даже однобайтовое целое число гарантировано нестандартное), и, в более общем плане, вы запускаете тест Миллера-Рабина, только если значение не является "очевидно" непустое", т.е. можно разделить на малые простые числа. Таким образом, вы получаете около 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 ( "false" ) до 1 ( "true" ). Это очень маловероятно - но не менее вероятно, чем вероятность 2 ^-80. См. fooobar.com/questions/69373/... для получения более подробной информации. Суть в том, что независимо от того, как вы убедитесь, что целое число является простым, у вас все еще есть неизбежный вероятностный элемент, а 40 раундов Миллера-Рабина уже дают вам лучшее, на что вы можете надеяться.

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

Ответ 2

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

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

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

Ответ 3

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

Итак, после 64 итераций в 2 ^ 128 есть только 1 шанс, что число является составным.

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

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

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

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

Например, согласно Wikipedia:

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

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

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

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

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

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

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

Ответ 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

Ответ 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 является псевдослучайным для одного основание, то более вероятно, чем среднее число, чтобы быть псевдопригодным для других оснований. Вот почему, например, мы видим, что так много psp base 2 также являются psp base 3.

Ответ 6

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

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

Ответ 7

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

Таким образом, вероятность того, что число является простым после n итераций, равна 4 ^ -n.