OpenCoverage

bn_gcd.c

Absolute File Name:/home/opencoverage/opencoverage/guest-scripts/libressl/src/crypto/bn/bn_gcd.c
Source codeSwitch to Preprocessed file
LineSourceCount
1/* $OpenBSD: bn_gcd.c,v 1.15 2017/01/29 17:49:22 beck Exp $ */-
2/* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com)-
3 * All rights reserved.-
4 *-
5 * This package is an SSL implementation written-
6 * by Eric Young (eay@cryptsoft.com).-
7 * The implementation was written so as to conform with Netscapes SSL.-
8 *-
9 * This library is free for commercial and non-commercial use as long as-
10 * the following conditions are aheared to. The following conditions-
11 * apply to all code found in this distribution, be it the RC4, RSA,-
12 * lhash, DES, etc., code; not just the SSL code. The SSL documentation-
13 * included with this distribution is covered by the same copyright terms-
14 * except that the holder is Tim Hudson (tjh@cryptsoft.com).-
15 *-
16 * Copyright remains Eric Young's, and as such any Copyright notices in-
17 * the code are not to be removed.-
18 * If this package is used in a product, Eric Young should be given attribution-
19 * as the author of the parts of the library used.-
20 * This can be in the form of a textual message at program startup or-
21 * in documentation (online or textual) provided with the package.-
22 *-
23 * Redistribution and use in source and binary forms, with or without-
24 * modification, are permitted provided that the following conditions-
25 * are met:-
26 * 1. Redistributions of source code must retain the copyright-
27 * notice, this list of conditions and the following disclaimer.-
28 * 2. Redistributions in binary form must reproduce the above copyright-
29 * notice, this list of conditions and the following disclaimer in the-
30 * documentation and/or other materials provided with the distribution.-
31 * 3. All advertising materials mentioning features or use of this software-
32 * must display the following acknowledgement:-
33 * "This product includes cryptographic software written by-
34 * Eric Young (eay@cryptsoft.com)"-
35 * The word 'cryptographic' can be left out if the rouines from the library-
36 * being used are not cryptographic related :-).-
37 * 4. If you include any Windows specific code (or a derivative thereof) from-
38 * the apps directory (application code) you must include an acknowledgement:-
39 * "This product includes software written by Tim Hudson (tjh@cryptsoft.com)"-
40 *-
41 * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND-
42 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE-
43 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE-
44 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE-
45 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL-
46 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS-
47 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)-
48 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT-
49 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY-
50 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF-
51 * SUCH DAMAGE.-
52 *-
53 * The licence and distribution terms for any publically available version or-
54 * derivative of this code cannot be changed. i.e. this code cannot simply be-
55 * copied and put under another distribution licence-
56 * [including the GNU Public Licence.]-
57 */-
58/* ====================================================================-
59 * Copyright (c) 1998-2001 The OpenSSL Project. All rights reserved.-
60 *-
61 * Redistribution and use in source and binary forms, with or without-
62 * modification, are permitted provided that the following conditions-
63 * are met:-
64 *-
65 * 1. Redistributions of source code must retain the above copyright-
66 * notice, this list of conditions and the following disclaimer.-
67 *-
68 * 2. Redistributions in binary form must reproduce the above copyright-
69 * notice, this list of conditions and the following disclaimer in-
70 * the documentation and/or other materials provided with the-
71 * distribution.-
72 *-
73 * 3. All advertising materials mentioning features or use of this-
74 * software must display the following acknowledgment:-
75 * "This product includes software developed by the OpenSSL Project-
76 * for use in the OpenSSL Toolkit. (http://www.openssl.org/)"-
77 *-
78 * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to-
79 * endorse or promote products derived from this software without-
80 * prior written permission. For written permission, please contact-
81 * openssl-core@openssl.org.-
82 *-
83 * 5. Products derived from this software may not be called "OpenSSL"-
84 * nor may "OpenSSL" appear in their names without prior written-
85 * permission of the OpenSSL Project.-
86 *-
87 * 6. Redistributions of any form whatsoever must retain the following-
88 * acknowledgment:-
89 * "This product includes software developed by the OpenSSL Project-
90 * for use in the OpenSSL Toolkit (http://www.openssl.org/)"-
91 *-
92 * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY-
93 * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE-
94 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR-
95 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE OpenSSL PROJECT OR-
96 * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,-
97 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT-
98 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;-
99 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)-
100 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,-
101 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)-
102 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED-
103 * OF THE POSSIBILITY OF SUCH DAMAGE.-
104 * ====================================================================-
105 *-
106 * This product includes cryptographic software written by Eric Young-
107 * (eay@cryptsoft.com). This product includes software written by Tim-
108 * Hudson (tjh@cryptsoft.com).-
109 *-
110 */-
111-
112#include <openssl/err.h>-
113-
114#include "bn_lcl.h"-
115-
116static BIGNUM *euclid(BIGNUM *a, BIGNUM *b);-
117static BIGNUM *BN_gcd_no_branch(BIGNUM *in, const BIGNUM *a, const BIGNUM *n,-
118 BN_CTX *ctx);-
119-
120int-
121BN_gcd(BIGNUM *r, const BIGNUM *in_a, const BIGNUM *in_b, BN_CTX *ctx)-
122{-
123 BIGNUM *a, *b, *t;-
124 int ret = 0;-
125-
126 bn_check_top(in_a);-
127 bn_check_top(in_b);-
128-
129 BN_CTX_start(ctx);-
130 if ((a = BN_CTX_get(ctx)) == NULL)
(a = BN_CTX_ge...== ((void *)0)Description
TRUEnever evaluated
FALSEnever evaluated
0
131 goto err;
never executed: goto err;
0
132 if ((b = BN_CTX_get(ctx)) == NULL)
(b = BN_CTX_ge...== ((void *)0)Description
TRUEnever evaluated
FALSEnever evaluated
0
133 goto err;
never executed: goto err;
0
134-
135 if (BN_copy(a, in_a) == NULL)
BN_copy(a, in_...== ((void *)0)Description
TRUEnever evaluated
FALSEnever evaluated
0
136 goto err;
never executed: goto err;
0
137 if (BN_copy(b, in_b) == NULL)
BN_copy(b, in_...== ((void *)0)Description
TRUEnever evaluated
FALSEnever evaluated
0
138 goto err;
never executed: goto err;
0
139 a->neg = 0;-
140 b->neg = 0;-
141-
142 if (BN_cmp(a, b) < 0) {
BN_cmp(a, b) < 0Description
TRUEnever evaluated
FALSEnever evaluated
0
143 t = a;-
144 a = b;-
145 b = t;-
146 }
never executed: end of block
0
147 t = euclid(a, b);-
148 if (t == NULL)
t == ((void *)0)Description
TRUEnever evaluated
FALSEnever evaluated
0
149 goto err;
never executed: goto err;
0
150-
151 if (BN_copy(r, t) == NULL)
BN_copy(r, t) == ((void *)0)Description
TRUEnever evaluated
FALSEnever evaluated
0
152 goto err;
never executed: goto err;
0
153 ret = 1;-
154-
155err:
code before this statement never executed: err:
0
156 BN_CTX_end(ctx);-
157 bn_check_top(r);-
158 return (ret);
never executed: return (ret);
0
159}-
160-
161int-
162BN_gcd_ct(BIGNUM *r, const BIGNUM *in_a, const BIGNUM *in_b, BN_CTX *ctx)-
163{-
164 if (BN_gcd_no_branch(r, in_a, in_b, ctx) == NULL)
BN_gcd_no_bran...== ((void *)0)Description
TRUEnever evaluated
FALSEevaluated 2 times by 1 test
Evaluated by:
  • libcrypto.so.44.0.1
0-2
165 return 0;
never executed: return 0;
0
166 return 1;
executed 2 times by 1 test: return 1;
Executed by:
  • libcrypto.so.44.0.1
2
167}-
168-
169int-
170BN_gcd_nonct(BIGNUM *r, const BIGNUM *in_a, const BIGNUM *in_b, BN_CTX *ctx)-
171{-
172 return BN_gcd(r, in_a, in_b, ctx);
never executed: return BN_gcd(r, in_a, in_b, ctx);
0
173}-
174-
175-
176static BIGNUM *-
177euclid(BIGNUM *a, BIGNUM *b)-
178{-
179 BIGNUM *t;-
180 int shifts = 0;-
181-
182 bn_check_top(a);-
183 bn_check_top(b);-
184-
185 /* 0 <= b <= a */-
186 while (!BN_is_zero(b)) {
!((b)->top == 0)Description
TRUEnever evaluated
FALSEnever evaluated
0
187 /* 0 < b <= a */-
188-
189 if (BN_is_odd(a)) {
((a)->top > 0)Description
TRUEnever evaluated
FALSEnever evaluated
((a)->d[0] & 1)Description
TRUEnever evaluated
FALSEnever evaluated
0
190 if (BN_is_odd(b)) {
((b)->top > 0)Description
TRUEnever evaluated
FALSEnever evaluated
((b)->d[0] & 1)Description
TRUEnever evaluated
FALSEnever evaluated
0
191 if (!BN_sub(a, a, b))
!BN_sub(a, a, b)Description
TRUEnever evaluated
FALSEnever evaluated
0
192 goto err;
never executed: goto err;
0
193 if (!BN_rshift1(a, a))
!BN_rshift1(a, a)Description
TRUEnever evaluated
FALSEnever evaluated
0
194 goto err;
never executed: goto err;
0
195 if (BN_cmp(a, b) < 0) {
BN_cmp(a, b) < 0Description
TRUEnever evaluated
FALSEnever evaluated
0
196 t = a;-
197 a = b;-
198 b = t;-
199 }
never executed: end of block
0
200 }
never executed: end of block
0
201 else /* a odd - b even */-
202 {-
203 if (!BN_rshift1(b, b))
!BN_rshift1(b, b)Description
TRUEnever evaluated
FALSEnever evaluated
0
204 goto err;
never executed: goto err;
0
205 if (BN_cmp(a, b) < 0) {
BN_cmp(a, b) < 0Description
TRUEnever evaluated
FALSEnever evaluated
0
206 t = a;-
207 a = b;-
208 b = t;-
209 }
never executed: end of block
0
210 }
never executed: end of block
0
211 }-
212 else /* a is even */-
213 {-
214 if (BN_is_odd(b)) {
((b)->top > 0)Description
TRUEnever evaluated
FALSEnever evaluated
((b)->d[0] & 1)Description
TRUEnever evaluated
FALSEnever evaluated
0
215 if (!BN_rshift1(a, a))
!BN_rshift1(a, a)Description
TRUEnever evaluated
FALSEnever evaluated
0
216 goto err;
never executed: goto err;
0
217 if (BN_cmp(a, b) < 0) {
BN_cmp(a, b) < 0Description
TRUEnever evaluated
FALSEnever evaluated
0
218 t = a;-
219 a = b;-
220 b = t;-
221 }
never executed: end of block
0
222 }
never executed: end of block
0
223 else /* a even - b even */-
224 {-
225 if (!BN_rshift1(a, a))
!BN_rshift1(a, a)Description
TRUEnever evaluated
FALSEnever evaluated
0
226 goto err;
never executed: goto err;
0
227 if (!BN_rshift1(b, b))
!BN_rshift1(b, b)Description
TRUEnever evaluated
FALSEnever evaluated
0
228 goto err;
never executed: goto err;
0
229 shifts++;-
230 }
never executed: end of block
0
231 }-
232 /* 0 <= b <= a */-
233 }-
234-
235 if (shifts) {
shiftsDescription
TRUEnever evaluated
FALSEnever evaluated
0
236 if (!BN_lshift(a, a, shifts))
!BN_lshift(a, a, shifts)Description
TRUEnever evaluated
FALSEnever evaluated
0
237 goto err;
never executed: goto err;
0
238 }
never executed: end of block
0
239 bn_check_top(a);-
240 return (a);
never executed: return (a);
0
241-
242err:-
243 return (NULL);
never executed: return ( ((void *)0) );
0
244}-
245-
246-
247/* solves ax == 1 (mod n) */-
248static BIGNUM *BN_mod_inverse_no_branch(BIGNUM *in, const BIGNUM *a,-
249 const BIGNUM *n, BN_CTX *ctx);-
250-
251static BIGNUM *-
252BN_mod_inverse_internal(BIGNUM *in, const BIGNUM *a, const BIGNUM *n, BN_CTX *ctx,-
253 int ct)-
254{-
255 BIGNUM *A, *B, *X, *Y, *M, *D, *T, *R = NULL;-
256 BIGNUM *ret = NULL;-
257 int sign;-
258-
259 if (ct)
ctDescription
TRUEevaluated 4086 times by 14 tests
Evaluated by:
  • bntest
  • dhtest
  • dsatest
  • ecdhtest
  • ecdsatest
  • ectest
  • exptest
  • libcrypto.so.44.0.1
  • mont
  • pkcs7test
  • rsa_test
  • servertest
  • ssltest
  • tlstest
FALSEnever evaluated
0-4086
260 return BN_mod_inverse_no_branch(in, a, n, ctx);
executed 4086 times by 14 tests: return BN_mod_inverse_no_branch(in, a, n, ctx);
Executed by:
  • bntest
  • dhtest
  • dsatest
  • ecdhtest
  • ecdsatest
  • ectest
  • exptest
  • libcrypto.so.44.0.1
  • mont
  • pkcs7test
  • rsa_test
  • servertest
  • ssltest
  • tlstest
4086
261-
262 bn_check_top(a);-
263 bn_check_top(n);-
264-
265 BN_CTX_start(ctx);-
266 if ((A = BN_CTX_get(ctx)) == NULL)
(A = BN_CTX_ge...== ((void *)0)Description
TRUEnever evaluated
FALSEnever evaluated
0
267 goto err;
never executed: goto err;
0
268 if ((B = BN_CTX_get(ctx)) == NULL)
(B = BN_CTX_ge...== ((void *)0)Description
TRUEnever evaluated
FALSEnever evaluated
0
269 goto err;
never executed: goto err;
0
270 if ((X = BN_CTX_get(ctx)) == NULL)
(X = BN_CTX_ge...== ((void *)0)Description
TRUEnever evaluated
FALSEnever evaluated
0
271 goto err;
never executed: goto err;
0
272 if ((D = BN_CTX_get(ctx)) == NULL)
(D = BN_CTX_ge...== ((void *)0)Description
TRUEnever evaluated
FALSEnever evaluated
0
273 goto err;
never executed: goto err;
0
274 if ((M = BN_CTX_get(ctx)) == NULL)
(M = BN_CTX_ge...== ((void *)0)Description
TRUEnever evaluated
FALSEnever evaluated
0
275 goto err;
never executed: goto err;
0
276 if ((Y = BN_CTX_get(ctx)) == NULL)
(Y = BN_CTX_ge...== ((void *)0)Description
TRUEnever evaluated
FALSEnever evaluated
0
277 goto err;
never executed: goto err;
0
278 if ((T = BN_CTX_get(ctx)) == NULL)
(T = BN_CTX_ge...== ((void *)0)Description
TRUEnever evaluated
FALSEnever evaluated
0
279 goto err;
never executed: goto err;
0
280-
281 if (in == NULL)
in == ((void *)0)Description
TRUEnever evaluated
FALSEnever evaluated
0
282 R = BN_new();
never executed: R = BN_new();
0
283 else-
284 R = in;
never executed: R = in;
0
285 if (R == NULL)
R == ((void *)0)Description
TRUEnever evaluated
FALSEnever evaluated
0
286 goto err;
never executed: goto err;
0
287-
288 BN_one(X);-
289 BN_zero(Y);-
290 if (BN_copy(B, a) == NULL)
BN_copy(B, a) == ((void *)0)Description
TRUEnever evaluated
FALSEnever evaluated
0
291 goto err;
never executed: goto err;
0
292 if (BN_copy(A, n) == NULL)
BN_copy(A, n) == ((void *)0)Description
TRUEnever evaluated
FALSEnever evaluated
0
293 goto err;
never executed: goto err;
0
294 A->neg = 0;-
295 if (B->neg || (BN_ucmp(B, A) >= 0)) {
B->negDescription
TRUEnever evaluated
FALSEnever evaluated
(BN_ucmp(B, A) >= 0)Description
TRUEnever evaluated
FALSEnever evaluated
0
296 if (!BN_nnmod(B, B, A, ctx))
!BN_nnmod(B, B, A, ctx)Description
TRUEnever evaluated
FALSEnever evaluated
0
297 goto err;
never executed: goto err;
0
298 }
never executed: end of block
0
299 sign = -1;-
300 /* From B = a mod |n|, A = |n| it follows that-
301 *-
302 * 0 <= B < A,-
303 * -sign*X*a == B (mod |n|),-
304 * sign*Y*a == A (mod |n|).-
305 */-
306-
307 if (BN_is_odd(n) && (BN_num_bits(n) <= (BN_BITS <= 32 ? 450 : 2048))) {
128 <= 32Description
TRUEnever evaluated
FALSEnever evaluated
((n)->top > 0)Description
TRUEnever evaluated
FALSEnever evaluated
((n)->d[0] & 1)Description
TRUEnever evaluated
FALSEnever evaluated
(BN_num_bits(n...? 450 : 2048))Description
TRUEnever evaluated
FALSEnever evaluated
0
308 /* Binary inversion algorithm; requires odd modulus.-
309 * This is faster than the general algorithm if the modulus-
310 * is sufficiently small (about 400 .. 500 bits on 32-bit-
311 * sytems, but much more on 64-bit systems) */-
312 int shift;-
313-
314 while (!BN_is_zero(B)) {
!((B)->top == 0)Description
TRUEnever evaluated
FALSEnever evaluated
0
315 /*-
316 * 0 < B < |n|,-
317 * 0 < A <= |n|,-
318 * (1) -sign*X*a == B (mod |n|),-
319 * (2) sign*Y*a == A (mod |n|)-
320 */-
321-
322 /* Now divide B by the maximum possible power of two in the integers,-
323 * and divide X by the same value mod |n|.-
324 * When we're done, (1) still holds. */-
325 shift = 0;-
326 while (!BN_is_bit_set(B, shift)) /* note that 0 < B */
!BN_is_bit_set(B, shift)Description
TRUEnever evaluated
FALSEnever evaluated
0
327 {-
328 shift++;-
329-
330 if (BN_is_odd(X)) {
((X)->top > 0)Description
TRUEnever evaluated
FALSEnever evaluated
((X)->d[0] & 1)Description
TRUEnever evaluated
FALSEnever evaluated
0
331 if (!BN_uadd(X, X, n))
!BN_uadd(X, X, n)Description
TRUEnever evaluated
FALSEnever evaluated
0
332 goto err;
never executed: goto err;
0
333 }
never executed: end of block
0
334 /* now X is even, so we can easily divide it by two */-
335 if (!BN_rshift1(X, X))
!BN_rshift1(X, X)Description
TRUEnever evaluated
FALSEnever evaluated
0
336 goto err;
never executed: goto err;
0
337 }
never executed: end of block
0
338 if (shift > 0) {
shift > 0Description
TRUEnever evaluated
FALSEnever evaluated
0
339 if (!BN_rshift(B, B, shift))
!BN_rshift(B, B, shift)Description
TRUEnever evaluated
FALSEnever evaluated
0
340 goto err;
never executed: goto err;
0
341 }
never executed: end of block
0
342-
343-
344 /* Same for A and Y. Afterwards, (2) still holds. */-
345 shift = 0;-
346 while (!BN_is_bit_set(A, shift)) /* note that 0 < A */
!BN_is_bit_set(A, shift)Description
TRUEnever evaluated
FALSEnever evaluated
0
347 {-
348 shift++;-
349-
350 if (BN_is_odd(Y)) {
((Y)->top > 0)Description
TRUEnever evaluated
FALSEnever evaluated
((Y)->d[0] & 1)Description
TRUEnever evaluated
FALSEnever evaluated
0
351 if (!BN_uadd(Y, Y, n))
!BN_uadd(Y, Y, n)Description
TRUEnever evaluated
FALSEnever evaluated
0
352 goto err;
never executed: goto err;
0
353 }
never executed: end of block
0
354 /* now Y is even */-
355 if (!BN_rshift1(Y, Y))
!BN_rshift1(Y, Y)Description
TRUEnever evaluated
FALSEnever evaluated
0
356 goto err;
never executed: goto err;
0
357 }
never executed: end of block
0
358 if (shift > 0) {
shift > 0Description
TRUEnever evaluated
FALSEnever evaluated
0
359 if (!BN_rshift(A, A, shift))
!BN_rshift(A, A, shift)Description
TRUEnever evaluated
FALSEnever evaluated
0
360 goto err;
never executed: goto err;
0
361 }
never executed: end of block
0
362-
363-
364 /* We still have (1) and (2).-
365 * Both A and B are odd.-
366 * The following computations ensure that-
367 *-
368 * 0 <= B < |n|,-
369 * 0 < A < |n|,-
370 * (1) -sign*X*a == B (mod |n|),-
371 * (2) sign*Y*a == A (mod |n|),-
372 *-
373 * and that either A or B is even in the next iteration.-
374 */-
375 if (BN_ucmp(B, A) >= 0) {
BN_ucmp(B, A) >= 0Description
TRUEnever evaluated
FALSEnever evaluated
0
376 /* -sign*(X + Y)*a == B - A (mod |n|) */-
377 if (!BN_uadd(X, X, Y))
!BN_uadd(X, X, Y)Description
TRUEnever evaluated
FALSEnever evaluated
0
378 goto err;
never executed: goto err;
0
379 /* NB: we could use BN_mod_add_quick(X, X, Y, n), but that-
380 * actually makes the algorithm slower */-
381 if (!BN_usub(B, B, A))
!BN_usub(B, B, A)Description
TRUEnever evaluated
FALSEnever evaluated
0
382 goto err;
never executed: goto err;
0
383 } else {
never executed: end of block
0
384 /* sign*(X + Y)*a == A - B (mod |n|) */-
385 if (!BN_uadd(Y, Y, X))
!BN_uadd(Y, Y, X)Description
TRUEnever evaluated
FALSEnever evaluated
0
386 goto err;
never executed: goto err;
0
387 /* as above, BN_mod_add_quick(Y, Y, X, n) would slow things down */-
388 if (!BN_usub(A, A, B))
!BN_usub(A, A, B)Description
TRUEnever evaluated
FALSEnever evaluated
0
389 goto err;
never executed: goto err;
0
390 }
never executed: end of block
0
391 }-
392 } else {
never executed: end of block
0
393 /* general inversion algorithm */-
394-
395 while (!BN_is_zero(B)) {
!((B)->top == 0)Description
TRUEnever evaluated
FALSEnever evaluated
0
396 BIGNUM *tmp;-
397-
398 /*-
399 * 0 < B < A,-
400 * (*) -sign*X*a == B (mod |n|),-
401 * sign*Y*a == A (mod |n|)-
402 */-
403-
404 /* (D, M) := (A/B, A%B) ... */-
405 if (BN_num_bits(A) == BN_num_bits(B)) {
BN_num_bits(A)...BN_num_bits(B)Description
TRUEnever evaluated
FALSEnever evaluated
0
406 if (!BN_one(D))
!(BN_set_word((D),1))Description
TRUEnever evaluated
FALSEnever evaluated
0
407 goto err;
never executed: goto err;
0
408 if (!BN_sub(M, A, B))
!BN_sub(M, A, B)Description
TRUEnever evaluated
FALSEnever evaluated
0
409 goto err;
never executed: goto err;
0
410 } else if (BN_num_bits(A) == BN_num_bits(B) + 1) {
never executed: end of block
BN_num_bits(A)...um_bits(B) + 1Description
TRUEnever evaluated
FALSEnever evaluated
0
411 /* A/B is 1, 2, or 3 */-
412 if (!BN_lshift1(T, B))
!BN_lshift1(T, B)Description
TRUEnever evaluated
FALSEnever evaluated
0
413 goto err;
never executed: goto err;
0
414 if (BN_ucmp(A, T) < 0) {
BN_ucmp(A, T) < 0Description
TRUEnever evaluated
FALSEnever evaluated
0
415 /* A < 2*B, so D=1 */-
416 if (!BN_one(D))
!(BN_set_word((D),1))Description
TRUEnever evaluated
FALSEnever evaluated
0
417 goto err;
never executed: goto err;
0
418 if (!BN_sub(M, A, B))
!BN_sub(M, A, B)Description
TRUEnever evaluated
FALSEnever evaluated
0
419 goto err;
never executed: goto err;
0
420 } else {
never executed: end of block
0
421 /* A >= 2*B, so D=2 or D=3 */-
422 if (!BN_sub(M, A, T))
!BN_sub(M, A, T)Description
TRUEnever evaluated
FALSEnever evaluated
0
423 goto err;
never executed: goto err;
0
424 if (!BN_add(D,T,B)) goto err; /* use D (:= 3*B) as temp */
never executed: goto err;
!BN_add(D,T,B)Description
TRUEnever evaluated
FALSEnever evaluated
0
425 if (BN_ucmp(A, D) < 0) {
BN_ucmp(A, D) < 0Description
TRUEnever evaluated
FALSEnever evaluated
0
426 /* A < 3*B, so D=2 */-
427 if (!BN_set_word(D, 2))
!BN_set_word(D, 2)Description
TRUEnever evaluated
FALSEnever evaluated
0
428 goto err;
never executed: goto err;
0
429 /* M (= A - 2*B) already has the correct value */-
430 } else {
never executed: end of block
0
431 /* only D=3 remains */-
432 if (!BN_set_word(D, 3))
!BN_set_word(D, 3)Description
TRUEnever evaluated
FALSEnever evaluated
0
433 goto err;
never executed: goto err;
0
434 /* currently M = A - 2*B, but we need M = A - 3*B */-
435 if (!BN_sub(M, M, B))
!BN_sub(M, M, B)Description
TRUEnever evaluated
FALSEnever evaluated
0
436 goto err;
never executed: goto err;
0
437 }
never executed: end of block
0
438 }-
439 } else {-
440 if (!BN_div_nonct(D, M, A, B, ctx))
!BN_div_nonct(D, M, A, B, ctx)Description
TRUEnever evaluated
FALSEnever evaluated
0
441 goto err;
never executed: goto err;
0
442 }
never executed: end of block
0
443-
444 /* Now-
445 * A = D*B + M;-
446 * thus we have-
447 * (**) sign*Y*a == D*B + M (mod |n|).-
448 */-
449 tmp = A; /* keep the BIGNUM object, the value does not matter */-
450-
451 /* (A, B) := (B, A mod B) ... */-
452 A = B;-
453 B = M;-
454 /* ... so we have 0 <= B < A again */-
455-
456 /* Since the former M is now B and the former B is now A,-
457 * (**) translates into-
458 * sign*Y*a == D*A + B (mod |n|),-
459 * i.e.-
460 * sign*Y*a - D*A == B (mod |n|).-
461 * Similarly, (*) translates into-
462 * -sign*X*a == A (mod |n|).-
463 *-
464 * Thus,-
465 * sign*Y*a + D*sign*X*a == B (mod |n|),-
466 * i.e.-
467 * sign*(Y + D*X)*a == B (mod |n|).-
468 *-
469 * So if we set (X, Y, sign) := (Y + D*X, X, -sign), we arrive back at-
470 * -sign*X*a == B (mod |n|),-
471 * sign*Y*a == A (mod |n|).-
472 * Note that X and Y stay non-negative all the time.-
473 */-
474-
475 /* most of the time D is very small, so we can optimize tmp := D*X+Y */-
476 if (BN_is_one(D)) {
(((D))->top == 1)Description
TRUEnever evaluated
FALSEnever evaluated
(((D))->d[0] =...gned long)(1))Description
TRUEnever evaluated
FALSEnever evaluated
((1) == 0)Description
TRUEnever evaluated
FALSEnever evaluated
(((D))->top == 0)Description
TRUEnever evaluated
FALSEnever evaluated
!(D)->negDescription
TRUEnever evaluated
FALSEnever evaluated
0
477 if (!BN_add(tmp, X, Y))
!BN_add(tmp, X, Y)Description
TRUEnever evaluated
FALSEnever evaluated
0
478 goto err;
never executed: goto err;
0
479 } else {
never executed: end of block
0
480 if (BN_is_word(D, 2)) {
(((D))->top == 1)Description
TRUEnever evaluated
FALSEnever evaluated
(((D))->d[0] =...ed long)((2)))Description
TRUEnever evaluated
FALSEnever evaluated
(((2)) == 0)Description
TRUEnever evaluated
FALSEnever evaluated
(((D))->top == 0)Description
TRUEnever evaluated
FALSEnever evaluated
!(D)->negDescription
TRUEnever evaluated
FALSEnever evaluated
0
481 if (!BN_lshift1(tmp, X))
!BN_lshift1(tmp, X)Description
TRUEnever evaluated
FALSEnever evaluated
0
482 goto err;
never executed: goto err;
0
483 } else if (BN_is_word(D, 4)) {
never executed: end of block
(((D))->top == 1)Description
TRUEnever evaluated
FALSEnever evaluated
(((D))->d[0] =...ed long)((4)))Description
TRUEnever evaluated
FALSEnever evaluated
(((4)) == 0)Description
TRUEnever evaluated
FALSEnever evaluated
(((D))->top == 0)Description
TRUEnever evaluated
FALSEnever evaluated
!(D)->negDescription
TRUEnever evaluated
FALSEnever evaluated
0
484 if (!BN_lshift(tmp, X, 2))
!BN_lshift(tmp, X, 2)Description
TRUEnever evaluated
FALSEnever evaluated
0
485 goto err;
never executed: goto err;
0
486 } else if (D->top == 1) {
never executed: end of block
D->top == 1Description
TRUEnever evaluated
FALSEnever evaluated
0
487 if (!BN_copy(tmp, X))
!BN_copy(tmp, X)Description
TRUEnever evaluated
FALSEnever evaluated
0
488 goto err;
never executed: goto err;
0
489 if (!BN_mul_word(tmp, D->d[0]))
!BN_mul_word(tmp, D->d[0])Description
TRUEnever evaluated
FALSEnever evaluated
0
490 goto err;
never executed: goto err;
0
491 } else {
never executed: end of block
0
492 if (!BN_mul(tmp, D,X, ctx))
!BN_mul(tmp, D,X, ctx)Description
TRUEnever evaluated
FALSEnever evaluated
0
493 goto err;
never executed: goto err;
0
494 }
never executed: end of block
0
495 if (!BN_add(tmp, tmp, Y))
!BN_add(tmp, tmp, Y)Description
TRUEnever evaluated
FALSEnever evaluated
0
496 goto err;
never executed: goto err;
0
497 }
never executed: end of block
0
498-
499 M = Y; /* keep the BIGNUM object, the value does not matter */-
500 Y = X;-
501 X = tmp;-
502 sign = -sign;-
503 }
never executed: end of block
0
504 }
never executed: end of block
0
505-
506 /*-
507 * The while loop (Euclid's algorithm) ends when-
508 * A == gcd(a,n);-
509 * we have-
510 * sign*Y*a == A (mod |n|),-
511 * where Y is non-negative.-
512 */-
513-
514 if (sign < 0) {
sign < 0Description
TRUEnever evaluated
FALSEnever evaluated
0
515 if (!BN_sub(Y, n, Y))
!BN_sub(Y, n, Y)Description
TRUEnever evaluated
FALSEnever evaluated
0
516 goto err;
never executed: goto err;
0
517 }
never executed: end of block
0
518 /* Now Y*a == A (mod |n|). */-
519-
520 if (BN_is_one(A)) {
(((A))->top == 1)Description
TRUEnever evaluated
FALSEnever evaluated
(((A))->d[0] =...gned long)(1))Description
TRUEnever evaluated
FALSEnever evaluated
((1) == 0)Description
TRUEnever evaluated
FALSEnever evaluated
(((A))->top == 0)Description
TRUEnever evaluated
FALSEnever evaluated
!(A)->negDescription
TRUEnever evaluated
FALSEnever evaluated
0
521 /* Y*a == 1 (mod |n|) */-
522 if (!Y->neg && BN_ucmp(Y, n) < 0) {
!Y->negDescription
TRUEnever evaluated
FALSEnever evaluated
BN_ucmp(Y, n) < 0Description
TRUEnever evaluated
FALSEnever evaluated
0
523 if (!BN_copy(R, Y))
!BN_copy(R, Y)Description
TRUEnever evaluated
FALSEnever evaluated
0
524 goto err;
never executed: goto err;
0
525 } else {
never executed: end of block
0
526 if (!BN_nnmod(R, Y,n, ctx))
!BN_nnmod(R, Y,n, ctx)Description
TRUEnever evaluated
FALSEnever evaluated
0
527 goto err;
never executed: goto err;
0
528 }
never executed: end of block
0
529 } else {-
530 BNerror(BN_R_NO_INVERSE);-
531 goto err;
never executed: goto err;
0
532 }-
533 ret = R;-
534-
535err:
code before this statement never executed: err:
0
536 if ((ret == NULL) && (in == NULL))
(ret == ((void *)0) )Description
TRUEnever evaluated
FALSEnever evaluated
(in == ((void *)0) )Description
TRUEnever evaluated
FALSEnever evaluated
0
537 BN_free(R);
never executed: BN_free(R);
0
538 BN_CTX_end(ctx);-
539 bn_check_top(ret);-
540 return (ret);
never executed: return (ret);
0
541}-
542-
543BIGNUM *-
544BN_mod_inverse(BIGNUM *in, const BIGNUM *a, const BIGNUM *n, BN_CTX *ctx)-
545{-
546 int ct = ((BN_get_flags(a, BN_FLG_CONSTTIME) != 0) ||
(((a)->flags&(0x04)) != 0)Description
TRUEnever evaluated
FALSEnever evaluated
0
547 (BN_get_flags(n, BN_FLG_CONSTTIME) != 0));
(((n)->flags&(0x04)) != 0)Description
TRUEnever evaluated
FALSEnever evaluated
0
548 return BN_mod_inverse_internal(in, a, n, ctx, ct);
never executed: return BN_mod_inverse_internal(in, a, n, ctx, ct);
0
549}-
550-
551BIGNUM *-
552BN_mod_inverse_nonct(BIGNUM *in, const BIGNUM *a, const BIGNUM *n, BN_CTX *ctx)-
553{-
554 return BN_mod_inverse_internal(in, a, n, ctx, 0);
never executed: return BN_mod_inverse_internal(in, a, n, ctx, 0);
0
555}-
556-
557BIGNUM *-
558BN_mod_inverse_ct(BIGNUM *in, const BIGNUM *a, const BIGNUM *n, BN_CTX *ctx)-
559{-
560 return BN_mod_inverse_internal(in, a, n, ctx, 1);
executed 4086 times by 14 tests: return BN_mod_inverse_internal(in, a, n, ctx, 1);
Executed by:
  • bntest
  • dhtest
  • dsatest
  • ecdhtest
  • ecdsatest
  • ectest
  • exptest
  • libcrypto.so.44.0.1
  • mont
  • pkcs7test
  • rsa_test
  • servertest
  • ssltest
  • tlstest
4086
561}-
562-
563/* BN_mod_inverse_no_branch is a special version of BN_mod_inverse.-
564 * It does not contain branches that may leak sensitive information.-
565 */-
566static BIGNUM *-
567BN_mod_inverse_no_branch(BIGNUM *in, const BIGNUM *a, const BIGNUM *n,-
568 BN_CTX *ctx)-
569{-
570 BIGNUM *A, *B, *X, *Y, *M, *D, *T, *R = NULL;-
571 BIGNUM local_A, local_B;-
572 BIGNUM *pA, *pB;-
573 BIGNUM *ret = NULL;-
574 int sign;-
575-
576 bn_check_top(a);-
577 bn_check_top(n);-
578-
579 BN_CTX_start(ctx);-
580 if ((A = BN_CTX_get(ctx)) == NULL)
(A = BN_CTX_ge...== ((void *)0)Description
TRUEnever evaluated
FALSEevaluated 4086 times by 14 tests
Evaluated by:
  • bntest
  • dhtest
  • dsatest
  • ecdhtest
  • ecdsatest
  • ectest
  • exptest
  • libcrypto.so.44.0.1
  • mont
  • pkcs7test
  • rsa_test
  • servertest
  • ssltest
  • tlstest
0-4086
581 goto err;
never executed: goto err;
0
582 if ((B = BN_CTX_get(ctx)) == NULL)
(B = BN_CTX_ge...== ((void *)0)Description
TRUEnever evaluated
FALSEevaluated 4086 times by 14 tests
Evaluated by:
  • bntest
  • dhtest
  • dsatest
  • ecdhtest
  • ecdsatest
  • ectest
  • exptest
  • libcrypto.so.44.0.1
  • mont
  • pkcs7test
  • rsa_test
  • servertest
  • ssltest
  • tlstest
0-4086
583 goto err;
never executed: goto err;
0
584 if ((X = BN_CTX_get(ctx)) == NULL)
(X = BN_CTX_ge...== ((void *)0)Description
TRUEnever evaluated
FALSEevaluated 4086 times by 14 tests
Evaluated by:
  • bntest
  • dhtest
  • dsatest
  • ecdhtest
  • ecdsatest
  • ectest
  • exptest
  • libcrypto.so.44.0.1
  • mont
  • pkcs7test
  • rsa_test
  • servertest
  • ssltest
  • tlstest
0-4086
585 goto err;
never executed: goto err;
0
586 if ((D = BN_CTX_get(ctx)) == NULL)
(D = BN_CTX_ge...== ((void *)0)Description
TRUEnever evaluated
FALSEevaluated 4086 times by 14 tests
Evaluated by:
  • bntest
  • dhtest
  • dsatest
  • ecdhtest
  • ecdsatest
  • ectest
  • exptest
  • libcrypto.so.44.0.1
  • mont
  • pkcs7test
  • rsa_test
  • servertest
  • ssltest
  • tlstest
0-4086
587 goto err;
never executed: goto err;
0
588 if ((M = BN_CTX_get(ctx)) == NULL)
(M = BN_CTX_ge...== ((void *)0)Description
TRUEnever evaluated
FALSEevaluated 4086 times by 14 tests
Evaluated by:
  • bntest
  • dhtest
  • dsatest
  • ecdhtest
  • ecdsatest
  • ectest
  • exptest
  • libcrypto.so.44.0.1
  • mont
  • pkcs7test
  • rsa_test
  • servertest
  • ssltest
  • tlstest
0-4086
589 goto err;
never executed: goto err;
0
590 if ((Y = BN_CTX_get(ctx)) == NULL)
(Y = BN_CTX_ge...== ((void *)0)Description
TRUEnever evaluated
FALSEevaluated 4086 times by 14 tests
Evaluated by:
  • bntest
  • dhtest
  • dsatest
  • ecdhtest
  • ecdsatest
  • ectest
  • exptest
  • libcrypto.so.44.0.1
  • mont
  • pkcs7test
  • rsa_test
  • servertest
  • ssltest
  • tlstest
0-4086
591 goto err;
never executed: goto err;
0
592 if ((T = BN_CTX_get(ctx)) == NULL)
(T = BN_CTX_ge...== ((void *)0)Description
TRUEnever evaluated
FALSEevaluated 4086 times by 14 tests
Evaluated by:
  • bntest
  • dhtest
  • dsatest
  • ecdhtest
  • ecdsatest
  • ectest
  • exptest
  • libcrypto.so.44.0.1
  • mont
  • pkcs7test
  • rsa_test
  • servertest
  • ssltest
  • tlstest
0-4086
593 goto err;
never executed: goto err;
0
594-
595 if (in == NULL)
in == ((void *)0)Description
TRUEevaluated 2 times by 2 tests
Evaluated by:
  • dsatest
  • libcrypto.so.44.0.1
FALSEevaluated 4084 times by 14 tests
Evaluated by:
  • bntest
  • dhtest
  • dsatest
  • ecdhtest
  • ecdsatest
  • ectest
  • exptest
  • libcrypto.so.44.0.1
  • mont
  • pkcs7test
  • rsa_test
  • servertest
  • ssltest
  • tlstest
2-4084
596 R = BN_new();
executed 2 times by 2 tests: R = BN_new();
Executed by:
  • dsatest
  • libcrypto.so.44.0.1
2
597 else-
598 R = in;
executed 4084 times by 14 tests: R = in;
Executed by:
  • bntest
  • dhtest
  • dsatest
  • ecdhtest
  • ecdsatest
  • ectest
  • exptest
  • libcrypto.so.44.0.1
  • mont
  • pkcs7test
  • rsa_test
  • servertest
  • ssltest
  • tlstest
4084
599 if (R == NULL)
R == ((void *)0)Description
TRUEnever evaluated
FALSEevaluated 4086 times by 14 tests
Evaluated by:
  • bntest
  • dhtest
  • dsatest
  • ecdhtest
  • ecdsatest
  • ectest
  • exptest
  • libcrypto.so.44.0.1
  • mont
  • pkcs7test
  • rsa_test
  • servertest
  • ssltest
  • tlstest
0-4086
600 goto err;
never executed: goto err;
0
601-
602 BN_one(X);-
603 BN_zero(Y);-
604 if (BN_copy(B, a) == NULL)
BN_copy(B, a) == ((void *)0)Description
TRUEnever evaluated
FALSEevaluated 4086 times by 14 tests
Evaluated by:
  • bntest
  • dhtest
  • dsatest
  • ecdhtest
  • ecdsatest
  • ectest
  • exptest
  • libcrypto.so.44.0.1
  • mont
  • pkcs7test
  • rsa_test
  • servertest
  • ssltest
  • tlstest
0-4086
605 goto err;
never executed: goto err;
0
606 if (BN_copy(A, n) == NULL)
BN_copy(A, n) == ((void *)0)Description
TRUEnever evaluated
FALSEevaluated 4086 times by 14 tests
Evaluated by:
  • bntest
  • dhtest
  • dsatest
  • ecdhtest
  • ecdsatest
  • ectest
  • exptest
  • libcrypto.so.44.0.1
  • mont
  • pkcs7test
  • rsa_test
  • servertest
  • ssltest
  • tlstest
0-4086
607 goto err;
never executed: goto err;
0
608 A->neg = 0;-
609-
610 if (B->neg || (BN_ucmp(B, A) >= 0)) {
B->negDescription
TRUEnever evaluated
FALSEevaluated 4086 times by 14 tests
Evaluated by:
  • bntest
  • dhtest
  • dsatest
  • ecdhtest
  • ecdsatest
  • ectest
  • exptest
  • libcrypto.so.44.0.1
  • mont
  • pkcs7test
  • rsa_test
  • servertest
  • ssltest
  • tlstest
(BN_ucmp(B, A) >= 0)Description
TRUEevaluated 2959 times by 14 tests
Evaluated by:
  • bntest
  • dhtest
  • dsatest
  • ecdhtest
  • ecdsatest
  • ectest
  • exptest
  • libcrypto.so.44.0.1
  • mont
  • pkcs7test
  • rsa_test
  • servertest
  • ssltest
  • tlstest
FALSEevaluated 1127 times by 10 tests
Evaluated by:
  • dsatest
  • ecdhtest
  • ecdsatest
  • ectest
  • libcrypto.so.44.0.1
  • pkcs7test
  • rsa_test
  • servertest
  • ssltest
  • tlstest
0-4086
611 /* Turn BN_FLG_CONSTTIME flag on, so that when BN_div is invoked,-
612 * BN_div_no_branch will be called eventually.-
613 */-
614 pB = &local_B;-
615 BN_with_flags(pB, B, BN_FLG_CONSTTIME);-
616 if (!BN_nnmod(B, pB, A, ctx))
!BN_nnmod(B, pB, A, ctx)Description
TRUEevaluated 1 time by 1 test
Evaluated by:
  • bntest
FALSEevaluated 2958 times by 14 tests
Evaluated by:
  • bntest
  • dhtest
  • dsatest
  • ecdhtest
  • ecdsatest
  • ectest
  • exptest
  • libcrypto.so.44.0.1
  • mont
  • pkcs7test
  • rsa_test
  • servertest
  • ssltest
  • tlstest
1-2958
617 goto err;
executed 1 time by 1 test: goto err;
Executed by:
  • bntest
1
618 }
executed 2958 times by 14 tests: end of block
Executed by:
  • bntest
  • dhtest
  • dsatest
  • ecdhtest
  • ecdsatest
  • ectest
  • exptest
  • libcrypto.so.44.0.1
  • mont
  • pkcs7test
  • rsa_test
  • servertest
  • ssltest
  • tlstest
2958
619 sign = -1;-
620 /* From B = a mod |n|, A = |n| it follows that-
621 *-
622 * 0 <= B < A,-
623 * -sign*X*a == B (mod |n|),-
624 * sign*Y*a == A (mod |n|).-
625 */-
626-
627 while (!BN_is_zero(B)) {
!((B)->top == 0)Description
TRUEevaluated 334754 times by 14 tests
Evaluated by:
  • bntest
  • dhtest
  • dsatest
  • ecdhtest
  • ecdsatest
  • ectest
  • exptest
  • libcrypto.so.44.0.1
  • mont
  • pkcs7test
  • rsa_test
  • servertest
  • ssltest
  • tlstest
FALSEevaluated 4085 times by 14 tests
Evaluated by:
  • bntest
  • dhtest
  • dsatest
  • ecdhtest
  • ecdsatest
  • ectest
  • exptest
  • libcrypto.so.44.0.1
  • mont
  • pkcs7test
  • rsa_test
  • servertest
  • ssltest
  • tlstest
4085-334754
628 BIGNUM *tmp;-
629-
630 /*-
631 * 0 < B < A,-
632 * (*) -sign*X*a == B (mod |n|),-
633 * sign*Y*a == A (mod |n|)-
634 */-
635-
636 /* Turn BN_FLG_CONSTTIME flag on, so that when BN_div is invoked,-
637 * BN_div_no_branch will be called eventually.-
638 */-
639 pA = &local_A;-
640 BN_with_flags(pA, A, BN_FLG_CONSTTIME);-
641-
642 /* (D, M) := (A/B, A%B) ... */-
643 if (!BN_div_ct(D, M, pA, B, ctx))
!BN_div_ct(D, M, pA, B, ctx)Description
TRUEnever evaluated
FALSEevaluated 334754 times by 14 tests
Evaluated by:
  • bntest
  • dhtest
  • dsatest
  • ecdhtest
  • ecdsatest
  • ectest
  • exptest
  • libcrypto.so.44.0.1
  • mont
  • pkcs7test
  • rsa_test
  • servertest
  • ssltest
  • tlstest
0-334754
644 goto err;
never executed: goto err;
0
645-
646 /* Now-
647 * A = D*B + M;-
648 * thus we have-
649 * (**) sign*Y*a == D*B + M (mod |n|).-
650 */-
651 tmp = A; /* keep the BIGNUM object, the value does not matter */-
652-
653 /* (A, B) := (B, A mod B) ... */-
654 A = B;-
655 B = M;-
656 /* ... so we have 0 <= B < A again */-
657-
658 /* Since the former M is now B and the former B is now A,-
659 * (**) translates into-
660 * sign*Y*a == D*A + B (mod |n|),-
661 * i.e.-
662 * sign*Y*a - D*A == B (mod |n|).-
663 * Similarly, (*) translates into-
664 * -sign*X*a == A (mod |n|).-
665 *-
666 * Thus,-
667 * sign*Y*a + D*sign*X*a == B (mod |n|),-
668 * i.e.-
669 * sign*(Y + D*X)*a == B (mod |n|).-
670 *-
671 * So if we set (X, Y, sign) := (Y + D*X, X, -sign), we arrive back at-
672 * -sign*X*a == B (mod |n|),-
673 * sign*Y*a == A (mod |n|).-
674 * Note that X and Y stay non-negative all the time.-
675 */-
676-
677 if (!BN_mul(tmp, D, X, ctx))
!BN_mul(tmp, D, X, ctx)Description
TRUEnever evaluated
FALSEevaluated 334754 times by 14 tests
Evaluated by:
  • bntest
  • dhtest
  • dsatest
  • ecdhtest
  • ecdsatest
  • ectest
  • exptest
  • libcrypto.so.44.0.1
  • mont
  • pkcs7test
  • rsa_test
  • servertest
  • ssltest
  • tlstest
0-334754
678 goto err;
never executed: goto err;
0
679 if (!BN_add(tmp, tmp, Y))
!BN_add(tmp, tmp, Y)Description
TRUEnever evaluated
FALSEevaluated 334754 times by 14 tests
Evaluated by:
  • bntest
  • dhtest
  • dsatest
  • ecdhtest
  • ecdsatest
  • ectest
  • exptest
  • libcrypto.so.44.0.1
  • mont
  • pkcs7test
  • rsa_test
  • servertest
  • ssltest
  • tlstest
0-334754
680 goto err;
never executed: goto err;
0
681-
682 M = Y; /* keep the BIGNUM object, the value does not matter */-
683 Y = X;-
684 X = tmp;-
685 sign = -sign;-
686 }
executed 334754 times by 14 tests: end of block
Executed by:
  • bntest
  • dhtest
  • dsatest
  • ecdhtest
  • ecdsatest
  • ectest
  • exptest
  • libcrypto.so.44.0.1
  • mont
  • pkcs7test
  • rsa_test
  • servertest
  • ssltest
  • tlstest
334754
687-
688 /*-
689 * The while loop (Euclid's algorithm) ends when-
690 * A == gcd(a,n);-
691 * we have-
692 * sign*Y*a == A (mod |n|),-
693 * where Y is non-negative.-
694 */-
695-
696 if (sign < 0) {
sign < 0Description
TRUEevaluated 1935 times by 14 tests
Evaluated by:
  • bntest
  • dhtest
  • dsatest
  • ecdhtest
  • ecdsatest
  • ectest
  • exptest
  • libcrypto.so.44.0.1
  • mont
  • pkcs7test
  • rsa_test
  • servertest
  • ssltest
  • tlstest
FALSEevaluated 2150 times by 14 tests
Evaluated by:
  • bntest
  • dhtest
  • dsatest
  • ecdhtest
  • ecdsatest
  • ectest
  • exptest
  • libcrypto.so.44.0.1
  • mont
  • pkcs7test
  • rsa_test
  • servertest
  • ssltest
  • tlstest
1935-2150
697 if (!BN_sub(Y, n, Y))
!BN_sub(Y, n, Y)Description
TRUEnever evaluated
FALSEevaluated 1935 times by 14 tests
Evaluated by:
  • bntest
  • dhtest
  • dsatest
  • ecdhtest
  • ecdsatest
  • ectest
  • exptest
  • libcrypto.so.44.0.1
  • mont
  • pkcs7test
  • rsa_test
  • servertest
  • ssltest
  • tlstest
0-1935
698 goto err;
never executed: goto err;
0
699 }
executed 1935 times by 14 tests: end of block
Executed by:
  • bntest
  • dhtest
  • dsatest
  • ecdhtest
  • ecdsatest
  • ectest
  • exptest
  • libcrypto.so.44.0.1
  • mont
  • pkcs7test
  • rsa_test
  • servertest
  • ssltest
  • tlstest
1935
700 /* Now Y*a == A (mod |n|). */-
701-
702 if (BN_is_one(A)) {
(((A))->top == 1)Description
TRUEevaluated 4085 times by 14 tests
Evaluated by:
  • bntest
  • dhtest
  • dsatest
  • ecdhtest
  • ecdsatest
  • ectest
  • exptest
  • libcrypto.so.44.0.1
  • mont
  • pkcs7test
  • rsa_test
  • servertest
  • ssltest
  • tlstest
FALSEnever evaluated
(((A))->d[0] =...gned long)(1))Description
TRUEevaluated 4084 times by 14 tests
Evaluated by:
  • bntest
  • dhtest
  • dsatest
  • ecdhtest
  • ecdsatest
  • ectest
  • exptest
  • libcrypto.so.44.0.1
  • mont
  • pkcs7test
  • rsa_test
  • servertest
  • ssltest
  • tlstest
FALSEevaluated 1 time by 1 test
Evaluated by:
  • bntest
((1) == 0)Description
TRUEnever evaluated
FALSEevaluated 1 time by 1 test
Evaluated by:
  • bntest
(((A))->top == 0)Description
TRUEnever evaluated
FALSEnever evaluated
!(A)->negDescription
TRUEevaluated 4084 times by 14 tests
Evaluated by:
  • bntest
  • dhtest
  • dsatest
  • ecdhtest
  • ecdsatest
  • ectest
  • exptest
  • libcrypto.so.44.0.1
  • mont
  • pkcs7test
  • rsa_test
  • servertest
  • ssltest
  • tlstest
FALSEnever evaluated
0-4085
703 /* Y*a == 1 (mod |n|) */-
704 if (!Y->neg && BN_ucmp(Y, n) < 0) {
!Y->negDescription
TRUEevaluated 4084 times by 14 tests
Evaluated by:
  • bntest
  • dhtest
  • dsatest
  • ecdhtest
  • ecdsatest
  • ectest
  • exptest
  • libcrypto.so.44.0.1
  • mont
  • pkcs7test
  • rsa_test
  • servertest
  • ssltest
  • tlstest
FALSEnever evaluated
BN_ucmp(Y, n) < 0Description
TRUEevaluated 4072 times by 14 tests
Evaluated by:
  • bntest
  • dhtest
  • dsatest
  • ecdhtest
  • ecdsatest
  • ectest
  • exptest
  • libcrypto.so.44.0.1
  • mont
  • pkcs7test
  • rsa_test
  • servertest
  • ssltest
  • tlstest
FALSEevaluated 12 times by 3 tests
Evaluated by:
  • ecdhtest
  • ecdsatest
  • ectest
0-4084
705 if (!BN_copy(R, Y))
!BN_copy(R, Y)Description
TRUEnever evaluated
FALSEevaluated 4072 times by 14 tests
Evaluated by:
  • bntest
  • dhtest
  • dsatest
  • ecdhtest
  • ecdsatest
  • ectest
  • exptest
  • libcrypto.so.44.0.1
  • mont
  • pkcs7test
  • rsa_test
  • servertest
  • ssltest
  • tlstest
0-4072
706 goto err;
never executed: goto err;
0
707 } else {
executed 4072 times by 14 tests: end of block
Executed by:
  • bntest
  • dhtest
  • dsatest
  • ecdhtest
  • ecdsatest
  • ectest
  • exptest
  • libcrypto.so.44.0.1
  • mont
  • pkcs7test
  • rsa_test
  • servertest
  • ssltest
  • tlstest
4072
708 if (!BN_nnmod(R, Y, n, ctx))
!BN_nnmod(R, Y, n, ctx)Description
TRUEnever evaluated
FALSEevaluated 12 times by 3 tests
Evaluated by:
  • ecdhtest
  • ecdsatest
  • ectest
0-12
709 goto err;
never executed: goto err;
0
710 }
executed 12 times by 3 tests: end of block
Executed by:
  • ecdhtest
  • ecdsatest
  • ectest
12
711 } else {-
712 BNerror(BN_R_NO_INVERSE);-
713 goto err;
executed 1 time by 1 test: goto err;
Executed by:
  • bntest
1
714 }-
715 ret = R;-
716-
717err:
code before this statement executed 4084 times by 14 tests: err:
Executed by:
  • bntest
  • dhtest
  • dsatest
  • ecdhtest
  • ecdsatest
  • ectest
  • exptest
  • libcrypto.so.44.0.1
  • mont
  • pkcs7test
  • rsa_test
  • servertest
  • ssltest
  • tlstest
4084
718 if ((ret == NULL) && (in == NULL))
(ret == ((void *)0) )Description
TRUEevaluated 2 times by 1 test
Evaluated by:
  • bntest
FALSEevaluated 4084 times by 14 tests
Evaluated by:
  • bntest
  • dhtest
  • dsatest
  • ecdhtest
  • ecdsatest
  • ectest
  • exptest
  • libcrypto.so.44.0.1
  • mont
  • pkcs7test
  • rsa_test
  • servertest
  • ssltest
  • tlstest
(in == ((void *)0) )Description
TRUEnever evaluated
FALSEevaluated 2 times by 1 test
Evaluated by:
  • bntest
0-4084
719 BN_free(R);
never executed: BN_free(R);
0
720 BN_CTX_end(ctx);-
721 bn_check_top(ret);-
722 return (ret);
executed 4086 times by 14 tests: return (ret);
Executed by:
  • bntest
  • dhtest
  • dsatest
  • ecdhtest
  • ecdsatest
  • ectest
  • exptest
  • libcrypto.so.44.0.1
  • mont
  • pkcs7test
  • rsa_test
  • servertest
  • ssltest
  • tlstest
4086
723}-
724-
725/*-
726 * BN_gcd_no_branch is a special version of BN_mod_inverse_no_branch.-
727 * that returns the GCD.-
728 */-
729static BIGNUM *-
730BN_gcd_no_branch(BIGNUM *in, const BIGNUM *a, const BIGNUM *n,-
731 BN_CTX *ctx)-
732{-
733 BIGNUM *A, *B, *X, *Y, *M, *D, *T, *R = NULL;-
734 BIGNUM local_A, local_B;-
735 BIGNUM *pA, *pB;-
736 BIGNUM *ret = NULL;-
737 int sign;-
738-
739 if (in == NULL)
in == ((void *)0)Description
TRUEnever evaluated
FALSEevaluated 2 times by 1 test
Evaluated by:
  • libcrypto.so.44.0.1
0-2
740 goto err;
never executed: goto err;
0
741 R = in;-
742-
743 bn_check_top(a);-
744 bn_check_top(n);-
745-
746 BN_CTX_start(ctx);-
747 if ((A = BN_CTX_get(ctx)) == NULL)
(A = BN_CTX_ge...== ((void *)0)Description
TRUEnever evaluated
FALSEevaluated 2 times by 1 test
Evaluated by:
  • libcrypto.so.44.0.1
0-2
748 goto err;
never executed: goto err;
0
749 if ((B = BN_CTX_get(ctx)) == NULL)
(B = BN_CTX_ge...== ((void *)0)Description
TRUEnever evaluated
FALSEevaluated 2 times by 1 test
Evaluated by:
  • libcrypto.so.44.0.1
0-2
750 goto err;
never executed: goto err;
0
751 if ((X = BN_CTX_get(ctx)) == NULL)
(X = BN_CTX_ge...== ((void *)0)Description
TRUEnever evaluated
FALSEevaluated 2 times by 1 test
Evaluated by:
  • libcrypto.so.44.0.1
0-2
752 goto err;
never executed: goto err;
0
753 if ((D = BN_CTX_get(ctx)) == NULL)
(D = BN_CTX_ge...== ((void *)0)Description
TRUEnever evaluated
FALSEevaluated 2 times by 1 test
Evaluated by:
  • libcrypto.so.44.0.1
0-2
754 goto err;
never executed: goto err;
0
755 if ((M = BN_CTX_get(ctx)) == NULL)
(M = BN_CTX_ge...== ((void *)0)Description
TRUEnever evaluated
FALSEevaluated 2 times by 1 test
Evaluated by:
  • libcrypto.so.44.0.1
0-2
756 goto err;
never executed: goto err;
0
757 if ((Y = BN_CTX_get(ctx)) == NULL)
(Y = BN_CTX_ge...== ((void *)0)Description
TRUEnever evaluated
FALSEevaluated 2 times by 1 test
Evaluated by:
  • libcrypto.so.44.0.1
0-2
758 goto err;
never executed: goto err;
0
759 if ((T = BN_CTX_get(ctx)) == NULL)
(T = BN_CTX_ge...== ((void *)0)Description
TRUEnever evaluated
FALSEevaluated 2 times by 1 test
Evaluated by:
  • libcrypto.so.44.0.1
0-2
760 goto err;
never executed: goto err;
0
761-
762 BN_one(X);-
763 BN_zero(Y);-
764 if (BN_copy(B, a) == NULL)
BN_copy(B, a) == ((void *)0)Description
TRUEnever evaluated
FALSEevaluated 2 times by 1 test
Evaluated by:
  • libcrypto.so.44.0.1
0-2
765 goto err;
never executed: goto err;
0
766 if (BN_copy(A, n) == NULL)
BN_copy(A, n) == ((void *)0)Description
TRUEnever evaluated
FALSEevaluated 2 times by 1 test
Evaluated by:
  • libcrypto.so.44.0.1
0-2
767 goto err;
never executed: goto err;
0
768 A->neg = 0;-
769-
770 if (B->neg || (BN_ucmp(B, A) >= 0)) {
B->negDescription
TRUEnever evaluated
FALSEevaluated 2 times by 1 test
Evaluated by:
  • libcrypto.so.44.0.1
(BN_ucmp(B, A) >= 0)Description
TRUEevaluated 2 times by 1 test
Evaluated by:
  • libcrypto.so.44.0.1
FALSEnever evaluated
0-2
771 /* Turn BN_FLG_CONSTTIME flag on, so that when BN_div is invoked,-
772 * BN_div_no_branch will be called eventually.-
773 */-
774 pB = &local_B;-
775 BN_with_flags(pB, B, BN_FLG_CONSTTIME);-
776 if (!BN_nnmod(B, pB, A, ctx))
!BN_nnmod(B, pB, A, ctx)Description
TRUEnever evaluated
FALSEevaluated 2 times by 1 test
Evaluated by:
  • libcrypto.so.44.0.1
0-2
777 goto err;
never executed: goto err;
0
778 }
executed 2 times by 1 test: end of block
Executed by:
  • libcrypto.so.44.0.1
2
779 sign = -1;-
780 /* From B = a mod |n|, A = |n| it follows that-
781 *-
782 * 0 <= B < A,-
783 * -sign*X*a == B (mod |n|),-
784 * sign*Y*a == A (mod |n|).-
785 */-
786-
787 while (!BN_is_zero(B)) {
!((B)->top == 0)Description
TRUEevaluated 19 times by 1 test
Evaluated by:
  • libcrypto.so.44.0.1
FALSEevaluated 2 times by 1 test
Evaluated by:
  • libcrypto.so.44.0.1
2-19
788 BIGNUM *tmp;-
789-
790 /*-
791 * 0 < B < A,-
792 * (*) -sign*X*a == B (mod |n|),-
793 * sign*Y*a == A (mod |n|)-
794 */-
795-
796 /* Turn BN_FLG_CONSTTIME flag on, so that when BN_div is invoked,-
797 * BN_div_no_branch will be called eventually.-
798 */-
799 pA = &local_A;-
800 BN_with_flags(pA, A, BN_FLG_CONSTTIME);-
801-
802 /* (D, M) := (A/B, A%B) ... */-
803 if (!BN_div_ct(D, M, pA, B, ctx))
!BN_div_ct(D, M, pA, B, ctx)Description
TRUEnever evaluated
FALSEevaluated 19 times by 1 test
Evaluated by:
  • libcrypto.so.44.0.1
0-19
804 goto err;
never executed: goto err;
0
805-
806 /* Now-
807 * A = D*B + M;-
808 * thus we have-
809 * (**) sign*Y*a == D*B + M (mod |n|).-
810 */-
811 tmp = A; /* keep the BIGNUM object, the value does not matter */-
812-
813 /* (A, B) := (B, A mod B) ... */-
814 A = B;-
815 B = M;-
816 /* ... so we have 0 <= B < A again */-
817-
818 /* Since the former M is now B and the former B is now A,-
819 * (**) translates into-
820 * sign*Y*a == D*A + B (mod |n|),-
821 * i.e.-
822 * sign*Y*a - D*A == B (mod |n|).-
823 * Similarly, (*) translates into-
824 * -sign*X*a == A (mod |n|).-
825 *-
826 * Thus,-
827 * sign*Y*a + D*sign*X*a == B (mod |n|),-
828 * i.e.-
829 * sign*(Y + D*X)*a == B (mod |n|).-
830 *-
831 * So if we set (X, Y, sign) := (Y + D*X, X, -sign), we arrive back at-
832 * -sign*X*a == B (mod |n|),-
833 * sign*Y*a == A (mod |n|).-
834 * Note that X and Y stay non-negative all the time.-
835 */-
836-
837 if (!BN_mul(tmp, D, X, ctx))
!BN_mul(tmp, D, X, ctx)Description
TRUEnever evaluated
FALSEevaluated 19 times by 1 test
Evaluated by:
  • libcrypto.so.44.0.1
0-19
838 goto err;
never executed: goto err;
0
839 if (!BN_add(tmp, tmp, Y))
!BN_add(tmp, tmp, Y)Description
TRUEnever evaluated
FALSEevaluated 19 times by 1 test
Evaluated by:
  • libcrypto.so.44.0.1
0-19
840 goto err;
never executed: goto err;
0
841-
842 M = Y; /* keep the BIGNUM object, the value does not matter */-
843 Y = X;-
844 X = tmp;-
845 sign = -sign;-
846 }
executed 19 times by 1 test: end of block
Executed by:
  • libcrypto.so.44.0.1
19
847-
848 /*-
849 * The while loop (Euclid's algorithm) ends when-
850 * A == gcd(a,n);-
851 */-
852-
853 if (!BN_copy(R, A))
!BN_copy(R, A)Description
TRUEnever evaluated
FALSEevaluated 2 times by 1 test
Evaluated by:
  • libcrypto.so.44.0.1
0-2
854 goto err;
never executed: goto err;
0
855 ret = R;-
856err:
code before this statement executed 2 times by 1 test: err:
Executed by:
  • libcrypto.so.44.0.1
2
857 if ((ret == NULL) && (in == NULL))
(ret == ((void *)0) )Description
TRUEnever evaluated
FALSEevaluated 2 times by 1 test
Evaluated by:
  • libcrypto.so.44.0.1
(in == ((void *)0) )Description
TRUEnever evaluated
FALSEnever evaluated
0-2
858 BN_free(R);
never executed: BN_free(R);
0
859 BN_CTX_end(ctx);-
860 bn_check_top(ret);-
861 return (ret);
executed 2 times by 1 test: return (ret);
Executed by:
  • libcrypto.so.44.0.1
2
862}-
Source codeSwitch to Preprocessed file
Generated by Squish Coco 4.2.2