| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
Provide bn_rand_in_range() which is a slightly tweaked version of what was
previously called bn_rand_range().
The way bn_rand_range() is called in libcrypto, the lower bound is always
expressible as a word. In fact, most of the time it is 1, the DH code uses
a 2, the MR tests in BPSW use 3 and an exceptinally high number appears in
the Tonelli-Shanks implementation where we use 32. Converting these lower
bounds to BIGNUMs on the call site is annoying so let bn_rand_interval()
do that internally and route that through bn_rand_in_range(). This way we
can avoid using BN_sub_word().
Adjust the bn_isqrt() test to use bn_rand_in_range() since that's the
only caller that uses actual BIGNUMs as lower bounds.
ok jsing
|
|
|
This is a reimplementation from scratch of the Tonelli-Shanks algorithm
based on Henri Cohen "A Course in Computational Algebraic Number Theory",
Springer GTM 138, section 1.5.1. It is API compatible with the previous
implementation, so no documentation change is required.
Contrary to the old implementation, this does not have any infinite loops
and has various additional sanity checks to prevent misbehavior in case
the input modulus is not a prime. It contains extensive comments and the
individual parts of the algorithm are split into digestible chunks instead
of having one huge function.
One difference of note is that it BN_mod_sqrt() now always returns the
smaller of the two possible answers. In other words, while its core is
non-deterministic, its answer is not.
ok jsing
|
