Pull BN_sqrt out of BCM
This function is completely irrelevant to cryptography.
Change-Id: I9819f11a4846838975df1da73d1034fc22987753
Reviewed-on: https://boringssl-review.googlesource.com/c/boringssl/+/78569
Auto-Submit: David Benjamin <davidben@google.com>
Reviewed-by: Adam Langley <agl@google.com>
Commit-Queue: Adam Langley <agl@google.com>
diff --git a/build.json b/build.json
index cbe98b4..9783857 100644
--- a/build.json
+++ b/build.json
@@ -205,6 +205,7 @@
"crypto/bn/bn_asn1.cc",
"crypto/bn/convert.cc",
"crypto/bn/exponentiation.cc",
+ "crypto/bn/sqrt.cc",
"crypto/buf/buf.cc",
"crypto/bytestring/asn1_compat.cc",
"crypto/bytestring/ber.cc",
diff --git a/crypto/bn/sqrt.cc b/crypto/bn/sqrt.cc
new file mode 100644
index 0000000..e23f1a3
--- /dev/null
+++ b/crypto/bn/sqrt.cc
@@ -0,0 +1,93 @@
+// Copyright 2000-2016 The OpenSSL Project Authors. All Rights Reserved.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// https://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+#include <openssl/bn.h>
+
+#include <openssl/err.h>
+
+
+int BN_sqrt(BIGNUM *out_sqrt, const BIGNUM *in, BN_CTX *ctx) {
+ BIGNUM *estimate, *tmp, *delta, *last_delta, *tmp2;
+ int ok = 0, last_delta_valid = 0;
+
+ if (in->neg) {
+ OPENSSL_PUT_ERROR(BN, BN_R_NEGATIVE_NUMBER);
+ return 0;
+ }
+ if (BN_is_zero(in)) {
+ BN_zero(out_sqrt);
+ return 1;
+ }
+
+ bssl::BN_CTXScope scope(ctx);
+ if (out_sqrt == in) {
+ estimate = BN_CTX_get(ctx);
+ } else {
+ estimate = out_sqrt;
+ }
+ tmp = BN_CTX_get(ctx);
+ last_delta = BN_CTX_get(ctx);
+ delta = BN_CTX_get(ctx);
+ if (estimate == NULL || tmp == NULL || last_delta == NULL || delta == NULL) {
+ goto err;
+ }
+
+ // We estimate that the square root of an n-bit number is 2^{n/2}.
+ if (!BN_lshift(estimate, BN_value_one(), BN_num_bits(in)/2)) {
+ goto err;
+ }
+
+ // This is Newton's method for finding a root of the equation |estimate|^2 -
+ // |in| = 0.
+ for (;;) {
+ // |estimate| = 1/2 * (|estimate| + |in|/|estimate|)
+ if (!BN_div(tmp, NULL, in, estimate, ctx) ||
+ !BN_add(tmp, tmp, estimate) ||
+ !BN_rshift1(estimate, tmp) ||
+ // |tmp| = |estimate|^2
+ !BN_sqr(tmp, estimate, ctx) ||
+ // |delta| = |in| - |tmp|
+ !BN_sub(delta, in, tmp)) {
+ OPENSSL_PUT_ERROR(BN, ERR_R_BN_LIB);
+ goto err;
+ }
+
+ delta->neg = 0;
+ // The difference between |in| and |estimate| squared is required to always
+ // decrease. This ensures that the loop always terminates, but I don't have
+ // a proof that it always finds the square root for a given square.
+ if (last_delta_valid && BN_cmp(delta, last_delta) >= 0) {
+ break;
+ }
+
+ last_delta_valid = 1;
+
+ tmp2 = last_delta;
+ last_delta = delta;
+ delta = tmp2;
+ }
+
+ if (BN_cmp(tmp, in) != 0) {
+ OPENSSL_PUT_ERROR(BN, BN_R_NOT_A_SQUARE);
+ goto err;
+ }
+
+ ok = 1;
+
+err:
+ if (ok && out_sqrt == in && !BN_copy(out_sqrt, estimate)) {
+ ok = 0;
+ }
+ return ok;
+}
diff --git a/crypto/fipsmodule/bn/sqrt.cc.inc b/crypto/fipsmodule/bn/sqrt.cc.inc
index df31df5..56d89e0 100644
--- a/crypto/fipsmodule/bn/sqrt.cc.inc
+++ b/crypto/fipsmodule/bn/sqrt.cc.inc
@@ -380,78 +380,3 @@
}
return ret;
}
-
-int BN_sqrt(BIGNUM *out_sqrt, const BIGNUM *in, BN_CTX *ctx) {
- BIGNUM *estimate, *tmp, *delta, *last_delta, *tmp2;
- int ok = 0, last_delta_valid = 0;
-
- if (in->neg) {
- OPENSSL_PUT_ERROR(BN, BN_R_NEGATIVE_NUMBER);
- return 0;
- }
- if (BN_is_zero(in)) {
- BN_zero(out_sqrt);
- return 1;
- }
-
- bssl::BN_CTXScope scope(ctx);
- if (out_sqrt == in) {
- estimate = BN_CTX_get(ctx);
- } else {
- estimate = out_sqrt;
- }
- tmp = BN_CTX_get(ctx);
- last_delta = BN_CTX_get(ctx);
- delta = BN_CTX_get(ctx);
- if (estimate == NULL || tmp == NULL || last_delta == NULL || delta == NULL) {
- goto err;
- }
-
- // We estimate that the square root of an n-bit number is 2^{n/2}.
- if (!BN_lshift(estimate, BN_value_one(), BN_num_bits(in)/2)) {
- goto err;
- }
-
- // This is Newton's method for finding a root of the equation |estimate|^2 -
- // |in| = 0.
- for (;;) {
- // |estimate| = 1/2 * (|estimate| + |in|/|estimate|)
- if (!BN_div(tmp, NULL, in, estimate, ctx) ||
- !BN_add(tmp, tmp, estimate) ||
- !BN_rshift1(estimate, tmp) ||
- // |tmp| = |estimate|^2
- !BN_sqr(tmp, estimate, ctx) ||
- // |delta| = |in| - |tmp|
- !BN_sub(delta, in, tmp)) {
- OPENSSL_PUT_ERROR(BN, ERR_R_BN_LIB);
- goto err;
- }
-
- delta->neg = 0;
- // The difference between |in| and |estimate| squared is required to always
- // decrease. This ensures that the loop always terminates, but I don't have
- // a proof that it always finds the square root for a given square.
- if (last_delta_valid && BN_cmp(delta, last_delta) >= 0) {
- break;
- }
-
- last_delta_valid = 1;
-
- tmp2 = last_delta;
- last_delta = delta;
- delta = tmp2;
- }
-
- if (BN_cmp(tmp, in) != 0) {
- OPENSSL_PUT_ERROR(BN, BN_R_NOT_A_SQUARE);
- goto err;
- }
-
- ok = 1;
-
-err:
- if (ok && out_sqrt == in && !BN_copy(out_sqrt, estimate)) {
- ok = 0;
- }
- return ok;
-}
diff --git a/gen/sources.bzl b/gen/sources.bzl
index 03ce8b8..ff0f337 100644
--- a/gen/sources.bzl
+++ b/gen/sources.bzl
@@ -304,6 +304,7 @@
"crypto/bn/bn_asn1.cc",
"crypto/bn/convert.cc",
"crypto/bn/exponentiation.cc",
+ "crypto/bn/sqrt.cc",
"crypto/buf/buf.cc",
"crypto/bytestring/asn1_compat.cc",
"crypto/bytestring/ber.cc",
diff --git a/gen/sources.cmake b/gen/sources.cmake
index 5ae6e0f..5536c13 100644
--- a/gen/sources.cmake
+++ b/gen/sources.cmake
@@ -318,6 +318,7 @@
crypto/bn/bn_asn1.cc
crypto/bn/convert.cc
crypto/bn/exponentiation.cc
+ crypto/bn/sqrt.cc
crypto/buf/buf.cc
crypto/bytestring/asn1_compat.cc
crypto/bytestring/ber.cc
diff --git a/gen/sources.gni b/gen/sources.gni
index e4079f1..ade8cd3 100644
--- a/gen/sources.gni
+++ b/gen/sources.gni
@@ -304,6 +304,7 @@
"crypto/bn/bn_asn1.cc",
"crypto/bn/convert.cc",
"crypto/bn/exponentiation.cc",
+ "crypto/bn/sqrt.cc",
"crypto/buf/buf.cc",
"crypto/bytestring/asn1_compat.cc",
"crypto/bytestring/ber.cc",
diff --git a/gen/sources.json b/gen/sources.json
index 8f4e1a4..a7cc03a 100644
--- a/gen/sources.json
+++ b/gen/sources.json
@@ -288,6 +288,7 @@
"crypto/bn/bn_asn1.cc",
"crypto/bn/convert.cc",
"crypto/bn/exponentiation.cc",
+ "crypto/bn/sqrt.cc",
"crypto/buf/buf.cc",
"crypto/bytestring/asn1_compat.cc",
"crypto/bytestring/ber.cc",
diff --git a/gen/sources.mk b/gen/sources.mk
index 02effd9..7db953e 100644
--- a/gen/sources.mk
+++ b/gen/sources.mk
@@ -298,6 +298,7 @@
crypto/bn/bn_asn1.cc \
crypto/bn/convert.cc \
crypto/bn/exponentiation.cc \
+ crypto/bn/sqrt.cc \
crypto/buf/buf.cc \
crypto/bytestring/asn1_compat.cc \
crypto/bytestring/ber.cc \
