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 <openssl/err.h> 60 #include <openssl/mem.h> 61 62 #include "internal.h" 63 64 65 int BN_add(BIGNUM *r, const BIGNUM *a, const BIGNUM *b) { 66 const BIGNUM *tmp; 67 int a_neg = a->neg, ret; 68 69 /* a + b a+b 70 * a + -b a-b 71 * -a + b b-a 72 * -a + -b -(a+b) 73 */ 74 if (a_neg ^ b->neg) { 75 /* only one is negative */ 76 if (a_neg) { 77 tmp = a; 78 a = b; 79 b = tmp; 80 } 81 82 /* we are now a - b */ 83 if (BN_ucmp(a, b) < 0) { 84 if (!BN_usub(r, b, a)) { 85 return 0; 86 } 87 r->neg = 1; 88 } else { 89 if (!BN_usub(r, a, b)) { 90 return 0; 91 } 92 r->neg = 0; 93 } 94 return 1; 95 } 96 97 ret = BN_uadd(r, a, b); 98 r->neg = a_neg; 99 return ret; 100 } 101 102 int BN_uadd(BIGNUM *r, const BIGNUM *a, const BIGNUM *b) { 103 int max, min, dif; 104 BN_ULONG *ap, *bp, *rp, carry, t1, t2; 105 const BIGNUM *tmp; 106 107 if (a->top < b->top) { 108 tmp = a; 109 a = b; 110 b = tmp; 111 } 112 max = a->top; 113 min = b->top; 114 dif = max - min; 115 116 if (bn_wexpand(r, max + 1) == NULL) { 117 return 0; 118 } 119 120 r->top = max; 121 122 ap = a->d; 123 bp = b->d; 124 rp = r->d; 125 126 carry = bn_add_words(rp, ap, bp, min); 127 rp += min; 128 ap += min; 129 bp += min; 130 131 if (carry) { 132 while (dif) { 133 dif--; 134 t1 = *(ap++); 135 t2 = (t1 + 1) & BN_MASK2; 136 *(rp++) = t2; 137 if (t2) { 138 carry = 0; 139 break; 140 } 141 } 142 if (carry) { 143 /* carry != 0 => dif == 0 */ 144 *rp = 1; 145 r->top++; 146 } 147 } 148 149 if (dif && rp != ap) { 150 while (dif--) { 151 /* copy remaining words if ap != rp */ 152 *(rp++) = *(ap++); 153 } 154 } 155 156 r->neg = 0; 157 return 1; 158 } 159 160 int BN_add_word(BIGNUM *a, BN_ULONG w) { 161 BN_ULONG l; 162 int i; 163 164 w &= BN_MASK2; 165 166 /* degenerate case: w is zero */ 167 if (!w) { 168 return 1; 169 } 170 171 /* degenerate case: a is zero */ 172 if (BN_is_zero(a)) { 173 return BN_set_word(a, w); 174 } 175 176 /* handle 'a' when negative */ 177 if (a->neg) { 178 a->neg = 0; 179 i = BN_sub_word(a, w); 180 if (!BN_is_zero(a)) { 181 a->neg = !(a->neg); 182 } 183 return i; 184 } 185 186 for (i = 0; w != 0 && i < a->top; i++) { 187 a->d[i] = l = (a->d[i] + w) & BN_MASK2; 188 w = (w > l) ? 1 : 0; 189 } 190 191 if (w && i == a->top) { 192 if (bn_wexpand(a, a->top + 1) == NULL) { 193 return 0; 194 } 195 a->top++; 196 a->d[i] = w; 197 } 198 199 return 1; 200 } 201 202 int BN_sub(BIGNUM *r, const BIGNUM *a, const BIGNUM *b) { 203 int max; 204 int add = 0, neg = 0; 205 const BIGNUM *tmp; 206 207 /* a - b a-b 208 * a - -b a+b 209 * -a - b -(a+b) 210 * -a - -b b-a 211 */ 212 if (a->neg) { 213 if (b->neg) { 214 tmp = a; 215 a = b; 216 b = tmp; 217 } else { 218 add = 1; 219 neg = 1; 220 } 221 } else { 222 if (b->neg) { 223 add = 1; 224 neg = 0; 225 } 226 } 227 228 if (add) { 229 if (!BN_uadd(r, a, b)) { 230 return 0; 231 } 232 233 r->neg = neg; 234 return 1; 235 } 236 237 /* We are actually doing a - b :-) */ 238 239 max = (a->top > b->top) ? a->top : b->top; 240 if (bn_wexpand(r, max) == NULL) { 241 return 0; 242 } 243 244 if (BN_ucmp(a, b) < 0) { 245 if (!BN_usub(r, b, a)) { 246 return 0; 247 } 248 r->neg = 1; 249 } else { 250 if (!BN_usub(r, a, b)) { 251 return 0; 252 } 253 r->neg = 0; 254 } 255 256 return 1; 257 } 258 259 int BN_usub(BIGNUM *r, const BIGNUM *a, const BIGNUM *b) { 260 int max, min, dif; 261 register BN_ULONG t1, t2, *ap, *bp, *rp; 262 int i, carry; 263 264 max = a->top; 265 min = b->top; 266 dif = max - min; 267 268 if (dif < 0) /* hmm... should not be happening */ 269 { 270 OPENSSL_PUT_ERROR(BN, BN_usub, BN_R_ARG2_LT_ARG3); 271 return 0; 272 } 273 274 if (bn_wexpand(r, max) == NULL) { 275 return 0; 276 } 277 278 ap = a->d; 279 bp = b->d; 280 rp = r->d; 281 282 carry = 0; 283 for (i = min; i != 0; i--) { 284 t1 = *(ap++); 285 t2 = *(bp++); 286 if (carry) { 287 carry = (t1 <= t2); 288 t1 = (t1 - t2 - 1) & BN_MASK2; 289 } else { 290 carry = (t1 < t2); 291 t1 = (t1 - t2) & BN_MASK2; 292 } 293 *(rp++) = t1 & BN_MASK2; 294 } 295 296 if (carry) /* subtracted */ 297 { 298 if (!dif) { 299 /* error: a < b */ 300 return 0; 301 } 302 303 while (dif) { 304 dif--; 305 t1 = *(ap++); 306 t2 = (t1 - 1) & BN_MASK2; 307 *(rp++) = t2; 308 if (t1) { 309 break; 310 } 311 } 312 } 313 314 if (rp != ap) { 315 for (;;) { 316 if (!dif--) { 317 break; 318 } 319 rp[0] = ap[0]; 320 if (!dif--) { 321 break; 322 } 323 rp[1] = ap[1]; 324 if (!dif--) { 325 break; 326 } 327 rp[2] = ap[2]; 328 if (!dif--) { 329 break; 330 } 331 rp[3] = ap[3]; 332 rp += 4; 333 ap += 4; 334 } 335 } 336 337 r->top = max; 338 r->neg = 0; 339 bn_correct_top(r); 340 341 return 1; 342 } 343 344 int BN_sub_word(BIGNUM *a, BN_ULONG w) { 345 int i; 346 347 w &= BN_MASK2; 348 349 /* degenerate case: w is zero */ 350 if (!w) { 351 return 1; 352 } 353 354 /* degenerate case: a is zero */ 355 if (BN_is_zero(a)) { 356 i = BN_set_word(a, w); 357 if (i != 0) { 358 BN_set_negative(a, 1); 359 } 360 return i; 361 } 362 363 /* handle 'a' when negative */ 364 if (a->neg) { 365 a->neg = 0; 366 i = BN_add_word(a, w); 367 a->neg = 1; 368 return i; 369 } 370 371 if ((a->top == 1) && (a->d[0] < w)) { 372 a->d[0] = w - a->d[0]; 373 a->neg = 1; 374 return 1; 375 } 376 377 i = 0; 378 for (;;) { 379 if (a->d[i] >= w) { 380 a->d[i] -= w; 381 break; 382 } else { 383 a->d[i] = (a->d[i] - w) & BN_MASK2; 384 i++; 385 w = 1; 386 } 387 } 388 389 if ((a->d[i] == 0) && (i == (a->top - 1))) { 390 a->top--; 391 } 392 393 return 1; 394 } 395
