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