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
Re : Re: open ssl rsa key generation improvement idea Prime generation
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 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
Re: Re : Re: open ssl rsa key generation improvement idea Prime generation
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
Re : Re: Re : Re: open ssl rsa key generation improvement idea Prime generation
Actually, I was proposing another way to perform incremental search using divisibility properties The fact is I agree with your b) point, I was trying to explain a way to do it sorry if I didn't make myself clear there are two main points : - incremental search can be improved by testing less values for example with a 1024 bits prime, just take 1016 bits at random, and compute all possible values for the last 8 bits such that the resulting number is not dividible by primes less than 25 this allows to avoid the 2/3 that would give candidates that are obviously not prime the question left is how to compute these values efficiently, or at least quicker than multiple divisions - with a reduced number of values for last byte, they can be randomly tested given the previous example, you get get less than hundred possibilities I think it is possible at this point to choose them successively in a random sequence, and thus reduce the discussed bias (Note that the random sequence can be chosen once and for all at beginning, and be reused for next tries) however, I'm still not sure that this would result in a gain in speed guess I'll have to produce some code before going deeper into details - Mail d'origine - De: Ben Laurie b...@links.org À: OpenSSL development openssl-dev@openssl.org Envoyé: Wed, 28 May 2014 14:54:00 +0200 (CEST) Objet: Re: Re : Re: open ssl rsa key generation improvement idea Prime generation 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 __ OpenSSL Project http://www.openssl.org Development Mailing List openssl-dev@openssl.org Automated List Manager majord...@openssl.org
Re: open ssl rsa key generation improvement idea
Nice idea.
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.
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.
We also don't currently deal with the case where add != 2 or rem != 1.
But its clearly possible without too much work.
You could use his branch as a basis for testing this idea:
https://github.com/openssl/openssl/pull/116.
On 26 May 2014 02:31, Russell Harkins russ...@russellharkins.info wrote:
Hi SSL Team,
I was looking for ways to make calculating RSA public/private keys faster.
I noticed that trial division was being done to test if a number is
divisible by small primes.
Roughly 2/3 of all odd numbers are divisible by primes less than 25. I
found a faster way to test the divisibility than using division.
In school, I learned some divisibility rules. For instance, when
determining if a large number is divisible by 3, add the sum of all the
digits. To see if a large number is divisible by 5, check the last digit
to see if it’s a zero or 5.
I’ve converted these divisibility rules into binary. For instance, to see
if a large number is divisible by 3, add the sum of all the bytes of the
large number and see if that sum is divisible by 3.
I’ve converted all the divisibility rules for all the primes less than 25
into binary. All the sums can be calculated at once.
I wrote a function to do this based on the BIGNUM that openssl uses:
BN_isdivisiblebyprimeslessthan25
The easiest way to test my function is to generate random numbers and test
the results of BN_isdivisiblebyprimeslessthan25 with another function that
does the division the old way.
Attached is a paper detailing the math behind the change.
Here’s the function and where to put it in openssl:
In file crypto\bn\bn_prime.c,
function BN_is_prime_fasttest_ex
After if (do_trial_division), add
if (BN_isdivisiblebyprimeslessthan25(a))
return 0;
bool bn:: BN_isdivisiblebyprimeslessthan25 (const BIGNUM *p)
{
int total3and5and17 = 0; // 256 mod 3 = 1, 256 mod 5 = 1, 256 mod 17 = 1
int total7 = 0;
int total11 = 0;
int total13 = 0;
int total19 = 0;
int total23 = 0;
const char sumBytes7[] = { 1, 4, 2}; // 1 mod 7 = 1, 256 mod 7 = 4,
65536 mod 7 = 2
const char sumBytes11[] = { 1, 3, 9, 5, 4}; // 1 mod 11 = 1, 256 mod 11
= 3, 65536 mod 11 = 9
const char sumBytes13[] = { 1, 9, 3}; // 1 mod 13 = 1, 256 mod 13 = 9,
65536 mod 13 = 3
const char sumBytes19[] = { 1, 9, 5, 7, 6, 16, 11, 4, 17};
const char sumBytes23[] = { 1, 3, 9, 4, 12, 13, 16, 2, 6, 18, 8};
int index7or13 = 0; // Array indexes for 7 and 13 are the same because
the array is the same size.
int index11 = 0;
int index19 = 0;
int index23 = 0;
int byteLoop;
int top;
BN_ULONG item;
int itemByte;
BN_ULONG *itemptr;
BN_ULONG *lastItem;
top = p-top;
if (top = 0)
{
return true;
}
itemptr = p-d;
lastItem = itemptr+top-1;
while(true)
{
item = *itemptr;
for(byteLoop=0;byteLoopsizeof(BN_ULONG);byteLoop++)
{
itemByte = (int)(item 255);
item = 8;
total3and5and17 += itemByte;
total7 += (sumBytes7[index7or13] * itemByte);
total13 += (sumBytes13[index7or13] * itemByte);
total11 += (sumBytes11[index11] * itemByte);
total19 += (sumBytes19[index19] * itemByte);
total23 += (sumBytes23[index23] * itemByte);
// Keep the array indexes in bounds.
index7or13 = (index7or13 + 1) % 3;
index11 = (index11 + 1) % 5;
index19 = (index19 + 1) % 9;
index23 = (index23 + 1) % 11;
}
// Move to the next item.
if (itemptr == lastItem)
{
break;
}
itemptr++;
}
bool returnValue = (((total3and5and17 % 3) == 0)
|| ((total3and5and17 % 5) == 0)
|| ((total7 % 7) == 0)
|| ((total11 % 11) == 0)
|| ((total13 % 13) == 0)
|| ((total3and5and17 % 17) == 0)
|| ((total19 % 19) == 0)
|| ((total23 % 23) == 0));
return returnValue;
}
Russell
RE: open ssl rsa key generation improvement idea
Note that the indexes for 7, 11, 13, and 19 repeat with period 45, so they
could be a single lookup table instead several tables with mod operations:
sumBytes = {
{ 1, 4, 2, 1, 4, 2, 1, 4, 2 ... },
{ 1, 3, 9, 5, 4, 1, 3, 9, 5, 4, ... },
{ 1, 9, 3, 1, 9, 3, ... },
{ 1, 9, 5, 7, 6, 16, 11, 4, 17, ... }
}
// sumBytes7[index7or13] - sumBytes[0][idx]
// sumBytes11[index11] - sumBytes[0][idx]
// etc
// only need one increment.
if (++idx == 45)
idx = 0;
-Tim
-Original Message-
From: owner-openssl-...@openssl.org [mailto:owner-openssl-...@openssl.org] On
Behalf Of Ben Laurie
Sent: Tuesday, May 27, 2014 4:04 PM
To: OpenSSL development; Felix Laurie von Massenbach
Subject: Re: open ssl rsa key generation improvement idea
Nice idea.
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.
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.
We also don't currently deal with the case where add != 2 or rem != 1.
But its clearly possible without too much work.
You could use his branch as a basis for testing this idea:
https://github.com/openssl/openssl/pull/116.
On 26 May 2014 02:31, Russell Harkins russ...@russellharkins.info wrote:
Hi SSL Team,
I was looking for ways to make calculating RSA public/private keys faster.
I noticed that trial division was being done to test if a number is
divisible by small primes.
Roughly 2/3 of all odd numbers are divisible by primes less than 25. I
found a faster way to test the divisibility than using division.
In school, I learned some divisibility rules. For instance, when
determining if a large number is divisible by 3, add the sum of all
the digits. To see if a large number is divisible by 5, check the
last digit to see if it’s a zero or 5.
I’ve converted these divisibility rules into binary. For instance, to
see if a large number is divisible by 3, add the sum of all the bytes
of the large number and see if that sum is divisible by 3.
I’ve converted all the divisibility rules for all the primes less than
25 into binary. All the sums can be calculated at once.
I wrote a function to do this based on the BIGNUM that openssl uses:
BN_isdivisiblebyprimeslessthan25
The easiest way to test my function is to generate random numbers and
test the results of BN_isdivisiblebyprimeslessthan25 with another
function that does the division the old way.
Attached is a paper detailing the math behind the change.
Here’s the function and where to put it in openssl:
In file crypto\bn\bn_prime.c,
function BN_is_prime_fasttest_ex
After if (do_trial_division), add
if (BN_isdivisiblebyprimeslessthan25(a))
return 0;
bool bn:: BN_isdivisiblebyprimeslessthan25 (const BIGNUM *p) {
int total3and5and17 = 0; // 256 mod 3 = 1, 256 mod 5 = 1, 256 mod 17 = 1
int total7 = 0;
int total11 = 0;
int total13 = 0;
int total19 = 0;
int total23 = 0;
const char sumBytes7[] = { 1, 4, 2}; // 1 mod 7 = 1, 256 mod 7 =
4,
65536 mod 7 = 2
const char sumBytes11[] = { 1, 3, 9, 5, 4}; // 1 mod 11 = 1, 256
mod 11 = 3, 65536 mod 11 = 9
const char sumBytes13[] = { 1, 9, 3}; // 1 mod 13 = 1, 256 mod 13
= 9,
65536 mod 13 = 3
const char sumBytes19[] = { 1, 9, 5, 7, 6, 16, 11, 4, 17};
const char sumBytes23[] = { 1, 3, 9, 4, 12, 13, 16, 2, 6, 18, 8};
int index7or13 = 0; // Array indexes for 7 and 13 are the same
because the array is the same size.
int index11 = 0;
int index19 = 0;
int index23 = 0;
int byteLoop;
int top;
BN_ULONG item;
int itemByte;
BN_ULONG *itemptr;
BN_ULONG *lastItem;
top = p-top;
if (top = 0)
{
return true;
}
itemptr = p-d;
lastItem = itemptr+top-1;
while(true)
{
item = *itemptr;
for(byteLoop=0;byteLoopsizeof(BN_ULONG);byteLoop++)
{
itemByte = (int)(item 255);
item = 8;
total3and5and17 += itemByte;
total7 += (sumBytes7[index7or13] * itemByte);
total13 += (sumBytes13[index7or13] * itemByte);
total11 += (sumBytes11[index11] * itemByte);
total19 += (sumBytes19[index19] * itemByte);
total23 += (sumBytes23[index23] * itemByte);
// Keep the array indexes in bounds.
index7or13 = (index7or13 + 1) % 3
Re: open ssl rsa key generation improvement idea
On Tue, May 27, 2014, Ben Laurie wrote: Nice idea. 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. 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. We also don't currently deal with the case where add != 2 or rem != 1. But its clearly possible without too much work. You could use his branch as a basis for testing this idea: https://github.com/openssl/openssl/pull/116. On the subject of possible improvements. I can vaguely recall an algorithm for testing multiple divisors simultaneously by multiplying lots of small primes together to produce a product, c and then seeing if gcd(c, p) == 1. Precomputing 2^k mod c for suitable values of k might help too. No idea if that would be faster though. 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 Development Mailing List openssl-dev@openssl.org Automated List Manager majord...@openssl.org
RE: open ssl rsa key generation improvement idea
I've converted all the divisibility rules for all the primes less than 25 into binary. All the sums can be calculated at once. Nice work! /r$ -- Principal Security Engineer Akamai Technologies, Cambridge, MA IM: rs...@jabber.me; Twitter: RichSalz __ OpenSSL Project http://www.openssl.org Development Mailing List openssl-dev@openssl.org Automated List Manager majord...@openssl.org
Re: open ssl rsa key generation improvement idea
Also, I should note that this approach is not portable. You need to
operate in the same base as BIGNUM does, or account for endianness is
the byte-level operations.
On 26 May 2014 02:31, Russell Harkins russ...@russellharkins.info wrote:
Hi SSL Team,
I was looking for ways to make calculating RSA public/private keys faster.
I noticed that trial division was being done to test if a number is
divisible by small primes.
Roughly 2/3 of all odd numbers are divisible by primes less than 25. I
found a faster way to test the divisibility than using division.
In school, I learned some divisibility rules. For instance, when
determining if a large number is divisible by 3, add the sum of all the
digits. To see if a large number is divisible by 5, check the last digit
to see if it’s a zero or 5.
I’ve converted these divisibility rules into binary. For instance, to see
if a large number is divisible by 3, add the sum of all the bytes of the
large number and see if that sum is divisible by 3.
I’ve converted all the divisibility rules for all the primes less than 25
into binary. All the sums can be calculated at once.
I wrote a function to do this based on the BIGNUM that openssl uses:
BN_isdivisiblebyprimeslessthan25
The easiest way to test my function is to generate random numbers and test
the results of BN_isdivisiblebyprimeslessthan25 with another function that
does the division the old way.
Attached is a paper detailing the math behind the change.
Here’s the function and where to put it in openssl:
In file crypto\bn\bn_prime.c,
function BN_is_prime_fasttest_ex
After if (do_trial_division), add
if (BN_isdivisiblebyprimeslessthan25(a))
return 0;
bool bn:: BN_isdivisiblebyprimeslessthan25 (const BIGNUM *p)
{
int total3and5and17 = 0; // 256 mod 3 = 1, 256 mod 5 = 1, 256 mod 17 = 1
int total7 = 0;
int total11 = 0;
int total13 = 0;
int total19 = 0;
int total23 = 0;
const char sumBytes7[] = { 1, 4, 2}; // 1 mod 7 = 1, 256 mod 7 = 4,
65536 mod 7 = 2
const char sumBytes11[] = { 1, 3, 9, 5, 4}; // 1 mod 11 = 1, 256 mod 11
= 3, 65536 mod 11 = 9
const char sumBytes13[] = { 1, 9, 3}; // 1 mod 13 = 1, 256 mod 13 = 9,
65536 mod 13 = 3
const char sumBytes19[] = { 1, 9, 5, 7, 6, 16, 11, 4, 17};
const char sumBytes23[] = { 1, 3, 9, 4, 12, 13, 16, 2, 6, 18, 8};
int index7or13 = 0; // Array indexes for 7 and 13 are the same because
the array is the same size.
int index11 = 0;
int index19 = 0;
int index23 = 0;
int byteLoop;
int top;
BN_ULONG item;
int itemByte;
BN_ULONG *itemptr;
BN_ULONG *lastItem;
top = p-top;
if (top = 0)
{
return true;
}
itemptr = p-d;
lastItem = itemptr+top-1;
while(true)
{
item = *itemptr;
for(byteLoop=0;byteLoopsizeof(BN_ULONG);byteLoop++)
{
itemByte = (int)(item 255);
item = 8;
total3and5and17 += itemByte;
total7 += (sumBytes7[index7or13] * itemByte);
total13 += (sumBytes13[index7or13] * itemByte);
total11 += (sumBytes11[index11] * itemByte);
total19 += (sumBytes19[index19] * itemByte);
total23 += (sumBytes23[index23] * itemByte);
// Keep the array indexes in bounds.
index7or13 = (index7or13 + 1) % 3;
index11 = (index11 + 1) % 5;
index19 = (index19 + 1) % 9;
index23 = (index23 + 1) % 11;
}
// Move to the next item.
if (itemptr == lastItem)
{
break;
}
itemptr++;
}
bool returnValue = (((total3and5and17 % 3) == 0)
|| ((total3and5and17 % 5) == 0)
|| ((total7 % 7) == 0)
|| ((total11 % 11) == 0)
|| ((total13 % 13) == 0)
|| ((total3and5and17 % 17) == 0)
|| ((total19 % 19) == 0)
|| ((total23 % 23) == 0));
return returnValue;
}
Russell Harkins
650-481-5261
__
OpenSSL Project http://www.openssl.org
Development Mailing List openssl-dev@openssl.org
Automated List Manager majord...@openssl.org
Re: open ssl rsa key generation improvement idea
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? 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. 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
