| Absolute File Name: | /home/opencoverage/opencoverage/guest-scripts/openssl/src/crypto/bn/bn_gcd.c |
| Source code | Switch to Preprocessed file |
| Line | Source | Count | ||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 1 | /* | - | ||||||||||||
| 2 | * Copyright 1995-2018 The OpenSSL Project Authors. All Rights Reserved. | - | ||||||||||||
| 3 | * | - | ||||||||||||
| 4 | * Licensed under the OpenSSL license (the "License"). You may not use | - | ||||||||||||
| 5 | * this file except in compliance with the License. You can obtain a copy | - | ||||||||||||
| 6 | * in the file LICENSE in the source distribution or at | - | ||||||||||||
| 7 | * https://www.openssl.org/source/license.html | - | ||||||||||||
| 8 | */ | - | ||||||||||||
| 9 | - | |||||||||||||
| 10 | #include "internal/cryptlib.h" | - | ||||||||||||
| 11 | #include "bn_lcl.h" | - | ||||||||||||
| 12 | - | |||||||||||||
| 13 | static BIGNUM *euclid(BIGNUM *a, BIGNUM *b); | - | ||||||||||||
| 14 | - | |||||||||||||
| 15 | int BN_gcd(BIGNUM *r, const BIGNUM *in_a, const BIGNUM *in_b, BN_CTX *ctx) | - | ||||||||||||
| 16 | { | - | ||||||||||||
| 17 | BIGNUM *a, *b, *t; | - | ||||||||||||
| 18 | int ret = 0; | - | ||||||||||||
| 19 | - | |||||||||||||
| 20 | bn_check_top(in_a); | - | ||||||||||||
| 21 | bn_check_top(in_b); | - | ||||||||||||
| 22 | - | |||||||||||||
| 23 | BN_CTX_start(ctx); | - | ||||||||||||
| 24 | a = BN_CTX_get(ctx); | - | ||||||||||||
| 25 | b = BN_CTX_get(ctx); | - | ||||||||||||
| 26 | if (b == NULL)
| 0-25 | ||||||||||||
| 27 | goto err; never executed: goto err; | 0 | ||||||||||||
| 28 | - | |||||||||||||
| 29 | if (BN_copy(a, in_a) == NULL)
| 0-25 | ||||||||||||
| 30 | goto err; never executed: goto err; | 0 | ||||||||||||
| 31 | if (BN_copy(b, in_b) == NULL)
| 0-25 | ||||||||||||
| 32 | goto err; never executed: goto err; | 0 | ||||||||||||
| 33 | a->neg = 0; | - | ||||||||||||
| 34 | b->neg = 0; | - | ||||||||||||
| 35 | - | |||||||||||||
| 36 | if (BN_cmp(a, b) < 0) {
| 11-14 | ||||||||||||
| 37 | t = a; | - | ||||||||||||
| 38 | a = b; | - | ||||||||||||
| 39 | b = t; | - | ||||||||||||
| 40 | } executed 14 times by 1 test: end of blockExecuted by:
| 14 | ||||||||||||
| 41 | t = euclid(a, b); | - | ||||||||||||
| 42 | if (t == NULL)
| 0-25 | ||||||||||||
| 43 | goto err; never executed: goto err; | 0 | ||||||||||||
| 44 | - | |||||||||||||
| 45 | if (BN_copy(r, t) == NULL)
| 0-25 | ||||||||||||
| 46 | goto err; never executed: goto err; | 0 | ||||||||||||
| 47 | ret = 1; | - | ||||||||||||
| 48 | err: code before this statement executed 25 times by 1 test: err:Executed by:
| 25 | ||||||||||||
| 49 | BN_CTX_end(ctx); | - | ||||||||||||
| 50 | bn_check_top(r); | - | ||||||||||||
| 51 | return ret; executed 25 times by 1 test: return ret;Executed by:
| 25 | ||||||||||||
| 52 | } | - | ||||||||||||
| 53 | - | |||||||||||||
| 54 | static BIGNUM *euclid(BIGNUM *a, BIGNUM *b) | - | ||||||||||||
| 55 | { | - | ||||||||||||
| 56 | BIGNUM *t; | - | ||||||||||||
| 57 | int shifts = 0; | - | ||||||||||||
| 58 | - | |||||||||||||
| 59 | bn_check_top(a); | - | ||||||||||||
| 60 | bn_check_top(b); | - | ||||||||||||
| 61 | - | |||||||||||||
| 62 | /* 0 <= b <= a */ | - | ||||||||||||
| 63 | while (!BN_is_zero(b)) {
| 25-29254 | ||||||||||||
| 64 | /* 0 < b <= a */ | - | ||||||||||||
| 65 | - | |||||||||||||
| 66 | if (BN_is_odd(a)) {
| 11312-17942 | ||||||||||||
| 67 | if (BN_is_odd(b)) {
| 3370-14572 | ||||||||||||
| 68 | if (!BN_sub(a, a, b))
| 0-14572 | ||||||||||||
| 69 | goto err; never executed: goto err; | 0 | ||||||||||||
| 70 | if (!BN_rshift1(a, a))
| 0-14572 | ||||||||||||
| 71 | goto err; never executed: goto err; | 0 | ||||||||||||
| 72 | if (BN_cmp(a, b) < 0) {
| 2563-12009 | ||||||||||||
| 73 | t = a; | - | ||||||||||||
| 74 | a = b; | - | ||||||||||||
| 75 | b = t; | - | ||||||||||||
| 76 | } executed 2563 times by 1 test: end of blockExecuted by:
| 2563 | ||||||||||||
| 77 | } else { /* a odd - b even */ executed 14572 times by 1 test: end of blockExecuted by:
| 14572 | ||||||||||||
| 78 | - | |||||||||||||
| 79 | if (!BN_rshift1(b, b))
| 0-3370 | ||||||||||||
| 80 | goto err; never executed: goto err; | 0 | ||||||||||||
| 81 | if (BN_cmp(a, b) < 0) {
| 0-3370 | ||||||||||||
| 82 | t = a; | - | ||||||||||||
| 83 | a = b; | - | ||||||||||||
| 84 | b = t; | - | ||||||||||||
| 85 | } never executed: end of block | 0 | ||||||||||||
| 86 | } executed 3370 times by 1 test: end of blockExecuted by:
| 3370 | ||||||||||||
| 87 | } else { /* a is even */ | - | ||||||||||||
| 88 | - | |||||||||||||
| 89 | if (BN_is_odd(b)) {
| 29-11283 | ||||||||||||
| 90 | if (!BN_rshift1(a, a))
| 0-11283 | ||||||||||||
| 91 | goto err; never executed: goto err; | 0 | ||||||||||||
| 92 | if (BN_cmp(a, b) < 0) {
| 779-10504 | ||||||||||||
| 93 | t = a; | - | ||||||||||||
| 94 | a = b; | - | ||||||||||||
| 95 | b = t; | - | ||||||||||||
| 96 | } executed 779 times by 1 test: end of blockExecuted by:
| 779 | ||||||||||||
| 97 | } else { /* a even - b even */ executed 11283 times by 1 test: end of blockExecuted by:
| 11283 | ||||||||||||
| 98 | - | |||||||||||||
| 99 | if (!BN_rshift1(a, a))
| 0-29 | ||||||||||||
| 100 | goto err; never executed: goto err; | 0 | ||||||||||||
| 101 | if (!BN_rshift1(b, b))
| 0-29 | ||||||||||||
| 102 | goto err; never executed: goto err; | 0 | ||||||||||||
| 103 | shifts++; | - | ||||||||||||
| 104 | } executed 29 times by 1 test: end of blockExecuted by:
| 29 | ||||||||||||
| 105 | } | - | ||||||||||||
| 106 | /* 0 <= b <= a */ | - | ||||||||||||
| 107 | } | - | ||||||||||||
| 108 | - | |||||||||||||
| 109 | if (shifts) {
| 1-24 | ||||||||||||
| 110 | if (!BN_lshift(a, a, shifts))
| 0-24 | ||||||||||||
| 111 | goto err; never executed: goto err; | 0 | ||||||||||||
| 112 | } executed 24 times by 1 test: end of blockExecuted by:
| 24 | ||||||||||||
| 113 | bn_check_top(a); | - | ||||||||||||
| 114 | return a; executed 25 times by 1 test: return a;Executed by:
| 25 | ||||||||||||
| 115 | err: | - | ||||||||||||
| 116 | return NULL; never executed: return ((void *)0) ; | 0 | ||||||||||||
| 117 | } | - | ||||||||||||
| 118 | - | |||||||||||||
| 119 | /* solves ax == 1 (mod n) */ | - | ||||||||||||
| 120 | static BIGNUM *BN_mod_inverse_no_branch(BIGNUM *in, | - | ||||||||||||
| 121 | const BIGNUM *a, const BIGNUM *n, | - | ||||||||||||
| 122 | BN_CTX *ctx); | - | ||||||||||||
| 123 | - | |||||||||||||
| 124 | BIGNUM *BN_mod_inverse(BIGNUM *in, | - | ||||||||||||
| 125 | const BIGNUM *a, const BIGNUM *n, BN_CTX *ctx) | - | ||||||||||||
| 126 | { | - | ||||||||||||
| 127 | BIGNUM *rv; | - | ||||||||||||
| 128 | int noinv; | - | ||||||||||||
| 129 | rv = int_bn_mod_inverse(in, a, n, ctx, &noinv); | - | ||||||||||||
| 130 | if (noinv)
| 455-79056 | ||||||||||||
| 131 | BNerr(BN_F_BN_MOD_INVERSE, BN_R_NO_INVERSE); executed 455 times by 1 test: ERR_put_error(3,(110),(108),__FILE__,131);Executed by:
| 455 | ||||||||||||
| 132 | return rv; executed 79511 times by 2 tests: return rv;Executed by:
| 79511 | ||||||||||||
| 133 | } | - | ||||||||||||
| 134 | - | |||||||||||||
| 135 | BIGNUM *int_bn_mod_inverse(BIGNUM *in, | - | ||||||||||||
| 136 | const BIGNUM *a, const BIGNUM *n, BN_CTX *ctx, | - | ||||||||||||
| 137 | int *pnoinv) | - | ||||||||||||
| 138 | { | - | ||||||||||||
| 139 | BIGNUM *A, *B, *X, *Y, *M, *D, *T, *R = NULL; | - | ||||||||||||
| 140 | BIGNUM *ret = NULL; | - | ||||||||||||
| 141 | int sign; | - | ||||||||||||
| 142 | - | |||||||||||||
| 143 | /* This is invalid input so we don't worry about constant time here */ | - | ||||||||||||
| 144 | if (BN_abs_is_word(n, 1) || BN_is_zero(n)) {
| 0-81259 | ||||||||||||
| 145 | if (pnoinv != NULL)
| 0-39 | ||||||||||||
| 146 | *pnoinv = 1; executed 39 times by 1 test: *pnoinv = 1;Executed by:
| 39 | ||||||||||||
| 147 | return NULL; executed 39 times by 1 test: return ((void *)0) ;Executed by:
| 39 | ||||||||||||
| 148 | } | - | ||||||||||||
| 149 | - | |||||||||||||
| 150 | if (pnoinv != NULL)
| 0-81220 | ||||||||||||
| 151 | *pnoinv = 0; executed 81220 times by 2 tests: *pnoinv = 0;Executed by:
| 81220 | ||||||||||||
| 152 | - | |||||||||||||
| 153 | if ((BN_get_flags(a, BN_FLG_CONSTTIME) != 0)
| 211-81009 | ||||||||||||
| 154 | || (BN_get_flags(n, BN_FLG_CONSTTIME) != 0)) {
| 10315-70694 | ||||||||||||
| 155 | return BN_mod_inverse_no_branch(in, a, n, ctx); executed 10526 times by 1 test: return BN_mod_inverse_no_branch(in, a, n, ctx);Executed by:
| 10526 | ||||||||||||
| 156 | } | - | ||||||||||||
| 157 | - | |||||||||||||
| 158 | bn_check_top(a); | - | ||||||||||||
| 159 | bn_check_top(n); | - | ||||||||||||
| 160 | - | |||||||||||||
| 161 | BN_CTX_start(ctx); | - | ||||||||||||
| 162 | A = BN_CTX_get(ctx); | - | ||||||||||||
| 163 | B = BN_CTX_get(ctx); | - | ||||||||||||
| 164 | X = BN_CTX_get(ctx); | - | ||||||||||||
| 165 | D = BN_CTX_get(ctx); | - | ||||||||||||
| 166 | M = BN_CTX_get(ctx); | - | ||||||||||||
| 167 | Y = BN_CTX_get(ctx); | - | ||||||||||||
| 168 | T = BN_CTX_get(ctx); | - | ||||||||||||
| 169 | if (T == NULL)
| 0-70694 | ||||||||||||
| 170 | goto err; never executed: goto err; | 0 | ||||||||||||
| 171 | - | |||||||||||||
| 172 | if (in == NULL)
| 0-70694 | ||||||||||||
| 173 | R = BN_new(); never executed: R = BN_new(); | 0 | ||||||||||||
| 174 | else | - | ||||||||||||
| 175 | R = in; executed 70694 times by 2 tests: R = in;Executed by:
| 70694 | ||||||||||||
| 176 | if (R == NULL)
| 0-70694 | ||||||||||||
| 177 | goto err; never executed: goto err; | 0 | ||||||||||||
| 178 | - | |||||||||||||
| 179 | BN_one(X); | - | ||||||||||||
| 180 | BN_zero(Y); | - | ||||||||||||
| 181 | if (BN_copy(B, a) == NULL)
| 0-70694 | ||||||||||||
| 182 | goto err; never executed: goto err; | 0 | ||||||||||||
| 183 | if (BN_copy(A, n) == NULL)
| 0-70694 | ||||||||||||
| 184 | goto err; never executed: goto err; | 0 | ||||||||||||
| 185 | A->neg = 0; | - | ||||||||||||
| 186 | if (B->neg || (BN_ucmp(B, A) >= 0)) {
| 0-70694 | ||||||||||||
| 187 | if (!BN_nnmod(B, B, A, ctx))
| 0-68387 | ||||||||||||
| 188 | goto err; never executed: goto err; | 0 | ||||||||||||
| 189 | } executed 68387 times by 2 tests: end of blockExecuted by:
| 68387 | ||||||||||||
| 190 | sign = -1; | - | ||||||||||||
| 191 | /*- | - | ||||||||||||
| 192 | * From B = a mod |n|, A = |n| it follows that | - | ||||||||||||
| 193 | * | - | ||||||||||||
| 194 | * 0 <= B < A, | - | ||||||||||||
| 195 | * -sign*X*a == B (mod |n|), | - | ||||||||||||
| 196 | * sign*Y*a == A (mod |n|). | - | ||||||||||||
| 197 | */ | - | ||||||||||||
| 198 | - | |||||||||||||
| 199 | if (BN_is_odd(n) && (BN_num_bits(n) <= 2048)) {
| 0-70143 | ||||||||||||
| 200 | /* | - | ||||||||||||
| 201 | * Binary inversion algorithm; requires odd modulus. This is faster | - | ||||||||||||
| 202 | * than the general algorithm if the modulus is sufficiently small | - | ||||||||||||
| 203 | * (about 400 .. 500 bits on 32-bit systems, but much more on 64-bit | - | ||||||||||||
| 204 | * systems) | - | ||||||||||||
| 205 | */ | - | ||||||||||||
| 206 | int shift; | - | ||||||||||||
| 207 | - | |||||||||||||
| 208 | while (!BN_is_zero(B)) {
| 70143-4775524 | ||||||||||||
| 209 | /*- | - | ||||||||||||
| 210 | * 0 < B < |n|, | - | ||||||||||||
| 211 | * 0 < A <= |n|, | - | ||||||||||||
| 212 | * (1) -sign*X*a == B (mod |n|), | - | ||||||||||||
| 213 | * (2) sign*Y*a == A (mod |n|) | - | ||||||||||||
| 214 | */ | - | ||||||||||||
| 215 | - | |||||||||||||
| 216 | /* | - | ||||||||||||
| 217 | * Now divide B by the maximum possible power of two in the | - | ||||||||||||
| 218 | * integers, and divide X by the same value mod |n|. When we're | - | ||||||||||||
| 219 | * done, (1) still holds. | - | ||||||||||||
| 220 | */ | - | ||||||||||||
| 221 | shift = 0; | - | ||||||||||||
| 222 | while (!BN_is_bit_set(B, shift)) { /* note that 0 < B */
| 1833163-4775524 | ||||||||||||
| 223 | shift++; | - | ||||||||||||
| 224 | - | |||||||||||||
| 225 | if (BN_is_odd(X)) {
| 870111-963052 | ||||||||||||
| 226 | if (!BN_uadd(X, X, n))
| 0-870111 | ||||||||||||
| 227 | goto err; never executed: goto err; | 0 | ||||||||||||
| 228 | } executed 870111 times by 2 tests: end of blockExecuted by:
| 870111 | ||||||||||||
| 229 | /* | - | ||||||||||||
| 230 | * now X is even, so we can easily divide it by two | - | ||||||||||||
| 231 | */ | - | ||||||||||||
| 232 | if (!BN_rshift1(X, X))
| 0-1833163 | ||||||||||||
| 233 | goto err; never executed: goto err; | 0 | ||||||||||||
| 234 | } executed 1833163 times by 2 tests: end of blockExecuted by:
| 1833163 | ||||||||||||
| 235 | if (shift > 0) {
| 1554190-3221334 | ||||||||||||
| 236 | if (!BN_rshift(B, B, shift))
| 0-1554190 | ||||||||||||
| 237 | goto err; never executed: goto err; | 0 | ||||||||||||
| 238 | } executed 1554190 times by 2 tests: end of blockExecuted by:
| 1554190 | ||||||||||||
| 239 | - | |||||||||||||
| 240 | /* | - | ||||||||||||
| 241 | * Same for A and Y. Afterwards, (2) still holds. | - | ||||||||||||
| 242 | */ | - | ||||||||||||
| 243 | shift = 0; | - | ||||||||||||
| 244 | while (!BN_is_bit_set(A, shift)) { /* note that 0 < A */
| 3437183-4775524 | ||||||||||||
| 245 | shift++; | - | ||||||||||||
| 246 | - | |||||||||||||
| 247 | if (BN_is_odd(Y)) {
| 1096353-2340830 | ||||||||||||
| 248 | if (!BN_uadd(Y, Y, n))
| 0-2340830 | ||||||||||||
| 249 | goto err; never executed: goto err; | 0 | ||||||||||||
| 250 | } executed 2340830 times by 2 tests: end of blockExecuted by:
| 2340830 | ||||||||||||
| 251 | /* now Y is even */ | - | ||||||||||||
| 252 | if (!BN_rshift1(Y, Y))
| 0-3437183 | ||||||||||||
| 253 | goto err; never executed: goto err; | 0 | ||||||||||||
| 254 | } executed 3437183 times by 2 tests: end of blockExecuted by:
| 3437183 | ||||||||||||
| 255 | if (shift > 0) {
| 1613783-3161741 | ||||||||||||
| 256 | if (!BN_rshift(A, A, shift))
| 0-3161741 | ||||||||||||
| 257 | goto err; never executed: goto err; | 0 | ||||||||||||
| 258 | } executed 3161741 times by 2 tests: end of blockExecuted by:
| 3161741 | ||||||||||||
| 259 | - | |||||||||||||
| 260 | /*- | - | ||||||||||||
| 261 | * We still have (1) and (2). | - | ||||||||||||
| 262 | * Both A and B are odd. | - | ||||||||||||
| 263 | * The following computations ensure that | - | ||||||||||||
| 264 | * | - | ||||||||||||
| 265 | * 0 <= B < |n|, | - | ||||||||||||
| 266 | * 0 < A < |n|, | - | ||||||||||||
| 267 | * (1) -sign*X*a == B (mod |n|), | - | ||||||||||||
| 268 | * (2) sign*Y*a == A (mod |n|), | - | ||||||||||||
| 269 | * | - | ||||||||||||
| 270 | * and that either A or B is even in the next iteration. | - | ||||||||||||
| 271 | */ | - | ||||||||||||
| 272 | if (BN_ucmp(B, A) >= 0) {
| 1613783-3161741 | ||||||||||||
| 273 | /* -sign*(X + Y)*a == B - A (mod |n|) */ | - | ||||||||||||
| 274 | if (!BN_uadd(X, X, Y))
| 0-1613783 | ||||||||||||
| 275 | goto err; never executed: goto err; | 0 | ||||||||||||
| 276 | /* | - | ||||||||||||
| 277 | * NB: we could use BN_mod_add_quick(X, X, Y, n), but that | - | ||||||||||||
| 278 | * actually makes the algorithm slower | - | ||||||||||||
| 279 | */ | - | ||||||||||||
| 280 | if (!BN_usub(B, B, A))
| 0-1613783 | ||||||||||||
| 281 | goto err; never executed: goto err; | 0 | ||||||||||||
| 282 | } else { executed 1613783 times by 2 tests: end of blockExecuted by:
| 1613783 | ||||||||||||
| 283 | /* sign*(X + Y)*a == A - B (mod |n|) */ | - | ||||||||||||
| 284 | if (!BN_uadd(Y, Y, X))
| 0-3161741 | ||||||||||||
| 285 | goto err; never executed: goto err; | 0 | ||||||||||||
| 286 | /* | - | ||||||||||||
| 287 | * as above, BN_mod_add_quick(Y, Y, X, n) would slow things down | - | ||||||||||||
| 288 | */ | - | ||||||||||||
| 289 | if (!BN_usub(A, A, B))
| 0-3161741 | ||||||||||||
| 290 | goto err; never executed: goto err; | 0 | ||||||||||||
| 291 | } executed 3161741 times by 2 tests: end of blockExecuted by:
| 3161741 | ||||||||||||
| 292 | } | - | ||||||||||||
| 293 | } else { executed 70143 times by 2 tests: end of blockExecuted by:
| 70143 | ||||||||||||
| 294 | /* general inversion algorithm */ | - | ||||||||||||
| 295 | - | |||||||||||||
| 296 | while (!BN_is_zero(B)) {
| 551-23007 | ||||||||||||
| 297 | BIGNUM *tmp; | - | ||||||||||||
| 298 | - | |||||||||||||
| 299 | /*- | - | ||||||||||||
| 300 | * 0 < B < A, | - | ||||||||||||
| 301 | * (*) -sign*X*a == B (mod |n|), | - | ||||||||||||
| 302 | * sign*Y*a == A (mod |n|) | - | ||||||||||||
| 303 | */ | - | ||||||||||||
| 304 | - | |||||||||||||
| 305 | /* (D, M) := (A/B, A%B) ... */ | - | ||||||||||||
| 306 | if (BN_num_bits(A) == BN_num_bits(B)) {
| 4676-18331 | ||||||||||||
| 307 | if (!BN_one(D))
| 0-4676 | ||||||||||||
| 308 | goto err; never executed: goto err; | 0 | ||||||||||||
| 309 | if (!BN_sub(M, A, B))
| 0-4676 | ||||||||||||
| 310 | goto err; never executed: goto err; | 0 | ||||||||||||
| 311 | } else if (BN_num_bits(A) == BN_num_bits(B) + 1) { executed 4676 times by 1 test: end of blockExecuted by:
| 4676-9861 | ||||||||||||
| 312 | /* A/B is 1, 2, or 3 */ | - | ||||||||||||
| 313 | if (!BN_lshift1(T, B))
| 0-8470 | ||||||||||||
| 314 | goto err; never executed: goto err; | 0 | ||||||||||||
| 315 | if (BN_ucmp(A, T) < 0) {
| 3710-4760 | ||||||||||||
| 316 | /* A < 2*B, so D=1 */ | - | ||||||||||||
| 317 | if (!BN_one(D))
| 0-4760 | ||||||||||||
| 318 | goto err; never executed: goto err; | 0 | ||||||||||||
| 319 | if (!BN_sub(M, A, B))
| 0-4760 | ||||||||||||
| 320 | goto err; never executed: goto err; | 0 | ||||||||||||
| 321 | } else { executed 4760 times by 1 test: end of blockExecuted by:
| 4760 | ||||||||||||
| 322 | /* A >= 2*B, so D=2 or D=3 */ | - | ||||||||||||
| 323 | if (!BN_sub(M, A, T))
| 0-3710 | ||||||||||||
| 324 | goto err; never executed: goto err; | 0 | ||||||||||||
| 325 | if (!BN_add(D, T, B))
| 0-3710 | ||||||||||||
| 326 | goto err; /* use D (:= 3*B) as temp */ never executed: goto err; | 0 | ||||||||||||
| 327 | if (BN_ucmp(A, D) < 0) {
| 632-3078 | ||||||||||||
| 328 | /* A < 3*B, so D=2 */ | - | ||||||||||||
| 329 | if (!BN_set_word(D, 2))
| 0-3078 | ||||||||||||
| 330 | goto err; never executed: goto err; | 0 | ||||||||||||
| 331 | /* | - | ||||||||||||
| 332 | * M (= A - 2*B) already has the correct value | - | ||||||||||||
| 333 | */ | - | ||||||||||||
| 334 | } else { executed 3078 times by 1 test: end of blockExecuted by:
| 3078 | ||||||||||||
| 335 | /* only D=3 remains */ | - | ||||||||||||
| 336 | if (!BN_set_word(D, 3))
| 0-632 | ||||||||||||
| 337 | goto err; never executed: goto err; | 0 | ||||||||||||
| 338 | /* | - | ||||||||||||
| 339 | * currently M = A - 2*B, but we need M = A - 3*B | - | ||||||||||||
| 340 | */ | - | ||||||||||||
| 341 | if (!BN_sub(M, M, B))
| 0-632 | ||||||||||||
| 342 | goto err; never executed: goto err; | 0 | ||||||||||||
| 343 | } executed 632 times by 1 test: end of blockExecuted by:
| 632 | ||||||||||||
| 344 | } | - | ||||||||||||
| 345 | } else { | - | ||||||||||||
| 346 | if (!BN_div(D, M, A, B, ctx))
| 0-9861 | ||||||||||||
| 347 | goto err; never executed: goto err; | 0 | ||||||||||||
| 348 | } executed 9861 times by 1 test: end of blockExecuted by:
| 9861 | ||||||||||||
| 349 | - | |||||||||||||
| 350 | /*- | - | ||||||||||||
| 351 | * Now | - | ||||||||||||
| 352 | * A = D*B + M; | - | ||||||||||||
| 353 | * thus we have | - | ||||||||||||
| 354 | * (**) sign*Y*a == D*B + M (mod |n|). | - | ||||||||||||
| 355 | */ | - | ||||||||||||
| 356 | - | |||||||||||||
| 357 | tmp = A; /* keep the BIGNUM object, the value does not matter */ | - | ||||||||||||
| 358 | - | |||||||||||||
| 359 | /* (A, B) := (B, A mod B) ... */ | - | ||||||||||||
| 360 | A = B; | - | ||||||||||||
| 361 | B = M; | - | ||||||||||||
| 362 | /* ... so we have 0 <= B < A again */ | - | ||||||||||||
| 363 | - | |||||||||||||
| 364 | /*- | - | ||||||||||||
| 365 | * Since the former M is now B and the former B is now A, | - | ||||||||||||
| 366 | * (**) translates into | - | ||||||||||||
| 367 | * sign*Y*a == D*A + B (mod |n|), | - | ||||||||||||
| 368 | * i.e. | - | ||||||||||||
| 369 | * sign*Y*a - D*A == B (mod |n|). | - | ||||||||||||
| 370 | * Similarly, (*) translates into | - | ||||||||||||
| 371 | * -sign*X*a == A (mod |n|). | - | ||||||||||||
| 372 | * | - | ||||||||||||
| 373 | * Thus, | - | ||||||||||||
| 374 | * sign*Y*a + D*sign*X*a == B (mod |n|), | - | ||||||||||||
| 375 | * i.e. | - | ||||||||||||
| 376 | * sign*(Y + D*X)*a == B (mod |n|). | - | ||||||||||||
| 377 | * | - | ||||||||||||
| 378 | * So if we set (X, Y, sign) := (Y + D*X, X, -sign), we arrive back at | - | ||||||||||||
| 379 | * -sign*X*a == B (mod |n|), | - | ||||||||||||
| 380 | * sign*Y*a == A (mod |n|). | - | ||||||||||||
| 381 | * Note that X and Y stay non-negative all the time. | - | ||||||||||||
| 382 | */ | - | ||||||||||||
| 383 | - | |||||||||||||
| 384 | /* | - | ||||||||||||
| 385 | * most of the time D is very small, so we can optimize tmp := D*X+Y | - | ||||||||||||
| 386 | */ | - | ||||||||||||
| 387 | if (BN_is_one(D)) {
| 9436-13571 | ||||||||||||
| 388 | if (!BN_add(tmp, X, Y))
| 0-9436 | ||||||||||||
| 389 | goto err; never executed: goto err; | 0 | ||||||||||||
| 390 | } else { executed 9436 times by 1 test: end of blockExecuted by:
| 9436 | ||||||||||||
| 391 | if (BN_is_word(D, 2)) {
| 4135-9436 | ||||||||||||
| 392 | if (!BN_lshift1(tmp, X))
| 0-4135 | ||||||||||||
| 393 | goto err; never executed: goto err; | 0 | ||||||||||||
| 394 | } else if (BN_is_word(D, 4)) { executed 4135 times by 1 test: end of blockExecuted by:
| 1560-7876 | ||||||||||||
| 395 | if (!BN_lshift(tmp, X, 2))
| 0-1560 | ||||||||||||
| 396 | goto err; never executed: goto err; | 0 | ||||||||||||
| 397 | } else if (D->top == 1) { executed 1560 times by 1 test: end of blockExecuted by:
| 6-7870 | ||||||||||||
| 398 | if (!BN_copy(tmp, X))
| 0-7870 | ||||||||||||
| 399 | goto err; never executed: goto err; | 0 | ||||||||||||
| 400 | if (!BN_mul_word(tmp, D->d[0]))
| 0-7870 | ||||||||||||
| 401 | goto err; never executed: goto err; | 0 | ||||||||||||
| 402 | } else { executed 7870 times by 1 test: end of blockExecuted by:
| 7870 | ||||||||||||
| 403 | if (!BN_mul(tmp, D, X, ctx))
| 0-6 | ||||||||||||
| 404 | goto err; never executed: goto err; | 0 | ||||||||||||
| 405 | } executed 6 times by 1 test: end of blockExecuted by:
| 6 | ||||||||||||
| 406 | if (!BN_add(tmp, tmp, Y))
| 0-13571 | ||||||||||||
| 407 | goto err; never executed: goto err; | 0 | ||||||||||||
| 408 | } executed 13571 times by 1 test: end of blockExecuted by:
| 13571 | ||||||||||||
| 409 | - | |||||||||||||
| 410 | M = Y; /* keep the BIGNUM object, the value does not matter */ | - | ||||||||||||
| 411 | Y = X; | - | ||||||||||||
| 412 | X = tmp; | - | ||||||||||||
| 413 | sign = -sign; | - | ||||||||||||
| 414 | } executed 23007 times by 1 test: end of blockExecuted by:
| 23007 | ||||||||||||
| 415 | } executed 551 times by 1 test: end of blockExecuted by:
| 551 | ||||||||||||
| 416 | - | |||||||||||||
| 417 | /*- | - | ||||||||||||
| 418 | * The while loop (Euclid's algorithm) ends when | - | ||||||||||||
| 419 | * A == gcd(a,n); | - | ||||||||||||
| 420 | * we have | - | ||||||||||||
| 421 | * sign*Y*a == A (mod |n|), | - | ||||||||||||
| 422 | * where Y is non-negative. | - | ||||||||||||
| 423 | */ | - | ||||||||||||
| 424 | - | |||||||||||||
| 425 | if (sign < 0) {
| 169-70525 | ||||||||||||
| 426 | if (!BN_sub(Y, n, Y))
| 0-70525 | ||||||||||||
| 427 | goto err; never executed: goto err; | 0 | ||||||||||||
| 428 | } executed 70525 times by 2 tests: end of blockExecuted by:
| 70525 | ||||||||||||
| 429 | /* Now Y*a == A (mod |n|). */ | - | ||||||||||||
| 430 | - | |||||||||||||
| 431 | if (BN_is_one(A)) {
| 416-70278 | ||||||||||||
| 432 | /* Y*a == 1 (mod |n|) */ | - | ||||||||||||
| 433 | if (!Y->neg && BN_ucmp(Y, n) < 0) {
| 0-45337 | ||||||||||||
| 434 | if (!BN_copy(R, Y))
| 0-24941 | ||||||||||||
| 435 | goto err; never executed: goto err; | 0 | ||||||||||||
| 436 | } else { executed 24941 times by 2 tests: end of blockExecuted by:
| 24941 | ||||||||||||
| 437 | if (!BN_nnmod(R, Y, n, ctx))
| 0-45337 | ||||||||||||
| 438 | goto err; never executed: goto err; | 0 | ||||||||||||
| 439 | } executed 45337 times by 2 tests: end of blockExecuted by:
| 45337 | ||||||||||||
| 440 | } else { | - | ||||||||||||
| 441 | if (pnoinv)
| 0-416 | ||||||||||||
| 442 | *pnoinv = 1; executed 416 times by 1 test: *pnoinv = 1;Executed by:
| 416 | ||||||||||||
| 443 | goto err; executed 416 times by 1 test: goto err;Executed by:
| 416 | ||||||||||||
| 444 | } | - | ||||||||||||
| 445 | ret = R; | - | ||||||||||||
| 446 | err: code before this statement executed 70278 times by 2 tests: err:Executed by:
| 70278 | ||||||||||||
| 447 | if ((ret == NULL) && (in == NULL))
| 0-70278 | ||||||||||||
| 448 | BN_free(R); never executed: BN_free(R); | 0 | ||||||||||||
| 449 | BN_CTX_end(ctx); | - | ||||||||||||
| 450 | bn_check_top(ret); | - | ||||||||||||
| 451 | return ret; executed 70694 times by 2 tests: return ret;Executed by:
| 70694 | ||||||||||||
| 452 | } | - | ||||||||||||
| 453 | - | |||||||||||||
| 454 | /* | - | ||||||||||||
| 455 | * BN_mod_inverse_no_branch is a special version of BN_mod_inverse. It does | - | ||||||||||||
| 456 | * not contain branches that may leak sensitive information. | - | ||||||||||||
| 457 | */ | - | ||||||||||||
| 458 | static BIGNUM *BN_mod_inverse_no_branch(BIGNUM *in, | - | ||||||||||||
| 459 | const BIGNUM *a, const BIGNUM *n, | - | ||||||||||||
| 460 | BN_CTX *ctx) | - | ||||||||||||
| 461 | { | - | ||||||||||||
| 462 | BIGNUM *A, *B, *X, *Y, *M, *D, *T, *R = NULL; | - | ||||||||||||
| 463 | BIGNUM *ret = NULL; | - | ||||||||||||
| 464 | int sign; | - | ||||||||||||
| 465 | - | |||||||||||||
| 466 | bn_check_top(a); | - | ||||||||||||
| 467 | bn_check_top(n); | - | ||||||||||||
| 468 | - | |||||||||||||
| 469 | BN_CTX_start(ctx); | - | ||||||||||||
| 470 | A = BN_CTX_get(ctx); | - | ||||||||||||
| 471 | B = BN_CTX_get(ctx); | - | ||||||||||||
| 472 | X = BN_CTX_get(ctx); | - | ||||||||||||
| 473 | D = BN_CTX_get(ctx); | - | ||||||||||||
| 474 | M = BN_CTX_get(ctx); | - | ||||||||||||
| 475 | Y = BN_CTX_get(ctx); | - | ||||||||||||
| 476 | T = BN_CTX_get(ctx); | - | ||||||||||||
| 477 | if (T == NULL)
| 0-10526 | ||||||||||||
| 478 | goto err; never executed: goto err; | 0 | ||||||||||||
| 479 | - | |||||||||||||
| 480 | if (in == NULL)
| 64-10462 | ||||||||||||
| 481 | R = BN_new(); executed 64 times by 1 test: R = BN_new();Executed by:
| 64 | ||||||||||||
| 482 | else | - | ||||||||||||
| 483 | R = in; executed 10462 times by 1 test: R = in;Executed by:
| 10462 | ||||||||||||
| 484 | if (R == NULL)
| 0-10526 | ||||||||||||
| 485 | goto err; never executed: goto err; | 0 | ||||||||||||
| 486 | - | |||||||||||||
| 487 | BN_one(X); | - | ||||||||||||
| 488 | BN_zero(Y); | - | ||||||||||||
| 489 | if (BN_copy(B, a) == NULL)
| 0-10526 | ||||||||||||
| 490 | goto err; never executed: goto err; | 0 | ||||||||||||
| 491 | if (BN_copy(A, n) == NULL)
| 0-10526 | ||||||||||||
| 492 | goto err; never executed: goto err; | 0 | ||||||||||||
| 493 | A->neg = 0; | - | ||||||||||||
| 494 | - | |||||||||||||
| 495 | if (B->neg || (BN_ucmp(B, A) >= 0)) {
| 0-10526 | ||||||||||||
| 496 | /* | - | ||||||||||||
| 497 | * Turn BN_FLG_CONSTTIME flag on, so that when BN_div is invoked, | - | ||||||||||||
| 498 | * BN_div_no_branch will be called eventually. | - | ||||||||||||
| 499 | */ | - | ||||||||||||
| 500 | { | - | ||||||||||||
| 501 | BIGNUM local_B; | - | ||||||||||||
| 502 | bn_init(&local_B); | - | ||||||||||||
| 503 | BN_with_flags(&local_B, B, BN_FLG_CONSTTIME); | - | ||||||||||||
| 504 | if (!BN_nnmod(B, &local_B, A, ctx))
| 0-8676 | ||||||||||||
| 505 | goto err; never executed: goto err; | 0 | ||||||||||||
| 506 | /* Ensure local_B goes out of scope before any further use of B */ | - | ||||||||||||
| 507 | } | - | ||||||||||||
| 508 | } executed 8676 times by 1 test: end of blockExecuted by:
| 8676 | ||||||||||||
| 509 | sign = -1; | - | ||||||||||||
| 510 | /*- | - | ||||||||||||
| 511 | * From B = a mod |n|, A = |n| it follows that | - | ||||||||||||
| 512 | * | - | ||||||||||||
| 513 | * 0 <= B < A, | - | ||||||||||||
| 514 | * -sign*X*a == B (mod |n|), | - | ||||||||||||
| 515 | * sign*Y*a == A (mod |n|). | - | ||||||||||||
| 516 | */ | - | ||||||||||||
| 517 | - | |||||||||||||
| 518 | while (!BN_is_zero(B)) {
| 10526-2412196 | ||||||||||||
| 519 | BIGNUM *tmp; | - | ||||||||||||
| 520 | - | |||||||||||||
| 521 | /*- | - | ||||||||||||
| 522 | * 0 < B < A, | - | ||||||||||||
| 523 | * (*) -sign*X*a == B (mod |n|), | - | ||||||||||||
| 524 | * sign*Y*a == A (mod |n|) | - | ||||||||||||
| 525 | */ | - | ||||||||||||
| 526 | - | |||||||||||||
| 527 | /* | - | ||||||||||||
| 528 | * Turn BN_FLG_CONSTTIME flag on, so that when BN_div is invoked, | - | ||||||||||||
| 529 | * BN_div_no_branch will be called eventually. | - | ||||||||||||
| 530 | */ | - | ||||||||||||
| 531 | { | - | ||||||||||||
| 532 | BIGNUM local_A; | - | ||||||||||||
| 533 | bn_init(&local_A); | - | ||||||||||||
| 534 | BN_with_flags(&local_A, A, BN_FLG_CONSTTIME); | - | ||||||||||||
| 535 | - | |||||||||||||
| 536 | /* (D, M) := (A/B, A%B) ... */ | - | ||||||||||||
| 537 | if (!BN_div(D, M, &local_A, B, ctx))
| 0-2412196 | ||||||||||||
| 538 | goto err; never executed: goto err; | 0 | ||||||||||||
| 539 | /* Ensure local_A goes out of scope before any further use of A */ | - | ||||||||||||
| 540 | } | - | ||||||||||||
| 541 | - | |||||||||||||
| 542 | /*- | - | ||||||||||||
| 543 | * Now | - | ||||||||||||
| 544 | * A = D*B + M; | - | ||||||||||||
| 545 | * thus we have | - | ||||||||||||
| 546 | * (**) sign*Y*a == D*B + M (mod |n|). | - | ||||||||||||
| 547 | */ | - | ||||||||||||
| 548 | - | |||||||||||||
| 549 | tmp = A; /* keep the BIGNUM object, the value does not | - | ||||||||||||
| 550 | * matter */ | - | ||||||||||||
| 551 | - | |||||||||||||
| 552 | /* (A, B) := (B, A mod B) ... */ | - | ||||||||||||
| 553 | A = B; | - | ||||||||||||
| 554 | B = M; | - | ||||||||||||
| 555 | /* ... so we have 0 <= B < A again */ | - | ||||||||||||
| 556 | - | |||||||||||||
| 557 | /*- | - | ||||||||||||
| 558 | * Since the former M is now B and the former B is now A, | - | ||||||||||||
| 559 | * (**) translates into | - | ||||||||||||
| 560 | * sign*Y*a == D*A + B (mod |n|), | - | ||||||||||||
| 561 | * i.e. | - | ||||||||||||
| 562 | * sign*Y*a - D*A == B (mod |n|). | - | ||||||||||||
| 563 | * Similarly, (*) translates into | - | ||||||||||||
| 564 | * -sign*X*a == A (mod |n|). | - | ||||||||||||
| 565 | * | - | ||||||||||||
| 566 | * Thus, | - | ||||||||||||
| 567 | * sign*Y*a + D*sign*X*a == B (mod |n|), | - | ||||||||||||
| 568 | * i.e. | - | ||||||||||||
| 569 | * sign*(Y + D*X)*a == B (mod |n|). | - | ||||||||||||
| 570 | * | - | ||||||||||||
| 571 | * So if we set (X, Y, sign) := (Y + D*X, X, -sign), we arrive back at | - | ||||||||||||
| 572 | * -sign*X*a == B (mod |n|), | - | ||||||||||||
| 573 | * sign*Y*a == A (mod |n|). | - | ||||||||||||
| 574 | * Note that X and Y stay non-negative all the time. | - | ||||||||||||
| 575 | */ | - | ||||||||||||
| 576 | - | |||||||||||||
| 577 | if (!BN_mul(tmp, D, X, ctx))
| 0-2412196 | ||||||||||||
| 578 | goto err; never executed: goto err; | 0 | ||||||||||||
| 579 | if (!BN_add(tmp, tmp, Y))
| 0-2412196 | ||||||||||||
| 580 | goto err; never executed: goto err; | 0 | ||||||||||||
| 581 | - | |||||||||||||
| 582 | M = Y; /* keep the BIGNUM object, the value does not | - | ||||||||||||
| 583 | * matter */ | - | ||||||||||||
| 584 | Y = X; | - | ||||||||||||
| 585 | X = tmp; | - | ||||||||||||
| 586 | sign = -sign; | - | ||||||||||||
| 587 | } executed 2412196 times by 1 test: end of blockExecuted by:
| 2412196 | ||||||||||||
| 588 | - | |||||||||||||
| 589 | /*- | - | ||||||||||||
| 590 | * The while loop (Euclid's algorithm) ends when | - | ||||||||||||
| 591 | * A == gcd(a,n); | - | ||||||||||||
| 592 | * we have | - | ||||||||||||
| 593 | * sign*Y*a == A (mod |n|), | - | ||||||||||||
| 594 | * where Y is non-negative. | - | ||||||||||||
| 595 | */ | - | ||||||||||||
| 596 | - | |||||||||||||
| 597 | if (sign < 0) {
| 3386-7140 | ||||||||||||
| 598 | if (!BN_sub(Y, n, Y))
| 0-7140 | ||||||||||||
| 599 | goto err; never executed: goto err; | 0 | ||||||||||||
| 600 | } executed 7140 times by 1 test: end of blockExecuted by:
| 7140 | ||||||||||||
| 601 | /* Now Y*a == A (mod |n|). */ | - | ||||||||||||
| 602 | - | |||||||||||||
| 603 | if (BN_is_one(A)) {
| 0-10526 | ||||||||||||
| 604 | /* Y*a == 1 (mod |n|) */ | - | ||||||||||||
| 605 | if (!Y->neg && BN_ucmp(Y, n) < 0) {
| 0-10526 | ||||||||||||
| 606 | if (!BN_copy(R, Y))
| 0-10526 | ||||||||||||
| 607 | goto err; never executed: goto err; | 0 | ||||||||||||
| 608 | } else { executed 10526 times by 1 test: end of blockExecuted by:
| 10526 | ||||||||||||
| 609 | if (!BN_nnmod(R, Y, n, ctx))
| 0 | ||||||||||||
| 610 | goto err; never executed: goto err; | 0 | ||||||||||||
| 611 | } never executed: end of block | 0 | ||||||||||||
| 612 | } else { | - | ||||||||||||
| 613 | BNerr(BN_F_BN_MOD_INVERSE_NO_BRANCH, BN_R_NO_INVERSE); | - | ||||||||||||
| 614 | goto err; never executed: goto err; | 0 | ||||||||||||
| 615 | } | - | ||||||||||||
| 616 | ret = R; | - | ||||||||||||
| 617 | err: code before this statement executed 10526 times by 1 test: err:Executed by:
| 10526 | ||||||||||||
| 618 | if ((ret == NULL) && (in == NULL))
| 0-10526 | ||||||||||||
| 619 | BN_free(R); never executed: BN_free(R); | 0 | ||||||||||||
| 620 | BN_CTX_end(ctx); | - | ||||||||||||
| 621 | bn_check_top(ret); | - | ||||||||||||
| 622 | return ret; executed 10526 times by 1 test: return ret;Executed by:
| 10526 | ||||||||||||
| 623 | } | - | ||||||||||||
| Source code | Switch to Preprocessed file |