1 /* 2 * Copyright 1995-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 BN_ULONG BN_mod_word(const BIGNUM *a, BN_ULONG w) 14 { 15 #ifndef BN_LLONG 16 BN_ULONG ret = 0; 17 #else 18 BN_ULLONG ret = 0; 19 #endif 20 int i; 21 22 if (w == 0) 23 return (BN_ULONG)-1; 24 25 #ifndef BN_LLONG 26 /* 27 * If |w| is too long and we don't have BN_ULLONG then we need to fall 28 * back to using BN_div_word 29 */ 30 if (w > ((BN_ULONG)1 << BN_BITS4)) { 31 BIGNUM *tmp = BN_dup(a); 32 if (tmp == NULL) 33 return (BN_ULONG)-1; 34 35 ret = BN_div_word(tmp, w); 36 BN_free(tmp); 37 38 return ret; 39 } 40 #endif 41 42 bn_check_top(a); 43 w &= BN_MASK2; 44 for (i = a->top - 1; i >= 0; i--) { 45 #ifndef BN_LLONG 46 /* 47 * We can assume here that | w <= ((BN_ULONG)1 << BN_BITS4) | and so 48 * | ret < ((BN_ULONG)1 << BN_BITS4) | and therefore the shifts here are 49 * safe and will not overflow 50 */ 51 ret = ((ret << BN_BITS4) | ((a->d[i] >> BN_BITS4) & BN_MASK2l)) % w; 52 ret = ((ret << BN_BITS4) | (a->d[i] & BN_MASK2l)) % w; 53 #else 54 ret = (BN_ULLONG) (((ret << (BN_ULLONG) BN_BITS2) | a->d[i]) % 55 (BN_ULLONG) w); 56 #endif 57 } 58 return (BN_ULONG)ret; 59 } 60 61 BN_ULONG BN_div_word(BIGNUM *a, BN_ULONG w) 62 { 63 BN_ULONG ret = 0; 64 int i, j; 65 66 bn_check_top(a); 67 w &= BN_MASK2; 68 69 if (!w) 70 /* actually this an error (division by zero) */ 71 return (BN_ULONG)-1; 72 if (a->top == 0) 73 return 0; 74 75 /* normalize input (so bn_div_words doesn't complain) */ 76 j = BN_BITS2 - BN_num_bits_word(w); 77 w <<= j; 78 if (!BN_lshift(a, a, j)) 79 return (BN_ULONG)-1; 80 81 for (i = a->top - 1; i >= 0; i--) { 82 BN_ULONG l, d; 83 84 l = a->d[i]; 85 d = bn_div_words(ret, l, w); 86 ret = (l - ((d * w) & BN_MASK2)) & BN_MASK2; 87 a->d[i] = d; 88 } 89 if ((a->top > 0) && (a->d[a->top - 1] == 0)) 90 a->top--; 91 ret >>= j; 92 if (!a->top) 93 a->neg = 0; /* don't allow negative zero */ 94 bn_check_top(a); 95 return ret; 96 } 97 98 int BN_add_word(BIGNUM *a, BN_ULONG w) 99 { 100 BN_ULONG l; 101 int i; 102 103 bn_check_top(a); 104 w &= BN_MASK2; 105 106 /* degenerate case: w is zero */ 107 if (!w) 108 return 1; 109 /* degenerate case: a is zero */ 110 if (BN_is_zero(a)) 111 return BN_set_word(a, w); 112 /* handle 'a' when negative */ 113 if (a->neg) { 114 a->neg = 0; 115 i = BN_sub_word(a, w); 116 if (!BN_is_zero(a)) 117 a->neg = !(a->neg); 118 return i; 119 } 120 for (i = 0; w != 0 && i < a->top; i++) { 121 a->d[i] = l = (a->d[i] + w) & BN_MASK2; 122 w = (w > l) ? 1 : 0; 123 } 124 if (w && i == a->top) { 125 if (bn_wexpand(a, a->top + 1) == NULL) 126 return 0; 127 a->top++; 128 a->d[i] = w; 129 } 130 bn_check_top(a); 131 return 1; 132 } 133 134 int BN_sub_word(BIGNUM *a, BN_ULONG w) 135 { 136 int i; 137 138 bn_check_top(a); 139 w &= BN_MASK2; 140 141 /* degenerate case: w is zero */ 142 if (!w) 143 return 1; 144 /* degenerate case: a is zero */ 145 if (BN_is_zero(a)) { 146 i = BN_set_word(a, w); 147 if (i != 0) 148 BN_set_negative(a, 1); 149 return i; 150 } 151 /* handle 'a' when negative */ 152 if (a->neg) { 153 a->neg = 0; 154 i = BN_add_word(a, w); 155 a->neg = 1; 156 return i; 157 } 158 159 if ((a->top == 1) && (a->d[0] < w)) { 160 a->d[0] = w - a->d[0]; 161 a->neg = 1; 162 return 1; 163 } 164 i = 0; 165 for (;;) { 166 if (a->d[i] >= w) { 167 a->d[i] -= w; 168 break; 169 } else { 170 a->d[i] = (a->d[i] - w) & BN_MASK2; 171 i++; 172 w = 1; 173 } 174 } 175 if ((a->d[i] == 0) && (i == (a->top - 1))) 176 a->top--; 177 bn_check_top(a); 178 return 1; 179 } 180 181 int BN_mul_word(BIGNUM *a, BN_ULONG w) 182 { 183 BN_ULONG ll; 184 185 bn_check_top(a); 186 w &= BN_MASK2; 187 if (a->top) { 188 if (w == 0) 189 BN_zero(a); 190 else { 191 ll = bn_mul_words(a->d, a->d, a->top, w); 192 if (ll) { 193 if (bn_wexpand(a, a->top + 1) == NULL) 194 return 0; 195 a->d[a->top++] = ll; 196 } 197 } 198 } 199 bn_check_top(a); 200 return 1; 201 } 202