Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 22
Хе, в джаве для >=1024 низкая точность.
Вероятность ошибки 62,5 из 1000. Но ничего не мешает прогнать тест нужное количество раз.
Вероятность ошибки 62,5 из 1000. Но ничего не мешает прогнать тест нужное количество раз.
Современная криптография больше топит за эллиптические кривые, где большие простые числа не очень нужны, и порядок размера параметров поменьше (256 — 512 битов).
Для систем на основе факторизации NIST, например, считает 1024-битные числа уже слишком маленькими, а 2048-битные — приемлемыми максимум до 2030 года. Я где-то видел, что NSA требует минимум 3072-битные параметры уже сейчас.
Вы все же несколько лукавите, утверждая, будто вероятностные подходы такие плохие
Вероятностные подходы работоспособны, но их работоспособность зависит от ряда факторов, таких как грамотность использующего их человека, организационные моменты, очень важные в криптографии, а так же всё тот же очевидный факт — вероятность может оказаться не в пользу использующего такой подход.
Поэтому, если есть возможность в корне устранить саму причину возникновения проблемы (то есть избавиться от вероятности), то есть очевидный смысл воспользоваться предлагаемым подходом.
У вероятностных тестов есть доказанная верхняя граница вероятности ложноположительного результата, которая зависит от количества проведенных тестов. Так, допустим, проведите тест 1000 раз, и вероятность ошибки будет настолько мала, что мы ошибемся от силы лишь один раз, даже если б проверяли миллиарды случайных чисел ежесекундно, начиная с момента Большого Взрыва.
Не совсем так. Для больших чисел (порядка 1024) количество обязательных для гарантированной проверки оснований систем счисления, равно количеству простых, меньших, чем само число. Это количество столь велико, что не то что ежесекундно, но вообще за множество полных циклов от большого взрыва до очередного коллапса вселенной, вы не сможете перебрать все варианты.
Плюс вероятностные тесты очень простые и крайне шустрые. Не нужно ждать 20 минут, чтоб произвести какую-то сотню простых чисел длиной 1000 бит.
Как вы видели, я предложил работающий код, а значит немного представляю, сколько времени может потребоваться на различные задачи. Скажу конкретно — генерация 1024-битных чисел с вероятностной проверкой мною производилась, но без точного учёта времени (были другие цели), хотя знаю точно (ибо долго ждал) — несколько сотен чисел необходимого размера с использованием той же библиотеки, что и в коде для генерации перемножением, потребуют от вас ожидания как раз минут пять, а то и 10 (повторюсь — время оценивал субъективно, но оценка такая — долго).
Кроме того, время, пусть даже в 4 раза большее, но измеряемое минутами, и при этом гарантирующее отсутствие псевдопростых, есть просто ничтожная затрата по сравнению с потенциально устраняемым ущербом. Ну и вспомним, что ключи генерируют раз в год (иногда в два), значит потерять пусть полчаса раз в год ради устранения возможного ущерба в размере многих миллионов — ну разве это затраты?
если мы смотрим на тест, который с вероятностью, допустим, не больше 2^(-1000) ошибается
А почему вы решили, что алгоритм ошибается с вероятностью 2^(-1000)? Но даже если принять вашу (некорректную) оценку, то любое доступное количество прогонов Миллера-Рабина никак не поможет против чисел Кармайкла, плюс нет гарантий от пропуска и других видов чисел. Поэтому нужно точнее оценивать вероятность ошибки, и при этом она будет на сотни порядков больше.
К тому же предоставленный Вами алгоритм обладает одним неприятным свойством: созданные случайные простые числа не совсем «случайны». Их можно легко воссоздать, если кто-то украдет список начальных простых чисел.
Ну это не проблема. Точнее эта проблема ни чуть не страшнее, чем проблема генерации простым перебором с проверкой, потому что выбор начала последовательности, которую мы проверяем, требует случайности того же порядка, что и генерируемое число, но если в наличии есть уже случайное число такого порядка, то ни что нам не мешает применить эту случайность к отсечению ветвей в дереве генерации, начиная от выбора начального набора простых, и далее по всем этапам. Если вы запустите предложенный код без ограничений, то увидите, что первое умножение сгенерированных чисел на единичные по модулю 3 простые из начального набора даёт нам десятки тысяч простых, которые, естественно, все так же могут участвовать в последующих этапах. То есть коэффициент размножения будет около 10, а количество этапов для 30-битных начальных значений — более 30. В целом одна тысяча простых грубо даст ~10^30 вариантов. Но простых в нашем распоряжении не тысяча, а очень большое количество. Так, простые числа до миллиарда уже дают нам 50 миллионов, а теперь прикиньте количество сочетаний из 50 миллионов по 1000, и умножьте потом на 10^30. И это всего лишь числа до миллиарда, но ни что не мешает нам взять и до триллиона (гененрировать их тем же решетом, например). Так что с этой стороны я не вижу проблем.
Вероятность ошибки оценивается по единичному испытанию, а далее — по формулам теории вероятностей. Об этом в википедии написано достаточно подробно. Вы же приняли прямо пропорциональную зависимость, то есть игнорировали формулы из теории вероятностей. Попробуйте всё же выполнить расчёт правильно.
Пугать я вас, разумеется, не собирался (хотя услышать более обоснованное мнение хотел, признаюсь, ведь многие склонны бросить слово и потом «замять»).
Но мне казалось, что раз мы совершаем повторное испытание при условии, что предыдущее дало один конкретный вариант из двух, то и подходить к оценке вероятности повторения ранее случившегося события (на том же испытуемом объекте) нужно с позиций условной вероятности.
Рад, что вы подробно описали свой ход мыслей. Кроме того, почитал ещё раз википедию, там тоже поддерживают ваш подход. Ну и признаюсь — вероятности изучал давно, а потому не уверен и в своей правоте.
Но тем не менее, если всё же говорить о времени выполнения теста, то очевидно, что предлагаемые вами 500 возведений в степень по модулю представляют из себя существенно большую нагрузку на процессор, нежели одно возведение в степень по модулю (для больших чисел) в случае предложенного выше алгоритма. А потому предложенный алгоритм имеет очевидное преимущество перед альтернативой в виде 500 (да пусть даже 10) возведений в степень по модулю.
Вообще, вместе с Java идут и исходники, надо подробнее будет посмотреть, как они реализовали этот тест. Раньше мельком заглядывал и видел какие-то ограничения по количеству возведений в степень.
Но мне казалось, что раз мы совершаем повторное испытание при условии, что предыдущее дало один конкретный вариант из двух, то и подходить к оценке вероятности повторения ранее случившегося события (на том же испытуемом объекте) нужно с позиций условной вероятности.
Рад, что вы подробно описали свой ход мыслей. Кроме того, почитал ещё раз википедию, там тоже поддерживают ваш подход. Ну и признаюсь — вероятности изучал давно, а потому не уверен и в своей правоте.
Но тем не менее, если всё же говорить о времени выполнения теста, то очевидно, что предлагаемые вами 500 возведений в степень по модулю представляют из себя существенно большую нагрузку на процессор, нежели одно возведение в степень по модулю (для больших чисел) в случае предложенного выше алгоритма. А потому предложенный алгоритм имеет очевидное преимущество перед альтернативой в виде 500 (да пусть даже 10) возведений в степень по модулю.
Вообще, вместе с Java идут и исходники, надо подробнее будет посмотреть, как они реализовали этот тест. Раньше мельком заглядывал и видел какие-то ограничения по количеству возведений в степень.
Посмотрел код Java-библиотеки. Там стоит ряд ограничений, в зависимости от размера проверяемого числа. Для размера 1024 и более стоит насильственное урезание количества повторов до 2. То есть либо 1 проверка, либо две.
Почему это сделано? Очевидно, что ради скорости. При этом, если вспомним, что вероятность выбрать систему счисления, ложно свидетельствующую о простоте числа, составляет 1/4. Если принимаем повторные попытки за независимые испытания, то в серии из 2-х испытаний получаем вероятность ложного ответа, равную 1/16. И это против гарантированного результата, хоть и достигаемого за несколько большее время (видимо от 4-5 раз больше). На мой взгляд выбор в данной ситуации абсолютно очевиден и однозначен. Ну а установка такого явного ограничения на количество повторов внутри библиотеки, да ещё и без указания на это в документации, это просто кричащее предупреждение — срочно меняйте подход при генерации простых для криптографии!
Почему это сделано? Очевидно, что ради скорости. При этом, если вспомним, что вероятность выбрать систему счисления, ложно свидетельствующую о простоте числа, составляет 1/4. Если принимаем повторные попытки за независимые испытания, то в серии из 2-х испытаний получаем вероятность ложного ответа, равную 1/16. И это против гарантированного результата, хоть и достигаемого за несколько большее время (видимо от 4-5 раз больше). На мой взгляд выбор в данной ситуации абсолютно очевиден и однозначен. Ну а установка такого явного ограничения на количество повторов внутри библиотеки, да ещё и без указания на это в документации, это просто кричащее предупреждение — срочно меняйте подход при генерации простых для криптографии!
Проверил — Джава тормозит.
Для вероятности ошибки порядка е-6 скорость генерации порядка 310 чисел в минуту на 3,9 ГГц для 1023 бит.
Для вероятности ошибки порядка е-6 скорость генерации порядка 310 чисел в минуту на 3,9 ГГц для 1023 бит.
Легко говорить о вероятностях, не располагая законом распределения случайной величины (ЗРСВ). Это для не очень подготовленного читателя, который не знает строгих способов определения вероятности СВ. Правильнее в данной ситуации говорить об оценках вероятностей, но при этом важно показать, что требования к таким оценкам выполнены. Показать это часто бывает не менее просто, чем установить ЗРСВ. Число опытов ситуацию не меняют. Это не статистика, а теория вероятностей. Так что вот так.
Забавно, как раз недавно писал статью на эту тему. Чтобы исключить вероятность ошибки, сегодня используют комбинацию вероятностных тестов на простоту. Такой подход называется тест Baillie–PSW и пока не найдено ни одного составного числа проходящего этот тест.
пока не найдено ни одного составного числа проходящего этот тест
Тест систематически прогонялся на числах до 2^64, а что там дальше — никто не знает.
Кроме того, в той же библиотеке Java, которая использовалась при написании генератора, реализованы лишь два теста — Миллера-Рабина и Люка-Лемера. То есть даже если предположить, что Baillie–PSW идеален, то как мы видим на примере Java — библиотеки далеко не идеальны. А выбирают их такие же неидеальные пользователи. В сумме вероятность проблемы получается отнюдь не нулевая. Ну и сами можете проверить — в Java переберите с миллион нечётных чисел с тестированием их стандартной библиотекой с небольшим коэффициентом certainity — получите сотни промахов.
Поэтому проблема есть, а раз она существует, то и решать её явно стоит, тем более, что решение по стоимости — копеечное.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Генерация простых чисел