On 28 May 2014 13:32, nicolas@free.fr wrote:
Hi,
it seems that the two discussions are somehow related
the idea of generating only prime candidates not dividible by small primes is
interesting but, due to incremental search, it will not apply to next
candidates
a) The incremental search introduces bias, so not clear we should
really maintain that
b) It isn't very hard to incorporate incremental search in our scheme
I am not suggesting that your idea is not also worthwhile - in
particular, you can probably go to higher primes than our scheme - the
tables quickly become pretty large...
however, it may be possible to use bit counting to perform a less biased walk
AND efficiently avoid prime dividible by first primes :
let say we generate randomly the first bytes of a key, except the last byte
it is then possible to compute quickly all possible values for the last byte
(or first depending on endianness) such that it is not dividible by first
primes (as well as (p-1)/2 using a bit shift)
looking at the last test of code provided, it can even be made quite
efficiently using CRT
given these values, we can test them in a random order in order to reduce the
bias of incremental search
in case of fail, just change last bit of second-to-last byte, and try again
it should be statistically correct to do this on the byte of highest weight,
but by applying this on the first byte we are sure that it will spawn a
(strong) prime, just like incremental search
This is just an idea as I didn't implement anything yet
however with full optimization this could be quicker than incremental search
And sorry if I'm mistaking anyhow
Nico
- Mail d'origine -
De: Ben Laurie b...@links.org
À: OpenSSL development openssl-dev@openssl.org
Envoyé: Wed, 28 May 2014 11:10:25 +0200 (CEST)
Objet: Re: open ssl rsa key generation improvement idea
On 28 May 2014 00:03, Viktor Dukhovni openssl-us...@dukhovni.org wrote:
On Tue, May 27, 2014 at 09:04:20PM +0100, Ben Laurie wrote:
It inspired my son, Felix, and I to think about a related idea:
generate random numbers which are inherently coprime to small primes.
Felix went on to implement the idea, and include benchmarks and tests.
When you say small, you mean really small right? Not the first
2048 primes as in the OpenSSL code, but say the first few, for
example those less than 25?
Yeah - we went up to 11 for the tests.
Not finished - while implementing, we noticed that the existing prime
number generators have a bias. We decided to remove that, which caused
prime candidate generation to take more than twice as long (it was 42%
of the speed on Felix' laptop) - but the good news is our technique
doubled the speed, getting most of the loss back.
Do the resulting candidates also avoid having small odd factors in
(p-1)? This means p != 0 or 1 mod each of the first batch of odd
primes.
No, but the method could be extended to do that pretty easily.
For the first 9 primes:
2, 3, 5, 7, 11, 13, 17, 19, 23
this leaves only
7,952,175 = 1 * 1 * 3 * 5 * 9 * 11 * 15 * 17 * 21
acceptable odd values modulo:
223,092,870 = 2 * 3 * 5 * 7 * 11 * 13 * 17 * 19 * 23
or ~7.1% of the odd candidates.
--
Viktor.
__
OpenSSL Project http://www.openssl.org
Development Mailing List openssl-dev@openssl.org
Automated List Manager majord...@openssl.org
__
OpenSSL Project http://www.openssl.org
Development Mailing List openssl-dev@openssl.org
Automated List Manager majord...@openssl.org
__
OpenSSL Project http://www.openssl.org
Development Mailing List openssl-dev@openssl.org
Automated List Manager majord...@openssl.org
__
OpenSSL Project http://www.openssl.org
Development Mailing List openssl-dev@openssl.org
Automated List Manager majord...@openssl.org
