1 // Copyright 2000-2016 The OpenSSL Project Authors. All Rights Reserved.
2 //
3 // Licensed under the Apache License, Version 2.0 (the "License");
4 // you may not use this file except in compliance with the License.
5 // You may obtain a copy of the License at
6 //
7 // https://www.apache.org/licenses/LICENSE-2.0
8 //
9 // Unless required by applicable law or agreed to in writing, software
10 // distributed under the License is distributed on an "AS IS" BASIS,
11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 // See the License for the specific language governing permissions and
13 // limitations under the License.
14
15 #include <openssl/bn.h>
16
17 #include <openssl/err.h>
18
19
BN_sqrt(BIGNUM * out_sqrt,const BIGNUM * in,BN_CTX * ctx)20 int BN_sqrt(BIGNUM *out_sqrt, const BIGNUM *in, BN_CTX *ctx) {
21 BIGNUM *estimate, *tmp, *delta, *last_delta, *tmp2;
22 int ok = 0, last_delta_valid = 0;
23
24 if (in->neg) {
25 OPENSSL_PUT_ERROR(BN, BN_R_NEGATIVE_NUMBER);
26 return 0;
27 }
28 if (BN_is_zero(in)) {
29 BN_zero(out_sqrt);
30 return 1;
31 }
32
33 bssl::BN_CTXScope scope(ctx);
34 if (out_sqrt == in) {
35 estimate = BN_CTX_get(ctx);
36 } else {
37 estimate = out_sqrt;
38 }
39 tmp = BN_CTX_get(ctx);
40 last_delta = BN_CTX_get(ctx);
41 delta = BN_CTX_get(ctx);
42 if (estimate == NULL || tmp == NULL || last_delta == NULL || delta == NULL) {
43 goto err;
44 }
45
46 // We estimate that the square root of an n-bit number is 2^{n/2}.
47 if (!BN_lshift(estimate, BN_value_one(), BN_num_bits(in)/2)) {
48 goto err;
49 }
50
51 // This is Newton's method for finding a root of the equation |estimate|^2 -
52 // |in| = 0.
53 for (;;) {
54 // |estimate| = 1/2 * (|estimate| + |in|/|estimate|)
55 if (!BN_div(tmp, NULL, in, estimate, ctx) ||
56 !BN_add(tmp, tmp, estimate) ||
57 !BN_rshift1(estimate, tmp) ||
58 // |tmp| = |estimate|^2
59 !BN_sqr(tmp, estimate, ctx) ||
60 // |delta| = |in| - |tmp|
61 !BN_sub(delta, in, tmp)) {
62 OPENSSL_PUT_ERROR(BN, ERR_R_BN_LIB);
63 goto err;
64 }
65
66 delta->neg = 0;
67 // The difference between |in| and |estimate| squared is required to always
68 // decrease. This ensures that the loop always terminates, but I don't have
69 // a proof that it always finds the square root for a given square.
70 if (last_delta_valid && BN_cmp(delta, last_delta) >= 0) {
71 break;
72 }
73
74 last_delta_valid = 1;
75
76 tmp2 = last_delta;
77 last_delta = delta;
78 delta = tmp2;
79 }
80
81 if (BN_cmp(tmp, in) != 0) {
82 OPENSSL_PUT_ERROR(BN, BN_R_NOT_A_SQUARE);
83 goto err;
84 }
85
86 ok = 1;
87
88 err:
89 if (ok && out_sqrt == in && !BN_copy(out_sqrt, estimate)) {
90 ok = 0;
91 }
92 return ok;
93 }
94