CVSROOT: /cvs
Module name: src
Changes by: t...@cvs.openbsd.org 2023/04/11 04:08:44
Modified files:
lib/libcrypto : Makefile
Added files:
lib/libcrypto/bn: bn_mod_sqrt.c
Removed files:
lib/libcrypto/bn: bn_sqrt.c
Log message:
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
