12423
66%

Ran 24 Jun 2020 08:11PM UTC

Jobs 1

Files 111

Run time 2min

Badge

Embed ▾

Committed 24 Jun 2020 08:05PM UTC coverage: 66.043% (-0.005%) from 66.048%

Build # 12423

Build Type

push

travis-pro

Committed by

web-flow

Commit Message

Use GCD to check RSA moduli for small primes (#4883)

The existing checkSmallPrimes function maintains a table of primes,
converts them to an array of *big.Int and uses the resulting values
for comparing against a RSA modulus as follows:

    for _, prime := range smallPrimes {
        if modulus % prime != 0 {
            return invalid
        }
    }
    return valid

This incurs substantial overhead as each prime is checked individually,
invoking QuoRem(...) each time. By multiplying the primes together into
a single *big.Int, we can utilize a single library call, GCD(...), and
check all the values at once. While a single GCD invocation is slower
than a single QuoRem, 133 such invocations of QuoRem are together
slower than the single GCD.

BenchmarkSmallPrimeGCD
BenchmarkSmallPrimeGCD-4                       72759             16240 ns/op
BenchmarkSmallPrimeIndividualMods
BenchmarkSmallPrimeIndividualMods-4             8866            165265 ns/op

This gives us room to later increase the number of smallPrimes, if
desired, while keeping the same timing profile. Currently the product
of the 133 primes in smallPrimes fits within 1040 bits.

Signed-off-by: Alexander Scheel <alexander.m.scheel@gmail.com>

Run Details

12990 of 19669 relevant lines covered (66.04%)

0.74 hits per line

Jobs

ID	Job ID	Ran	Files	Coverage
7	12423.7 (RUN="coverage" CONTAINER="netaccess")	24 Jun 2020 08:11PM UTC	111	66.04	Travis Job 12423.7

letsencrypt / boulder / 12423
66%

README BADGES
x

Markdown

Textile

RDoc

HTML

Rst

Jobs

Source Files on build 12423

letsencrypt / boulder / 12423 66%

README BADGES x

Markdown

Textile

RDoc

HTML

Rst

Jobs

Source Files on build 12423

letsencrypt / boulder / 12423
66%

README BADGES
x