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