On Thu, Feb 16, 2012, Jakob Bohm wrote: > On 2/16/2012 11:36 AM, Magosányi Árpád wrote: > >Hi! > > > >Is the sentence "It checks that p and q are in fact prime, and > >that n = p*q" in RSA_check_key's documentation mean that it checks > >for weak primes, like the ones mentioned here?: > >http://arstechnica.com/business/news/2012/02/crypto-shocker-four-of-every-1000-public-keys-provide-no-security.ars > > > >As I understand there are two cases. > >One is when the prime is not exactly prime. I would expect > >RSA_check_key to find this out, but what is the extent of the > >check? > >The other cause is a clash with already existing prime factors out > >there. I guess that checking for this would involve looking up a > >list of prime factors collected on the net. Is there such tool > >accessible to mere mortals? > > > All the practical ways of creating and checking primes for > use in crypto have the following features: > > 1. They are statistical tests, each round of testing that > passes increases the probability that this is really a > prime, you stop if it says "not a prime" (an absolute > non-statistical rejection) or until the combined > probability is big enough for you. Someone else on this > list can hopefully give you the number of rounds and > resulting probabilities used by OpenSSL. >
OpenSSL uses trial division and a slight variation of the Miller Rabin algorithm. See the macro BN_prime_checks_for_size and the associated comments in that header file for references. Provable prime schemes do exist such as the Shawe-Taylor algorithm mentioned in FIPS 186-3 et al but OpenSSL doesn't currently use them. Steve. -- Dr Stephen N. Henson. OpenSSL project core developer. Commercial tech support now available see: http://www.openssl.org ______________________________________________________________________ OpenSSL Project http://www.openssl.org User Support Mailing List openssl-users@openssl.org Automated List Manager majord...@openssl.org
