Add a new implementation of BN_mod_sqrt()
authortb <tb@openbsd.org>
Tue, 11 Apr 2023 10:08:44 +0000 (10:08 +0000)
committertb <tb@openbsd.org>
Tue, 11 Apr 2023 10:08:44 +0000 (10:08 +0000)
commit5290b413a618730f10a157bc2e37c5719200fa7f
tree17fdf39088cd2135fa2a8b80d2ee19bb7e74fba6
parentb2cabbc12a1e72cb4d2da0aba0e38395928f0709
Add a new implementation of BN_mod_sqrt()

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
lib/libcrypto/Makefile
lib/libcrypto/bn/bn_mod_sqrt.c [new file with mode: 0644]
lib/libcrypto/bn/bn_sqrt.c [deleted file]