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 "internal.h" 60 61 int BN_lshift(BIGNUM *r, const BIGNUM *a, int n) { 62 int i, nw, lb, rb; 63 BN_ULONG *t, *f; 64 BN_ULONG l; 65 66 r->neg = a->neg; 67 nw = n / BN_BITS2; 68 if (bn_wexpand(r, a->top + nw + 1) == NULL) { 69 return 0; 70 } 71 lb = n % BN_BITS2; 72 rb = BN_BITS2 - lb; 73 f = a->d; 74 t = r->d; 75 t[a->top + nw] = 0; 76 if (lb == 0) { 77 for (i = a->top - 1; i >= 0; i--) { 78 t[nw + i] = f[i]; 79 } 80 } else { 81 for (i = a->top - 1; i >= 0; i--) { 82 l = f[i]; 83 t[nw + i + 1] |= (l >> rb) & BN_MASK2; 84 t[nw + i] = (l << lb) & BN_MASK2; 85 } 86 } 87 memset(t, 0, nw * sizeof(t[0])); 88 r->top = a->top + nw + 1; 89 bn_correct_top(r); 90 91 return 1; 92 } 93 94 int BN_lshift1(BIGNUM *r, const BIGNUM *a) { 95 BN_ULONG *ap, *rp, t, c; 96 int i; 97 98 if (r != a) { 99 r->neg = a->neg; 100 if (bn_wexpand(r, a->top + 1) == NULL) { 101 return 0; 102 } 103 r->top = a->top; 104 } else { 105 if (bn_wexpand(r, a->top + 1) == NULL) { 106 return 0; 107 } 108 } 109 ap = a->d; 110 rp = r->d; 111 c = 0; 112 for (i = 0; i < a->top; i++) { 113 t = *(ap++); 114 *(rp++) = ((t << 1) | c) & BN_MASK2; 115 c = (t & BN_TBIT) ? 1 : 0; 116 } 117 if (c) { 118 *rp = 1; 119 r->top++; 120 } 121 122 return 1; 123 } 124 125 int BN_rshift(BIGNUM *r, const BIGNUM *a, int n) { 126 int i, j, nw, lb, rb; 127 BN_ULONG *t, *f; 128 BN_ULONG l, tmp; 129 130 nw = n / BN_BITS2; 131 rb = n % BN_BITS2; 132 lb = BN_BITS2 - rb; 133 if (nw >= a->top || a->top == 0) { 134 BN_zero(r); 135 return 1; 136 } 137 i = (BN_num_bits(a) - n + (BN_BITS2 - 1)) / BN_BITS2; 138 if (r != a) { 139 r->neg = a->neg; 140 if (bn_wexpand(r, i) == NULL) { 141 return 0; 142 } 143 } else { 144 if (n == 0) { 145 return 1; /* or the copying loop will go berserk */ 146 } 147 } 148 149 f = &(a->d[nw]); 150 t = r->d; 151 j = a->top - nw; 152 r->top = i; 153 154 if (rb == 0) { 155 for (i = j; i != 0; i--) { 156 *(t++) = *(f++); 157 } 158 } else { 159 l = *(f++); 160 for (i = j - 1; i != 0; i--) { 161 tmp = (l >> rb) & BN_MASK2; 162 l = *(f++); 163 *(t++) = (tmp | (l << lb)) & BN_MASK2; 164 } 165 if ((l = (l >> rb) & BN_MASK2)) { 166 *(t) = l; 167 } 168 } 169 170 return 1; 171 } 172 173 int BN_rshift1(BIGNUM *r, const BIGNUM *a) { 174 BN_ULONG *ap, *rp, t, c; 175 int i, j; 176 177 if (BN_is_zero(a)) { 178 BN_zero(r); 179 return 1; 180 } 181 i = a->top; 182 ap = a->d; 183 j = i - (ap[i - 1] == 1); 184 if (a != r) { 185 if (bn_wexpand(r, j) == NULL) { 186 return 0; 187 } 188 r->neg = a->neg; 189 } 190 rp = r->d; 191 t = ap[--i]; 192 c = (t & 1) ? BN_TBIT : 0; 193 if (t >>= 1) { 194 rp[i] = t; 195 } 196 while (i > 0) { 197 t = ap[--i]; 198 rp[i] = ((t >> 1) & BN_MASK2) | c; 199 c = (t & 1) ? BN_TBIT : 0; 200 } 201 r->top = j; 202 203 return 1; 204 } 205 206 int BN_set_bit(BIGNUM *a, int n) { 207 int i, j, k; 208 209 if (n < 0) { 210 return 0; 211 } 212 213 i = n / BN_BITS2; 214 j = n % BN_BITS2; 215 if (a->top <= i) { 216 if (bn_wexpand(a, i + 1) == NULL) { 217 return 0; 218 } 219 for (k = a->top; k < i + 1; k++) { 220 a->d[k] = 0; 221 } 222 a->top = i + 1; 223 } 224 225 a->d[i] |= (((BN_ULONG)1) << j); 226 227 return 1; 228 } 229 230 int BN_clear_bit(BIGNUM *a, int n) { 231 int i, j; 232 233 if (n < 0) { 234 return 0; 235 } 236 237 i = n / BN_BITS2; 238 j = n % BN_BITS2; 239 if (a->top <= i) { 240 return 0; 241 } 242 243 a->d[i] &= (~(((BN_ULONG)1) << j)); 244 bn_correct_top(a); 245 return 1; 246 } 247 248 int BN_is_bit_set(const BIGNUM *a, int n) { 249 int i, j; 250 251 if (n < 0) { 252 return 0; 253 } 254 i = n / BN_BITS2; 255 j = n % BN_BITS2; 256 if (a->top <= i) { 257 return 0; 258 } 259 260 return (a->d[i]>>j)&1; 261 } 262 263 int BN_mask_bits(BIGNUM *a, int n) { 264 int b, w; 265 266 if (n < 0) { 267 return 0; 268 } 269 270 w = n / BN_BITS2; 271 b = n % BN_BITS2; 272 if (w >= a->top) { 273 return 0; 274 } 275 if (b == 0) { 276 a->top = w; 277 } else { 278 a->top = w + 1; 279 a->d[w] &= ~(BN_MASK2 << b); 280 } 281 282 bn_correct_top(a); 283 return 1; 284 } 285