open ssl rsa key generation improvement idea

[Russell Harkins]

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

Divisibility Rules in Binary and Their Performance Impact on RSA Key Generation.odt
Description: Binary data