document BN_mod_sqrt(3)

4 files changed, 119 insertions, 5 deletions

diff --git a/src/lib/libcrypto/man/BN_kronecker.3 b/src/lib/libcrypto/man/BN_kronecker.3
index af1c298bb5..90b7f43230 100644
--- a/src/lib/libcrypto/man/BN_kronecker.3
+++ b/src/lib/libcrypto/man/BN_kronecker.3
@@ -1,4 +1,4 @@
-.\" $OpenBSD: BN_kronecker.3,v 1.1 2022/11/14 19:51:35 schwarze Exp $
+.\" $OpenBSD: BN_kronecker.3,v 1.2 2022/11/15 17:55:00 schwarze Exp $
 .\"
 .\" Copyright (c) 2022 Ingo Schwarze <schwarze@openbsd.org>
 .\"
@@ -14,7 +14,7 @@
 .\" ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
 .\" OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
 .\"
-.Dd $Mdocdate: November 14 2022 $
+.Dd $Mdocdate: November 15 2022 $
 .Dt BN_KRONECKER 3
 .Os
 .Sh NAME
@@ -41,6 +41,7 @@ returns \-1, 0, or 1 in case of success or \-2 on error.
 .Sh SEE ALSO
 .Xr BN_CTX_new 3 ,
 .Xr BN_gcd 3 ,
+.Xr BN_mod_sqrt 3 ,
 .Xr BN_new 3
 .Rs
 .%A Henri Cohen
diff --git a/src/lib/libcrypto/man/BN_mod_sqrt.3 b/src/lib/libcrypto/man/BN_mod_sqrt.3
new file mode 100644
index 0000000000..a3f84e5519
--- /dev/null
+++ b/src/lib/libcrypto/man/BN_mod_sqrt.3
@@ -0,0 +1,111 @@
+.\" $OpenBSD: BN_mod_sqrt.3,v 1.1 2022/11/15 17:55:00 schwarze Exp $
+.\"
+.\" Copyright (c) 2022 Ingo Schwarze <schwarze@openbsd.org>
+.\"
+.\" Permission to use, copy, modify, and distribute this software for any
+.\" purpose with or without fee is hereby granted, provided that the above
+.\" copyright notice and this permission notice appear in all copies.
+.\"
+.\" THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
+.\" WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
+.\" MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
+.\" ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
+.\" WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
+.\" ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
+.\" OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
+.\"
+.Dd $Mdocdate: November 15 2022 $
+.Dt BN_MOD_SQRT 3
+.Os
+.Sh NAME
+.Nm BN_mod_sqrt
+.Nd square root in a prime field
+.Sh SYNOPSIS
+.In openssl/bn.h
+.Ft BIGNUM *
+.Fo BN_mod_sqrt
+.Fa "BIGNUM *r"
+.Fa "const BIGNUM *a"
+.Fa "const BIGNUM *p"
+.Fa "BN_CTX *ctx"
+.Fc
+.Sh DESCRIPTION
+.Fn BN_mod_sqrt
+solves
+.Bd -unfilled -offset indent
+.EQ
+r sup 2 == a ( roman mod p )
+.EN
+.Ed
+.Pp
+for
+.Fa r
+in the prime field of characteristic
+.Fa p
+using the Tonelli-Shanks algorithm if needed
+and places one of the two solutions into
+.Fa r .
+The other solution is
+.Fa p
+\-
+.Fa r .
+.Pp
+The argument
+.Fa p
+is expected to be a prime number.
+.Sh RETURN VALUES
+In case of success,
+.Fn BN_mod_sqrt
+returns
+.Fa r ,
+or a newly allocated
+.Vt BIGNUM
+object if the
+.Fa r
+argument is
+.Dv NULL .
+.Pp
+In case of failure,
+.Dv NULL
+is returned.
+This for example happens if
+.Fa a
+is not a quadratic residue or if memory allocation fails.
+.Sh SEE ALSO
+.Xr BN_CTX_new 3 ,
+.Xr BN_kronecker 3 ,
+.Xr BN_mod_sqr 3 ,
+.Xr BN_new 3
+.Rs
+.%A Henri Cohen
+.%B A Course in Computational Algebraic Number Theory
+.%I Springer
+.%C Berlin
+.%D 1993
+.%O Algorithm 1.5.1
+.Re
+.Sh HISTORY
+.Fn BN_mod_sqrt
+first appeared in OpenSSL 0.9.7 and has been available since
+.Ox 3.2 .
+.Sh CAVEATS
+If
+.Fa p
+is not prime,
+.Fn BN_mod_sqrt
+may succeed or fail.
+If it succeeds, the square of the returned value is congruent to
+.Fa a
+modulo
+.Fa p .
+If it fails, the reason reported by
+.Xr ERR_get_error 3
+is often misleading.
+In particular, even if
+.Fa a
+is a perfect square,
+.Fn BN_mod_sqrt
+often reports 
+.Dq not a square
+instead of
+.Dq p is not prime .
diff --git a/src/lib/libcrypto/man/BN_new.3 b/src/lib/libcrypto/man/BN_new.3
index 90c0fb4e34..4d73b73030 100644
--- a/src/lib/libcrypto/man/BN_new.3
+++ b/src/lib/libcrypto/man/BN_new.3
@@ -1,4 +1,4 @@
-.\" $OpenBSD: BN_new.3,v 1.19 2022/11/14 19:51:35 schwarze Exp $
+.\" $OpenBSD: BN_new.3,v 1.20 2022/11/15 17:55:00 schwarze Exp $
 .\" full merge up to: OpenSSL man3/BN_new 2457c19d Mar 6 08:43:36 2004 +0000
 .\" selective merge up to: man3/BN_new 681acb31 Sep 29 13:10:34 2017 +0200
 .\" full merge up to: OpenSSL man7/bn 05ea606a May 20 20:52:46 2016 -0400
@@ -50,7 +50,7 @@
 .\" ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
 .\" OF THE POSSIBILITY OF SUCH DAMAGE.
 .\"
-.Dd $Mdocdate: November 14 2022 $
+.Dd $Mdocdate: November 15 2022 $
 .Dt BN_NEW 3
 .Os
 .Sh NAME
@@ -159,6 +159,7 @@ and sets an error code that can be obtained by
 .Xr BN_mod_inverse 3 ,
 .Xr BN_mod_mul_montgomery 3 ,
 .Xr BN_mod_mul_reciprocal 3 ,
+.Xr BN_mod_sqrt 3 ,
 .Xr BN_num_bytes 3 ,
 .Xr BN_rand 3 ,
 .Xr BN_security_bits 3 ,
diff --git a/src/lib/libcrypto/man/Makefile b/src/lib/libcrypto/man/Makefile
index 9f514044c2..f1142ab014 100644
--- a/src/lib/libcrypto/man/Makefile
+++ b/src/lib/libcrypto/man/Makefile
@@ -1,4 +1,4 @@
-# $OpenBSD: Makefile,v 1.235 2022/11/14 19:51:35 schwarze Exp $
+# $OpenBSD: Makefile,v 1.236 2022/11/15 17:55:00 schwarze Exp $
 
 .include <bsd.own.mk>
 
@@ -76,6 +76,7 @@ MAN=	\
         BN_mod_inverse.3 \
         BN_mod_mul_montgomery.3 \
         BN_mod_mul_reciprocal.3 \
+        BN_mod_sqrt.3 \
         BN_new.3 \
         BN_num_bytes.3 \
         BN_rand.3 \