1 /* Copyright (C) 1995-1998 Eric Young (eay (at) cryptsoft.com) 2 * All rights reserved. 3 * 4 * This package is an SSL implementation written 5 * by Eric Young (eay (at) cryptsoft.com). 6 * The implementation was written so as to conform with Netscapes SSL. 7 * 8 * This library is free for commercial and non-commercial use as long as 9 * the following conditions are aheared to. The following conditions 10 * apply to all code found in this distribution, be it the RC4, RSA, 11 * lhash, DES, etc., code; not just the SSL code. The SSL documentation 12 * included with this distribution is covered by the same copyright terms 13 * except that the holder is Tim Hudson (tjh (at) cryptsoft.com). 14 * 15 * Copyright remains Eric Young's, and as such any Copyright notices in 16 * the code are not to be removed. 17 * If this package is used in a product, Eric Young should be given attribution 18 * as the author of the parts of the library used. 19 * This can be in the form of a textual message at program startup or 20 * in documentation (online or textual) provided with the package. 21 * 22 * Redistribution and use in source and binary forms, with or without 23 * modification, are permitted provided that the following conditions 24 * are met: 25 * 1. Redistributions of source code must retain the copyright 26 * notice, this list of conditions and the following disclaimer. 27 * 2. Redistributions in binary form must reproduce the above copyright 28 * notice, this list of conditions and the following disclaimer in the 29 * documentation and/or other materials provided with the distribution. 30 * 3. All advertising materials mentioning features or use of this software 31 * must display the following acknowledgement: 32 * "This product includes cryptographic software written by 33 * Eric Young (eay (at) cryptsoft.com)" 34 * The word 'cryptographic' can be left out if the rouines from the library 35 * being used are not cryptographic related :-). 36 * 4. If you include any Windows specific code (or a derivative thereof) from 37 * the apps directory (application code) you must include an acknowledgement: 38 * "This product includes software written by Tim Hudson (tjh (at) cryptsoft.com)" 39 * 40 * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND 41 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 42 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 43 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 44 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 45 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 46 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 47 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 48 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 49 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 50 * SUCH DAMAGE. 51 * 52 * The licence and distribution terms for any publically available version or 53 * derivative of this code cannot be changed. i.e. this code cannot simply be 54 * copied and put under another distribution licence 55 * [including the GNU Public Licence.] */ 56 57 #include <openssl/bn.h> 58 59 #include <string.h> 60 61 #include <openssl/err.h> 62 63 #include "internal.h" 64 65 66 int BN_lshift(BIGNUM *r, const BIGNUM *a, int n) { 67 int i, nw, lb, rb; 68 BN_ULONG *t, *f; 69 BN_ULONG l; 70 71 if (n < 0) { 72 OPENSSL_PUT_ERROR(BN, BN_R_NEGATIVE_NUMBER); 73 return 0; 74 } 75 76 r->neg = a->neg; 77 nw = n / BN_BITS2; 78 if (!bn_wexpand(r, a->top + nw + 1)) { 79 return 0; 80 } 81 lb = n % BN_BITS2; 82 rb = BN_BITS2 - lb; 83 f = a->d; 84 t = r->d; 85 t[a->top + nw] = 0; 86 if (lb == 0) { 87 for (i = a->top - 1; i >= 0; i--) { 88 t[nw + i] = f[i]; 89 } 90 } else { 91 for (i = a->top - 1; i >= 0; i--) { 92 l = f[i]; 93 t[nw + i + 1] |= l >> rb; 94 t[nw + i] = l << lb; 95 } 96 } 97 OPENSSL_memset(t, 0, nw * sizeof(t[0])); 98 r->top = a->top + nw + 1; 99 bn_correct_top(r); 100 101 return 1; 102 } 103 104 int BN_lshift1(BIGNUM *r, const BIGNUM *a) { 105 BN_ULONG *ap, *rp, t, c; 106 int i; 107 108 if (r != a) { 109 r->neg = a->neg; 110 if (!bn_wexpand(r, a->top + 1)) { 111 return 0; 112 } 113 r->top = a->top; 114 } else { 115 if (!bn_wexpand(r, a->top + 1)) { 116 return 0; 117 } 118 } 119 ap = a->d; 120 rp = r->d; 121 c = 0; 122 for (i = 0; i < a->top; i++) { 123 t = *(ap++); 124 *(rp++) = (t << 1) | c; 125 c = t >> (BN_BITS2 - 1); 126 } 127 if (c) { 128 *rp = 1; 129 r->top++; 130 } 131 132 return 1; 133 } 134 135 int BN_rshift(BIGNUM *r, const BIGNUM *a, int n) { 136 int i, j, nw, lb, rb; 137 BN_ULONG *t, *f; 138 BN_ULONG l, tmp; 139 140 if (n < 0) { 141 OPENSSL_PUT_ERROR(BN, BN_R_NEGATIVE_NUMBER); 142 return 0; 143 } 144 145 nw = n / BN_BITS2; 146 rb = n % BN_BITS2; 147 lb = BN_BITS2 - rb; 148 if (nw >= a->top || a->top == 0) { 149 BN_zero(r); 150 return 1; 151 } 152 i = (BN_num_bits(a) - n + (BN_BITS2 - 1)) / BN_BITS2; 153 if (r != a) { 154 r->neg = a->neg; 155 if (!bn_wexpand(r, i)) { 156 return 0; 157 } 158 } else { 159 if (n == 0) { 160 return 1; // or the copying loop will go berserk 161 } 162 } 163 164 f = &(a->d[nw]); 165 t = r->d; 166 j = a->top - nw; 167 r->top = i; 168 169 if (rb == 0) { 170 for (i = j; i != 0; i--) { 171 *(t++) = *(f++); 172 } 173 } else { 174 l = *(f++); 175 for (i = j - 1; i != 0; i--) { 176 tmp = l >> rb; 177 l = *(f++); 178 *(t++) = tmp | (l << lb); 179 } 180 l >>= rb; 181 if (l) { 182 *(t) = l; 183 } 184 } 185 186 if (r->top == 0) { 187 r->neg = 0; 188 } 189 190 return 1; 191 } 192 193 int BN_rshift1(BIGNUM *r, const BIGNUM *a) { 194 BN_ULONG *ap, *rp, t, c; 195 int i, j; 196 197 if (BN_is_zero(a)) { 198 BN_zero(r); 199 return 1; 200 } 201 i = a->top; 202 ap = a->d; 203 j = i - (ap[i - 1] == 1); 204 if (a != r) { 205 if (!bn_wexpand(r, j)) { 206 return 0; 207 } 208 r->neg = a->neg; 209 } 210 rp = r->d; 211 t = ap[--i]; 212 c = t << (BN_BITS2 - 1); 213 if (t >>= 1) { 214 rp[i] = t; 215 } 216 while (i > 0) { 217 t = ap[--i]; 218 rp[i] = (t >> 1) | c; 219 c = t << (BN_BITS2 - 1); 220 } 221 r->top = j; 222 223 if (r->top == 0) { 224 r->neg = 0; 225 } 226 227 return 1; 228 } 229 230 int BN_set_bit(BIGNUM *a, int n) { 231 if (n < 0) { 232 return 0; 233 } 234 235 int i = n / BN_BITS2; 236 int j = n % BN_BITS2; 237 if (a->top <= i) { 238 if (!bn_wexpand(a, i + 1)) { 239 return 0; 240 } 241 for (int k = a->top; k < i + 1; k++) { 242 a->d[k] = 0; 243 } 244 a->top = i + 1; 245 } 246 247 a->d[i] |= (((BN_ULONG)1) << j); 248 249 return 1; 250 } 251 252 int BN_clear_bit(BIGNUM *a, int n) { 253 int i, j; 254 255 if (n < 0) { 256 return 0; 257 } 258 259 i = n / BN_BITS2; 260 j = n % BN_BITS2; 261 if (a->top <= i) { 262 return 0; 263 } 264 265 a->d[i] &= (~(((BN_ULONG)1) << j)); 266 bn_correct_top(a); 267 return 1; 268 } 269 270 int bn_is_bit_set_words(const BN_ULONG *a, size_t num, unsigned bit) { 271 unsigned i = bit / BN_BITS2; 272 unsigned j = bit % BN_BITS2; 273 if (i >= num) { 274 return 0; 275 } 276 return (a[i] >> j) & 1; 277 } 278 279 int BN_is_bit_set(const BIGNUM *a, int n) { 280 if (n < 0) { 281 return 0; 282 } 283 return bn_is_bit_set_words(a->d, a->top, n); 284 } 285 286 int BN_mask_bits(BIGNUM *a, int n) { 287 if (n < 0) { 288 return 0; 289 } 290 291 int w = n / BN_BITS2; 292 int b = n % BN_BITS2; 293 if (w >= a->top) { 294 return 0; 295 } 296 if (b == 0) { 297 a->top = w; 298 } else { 299 a->top = w + 1; 300 a->d[w] &= ~(BN_MASK2 << b); 301 } 302 303 bn_correct_top(a); 304 return 1; 305 } 306
