| Absolute File Name: | /home/opencoverage/opencoverage/guest-scripts/libressl/src/crypto/bn/bn_mod.c | 
| Source code | Switch to Preprocessed file | 
| Line | Source | Count | ||||||
|---|---|---|---|---|---|---|---|---|
| 1 | /* $OpenBSD: bn_mod.c,v 1.12 2017/01/29 17:49:22 beck Exp $ */ | - | ||||||
| 2 | /* Includes code written by Lenka Fibikova <fibikova@exp-math.uni-essen.de> | - | ||||||
| 3 | * 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 | /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com) | - | ||||||
| 58 | * All rights reserved. | - | ||||||
| 59 | * | - | ||||||
| 60 | * This package is an SSL implementation written | - | ||||||
| 61 | * by Eric Young (eay@cryptsoft.com). | - | ||||||
| 62 | * The implementation was written so as to conform with Netscapes SSL. | - | ||||||
| 63 | * | - | ||||||
| 64 | * This library is free for commercial and non-commercial use as long as | - | ||||||
| 65 | * the following conditions are aheared to. The following conditions | - | ||||||
| 66 | * apply to all code found in this distribution, be it the RC4, RSA, | - | ||||||
| 67 | * lhash, DES, etc., code; not just the SSL code. The SSL documentation | - | ||||||
| 68 | * included with this distribution is covered by the same copyright terms | - | ||||||
| 69 | * except that the holder is Tim Hudson (tjh@cryptsoft.com). | - | ||||||
| 70 | * | - | ||||||
| 71 | * Copyright remains Eric Young's, and as such any Copyright notices in | - | ||||||
| 72 | * the code are not to be removed. | - | ||||||
| 73 | * If this package is used in a product, Eric Young should be given attribution | - | ||||||
| 74 | * as the author of the parts of the library used. | - | ||||||
| 75 | * This can be in the form of a textual message at program startup or | - | ||||||
| 76 | * in documentation (online or textual) provided with the package. | - | ||||||
| 77 | * | - | ||||||
| 78 | * Redistribution and use in source and binary forms, with or without | - | ||||||
| 79 | * modification, are permitted provided that the following conditions | - | ||||||
| 80 | * are met: | - | ||||||
| 81 | * 1. Redistributions of source code must retain the copyright | - | ||||||
| 82 | * notice, this list of conditions and the following disclaimer. | - | ||||||
| 83 | * 2. Redistributions in binary form must reproduce the above copyright | - | ||||||
| 84 | * notice, this list of conditions and the following disclaimer in the | - | ||||||
| 85 | * documentation and/or other materials provided with the distribution. | - | ||||||
| 86 | * 3. All advertising materials mentioning features or use of this software | - | ||||||
| 87 | * must display the following acknowledgement: | - | ||||||
| 88 | * "This product includes cryptographic software written by | - | ||||||
| 89 | * Eric Young (eay@cryptsoft.com)" | - | ||||||
| 90 | * The word 'cryptographic' can be left out if the rouines from the library | - | ||||||
| 91 | * being used are not cryptographic related :-). | - | ||||||
| 92 | * 4. If you include any Windows specific code (or a derivative thereof) from | - | ||||||
| 93 | * the apps directory (application code) you must include an acknowledgement: | - | ||||||
| 94 | * "This product includes software written by Tim Hudson (tjh@cryptsoft.com)" | - | ||||||
| 95 | * | - | ||||||
| 96 | * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND | - | ||||||
| 97 | * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE | - | ||||||
| 98 | * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE | - | ||||||
| 99 | * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE | - | ||||||
| 100 | * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL | - | ||||||
| 101 | * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS | - | ||||||
| 102 | * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) | - | ||||||
| 103 | * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT | - | ||||||
| 104 | * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY | - | ||||||
| 105 | * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF | - | ||||||
| 106 | * SUCH DAMAGE. | - | ||||||
| 107 | * | - | ||||||
| 108 | * The licence and distribution terms for any publically available version or | - | ||||||
| 109 | * derivative of this code cannot be changed. i.e. this code cannot simply be | - | ||||||
| 110 | * copied and put under another distribution licence | - | ||||||
| 111 | * [including the GNU Public Licence.] | - | ||||||
| 112 | */ | - | ||||||
| 113 | - | |||||||
| 114 | #include <openssl/err.h> | - | ||||||
| 115 | - | |||||||
| 116 | #include "bn_lcl.h" | - | ||||||
| 117 | - | |||||||
| 118 | int | - | ||||||
| 119 | BN_nnmod(BIGNUM *r, const BIGNUM *m, const BIGNUM *d, BN_CTX *ctx) | - | ||||||
| 120 | { | - | ||||||
| 121 | /* like BN_mod, but returns non-negative remainder | - | ||||||
| 122 | * (i.e., 0 <= r < |d| always holds) */ | - | ||||||
| 123 | - | |||||||
| 124 | if (!(BN_mod_ct(r, m,d, ctx))) 
 | 5-112872 | ||||||
| 125 | return 0; executed 5 times by 1 test:  return 0;Executed by: 
 | 5 | ||||||
| 126 | if (!r->neg) 
 | 243-112629 | ||||||
| 127 | return 1; executed 112629 times by 14 tests:  return 1;Executed by: 
 | 112629 | ||||||
| 128 | /* now -|d| < r < 0, so we have to set r := r + |d| */ | - | ||||||
| 129 | if (d->neg) 
 | 0-243 | ||||||
| 130 | return BN_sub(r, r, d); never executed:  return BN_sub(r, r, d); | 0 | ||||||
| 131 | else | - | ||||||
| 132 | return BN_add(r, r, d); executed 243 times by 2 tests:  return BN_add(r, r, d);Executed by: 
 | 243 | ||||||
| 133 | } | - | ||||||
| 134 | - | |||||||
| 135 | int | - | ||||||
| 136 | BN_mod_add(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, const BIGNUM *m, | - | ||||||
| 137 | BN_CTX *ctx) | - | ||||||
| 138 | { | - | ||||||
| 139 | if (!BN_add(r, a, b)) 
 | 0-120 | ||||||
| 140 | return 0; never executed:  return 0; | 0 | ||||||
| 141 | return BN_nnmod(r, r, m, ctx); executed 120 times by 4 tests:  return BN_nnmod(r, r, m, ctx);Executed by: 
 | 120 | ||||||
| 142 | } | - | ||||||
| 143 | - | |||||||
| 144 | /* BN_mod_add variant that may be used if both a and b are non-negative | - | ||||||
| 145 | * and less than m */ | - | ||||||
| 146 | int | - | ||||||
| 147 | BN_mod_add_quick(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, const BIGNUM *m) | - | ||||||
| 148 | { | - | ||||||
| 149 | if (!BN_uadd(r, a, b)) 
 | 0-585006 | ||||||
| 150 | return 0; never executed:  return 0; | 0 | ||||||
| 151 | if (BN_ucmp(r, m) >= 0) 
 | 287369-297637 | ||||||
| 152 | return BN_usub(r, r, m); executed 287369 times by 4 tests:  return BN_usub(r, r, m);Executed by: 
 | 287369 | ||||||
| 153 | return 1; executed 297637 times by 4 tests:  return 1;Executed by: 
 | 297637 | ||||||
| 154 | } | - | ||||||
| 155 | - | |||||||
| 156 | int | - | ||||||
| 157 | BN_mod_sub(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, const BIGNUM *m, | - | ||||||
| 158 | BN_CTX *ctx) | - | ||||||
| 159 | { | - | ||||||
| 160 | if (!BN_sub(r, a, b)) 
 | 0 | ||||||
| 161 | return 0; never executed:  return 0; | 0 | ||||||
| 162 | return BN_nnmod(r, r, m, ctx); never executed:  return BN_nnmod(r, r, m, ctx); | 0 | ||||||
| 163 | } | - | ||||||
| 164 | - | |||||||
| 165 | /* BN_mod_sub variant that may be used if both a and b are non-negative | - | ||||||
| 166 | * and less than m */ | - | ||||||
| 167 | int | - | ||||||
| 168 | BN_mod_sub_quick(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, const BIGNUM *m) | - | ||||||
| 169 | { | - | ||||||
| 170 | if (!BN_sub(r, a, b)) 
 | 0-1256535 | ||||||
| 171 | return 0; never executed:  return 0; | 0 | ||||||
| 172 | if (r->neg) 
 | 628051-628484 | ||||||
| 173 | return BN_add(r, r, m); executed 628484 times by 4 tests:  return BN_add(r, r, m);Executed by: 
 | 628484 | ||||||
| 174 | return 1; executed 628051 times by 4 tests:  return 1;Executed by: 
 | 628051 | ||||||
| 175 | } | - | ||||||
| 176 | - | |||||||
| 177 | /* slow but works */ | - | ||||||
| 178 | int | - | ||||||
| 179 | BN_mod_mul(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, const BIGNUM *m, | - | ||||||
| 180 | BN_CTX *ctx) | - | ||||||
| 181 | { | - | ||||||
| 182 | BIGNUM *t; | - | ||||||
| 183 | int ret = 0; | - | ||||||
| 184 | - | |||||||
| 185 | bn_check_top(a); | - | ||||||
| 186 | bn_check_top(b); | - | ||||||
| 187 | bn_check_top(m); | - | ||||||
| 188 | - | |||||||
| 189 | BN_CTX_start(ctx); | - | ||||||
| 190 | if ((t = BN_CTX_get(ctx)) == NULL) 
 | 0-88348 | ||||||
| 191 | goto err; never executed:  goto err; | 0 | ||||||
| 192 | if (a == b) { 
 | 17056-71292 | ||||||
| 193 | if (!BN_sqr(t, a, ctx)) 
 | 0-71292 | ||||||
| 194 | goto err; never executed:  goto err; | 0 | ||||||
| 195 | } else { executed 71292 times by 9 tests:  end of blockExecuted by: 
 | 71292 | ||||||
| 196 | if (!BN_mul(t, a,b, ctx)) 
 | 0-17056 | ||||||
| 197 | goto err; never executed:  goto err; | 0 | ||||||
| 198 | } executed 17056 times by 12 tests:  end of blockExecuted by: 
 | 17056 | ||||||
| 199 | if (!BN_nnmod(r, t,m, ctx)) 
 | 1-88347 | ||||||
| 200 | goto err; executed 1 time by 1 test:  goto err;Executed by: 
 | 1 | ||||||
| 201 | bn_check_top(r); | - | ||||||
| 202 | ret = 1; | - | ||||||
| 203 | - | |||||||
| 204 | err: code before this statement executed 88347 times by 14 tests:  err:Executed by: 
 | 88347 | ||||||
| 205 | BN_CTX_end(ctx); | - | ||||||
| 206 | return (ret); executed 88348 times by 14 tests:  return (ret);Executed by: 
 | 88348 | ||||||
| 207 | } | - | ||||||
| 208 | - | |||||||
| 209 | int | - | ||||||
| 210 | BN_mod_sqr(BIGNUM *r, const BIGNUM *a, const BIGNUM *m, BN_CTX *ctx) | - | ||||||
| 211 | { | - | ||||||
| 212 | if (!BN_sqr(r, a, ctx)) 
 | 0-934 | ||||||
| 213 | return 0; never executed:  return 0; | 0 | ||||||
| 214 | /* r->neg == 0, thus we don't need BN_nnmod */ | - | ||||||
| 215 | return BN_mod_ct(r, r, m, ctx); executed 934 times by 5 tests:  return BN_div_ct( ((void *)0) ,(r),(r),(m),(ctx));Executed by: 
 | 934 | ||||||
| 216 | } | - | ||||||
| 217 | - | |||||||
| 218 | int | - | ||||||
| 219 | BN_mod_lshift1(BIGNUM *r, const BIGNUM *a, const BIGNUM *m, BN_CTX *ctx) | - | ||||||
| 220 | { | - | ||||||
| 221 | if (!BN_lshift1(r, a)) 
 | 0 | ||||||
| 222 | return 0; never executed:  return 0; | 0 | ||||||
| 223 | bn_check_top(r); | - | ||||||
| 224 | return BN_nnmod(r, r, m, ctx); never executed:  return BN_nnmod(r, r, m, ctx); | 0 | ||||||
| 225 | } | - | ||||||
| 226 | - | |||||||
| 227 | /* BN_mod_lshift1 variant that may be used if a is non-negative | - | ||||||
| 228 | * and less than m */ | - | ||||||
| 229 | int | - | ||||||
| 230 | BN_mod_lshift1_quick(BIGNUM *r, const BIGNUM *a, const BIGNUM *m) | - | ||||||
| 231 | { | - | ||||||
| 232 | if (!BN_lshift1(r, a)) 
 | 0-618748 | ||||||
| 233 | return 0; never executed:  return 0; | 0 | ||||||
| 234 | bn_check_top(r); | - | ||||||
| 235 | if (BN_cmp(r, m) >= 0) 
 | 309036-309712 | ||||||
| 236 | return BN_sub(r, r, m); executed 309036 times by 5 tests:  return BN_sub(r, r, m);Executed by: 
 | 309036 | ||||||
| 237 | return 1; executed 309712 times by 5 tests:  return 1;Executed by: 
 | 309712 | ||||||
| 238 | } | - | ||||||
| 239 | - | |||||||
| 240 | int | - | ||||||
| 241 | BN_mod_lshift(BIGNUM *r, const BIGNUM *a, int n, const BIGNUM *m, BN_CTX *ctx) | - | ||||||
| 242 | { | - | ||||||
| 243 | BIGNUM *abs_m = NULL; | - | ||||||
| 244 | int ret; | - | ||||||
| 245 | - | |||||||
| 246 | if (!BN_nnmod(r, a, m, ctx)) 
 | 0 | ||||||
| 247 | return 0; never executed:  return 0; | 0 | ||||||
| 248 | - | |||||||
| 249 | if (m->neg) { 
 | 0 | ||||||
| 250 | abs_m = BN_dup(m); | - | ||||||
| 251 | if (abs_m == NULL) 
 | 0 | ||||||
| 252 | return 0; never executed:  return 0; | 0 | ||||||
| 253 | abs_m->neg = 0; | - | ||||||
| 254 | } never executed:  end of block | 0 | ||||||
| 255 | - | |||||||
| 256 | ret = BN_mod_lshift_quick(r, r, n, (abs_m ? abs_m : m)); | - | ||||||
| 257 | bn_check_top(r); | - | ||||||
| 258 | - | |||||||
| 259 | BN_free(abs_m); | - | ||||||
| 260 | return ret; never executed:  return ret; | 0 | ||||||
| 261 | } | - | ||||||
| 262 | - | |||||||
| 263 | /* BN_mod_lshift variant that may be used if a is non-negative | - | ||||||
| 264 | * and less than m */ | - | ||||||
| 265 | int | - | ||||||
| 266 | BN_mod_lshift_quick(BIGNUM *r, const BIGNUM *a, int n, const BIGNUM *m) | - | ||||||
| 267 | { | - | ||||||
| 268 | if (r != a) { 
 | 163199 | ||||||
| 269 | if (BN_copy(r, a) == NULL) 
 | 0-163199 | ||||||
| 270 | return 0; never executed:  return 0; | 0 | ||||||
| 271 | } executed 163199 times by 4 tests:  end of blockExecuted by: 
 | 163199 | ||||||
| 272 | - | |||||||
| 273 | while (n > 0) { 
 | 326398-664617 | ||||||
| 274 | int max_shift; | - | ||||||
| 275 | - | |||||||
| 276 | /* 0 < r < m */ | - | ||||||
| 277 | max_shift = BN_num_bits(m) - BN_num_bits(r); | - | ||||||
| 278 | /* max_shift >= 0 */ | - | ||||||
| 279 | - | |||||||
| 280 | if (max_shift < 0) { 
 | 0-664617 | ||||||
| 281 | BNerror(BN_R_INPUT_NOT_REDUCED); | - | ||||||
| 282 | return 0; never executed:  return 0; | 0 | ||||||
| 283 | } | - | ||||||
| 284 | - | |||||||
| 285 | if (max_shift > n) 
 | 100868-563749 | ||||||
| 286 | max_shift = n; executed 100868 times by 4 tests:  max_shift = n;Executed by: 
 | 100868 | ||||||
| 287 | - | |||||||
| 288 | if (max_shift) { 
 | 313521-351096 | ||||||
| 289 | if (!BN_lshift(r, r, max_shift)) 
 | 0-351096 | ||||||
| 290 | return 0; never executed:  return 0; | 0 | ||||||
| 291 | n -= max_shift; | - | ||||||
| 292 | } else { executed 351096 times by 4 tests:  end of blockExecuted by: 
 | 351096 | ||||||
| 293 | if (!BN_lshift1(r, r)) 
 | 0-313521 | ||||||
| 294 | return 0; never executed:  return 0; | 0 | ||||||
| 295 | --n; | - | ||||||
| 296 | } executed 313521 times by 4 tests:  end of blockExecuted by: 
 | 313521 | ||||||
| 297 | - | |||||||
| 298 | /* BN_num_bits(r) <= BN_num_bits(m) */ | - | ||||||
| 299 | - | |||||||
| 300 | if (BN_cmp(r, m) >= 0) { 
 | 257533-407084 | ||||||
| 301 | if (!BN_sub(r, r, m)) 
 | 0-407084 | ||||||
| 302 | return 0; never executed:  return 0; | 0 | ||||||
| 303 | } executed 407084 times by 4 tests:  end of blockExecuted by: 
 | 407084 | ||||||
| 304 | } executed 664617 times by 4 tests:  end of blockExecuted by: 
 | 664617 | ||||||
| 305 | bn_check_top(r); | - | ||||||
| 306 | - | |||||||
| 307 | return 1; executed 326398 times by 4 tests:  return 1;Executed by: 
 | 326398 | ||||||
| 308 | } | - | ||||||
| Source code | Switch to Preprocessed file |