Adam Langley | d9e397b | 2015-01-22 14:27:53 -0800 | [diff] [blame] | 1 | /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com) |
| 2 | * All rights reserved. |
| 3 | * |
| 4 | * This package is an SSL implementation written |
| 5 | * by Eric Young (eay@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@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@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@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 | |
Adam Langley | 4139edb | 2016-01-13 15:00:54 -0800 | [diff] [blame] | 59 | #include <string.h> |
| 60 | |
Adam Langley | d9e397b | 2015-01-22 14:27:53 -0800 | [diff] [blame] | 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 | |
Robert Sloan | 8f860b1 | 2017-08-28 07:37:06 -0700 | [diff] [blame] | 71 | // a + b a+b |
| 72 | // a + -b a-b |
| 73 | // -a + b b-a |
| 74 | // -a + -b -(a+b) |
Adam Langley | d9e397b | 2015-01-22 14:27:53 -0800 | [diff] [blame] | 75 | if (a_neg ^ b->neg) { |
Robert Sloan | 8f860b1 | 2017-08-28 07:37:06 -0700 | [diff] [blame] | 76 | // only one is negative |
Adam Langley | d9e397b | 2015-01-22 14:27:53 -0800 | [diff] [blame] | 77 | if (a_neg) { |
| 78 | tmp = a; |
| 79 | a = b; |
| 80 | b = tmp; |
| 81 | } |
| 82 | |
Robert Sloan | 8f860b1 | 2017-08-28 07:37:06 -0700 | [diff] [blame] | 83 | // we are now a - b |
Adam Langley | d9e397b | 2015-01-22 14:27:53 -0800 | [diff] [blame] | 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 | |
Robert Sloan | 9254e68 | 2017-04-24 09:42:06 -0700 | [diff] [blame] | 117 | if (!bn_wexpand(r, max + 1)) { |
Adam Langley | d9e397b | 2015-01-22 14:27:53 -0800 | [diff] [blame] | 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++); |
Robert Sloan | 29c1d2c | 2017-10-30 14:10:28 -0700 | [diff] [blame] | 136 | t2 = t1 + 1; |
Adam Langley | d9e397b | 2015-01-22 14:27:53 -0800 | [diff] [blame] | 137 | *(rp++) = t2; |
| 138 | if (t2) { |
| 139 | carry = 0; |
| 140 | break; |
| 141 | } |
| 142 | } |
| 143 | if (carry) { |
Robert Sloan | 8f860b1 | 2017-08-28 07:37:06 -0700 | [diff] [blame] | 144 | // carry != 0 => dif == 0 |
Adam Langley | d9e397b | 2015-01-22 14:27:53 -0800 | [diff] [blame] | 145 | *rp = 1; |
| 146 | r->top++; |
| 147 | } |
| 148 | } |
| 149 | |
| 150 | if (dif && rp != ap) { |
| 151 | while (dif--) { |
Robert Sloan | 8f860b1 | 2017-08-28 07:37:06 -0700 | [diff] [blame] | 152 | // copy remaining words if ap != rp |
Adam Langley | d9e397b | 2015-01-22 14:27:53 -0800 | [diff] [blame] | 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 | |
Robert Sloan | 8f860b1 | 2017-08-28 07:37:06 -0700 | [diff] [blame] | 165 | // degenerate case: w is zero |
Adam Langley | d9e397b | 2015-01-22 14:27:53 -0800 | [diff] [blame] | 166 | if (!w) { |
| 167 | return 1; |
| 168 | } |
| 169 | |
Robert Sloan | 8f860b1 | 2017-08-28 07:37:06 -0700 | [diff] [blame] | 170 | // degenerate case: a is zero |
Adam Langley | d9e397b | 2015-01-22 14:27:53 -0800 | [diff] [blame] | 171 | if (BN_is_zero(a)) { |
| 172 | return BN_set_word(a, w); |
| 173 | } |
| 174 | |
Robert Sloan | 8f860b1 | 2017-08-28 07:37:06 -0700 | [diff] [blame] | 175 | // handle 'a' when negative |
Adam Langley | d9e397b | 2015-01-22 14:27:53 -0800 | [diff] [blame] | 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++) { |
Robert Sloan | 29c1d2c | 2017-10-30 14:10:28 -0700 | [diff] [blame] | 186 | a->d[i] = l = a->d[i] + w; |
Adam Langley | d9e397b | 2015-01-22 14:27:53 -0800 | [diff] [blame] | 187 | w = (w > l) ? 1 : 0; |
| 188 | } |
| 189 | |
| 190 | if (w && i == a->top) { |
Robert Sloan | 9254e68 | 2017-04-24 09:42:06 -0700 | [diff] [blame] | 191 | if (!bn_wexpand(a, a->top + 1)) { |
Adam Langley | d9e397b | 2015-01-22 14:27:53 -0800 | [diff] [blame] | 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) { |
Adam Langley | d9e397b | 2015-01-22 14:27:53 -0800 | [diff] [blame] | 202 | int add = 0, neg = 0; |
| 203 | const BIGNUM *tmp; |
| 204 | |
Robert Sloan | 8f860b1 | 2017-08-28 07:37:06 -0700 | [diff] [blame] | 205 | // a - b a-b |
| 206 | // a - -b a+b |
| 207 | // -a - b -(a+b) |
| 208 | // -a - -b b-a |
Adam Langley | d9e397b | 2015-01-22 14:27:53 -0800 | [diff] [blame] | 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 | |
Adam Langley | d9e397b | 2015-01-22 14:27:53 -0800 | [diff] [blame] | 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 | |
Robert Sloan | 8f860b1 | 2017-08-28 07:37:06 -0700 | [diff] [blame] | 258 | if (dif < 0) // hmm... should not be happening |
Adam Langley | d9e397b | 2015-01-22 14:27:53 -0800 | [diff] [blame] | 259 | { |
Kenny Root | b849459 | 2015-09-25 02:29:14 +0000 | [diff] [blame] | 260 | OPENSSL_PUT_ERROR(BN, BN_R_ARG2_LT_ARG3); |
Adam Langley | d9e397b | 2015-01-22 14:27:53 -0800 | [diff] [blame] | 261 | return 0; |
| 262 | } |
| 263 | |
Robert Sloan | 9254e68 | 2017-04-24 09:42:06 -0700 | [diff] [blame] | 264 | if (!bn_wexpand(r, max)) { |
Adam Langley | d9e397b | 2015-01-22 14:27:53 -0800 | [diff] [blame] | 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); |
Robert Sloan | 29c1d2c | 2017-10-30 14:10:28 -0700 | [diff] [blame] | 278 | t1 -= t2 + 1; |
Adam Langley | d9e397b | 2015-01-22 14:27:53 -0800 | [diff] [blame] | 279 | } else { |
| 280 | carry = (t1 < t2); |
Robert Sloan | 29c1d2c | 2017-10-30 14:10:28 -0700 | [diff] [blame] | 281 | t1 -= t2; |
Adam Langley | d9e397b | 2015-01-22 14:27:53 -0800 | [diff] [blame] | 282 | } |
Robert Sloan | 29c1d2c | 2017-10-30 14:10:28 -0700 | [diff] [blame] | 283 | *(rp++) = t1; |
Adam Langley | d9e397b | 2015-01-22 14:27:53 -0800 | [diff] [blame] | 284 | } |
| 285 | |
Robert Sloan | 8f860b1 | 2017-08-28 07:37:06 -0700 | [diff] [blame] | 286 | if (carry) // subtracted |
Adam Langley | d9e397b | 2015-01-22 14:27:53 -0800 | [diff] [blame] | 287 | { |
| 288 | if (!dif) { |
Robert Sloan | 8f860b1 | 2017-08-28 07:37:06 -0700 | [diff] [blame] | 289 | // error: a < b |
Adam Langley | d9e397b | 2015-01-22 14:27:53 -0800 | [diff] [blame] | 290 | return 0; |
| 291 | } |
| 292 | |
| 293 | while (dif) { |
| 294 | dif--; |
| 295 | t1 = *(ap++); |
Robert Sloan | 29c1d2c | 2017-10-30 14:10:28 -0700 | [diff] [blame] | 296 | t2 = t1 - 1; |
Adam Langley | d9e397b | 2015-01-22 14:27:53 -0800 | [diff] [blame] | 297 | *(rp++) = t2; |
| 298 | if (t1) { |
| 299 | break; |
| 300 | } |
| 301 | } |
| 302 | } |
| 303 | |
Adam Langley | 4139edb | 2016-01-13 15:00:54 -0800 | [diff] [blame] | 304 | if (dif > 0 && rp != ap) { |
Robert Sloan | 69939df | 2017-01-09 10:53:07 -0800 | [diff] [blame] | 305 | OPENSSL_memcpy(rp, ap, sizeof(*rp) * dif); |
Adam Langley | d9e397b | 2015-01-22 14:27:53 -0800 | [diff] [blame] | 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 | |
Robert Sloan | 8f860b1 | 2017-08-28 07:37:06 -0700 | [diff] [blame] | 318 | // degenerate case: w is zero |
Adam Langley | d9e397b | 2015-01-22 14:27:53 -0800 | [diff] [blame] | 319 | if (!w) { |
| 320 | return 1; |
| 321 | } |
| 322 | |
Robert Sloan | 8f860b1 | 2017-08-28 07:37:06 -0700 | [diff] [blame] | 323 | // degenerate case: a is zero |
Adam Langley | d9e397b | 2015-01-22 14:27:53 -0800 | [diff] [blame] | 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 | |
Robert Sloan | 8f860b1 | 2017-08-28 07:37:06 -0700 | [diff] [blame] | 332 | // handle 'a' when negative |
Adam Langley | d9e397b | 2015-01-22 14:27:53 -0800 | [diff] [blame] | 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 { |
Robert Sloan | 29c1d2c | 2017-10-30 14:10:28 -0700 | [diff] [blame] | 352 | a->d[i] -= w; |
Adam Langley | d9e397b | 2015-01-22 14:27:53 -0800 | [diff] [blame] | 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 | } |