Использование BigInteger.isProbablePrime() для создания криптографически безопасных простых чисел

Можете ли вы использовать BigInteger.isProbablePrime() для создания криптографически безопасных простых чисел? Какая определенность необходима для того, чтобы они были «в безопасности»?


java cryptography public-key-encryption biginteger primes
person Puzzler3141    schedule 17.04.2014    source источник

Ответы (3)


arrow_upward
5
arrow_downward

У меня нет ученой степени в области криптографии, так что отнеситесь к этому с недоверием.

У вас есть две основные области для беспокойства:

  1. Ваши простые числа должны быть непредсказуемо случайными. Это означает, что вам нужно использовать такой источник, как SecureRandom для создания простых чисел. Как бы ни были уверены в вашей простоте, если они предсказуемы, вся криптосистема не достигает своей цели. Если вы используете конструктор BigInteger(int bitLength, int certainty, Random rnd), вы можете передать свой SecureRandom, поскольку он является подклассом Random.

  2. Ваши потенциальные простые числа должны быть достаточно уверены в том, что они являются простыми числами (я предполагаю, что вы используете алгоритм, основанный на сложности факторинга). Если вы получили вероятное простое число, но злоумышленник может с большой долей вероятности разложить его на множители в течение 5 минут, потому что у него был фактор, который никогда не был замечен в проведенном вами тесте на простоту, вам несколько не повезло с вашим алгоритмом. Обычно используется Рабин-Миллер, и в этом ответе указано, что для 32-битных целых чисел достаточно уверенности в 15. Рекомендуется значение до 40 , а все, что выше этого значения, не имеет смысла.

person nanofarad    schedule 17.04.2014
comment
Тест Рабина-Миллера обычно считается устаревшим. В настоящее время в большинстве приложений используется своего рода тест псевдопростых чисел Лукаса, например тест Бэйли-Вагстаффа или тест BPSW, использующий вариант Фробениуса псевдопростых чисел Лукаса. Помимо того, что эти тесты быстрее, чем тест Миллера-Рабина для большого количества оснований, они также менее склонны к ошибкам; на самом деле, нет известных контрпримеров даже для простого теста Бэйли-Вагстаффа, не говоря уже о его более сильных вариантах. Mathematica, например, выполняет пробное деление на тысячу, строгие проверки псевдопростых чисел с основанием 2 и 3 и строгую проверку псевдопростых чисел Лукаса. - person user448810; 18.04.2014
comment
@ user448810 Спасибо за предупреждение, ОП оценит этот добавленный лакомый кусочек. - person nanofarad; 18.04.2014
comment
@ user448810 - Тест MR не считается «устаревшим», и на самом деле очень немногие приложения используют тест Lucas и / или BPSW. Большинство криптографических пакетов по-прежнему используют тест MR, поскольку он относительно прост в реализации, хорошо понятен и не требует сложности рекурсивной оценки символа Якоби. Подавляющее большинство композитов не пройдут один тест MR, поэтому он обычно быстрее для рандомизированных или добавочных простых поисков, поскольку частота простых чисел уменьшается. - person Brett Hale; 24.04.2014
comment
@BrettHale: Да, некоторые криптографические пакеты все еще используют MR, потому что этого достаточно для их нужд, и потому что MR встроен, если вы используете GMP или BigInteger для арифметики. Но своего рода BPSW теперь является стандартом среди математиков. Обратите внимание, что BPSW разделяет с MR быструю окупаемость композитов, поскольку она начинается с сильного теста псевдопростого числа. Также обратите внимание, что один тест на строгие псевдопростые числа, за которым следует какой-либо тест Лукаса, быстрее, чем 15 тестов на строгие псевдопростые числа, поэтому BPSW быстрее, чем MR для простых чисел. И я никогда не слышал, чтобы кто-нибудь говорил, что вычисление символа Якоби сложно. ;) - person user448810; 24.04.2014
comment
@ user448810 - и это подчеркивает разницу между математической теорией и криптографическими требованиями с должным учетом сложности, занимаемой площади, анализа побочных каналов и т. д. Возможно, вы знаете об этом больше, чем авторы GMP или различные SSL / криптографические библиотеки, но также возможно, что у них есть веские причины для своих решений. - person Brett Hale; 25.04.2014
comment
@ user448810 Одним из важных свойств MR является то, что он гарантирует обнаружение не простых чисел с вероятностью не менее 3/4 для каждого тестируемого вами основания. Таким образом, для 64 тестов вам гарантируется, что вероятность увидеть простое число не превышает 2^{-128}. В частности, это работает даже для состязательно выбранных композитов. Для простых чисел, используемых в RSA, это не проблема, но в других контекстах это может иметь значение. - person CodesInChaos; 27.04.2014

arrow_upward
4
arrow_downward

таким образом я создал безопасный BigInteger для своего криптографического приложения.

Вот мой код:

        BigInteger b = new BigInteger(25, new SecureRandom());

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

Почитав комментарии, дальше получилось. Вот способ, который гарантирует вам большую уверенность в получении простого числа.

 BigInteger b =BigInteger.probablePrime(25, new SecureRandom(););
person maxx777    schedule 17.04.2014
comment
Это не простое число. Я бы добавил, как вы решаете вероятностное поведение теста простоты BigInteger. - person nanofarad; 18.04.2014
comment
@hexafraction хорошо, я отредактировал свой ответ. Этот код дает гораздо больше шансов получить простое число. Если это достаточно хорошо, вы можете удалить свой отрицательный голос. - person maxx777; 18.04.2014
comment
Какой минус? В вашем посте 3 вверх и 0 вниз. Тем не менее, я проголосовал за это. - person nanofarad; 18.04.2014
comment
@hexafraction, лол .. спасибо за голосование. Когда я увидел, что было только два голоса вместо трех, а мои репо-пойнты были меньше. Так что я подумал, что вы, будучи более опытным и с лучшим ответом, проголосовали за меня. Спасибо и за знания - person maxx777; 18.04.2014

arrow_upward
1
arrow_downward

Как говорит @hexafraction, вам нужно использовать SecureRandom() для генерации случайного числа криптографического качества. Javadoc говорит, что сгенерированное простое число безопасно 2^-100. Если вам нужна более высокая безопасность (скажем, 2^-128 для безопасности, эквивалентной AES), запустите больше итераций тест Миллера-Рабина на нем. Каждая итерация дает вам дополнительную безопасность 2^-2, поэтому четырнадцать итераций дадут вам 2^-128.

person rossum    schedule 17.04.2014