From a289ca2f4e7ee0cb4d49652d35d925bb4d5a9c53 Mon Sep 17 00:00:00 2001 From: schwarze Date: Tue, 15 Nov 2022 17:55:00 +0000 Subject: [PATCH] document BN_mod_sqrt(3) --- lib/libcrypto/man/BN_kronecker.3 | 5 +- lib/libcrypto/man/BN_mod_sqrt.3 | 111 +++++++++++++++++++++++++++++++ lib/libcrypto/man/BN_new.3 | 5 +- lib/libcrypto/man/Makefile | 3 +- 4 files changed, 119 insertions(+), 5 deletions(-) create mode 100644 lib/libcrypto/man/BN_mod_sqrt.3 diff --git a/lib/libcrypto/man/BN_kronecker.3 b/lib/libcrypto/man/BN_kronecker.3 index af1c298bb5d..90b7f43230b 100644 --- a/lib/libcrypto/man/BN_kronecker.3 +++ b/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 .\" @@ -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/lib/libcrypto/man/BN_mod_sqrt.3 b/lib/libcrypto/man/BN_mod_sqrt.3 new file mode 100644 index 00000000000..a3f84e55199 --- /dev/null +++ b/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 +.\" +.\" 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/lib/libcrypto/man/BN_new.3 b/lib/libcrypto/man/BN_new.3 index 90c0fb4e343..4d73b730303 100644 --- a/lib/libcrypto/man/BN_new.3 +++ b/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/lib/libcrypto/man/Makefile b/lib/libcrypto/man/Makefile index 9f514044c2d..f1142ab0149 100644 --- a/lib/libcrypto/man/Makefile +++ b/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 @@ -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 \ -- 2.20.1