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;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
