| barrett.cpp |
Barrett Reduction
This function assumes that the significant size of x_words (ie the number of
words with a value other than zero) is at most 2 * mod_words. In any case, any
larger value cannot be reduced using Barrett reduction; callers should have
already checked for this.
|
7191 |
- |
| barrett.h |
Barrett Reduction
|
2043 |
- |
| dsa_gen.cpp |
Check if this size is allowed by FIPS 186-3
|
3612 |
- |
| info.txt |
|
359 |
- |
| make_prm.cpp |
If v % p == (p-1)/2 then 2*v+1 == 0 (mod p)
So if potentially generating a safe prime, we want to
avoid this value because 2*v+1 will certainly not be prime.
See "Safe Prime Generation with a Combined Sieve" M. Wiener
https://eprint.iacr.org/2003/186.pdf
|
9562 |
- |
| mod_inv.cpp |
This uses a modular inversion algorithm designed by Niels Möller
and implemented in Nettle. The same algorithm was later also
adapted to GMP in mpn_sec_invert.
It can be easily implemented in a way that does not depend on
secret branches or memory lookups, providing resistance against
some forms of side channel attack.
There is also a description of the algorithm in Appendix 5 of "Fast
Software Polynomial Multiplication on ARM Processors using the NEON Engine"
by Danilo Câmara, Conrado P. L. Gouvêa, Julio López, and Ricardo
Dahab in LNCS 8182
https://inria.hal.science/hal-01506572/document
Thanks to Niels for creating the algorithm, explaining some things
about it, and the reference to the paper.
|
11923 |
- |
| mod_inv.h |
Compute the inverse of x modulo some integer m
Returns nullopt if no such integer exists eg if gcd(x, m) > 1
This algorithm is const time with respect to x, aside from its
length. It also avoids leaking information about the modulus m,
except that it does leak which of 3 categories the modulus is in:
- An odd integer
- A power of 2
- Some even number not a power of 2
And if the modulus is even, it leaks the power of 2 which divides
the modulus.
@param x a positive integer less than m
@param m a positive integer
Throws Invalid_Argument if x or m are negative
|
3572 |
- |
| monty.cpp |
|
11443 |
- |
| monty.h |
Parameters for Montgomery Reduction
|
4940 |
- |
| monty_exp.cpp |
|
7975 |
- |
| monty_exp.h |
Precompute for calculating values g^x mod p
|
2258 |
- |
| numthry.cpp |
Tonelli-Shanks algorithm
|
10830 |
- |
| numthry.h |
Return the absolute value
@param n an integer
@return absolute value of n
|
6411 |
- |
| primality.cpp |
This unpoison is not ideal but realistically there is no way to
hide the number of loop iterations (below). The main user of
secret primes is RSA and we always generate RSA primes such that
p == 3 (mod 4), which means s is always 1.
|
5347 |
- |
| primality.h |
Perform Lucas primality test
@see FIPS 186-4 C.3.3
@warning it is possible to construct composite integers which pass
this test alone.
@param n the positive integer to test
@param mod_n a pre-created Barrett_Reduction for n
@return true if n seems probably prime, false if n is composite
|
4229 |
- |
| primes.cpp |
|
47157 |
- |
| reducer.cpp |
|
567 |
- |
| reducer.h |
Modular Reducer
This class is deprecated without replacement
|
2568 |
- |