Генерация ДЕЙСТВИТЕЛЬНО больших простых чисел

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


encryption rsa public-key primes
person nonpolynomial237    schedule 18.07.2009    source источник

Ответы (5)


arrow_upward
18
arrow_downward

Вы не можете точно генерировать простые числа. Вы случайным образом генерируете большое нечетное число, затем проверяете, является ли это число простым, а если нет, генерируете другое случайным образом. Есть некоторые законы простых чисел, которые в основном утверждают, что ваши шансы "получить" простое число случайными попытками равны (2 / ln n)

Например, если вам нужно 512-битное случайное простое число, вы найдете его в 2 / (512 * ln (2)). Таким образом, примерно 1 из каждых 177 чисел, которые вы попробуете, будет простым.

Есть несколько способов проверить, является ли число простым, один хороший - это "тест Миллера-Рабина" , как указано в другом ответе на этот вопрос. вопрос.

Кроме того, в OpenSSL есть хорошая утилита для проверки простых чисел:

$ openssl prime 119054759245460753
1A6F7AC39A53511 is not prime
person mox1    schedule 20.07.2009
comment
Спасибо. Это объясняет множество моих проблем. - person nonpolynomial237; 03.08.2009
comment
вы также можете генерировать простые числа в openssl: openssl prime -generate -bits 512 - person mykhal; 15.08.2015
comment
Наибольшее 512-битное простое число равно 2**512-569, найдено с помощью: python -c 'print("\n".join([str(2**512-(x*2+1)) for x in range(1000)]))' | xargs -n 1 openssl prime - person Erik Aronesty; 15.08.2018

arrow_upward
3
arrow_downward

Посмотрите, как это делает TrueCrypt. Также обратите внимание на Рабина-Миллера для тестирования больших псевдопричин.

person JP Alioto    schedule 18.07.2009
comment
Почему вы думаете, что TrueCrypt генерирует простые числа? Насколько мне известно, он использует только симметричное шифрование. - person CodesInChaos; 20.01.2015

arrow_upward
3
arrow_downward

Существует алгоритм, созданный У. Маурером, который генерирует случайные доказуемые (в отличие от статистически высоковероятных) простых чисел, которые почти равномерно распределяются по множеству всех простых чисел особого размера. У меня есть довольно эффективная реализация Python по адресу: http://s13.zetaboards.com/Crypto/topic/7234475/1/

person Mok-Kong Shen    schedule 20.01.2015

arrow_upward
2
arrow_downward

Вы не упомянули, какой язык используете. У некоторых есть встроенный способ сделать это. Например, в java это так же просто, как вызвать nextProbablePrime () для BigInteger.

person Peter Recore    schedule 18.07.2009
comment
В зависимости от того, как реализована эта функция, вы можете поставить под угрозу выбор ключа, если пространство поиска уменьшится. - person Stephen; 15.02.2012

arrow_upward
1
arrow_downward

У Mono есть класс BigInteger с открытым исходным кодом, как и у java. Вы можете взглянуть на них. Они, наверное, портативные :) g'luck

person albertjan    schedule 20.07.2009