OpenCoverage

bn_sqrt.c

Absolute File Name:/home/opencoverage/opencoverage/guest-scripts/libressl/src/crypto/bn/bn_sqrt.c
Source codeSwitch to Preprocessed file
LineSourceCount
1/* $OpenBSD: bn_sqrt.c,v 1.9 2017/01/29 17:49:22 beck Exp $ */-
2/* Written by Lenka Fibikova <fibikova@exp-math.uni-essen.de>-
3 * and Bodo Moeller for the OpenSSL project. */-
4/* ====================================================================-
5 * Copyright (c) 1998-2000 The OpenSSL Project. All rights reserved.-
6 *-
7 * Redistribution and use in source and binary forms, with or without-
8 * modification, are permitted provided that the following conditions-
9 * are met:-
10 *-
11 * 1. Redistributions of source code must retain the above copyright-
12 * notice, this list of conditions and the following disclaimer.-
13 *-
14 * 2. Redistributions in binary form must reproduce the above copyright-
15 * notice, this list of conditions and the following disclaimer in-
16 * the documentation and/or other materials provided with the-
17 * distribution.-
18 *-
19 * 3. All advertising materials mentioning features or use of this-
20 * software must display the following acknowledgment:-
21 * "This product includes software developed by the OpenSSL Project-
22 * for use in the OpenSSL Toolkit. (http://www.openssl.org/)"-
23 *-
24 * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to-
25 * endorse or promote products derived from this software without-
26 * prior written permission. For written permission, please contact-
27 * openssl-core@openssl.org.-
28 *-
29 * 5. Products derived from this software may not be called "OpenSSL"-
30 * nor may "OpenSSL" appear in their names without prior written-
31 * permission of the OpenSSL Project.-
32 *-
33 * 6. Redistributions of any form whatsoever must retain the following-
34 * acknowledgment:-
35 * "This product includes software developed by the OpenSSL Project-
36 * for use in the OpenSSL Toolkit (http://www.openssl.org/)"-
37 *-
38 * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY-
39 * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE-
40 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR-
41 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE OpenSSL PROJECT OR-
42 * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,-
43 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT-
44 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;-
45 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)-
46 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,-
47 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)-
48 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED-
49 * OF THE POSSIBILITY OF SUCH DAMAGE.-
50 * ====================================================================-
51 *-
52 * This product includes cryptographic software written by Eric Young-
53 * (eay@cryptsoft.com). This product includes software written by Tim-
54 * Hudson (tjh@cryptsoft.com).-
55 *-
56 */-
57-
58#include <openssl/err.h>-
59-
60#include "bn_lcl.h"-
61-
62BIGNUM *-
63BN_mod_sqrt(BIGNUM *in, const BIGNUM *a, const BIGNUM *p, BN_CTX *ctx)-
64/* Returns 'ret' such that-
65 * ret^2 == a (mod p),-
66 * using the Tonelli/Shanks algorithm (cf. Henri Cohen, "A Course-
67 * in Algebraic Computational Number Theory", algorithm 1.5.1).-
68 * 'p' must be prime!-
69 */-
70{-
71 BIGNUM *ret = in;-
72 int err = 1;-
73 int r;-
74 BIGNUM *A, *b, *q, *t, *x, *y;-
75 int e, i, j;-
76-
77 if (!BN_is_odd(p) || BN_abs_is_word(p, 1)) {
((p)->top > 0)Description
TRUEevaluated 87 times by 2 tests
Evaluated by:
  • bntest
  • ectest
FALSEnever evaluated
((p)->d[0] & 1)Description
TRUEevaluated 82 times by 2 tests
Evaluated by:
  • bntest
  • ectest
FALSEevaluated 5 times by 1 test
Evaluated by:
  • bntest
((p)->top == 1)Description
TRUEevaluated 37 times by 2 tests
Evaluated by:
  • bntest
  • ectest
FALSEevaluated 45 times by 2 tests
Evaluated by:
  • bntest
  • ectest
((p)->d[0] == ...gned long)(1))Description
TRUEnever evaluated
FALSEevaluated 37 times by 2 tests
Evaluated by:
  • bntest
  • ectest
((1) == 0)Description
TRUEnever evaluated
FALSEevaluated 82 times by 2 tests
Evaluated by:
  • bntest
  • ectest
((p)->top == 0)Description
TRUEnever evaluated
FALSEnever evaluated
0-87
78 if (BN_abs_is_word(p, 2)) {
((p)->top == 1)Description
TRUEevaluated 5 times by 1 test
Evaluated by:
  • bntest
FALSEnever evaluated
((p)->d[0] == ...gned long)(2))Description
TRUEevaluated 5 times by 1 test
Evaluated by:
  • bntest
FALSEnever evaluated
((2) == 0)Description
TRUEnever evaluated
FALSEnever evaluated
((p)->top == 0)Description
TRUEnever evaluated
FALSEnever evaluated
0-5
79 if (ret == NULL)
ret == ((void *)0)Description
TRUEnever evaluated
FALSEevaluated 5 times by 1 test
Evaluated by:
  • bntest
0-5
80 ret = BN_new();
never executed: ret = BN_new();
0
81 if (ret == NULL)
ret == ((void *)0)Description
TRUEnever evaluated
FALSEevaluated 5 times by 1 test
Evaluated by:
  • bntest
0-5
82 goto end;
never executed: goto end;
0
83 if (!BN_set_word(ret, BN_is_bit_set(a, 0))) {
!BN_set_word(r...bit_set(a, 0))Description
TRUEnever evaluated
FALSEevaluated 5 times by 1 test
Evaluated by:
  • bntest
0-5
84 if (ret != in)
ret != inDescription
TRUEnever evaluated
FALSEnever evaluated
0
85 BN_free(ret);
never executed: BN_free(ret);
0
86 return NULL;
never executed: return ((void *)0) ;
0
87 }-
88 bn_check_top(ret);-
89 return ret;
executed 5 times by 1 test: return ret;
Executed by:
  • bntest
5
90 }-
91-
92 BNerror(BN_R_P_IS_NOT_PRIME);-
93 return (NULL);
never executed: return ( ((void *)0) );
0
94 }-
95-
96 if (BN_is_zero(a) || BN_is_one(a)) {
((a)->top == 0)Description
TRUEevaluated 6 times by 1 test
Evaluated by:
  • bntest
FALSEevaluated 76 times by 2 tests
Evaluated by:
  • bntest
  • ectest
(((a))->top == 1)Description
TRUEevaluated 31 times by 2 tests
Evaluated by:
  • bntest
  • ectest
FALSEevaluated 45 times by 2 tests
Evaluated by:
  • bntest
  • ectest
(((a))->d[0] =...gned long)(1))Description
TRUEevaluated 2 times by 1 test
Evaluated by:
  • bntest
FALSEevaluated 29 times by 2 tests
Evaluated by:
  • bntest
  • ectest
((1) == 0)Description
TRUEnever evaluated
FALSEevaluated 74 times by 2 tests
Evaluated by:
  • bntest
  • ectest
(((a))->top == 0)Description
TRUEnever evaluated
FALSEnever evaluated
!(a)->negDescription
TRUEevaluated 1 time by 1 test
Evaluated by:
  • bntest
FALSEevaluated 1 time by 1 test
Evaluated by:
  • bntest
0-76
97 if (ret == NULL)
ret == ((void *)0)Description
TRUEnever evaluated
FALSEevaluated 7 times by 1 test
Evaluated by:
  • bntest
0-7
98 ret = BN_new();
never executed: ret = BN_new();
0
99 if (ret == NULL)
ret == ((void *)0)Description
TRUEnever evaluated
FALSEevaluated 7 times by 1 test
Evaluated by:
  • bntest
0-7
100 goto end;
never executed: goto end;
0
101 if (!BN_set_word(ret, BN_is_one(a))) {
!BN_set_word(r...&& !(a)->neg))Description
TRUEnever evaluated
FALSEevaluated 7 times by 1 test
Evaluated by:
  • bntest
0-7
102 if (ret != in)
ret != inDescription
TRUEnever evaluated
FALSEnever evaluated
0
103 BN_free(ret);
never executed: BN_free(ret);
0
104 return NULL;
never executed: return ((void *)0) ;
0
105 }-
106 bn_check_top(ret);-
107 return ret;
executed 7 times by 1 test: return ret;
Executed by:
  • bntest
7
108 }-
109-
110 BN_CTX_start(ctx);-
111 if ((A = BN_CTX_get(ctx)) == NULL)
(A = BN_CTX_ge...== ((void *)0)Description
TRUEnever evaluated
FALSEevaluated 75 times by 2 tests
Evaluated by:
  • bntest
  • ectest
0-75
112 goto end;
never executed: goto end;
0
113 if ((b = BN_CTX_get(ctx)) == NULL)
(b = BN_CTX_ge...== ((void *)0)Description
TRUEnever evaluated
FALSEevaluated 75 times by 2 tests
Evaluated by:
  • bntest
  • ectest
0-75
114 goto end;
never executed: goto end;
0
115 if ((q = BN_CTX_get(ctx)) == NULL)
(q = BN_CTX_ge...== ((void *)0)Description
TRUEnever evaluated
FALSEevaluated 75 times by 2 tests
Evaluated by:
  • bntest
  • ectest
0-75
116 goto end;
never executed: goto end;
0
117 if ((t = BN_CTX_get(ctx)) == NULL)
(t = BN_CTX_ge...== ((void *)0)Description
TRUEnever evaluated
FALSEevaluated 75 times by 2 tests
Evaluated by:
  • bntest
  • ectest
0-75
118 goto end;
never executed: goto end;
0
119 if ((x = BN_CTX_get(ctx)) == NULL)
(x = BN_CTX_ge...== ((void *)0)Description
TRUEnever evaluated
FALSEevaluated 75 times by 2 tests
Evaluated by:
  • bntest
  • ectest
0-75
120 goto end;
never executed: goto end;
0
121 if ((y = BN_CTX_get(ctx)) == NULL)
(y = BN_CTX_ge...== ((void *)0)Description
TRUEnever evaluated
FALSEevaluated 75 times by 2 tests
Evaluated by:
  • bntest
  • ectest
0-75
122 goto end;
never executed: goto end;
0
123-
124 if (ret == NULL)
ret == ((void *)0)Description
TRUEnever evaluated
FALSEevaluated 75 times by 2 tests
Evaluated by:
  • bntest
  • ectest
0-75
125 ret = BN_new();
never executed: ret = BN_new();
0
126 if (ret == NULL)
ret == ((void *)0)Description
TRUEnever evaluated
FALSEevaluated 75 times by 2 tests
Evaluated by:
  • bntest
  • ectest
0-75
127 goto end;
never executed: goto end;
0
128-
129 /* A = a mod p */-
130 if (!BN_nnmod(A, a, p, ctx))
!BN_nnmod(A, a, p, ctx)Description
TRUEnever evaluated
FALSEevaluated 75 times by 2 tests
Evaluated by:
  • bntest
  • ectest
0-75
131 goto end;
never executed: goto end;
0
132-
133 /* now write |p| - 1 as 2^e*q where q is odd */-
134 e = 1;-
135 while (!BN_is_bit_set(p, e))
!BN_is_bit_set(p, e)Description
TRUEevaluated 153 times by 2 tests
Evaluated by:
  • bntest
  • ectest
FALSEevaluated 75 times by 2 tests
Evaluated by:
  • bntest
  • ectest
75-153
136 e++;
executed 153 times by 2 tests: e++;
Executed by:
  • bntest
  • ectest
153
137 /* we'll set q later (if needed) */-
138-
139 if (e == 1) {
e == 1Description
TRUEevaluated 41 times by 2 tests
Evaluated by:
  • bntest
  • ectest
FALSEevaluated 34 times by 2 tests
Evaluated by:
  • bntest
  • ectest
34-41
140 /* The easy case: (|p|-1)/2 is odd, so 2 has an inverse-
141 * modulo (|p|-1)/2, and square roots can be computed-
142 * directly by modular exponentiation.-
143 * We have-
144 * 2 * (|p|+1)/4 == 1 (mod (|p|-1)/2),-
145 * so we can use exponent (|p|+1)/4, i.e. (|p|-3)/4 + 1.-
146 */-
147 if (!BN_rshift(q, p, 2))
!BN_rshift(q, p, 2)Description
TRUEnever evaluated
FALSEevaluated 41 times by 2 tests
Evaluated by:
  • bntest
  • ectest
0-41
148 goto end;
never executed: goto end;
0
149 q->neg = 0;-
150 if (!BN_add_word(q, 1))
!BN_add_word(q, 1)Description
TRUEnever evaluated
FALSEevaluated 41 times by 2 tests
Evaluated by:
  • bntest
  • ectest
0-41
151 goto end;
never executed: goto end;
0
152 if (!BN_mod_exp_ct(ret, A, q, p, ctx))
!BN_mod_exp_ct... A, q, p, ctx)Description
TRUEnever evaluated
FALSEevaluated 41 times by 2 tests
Evaluated by:
  • bntest
  • ectest
0-41
153 goto end;
never executed: goto end;
0
154 err = 0;-
155 goto vrfy;
executed 41 times by 2 tests: goto vrfy;
Executed by:
  • bntest
  • ectest
41
156 }-
157-
158 if (e == 2) {
e == 2Description
TRUEevaluated 18 times by 1 test
Evaluated by:
  • bntest
FALSEevaluated 16 times by 2 tests
Evaluated by:
  • bntest
  • ectest
16-18
159 /* |p| == 5 (mod 8)-
160 *-
161 * In this case 2 is always a non-square since-
162 * Legendre(2,p) = (-1)^((p^2-1)/8) for any odd prime.-
163 * So if a really is a square, then 2*a is a non-square.-
164 * Thus for-
165 * b := (2*a)^((|p|-5)/8),-
166 * i := (2*a)*b^2-
167 * we have-
168 * i^2 = (2*a)^((1 + (|p|-5)/4)*2)-
169 * = (2*a)^((p-1)/2)-
170 * = -1;-
171 * so if we set-
172 * x := a*b*(i-1),-
173 * then-
174 * x^2 = a^2 * b^2 * (i^2 - 2*i + 1)-
175 * = a^2 * b^2 * (-2*i)-
176 * = a*(-i)*(2*a*b^2)-
177 * = a*(-i)*i-
178 * = a.-
179 *-
180 * (This is due to A.O.L. Atkin,-
181 * <URL: http://listserv.nodak.edu/scripts/wa.exe?A2=ind9211&L=nmbrthry&O=T&P=562>,-
182 * November 1992.)-
183 */-
184-
185 /* t := 2*a */-
186 if (!BN_mod_lshift1_quick(t, A, p))
!BN_mod_lshift1_quick(t, A, p)Description
TRUEnever evaluated
FALSEevaluated 18 times by 1 test
Evaluated by:
  • bntest
0-18
187 goto end;
never executed: goto end;
0
188-
189 /* b := (2*a)^((|p|-5)/8) */-
190 if (!BN_rshift(q, p, 3))
!BN_rshift(q, p, 3)Description
TRUEnever evaluated
FALSEevaluated 18 times by 1 test
Evaluated by:
  • bntest
0-18
191 goto end;
never executed: goto end;
0
192 q->neg = 0;-
193 if (!BN_mod_exp_ct(b, t, q, p, ctx))
!BN_mod_exp_ct... t, q, p, ctx)Description
TRUEnever evaluated
FALSEevaluated 18 times by 1 test
Evaluated by:
  • bntest
0-18
194 goto end;
never executed: goto end;
0
195-
196 /* y := b^2 */-
197 if (!BN_mod_sqr(y, b, p, ctx))
!BN_mod_sqr(y, b, p, ctx)Description
TRUEnever evaluated
FALSEevaluated 18 times by 1 test
Evaluated by:
  • bntest
0-18
198 goto end;
never executed: goto end;
0
199-
200 /* t := (2*a)*b^2 - 1*/-
201 if (!BN_mod_mul(t, t, y, p, ctx))
!BN_mod_mul(t, t, y, p, ctx)Description
TRUEnever evaluated
FALSEevaluated 18 times by 1 test
Evaluated by:
  • bntest
0-18
202 goto end;
never executed: goto end;
0
203 if (!BN_sub_word(t, 1))
!BN_sub_word(t, 1)Description
TRUEnever evaluated
FALSEevaluated 18 times by 1 test
Evaluated by:
  • bntest
0-18
204 goto end;
never executed: goto end;
0
205-
206 /* x = a*b*t */-
207 if (!BN_mod_mul(x, A, b, p, ctx))
!BN_mod_mul(x, A, b, p, ctx)Description
TRUEnever evaluated
FALSEevaluated 18 times by 1 test
Evaluated by:
  • bntest
0-18
208 goto end;
never executed: goto end;
0
209 if (!BN_mod_mul(x, x, t, p, ctx))
!BN_mod_mul(x, x, t, p, ctx)Description
TRUEnever evaluated
FALSEevaluated 18 times by 1 test
Evaluated by:
  • bntest
0-18
210 goto end;
never executed: goto end;
0
211-
212 if (!BN_copy(ret, x))
!BN_copy(ret, x)Description
TRUEnever evaluated
FALSEevaluated 18 times by 1 test
Evaluated by:
  • bntest
0-18
213 goto end;
never executed: goto end;
0
214 err = 0;-
215 goto vrfy;
executed 18 times by 1 test: goto vrfy;
Executed by:
  • bntest
18
216 }-
217-
218 /* e > 2, so we really have to use the Tonelli/Shanks algorithm.-
219 * First, find some y that is not a square. */-
220 if (!BN_copy(q, p)) goto end; /* use 'q' as temp */
never executed: goto end;
!BN_copy(q, p)Description
TRUEnever evaluated
FALSEevaluated 16 times by 2 tests
Evaluated by:
  • bntest
  • ectest
0-16
221 q->neg = 0;-
222 i = 2;-
223 do {-
224 /* For efficiency, try small numbers first;-
225 * if this fails, try random numbers.-
226 */-
227 if (i < 22) {
i < 22Description
TRUEevaluated 40 times by 2 tests
Evaluated by:
  • bntest
  • ectest
FALSEnever evaluated
0-40
228 if (!BN_set_word(y, i))
!BN_set_word(y, i)Description
TRUEnever evaluated
FALSEevaluated 40 times by 2 tests
Evaluated by:
  • bntest
  • ectest
0-40
229 goto end;
never executed: goto end;
0
230 } else {
executed 40 times by 2 tests: end of block
Executed by:
  • bntest
  • ectest
40
231 if (!BN_pseudo_rand(y, BN_num_bits(p), 0, 0))
!BN_pseudo_ran...bits(p), 0, 0)Description
TRUEnever evaluated
FALSEnever evaluated
0
232 goto end;
never executed: goto end;
0
233 if (BN_ucmp(y, p) >= 0) {
BN_ucmp(y, p) >= 0Description
TRUEnever evaluated
FALSEnever evaluated
0
234 if (p->neg) {
p->negDescription
TRUEnever evaluated
FALSEnever evaluated
0
235 if (!BN_add(y, y, p))
!BN_add(y, y, p)Description
TRUEnever evaluated
FALSEnever evaluated
0
236 goto end;
never executed: goto end;
0
237 } else {
never executed: end of block
0
238 if (!BN_sub(y, y, p))
!BN_sub(y, y, p)Description
TRUEnever evaluated
FALSEnever evaluated
0
239 goto end;
never executed: goto end;
0
240 }
never executed: end of block
0
241 }-
242 /* now 0 <= y < |p| */-
243 if (BN_is_zero(y))
((y)->top == 0)Description
TRUEnever evaluated
FALSEnever evaluated
0
244 if (!BN_set_word(y, i))
!BN_set_word(y, i)Description
TRUEnever evaluated
FALSEnever evaluated
0
245 goto end;
never executed: goto end;
0
246 }
never executed: end of block
0
247-
248 r = BN_kronecker(y, q, ctx); /* here 'q' is |p| */-
249 if (r < -1)
r < -1Description
TRUEnever evaluated
FALSEevaluated 40 times by 2 tests
Evaluated by:
  • bntest
  • ectest
0-40
250 goto end;
never executed: goto end;
0
251 if (r == 0) {
r == 0Description
TRUEnever evaluated
FALSEevaluated 40 times by 2 tests
Evaluated by:
  • bntest
  • ectest
0-40
252 /* m divides p */-
253 BNerror(BN_R_P_IS_NOT_PRIME);-
254 goto end;
never executed: goto end;
0
255 }-
256 }
executed 40 times by 2 tests: end of block
Executed by:
  • bntest
  • ectest
40
257 while (r == 1 && ++i < 82);
r == 1Description
TRUEevaluated 24 times by 2 tests
Evaluated by:
  • bntest
  • ectest
FALSEevaluated 16 times by 2 tests
Evaluated by:
  • bntest
  • ectest
++i < 82Description
TRUEevaluated 24 times by 2 tests
Evaluated by:
  • bntest
  • ectest
FALSEnever evaluated
0-24
258-
259 if (r != -1) {
r != -1Description
TRUEnever evaluated
FALSEevaluated 16 times by 2 tests
Evaluated by:
  • bntest
  • ectest
0-16
260 /* Many rounds and still no non-square -- this is more likely-
261 * a bug than just bad luck.-
262 * Even if p is not prime, we should have found some y-
263 * such that r == -1.-
264 */-
265 BNerror(BN_R_TOO_MANY_ITERATIONS);-
266 goto end;
never executed: goto end;
0
267 }-
268-
269 /* Here's our actual 'q': */-
270 if (!BN_rshift(q, q, e))
!BN_rshift(q, q, e)Description
TRUEnever evaluated
FALSEevaluated 16 times by 2 tests
Evaluated by:
  • bntest
  • ectest
0-16
271 goto end;
never executed: goto end;
0
272-
273 /* Now that we have some non-square, we can find an element-
274 * of order 2^e by computing its q'th power. */-
275 if (!BN_mod_exp_ct(y, y, q, p, ctx))
!BN_mod_exp_ct... y, q, p, ctx)Description
TRUEnever evaluated
FALSEevaluated 16 times by 2 tests
Evaluated by:
  • bntest
  • ectest
0-16
276 goto end;
never executed: goto end;
0
277 if (BN_is_one(y)) {
(((y))->top == 1)Description
TRUEevaluated 5 times by 1 test
Evaluated by:
  • bntest
FALSEevaluated 11 times by 2 tests
Evaluated by:
  • bntest
  • ectest
(((y))->d[0] =...gned long)(1))Description
TRUEnever evaluated
FALSEevaluated 5 times by 1 test
Evaluated by:
  • bntest
((1) == 0)Description
TRUEnever evaluated
FALSEevaluated 16 times by 2 tests
Evaluated by:
  • bntest
  • ectest
(((y))->top == 0)Description
TRUEnever evaluated
FALSEnever evaluated
!(y)->negDescription
TRUEnever evaluated
FALSEnever evaluated
0-16
278 BNerror(BN_R_P_IS_NOT_PRIME);-
279 goto end;
never executed: goto end;
0
280 }-
281-
282 /* Now we know that (if p is indeed prime) there is an integer-
283 * k, 0 <= k < 2^e, such that-
284 *-
285 * a^q * y^k == 1 (mod p).-
286 *-
287 * As a^q is a square and y is not, k must be even.-
288 * q+1 is even, too, so there is an element-
289 *-
290 * X := a^((q+1)/2) * y^(k/2),-
291 *-
292 * and it satisfies-
293 *-
294 * X^2 = a^q * a * y^k-
295 * = a,-
296 *-
297 * so it is the square root that we are looking for.-
298 */-
299-
300 /* t := (q-1)/2 (note that q is odd) */-
301 if (!BN_rshift1(t, q))
!BN_rshift1(t, q)Description
TRUEnever evaluated
FALSEevaluated 16 times by 2 tests
Evaluated by:
  • bntest
  • ectest
0-16
302 goto end;
never executed: goto end;
0
303-
304 /* x := a^((q-1)/2) */-
305 if (BN_is_zero(t)) /* special case: p = 2^e + 1 */
((t)->top == 0)Description
TRUEevaluated 5 times by 1 test
Evaluated by:
  • bntest
FALSEevaluated 11 times by 2 tests
Evaluated by:
  • bntest
  • ectest
5-11
306 {-
307 if (!BN_nnmod(t, A, p, ctx))
!BN_nnmod(t, A, p, ctx)Description
TRUEnever evaluated
FALSEevaluated 5 times by 1 test
Evaluated by:
  • bntest
0-5
308 goto end;
never executed: goto end;
0
309 if (BN_is_zero(t)) {
((t)->top == 0)Description
TRUEevaluated 1 time by 1 test
Evaluated by:
  • bntest
FALSEevaluated 4 times by 1 test
Evaluated by:
  • bntest
1-4
310 /* special case: a == 0 (mod p) */-
311 BN_zero(ret);-
312 err = 0;-
313 goto end;
executed 1 time by 1 test: goto end;
Executed by:
  • bntest
1
314 } else if (!BN_one(x))
!(BN_set_word((x),1))Description
TRUEnever evaluated
FALSEevaluated 4 times by 1 test
Evaluated by:
  • bntest
0-4
315 goto end;
never executed: goto end;
0
316 } else {
executed 4 times by 1 test: end of block
Executed by:
  • bntest
4
317 if (!BN_mod_exp_ct(x, A, t, p, ctx))
!BN_mod_exp_ct... A, t, p, ctx)Description
TRUEnever evaluated
FALSEevaluated 11 times by 2 tests
Evaluated by:
  • bntest
  • ectest
0-11
318 goto end;
never executed: goto end;
0
319 if (BN_is_zero(x)) {
((x)->top == 0)Description
TRUEnever evaluated
FALSEevaluated 11 times by 2 tests
Evaluated by:
  • bntest
  • ectest
0-11
320 /* special case: a == 0 (mod p) */-
321 BN_zero(ret);-
322 err = 0;-
323 goto end;
never executed: goto end;
0
324 }-
325 }
executed 11 times by 2 tests: end of block
Executed by:
  • bntest
  • ectest
11
326-
327 /* b := a*x^2 (= a^q) */-
328 if (!BN_mod_sqr(b, x, p, ctx))
!BN_mod_sqr(b, x, p, ctx)Description
TRUEnever evaluated
FALSEevaluated 15 times by 2 tests
Evaluated by:
  • bntest
  • ectest
0-15
329 goto end;
never executed: goto end;
0
330 if (!BN_mod_mul(b, b, A, p, ctx))
!BN_mod_mul(b, b, A, p, ctx)Description
TRUEnever evaluated
FALSEevaluated 15 times by 2 tests
Evaluated by:
  • bntest
  • ectest
0-15
331 goto end;
never executed: goto end;
0
332-
333 /* x := a*x (= a^((q+1)/2)) */-
334 if (!BN_mod_mul(x, x, A, p, ctx))
!BN_mod_mul(x, x, A, p, ctx)Description
TRUEnever evaluated
FALSEevaluated 15 times by 2 tests
Evaluated by:
  • bntest
  • ectest
0-15
335 goto end;
never executed: goto end;
0
336-
337 while (1) {-
338 /* Now b is a^q * y^k for some even k (0 <= k < 2^E-
339 * where E refers to the original value of e, which we-
340 * don't keep in a variable), and x is a^((q+1)/2) * y^(k/2).-
341 *-
342 * We have a*b = x^2,-
343 * y^2^(e-1) = -1,-
344 * b^2^(e-1) = 1.-
345 */-
346-
347 if (BN_is_one(b)) {
(((b))->top == 1)Description
TRUEevaluated 21 times by 2 tests
Evaluated by:
  • bntest
  • ectest
FALSEevaluated 51 times by 2 tests
Evaluated by:
  • bntest
  • ectest
(((b))->d[0] =...gned long)(1))Description
TRUEevaluated 15 times by 2 tests
Evaluated by:
  • bntest
  • ectest
FALSEevaluated 6 times by 1 test
Evaluated by:
  • bntest
((1) == 0)Description
TRUEnever evaluated
FALSEevaluated 57 times by 2 tests
Evaluated by:
  • bntest
  • ectest
(((b))->top == 0)Description
TRUEnever evaluated
FALSEnever evaluated
!(b)->negDescription
TRUEevaluated 15 times by 2 tests
Evaluated by:
  • bntest
  • ectest
FALSEnever evaluated
0-57
348 if (!BN_copy(ret, x))
!BN_copy(ret, x)Description
TRUEnever evaluated
FALSEevaluated 15 times by 2 tests
Evaluated by:
  • bntest
  • ectest
0-15
349 goto end;
never executed: goto end;
0
350 err = 0;-
351 goto vrfy;
executed 15 times by 2 tests: goto vrfy;
Executed by:
  • bntest
  • ectest
15
352 }-
353-
354-
355 /* find smallest i such that b^(2^i) = 1 */-
356 i = 1;-
357 if (!BN_mod_sqr(t, b, p, ctx))
!BN_mod_sqr(t, b, p, ctx)Description
TRUEnever evaluated
FALSEevaluated 57 times by 2 tests
Evaluated by:
  • bntest
  • ectest
0-57
358 goto end;
never executed: goto end;
0
359 while (!BN_is_one(t)) {
(((t))->top == 1)Description
TRUEevaluated 66 times by 2 tests
Evaluated by:
  • bntest
  • ectest
FALSEevaluated 1780 times by 2 tests
Evaluated by:
  • bntest
  • ectest
(((t))->d[0] =...gned long)(1))Description
TRUEevaluated 57 times by 2 tests
Evaluated by:
  • bntest
  • ectest
FALSEevaluated 9 times by 1 test
Evaluated by:
  • bntest
((1) == 0)Description
TRUEnever evaluated
FALSEevaluated 1789 times by 2 tests
Evaluated by:
  • bntest
  • ectest
(((t))->top == 0)Description
TRUEnever evaluated
FALSEnever evaluated
!(t)->negDescription
TRUEevaluated 57 times by 2 tests
Evaluated by:
  • bntest
  • ectest
FALSEnever evaluated
0-1789
360 i++;-
361 if (i == e) {
i == eDescription
TRUEnever evaluated
FALSEevaluated 1789 times by 2 tests
Evaluated by:
  • bntest
  • ectest
0-1789
362 BNerror(BN_R_NOT_A_SQUARE);-
363 goto end;
never executed: goto end;
0
364 }-
365 if (!BN_mod_mul(t, t, t, p, ctx))
!BN_mod_mul(t, t, t, p, ctx)Description
TRUEnever evaluated
FALSEevaluated 1789 times by 2 tests
Evaluated by:
  • bntest
  • ectest
0-1789
366 goto end;
never executed: goto end;
0
367 }
executed 1789 times by 2 tests: end of block
Executed by:
  • bntest
  • ectest
1789
368-
369-
370 /* t := y^2^(e - i - 1) */-
371 if (!BN_copy(t, y))
!BN_copy(t, y)Description
TRUEnever evaluated
FALSEevaluated 57 times by 2 tests
Evaluated by:
  • bntest
  • ectest
0-57
372 goto end;
never executed: goto end;
0
373 for (j = e - i - 1; j > 0; j--) {
j > 0Description
TRUEevaluated 64 times by 2 tests
Evaluated by:
  • bntest
  • ectest
FALSEevaluated 57 times by 2 tests
Evaluated by:
  • bntest
  • ectest
57-64
374 if (!BN_mod_sqr(t, t, p, ctx))
!BN_mod_sqr(t, t, p, ctx)Description
TRUEnever evaluated
FALSEevaluated 64 times by 2 tests
Evaluated by:
  • bntest
  • ectest
0-64
375 goto end;
never executed: goto end;
0
376 }
executed 64 times by 2 tests: end of block
Executed by:
  • bntest
  • ectest
64
377 if (!BN_mod_mul(y, t, t, p, ctx))
!BN_mod_mul(y, t, t, p, ctx)Description
TRUEnever evaluated
FALSEevaluated 57 times by 2 tests
Evaluated by:
  • bntest
  • ectest
0-57
378 goto end;
never executed: goto end;
0
379 if (!BN_mod_mul(x, x, t, p, ctx))
!BN_mod_mul(x, x, t, p, ctx)Description
TRUEnever evaluated
FALSEevaluated 57 times by 2 tests
Evaluated by:
  • bntest
  • ectest
0-57
380 goto end;
never executed: goto end;
0
381 if (!BN_mod_mul(b, b, y, p, ctx))
!BN_mod_mul(b, b, y, p, ctx)Description
TRUEnever evaluated
FALSEevaluated 57 times by 2 tests
Evaluated by:
  • bntest
  • ectest
0-57
382 goto end;
never executed: goto end;
0
383 e = i;-
384 }
executed 57 times by 2 tests: end of block
Executed by:
  • bntest
  • ectest
57
385-
386vrfy:
code before this statement never executed: vrfy:
0
387 if (!err) {
!errDescription
TRUEevaluated 74 times by 2 tests
Evaluated by:
  • bntest
  • ectest
FALSEnever evaluated
0-74
388 /* verify the result -- the input might have been not a square-
389 * (test added in 0.9.8) */-
390-
391 if (!BN_mod_sqr(x, ret, p, ctx))
!BN_mod_sqr(x, ret, p, ctx)Description
TRUEnever evaluated
FALSEevaluated 74 times by 2 tests
Evaluated by:
  • bntest
  • ectest
0-74
392 err = 1;
never executed: err = 1;
0
393-
394 if (!err && 0 != BN_cmp(x, A)) {
!errDescription
TRUEevaluated 74 times by 2 tests
Evaluated by:
  • bntest
  • ectest
FALSEnever evaluated
0 != BN_cmp(x, A)Description
TRUEnever evaluated
FALSEevaluated 74 times by 2 tests
Evaluated by:
  • bntest
  • ectest
0-74
395 BNerror(BN_R_NOT_A_SQUARE);-
396 err = 1;-
397 }
never executed: end of block
0
398 }
executed 74 times by 2 tests: end of block
Executed by:
  • bntest
  • ectest
74
399-
400end:
code before this statement executed 74 times by 2 tests: end:
Executed by:
  • bntest
  • ectest
74
401 if (err) {
errDescription
TRUEnever evaluated
FALSEevaluated 75 times by 2 tests
Evaluated by:
  • bntest
  • ectest
0-75
402 if (ret != NULL && ret != in) {
ret != ((void *)0)Description
TRUEnever evaluated
FALSEnever evaluated
ret != inDescription
TRUEnever evaluated
FALSEnever evaluated
0
403 BN_clear_free(ret);-
404 }
never executed: end of block
0
405 ret = NULL;-
406 }
never executed: end of block
0
407 BN_CTX_end(ctx);-
408 bn_check_top(ret);-
409 return ret;
executed 75 times by 2 tests: return ret;
Executed by:
  • bntest
  • ectest
75
410}-
Source codeSwitch to Preprocessed file
Generated by Squish Coco 4.2.2