12425
66%

Ran 24 Jun 2020 10:35PM UTC

Jobs 1

Files 111

Run time 19s

Badge

Embed ▾

Committed 24 Jun 2020 08:05PM UTC coverage: 66.043%. Remained the same

Build # 12425

Build Type

cron

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	12425.7 (RUN="coverage" CONTAINER="netaccess")	24 Jun 2020 10:35PM UTC	0	66.04	Travis Job 12425.7

Source Files on build 12425

Detailed source file information is not available for this build.

letsencrypt / boulder / 12425
66%

README BADGES
x

Markdown

Textile

RDoc

HTML

Rst

Jobs

Source Files on build 12425

letsencrypt / boulder / 12425 66%

README BADGES x

Markdown

Textile

RDoc

HTML

Rst

Jobs

Source Files on build 12425

letsencrypt / boulder / 12425
66%

README BADGES
x