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_lshift, 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) == NULL) { 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) & BN_MASK2; 94 t[nw + i] = (l << lb) & BN_MASK2; 95 } 96 } 97 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) == NULL) { 111 return 0; 112 } 113 r->top = a->top; 114 } else { 115 if (bn_wexpand(r, a->top + 1) == NULL) { 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) & BN_MASK2; 125 c = (t & BN_TBIT) ? 1 : 0; 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_rshift, 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) == NULL) { 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) & BN_MASK2; 177 l = *(f++); 178 *(t++) = (tmp | (l << lb)) & BN_MASK2; 179 } 180 if ((l = (l >> rb) & BN_MASK2)) { 181 *(t) = l; 182 } 183 } 184 185 return 1; 186 } 187 188 int BN_rshift1(BIGNUM *r, const BIGNUM *a) { 189 BN_ULONG *ap, *rp, t, c; 190 int i, j; 191 192 if (BN_is_zero(a)) { 193 BN_zero(r); 194 return 1; 195 } 196 i = a->top; 197 ap = a->d; 198 j = i - (ap[i - 1] == 1); 199 if (a != r) { 200 if (bn_wexpand(r, j) == NULL) { 201 return 0; 202 } 203 r->neg = a->neg; 204 } 205 rp = r->d; 206 t = ap[--i]; 207 c = (t & 1) ? BN_TBIT : 0; 208 if (t >>= 1) { 209 rp[i] = t; 210 } 211 while (i > 0) { 212 t = ap[--i]; 213 rp[i] = ((t >> 1) & BN_MASK2) | c; 214 c = (t & 1) ? BN_TBIT : 0; 215 } 216 r->top = j; 217 218 return 1; 219 } 220 221 int BN_set_bit(BIGNUM *a, int n) { 222 int i, j, k; 223 224 if (n < 0) { 225 return 0; 226 } 227 228 i = n / BN_BITS2; 229 j = n % BN_BITS2; 230 if (a->top <= i) { 231 if (bn_wexpand(a, i + 1) == NULL) { 232 return 0; 233 } 234 for (k = a->top; k < i + 1; k++) { 235 a->d[k] = 0; 236 } 237 a->top = i + 1; 238 } 239 240 a->d[i] |= (((BN_ULONG)1) << j); 241 242 return 1; 243 } 244 245 int BN_clear_bit(BIGNUM *a, int n) { 246 int i, j; 247 248 if (n < 0) { 249 return 0; 250 } 251 252 i = n / BN_BITS2; 253 j = n % BN_BITS2; 254 if (a->top <= i) { 255 return 0; 256 } 257 258 a->d[i] &= (~(((BN_ULONG)1) << j)); 259 bn_correct_top(a); 260 return 1; 261 } 262 263 int BN_is_bit_set(const BIGNUM *a, int n) { 264 int i, j; 265 266 if (n < 0) { 267 return 0; 268 } 269 i = n / BN_BITS2; 270 j = n % BN_BITS2; 271 if (a->top <= i) { 272 return 0; 273 } 274 275 return (a->d[i]>>j)&1; 276 } 277 278 int BN_mask_bits(BIGNUM *a, int n) { 279 int b, w; 280 281 if (n < 0) { 282 return 0; 283 } 284 285 w = n / BN_BITS2; 286 b = n % BN_BITS2; 287 if (w >= a->top) { 288 return 0; 289 } 290 if (b == 0) { 291 a->top = w; 292 } else { 293 a->top = w + 1; 294 a->d[w] &= ~(BN_MASK2 << b); 295 } 296 297 bn_correct_top(a); 298 return 1; 299 } 300
