Генерация больших простых чисел для алгоритма шифрования RSA

Question

Что я должен сделать, чтобы сгенерировать большие простые числа для RSA?

Как вы знаете, нам нужно большие простые числа, чтобы сделать закрытые и открытые ключи для алгоритма шифрования RSA.

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

Answer 1

Если вы хотите составить несколько больших простых чисел, вы можете написать программу на python, используя модуль pycrypto.Эта публикация будет полезна Использование RSA в Python

from Crypto.PublicKey import RSA
RSAkey = RSA.generate(1024)
print getattr(RSAkey.key, 'n')
print getattr(RSAkey.key, 'p')
print getattr(RSAkey.key, 'q')

Answer 2

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

Отличный ресурс по теории и реализации простого поколения здесь .

Answer 3

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

Однако я поиграл с генерацией простых чисел с использованием Python и GMP:

http://stromberg.dnsalias.org/svn/huge-prime/trunk/

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