From 2389f1d8a42806b852cf81082f3eb70ecbfdd8ae Mon Sep 17 00:00:00 2001
From: tb <>
Date: Tue, 11 Apr 2023 10:08:44 +0000
Subject: 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
---
 src/lib/libcrypto/Makefile | 4 ++--
 1 file changed, 2 insertions(+), 2 deletions(-)

(limited to 'src/lib/libcrypto/Makefile')

diff --git a/src/lib/libcrypto/Makefile b/src/lib/libcrypto/Makefile
index b9a251a1d9..5405d79449 100644
--- a/src/lib/libcrypto/Makefile
+++ b/src/lib/libcrypto/Makefile
@@ -1,4 +1,4 @@
-# $OpenBSD: Makefile,v 1.99 2023/03/01 11:28:30 tb Exp $
+# $OpenBSD: Makefile,v 1.100 2023/04/11 10:08:44 tb Exp $
 
 LIB=	crypto
 LIBREBUILD=y
@@ -191,6 +191,7 @@ SRCS+= bn_isqrt.c
 SRCS+= bn_kron.c
 SRCS+= bn_lib.c
 SRCS+= bn_mod.c
+SRCS+= bn_mod_sqrt.c
 SRCS+= bn_mont.c
 SRCS+= bn_mpi.c
 SRCS+= bn_mul.c
@@ -202,7 +203,6 @@ SRCS+= bn_recp.c
 SRCS+= bn_shift.c
 SRCS+= bn_small_primes.c
 SRCS+= bn_sqr.c
-SRCS+= bn_sqrt.c
 SRCS+= bn_word.c
 SRCS+= bn_x931p.c
 
-- 
cgit v1.2.3-55-g6feb