1 /* 2 * Copyright 1998-2016 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 int BN_nnmod(BIGNUM *r, const BIGNUM *m, const BIGNUM *d, BN_CTX *ctx) 14 { 15 /* 16 * like BN_mod, but returns non-negative remainder (i.e., 0 <= r < |d| 17 * always holds) 18 */ 19 20 if (!(BN_mod(r, m, d, ctx))) 21 return 0; 22 if (!r->neg) 23 return 1; 24 /* now -|d| < r < 0, so we have to set r := r + |d| */ 25 return (d->neg ? BN_sub : BN_add) (r, r, d); 26 } 27 28 int BN_mod_add(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, const BIGNUM *m, 29 BN_CTX *ctx) 30 { 31 if (!BN_add(r, a, b)) 32 return 0; 33 return BN_nnmod(r, r, m, ctx); 34 } 35 36 /* 37 * BN_mod_add variant that may be used if both a and b are non-negative and 38 * less than m 39 */ 40 int BN_mod_add_quick(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, 41 const BIGNUM *m) 42 { 43 if (!BN_uadd(r, a, b)) 44 return 0; 45 if (BN_ucmp(r, m) >= 0) 46 return BN_usub(r, r, m); 47 return 1; 48 } 49 50 int BN_mod_sub(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, const BIGNUM *m, 51 BN_CTX *ctx) 52 { 53 if (!BN_sub(r, a, b)) 54 return 0; 55 return BN_nnmod(r, r, m, ctx); 56 } 57 58 /* 59 * BN_mod_sub variant that may be used if both a and b are non-negative and 60 * less than m 61 */ 62 int BN_mod_sub_quick(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, 63 const BIGNUM *m) 64 { 65 if (!BN_sub(r, a, b)) 66 return 0; 67 if (r->neg) 68 return BN_add(r, r, m); 69 return 1; 70 } 71 72 /* slow but works */ 73 int BN_mod_mul(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, const BIGNUM *m, 74 BN_CTX *ctx) 75 { 76 BIGNUM *t; 77 int ret = 0; 78 79 bn_check_top(a); 80 bn_check_top(b); 81 bn_check_top(m); 82 83 BN_CTX_start(ctx); 84 if ((t = BN_CTX_get(ctx)) == NULL) 85 goto err; 86 if (a == b) { 87 if (!BN_sqr(t, a, ctx)) 88 goto err; 89 } else { 90 if (!BN_mul(t, a, b, ctx)) 91 goto err; 92 } 93 if (!BN_nnmod(r, t, m, ctx)) 94 goto err; 95 bn_check_top(r); 96 ret = 1; 97 err: 98 BN_CTX_end(ctx); 99 return (ret); 100 } 101 102 int BN_mod_sqr(BIGNUM *r, const BIGNUM *a, const BIGNUM *m, BN_CTX *ctx) 103 { 104 if (!BN_sqr(r, a, ctx)) 105 return 0; 106 /* r->neg == 0, thus we don't need BN_nnmod */ 107 return BN_mod(r, r, m, ctx); 108 } 109 110 int BN_mod_lshift1(BIGNUM *r, const BIGNUM *a, const BIGNUM *m, BN_CTX *ctx) 111 { 112 if (!BN_lshift1(r, a)) 113 return 0; 114 bn_check_top(r); 115 return BN_nnmod(r, r, m, ctx); 116 } 117 118 /* 119 * BN_mod_lshift1 variant that may be used if a is non-negative and less than 120 * m 121 */ 122 int BN_mod_lshift1_quick(BIGNUM *r, const BIGNUM *a, const BIGNUM *m) 123 { 124 if (!BN_lshift1(r, a)) 125 return 0; 126 bn_check_top(r); 127 if (BN_cmp(r, m) >= 0) 128 return BN_sub(r, r, m); 129 return 1; 130 } 131 132 int BN_mod_lshift(BIGNUM *r, const BIGNUM *a, int n, const BIGNUM *m, 133 BN_CTX *ctx) 134 { 135 BIGNUM *abs_m = NULL; 136 int ret; 137 138 if (!BN_nnmod(r, a, m, ctx)) 139 return 0; 140 141 if (m->neg) { 142 abs_m = BN_dup(m); 143 if (abs_m == NULL) 144 return 0; 145 abs_m->neg = 0; 146 } 147 148 ret = BN_mod_lshift_quick(r, r, n, (abs_m ? abs_m : m)); 149 bn_check_top(r); 150 151 BN_free(abs_m); 152 return ret; 153 } 154 155 /* 156 * BN_mod_lshift variant that may be used if a is non-negative and less than 157 * m 158 */ 159 int BN_mod_lshift_quick(BIGNUM *r, const BIGNUM *a, int n, const BIGNUM *m) 160 { 161 if (r != a) { 162 if (BN_copy(r, a) == NULL) 163 return 0; 164 } 165 166 while (n > 0) { 167 int max_shift; 168 169 /* 0 < r < m */ 170 max_shift = BN_num_bits(m) - BN_num_bits(r); 171 /* max_shift >= 0 */ 172 173 if (max_shift < 0) { 174 BNerr(BN_F_BN_MOD_LSHIFT_QUICK, BN_R_INPUT_NOT_REDUCED); 175 return 0; 176 } 177 178 if (max_shift > n) 179 max_shift = n; 180 181 if (max_shift) { 182 if (!BN_lshift(r, r, max_shift)) 183 return 0; 184 n -= max_shift; 185 } else { 186 if (!BN_lshift1(r, r)) 187 return 0; 188 --n; 189 } 190 191 /* BN_num_bits(r) <= BN_num_bits(m) */ 192 193 if (BN_cmp(r, m) >= 0) { 194 if (!BN_sub(r, r, m)) 195 return 0; 196 } 197 } 198 bn_check_top(r); 199 200 return 1; 201 } 202