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;byteLoop<sizeof(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
________________________________
This transmission may contain information that is privileged, confidential,
and/or exempt from disclosure under applicable law. If you are not the intended
recipient, you are hereby notified that any disclosure, copying, distribution,
or use of the information contained herein (including any reliance thereon) is
strictly prohibited. If you received this transmission in error, please
immediately contact the sender and destroy the material in its entirety,
whether in electronic or hard copy format.
