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_consttime(BIGNUM *r, const BIGNUM *a, const BIGNUM *b) { 104 // Widths are public, so we normalize to make |a| the larger one. 105 if (a->width < b->width) { 106 const BIGNUM *tmp = a; 107 a = b; 108 b = tmp; 109 } 110 111 int max = a->width; 112 int min = b->width; 113 if (!bn_wexpand(r, max + 1)) { 114 return 0; 115 } 116 r->width = max + 1; 117 118 BN_ULONG carry = bn_add_words(r->d, a->d, b->d, min); 119 for (int i = min; i < max; i++) { 120 // |r| and |a| may alias, so use a temporary. 121 BN_ULONG tmp = carry + a->d[i]; 122 carry = tmp < a->d[i]; 123 r->d[i] = tmp; 124 } 125 126 r->d[max] = carry; 127 return 1; 128 } 129 130 int BN_uadd(BIGNUM *r, const BIGNUM *a, const BIGNUM *b) { 131 if (!bn_uadd_consttime(r, a, b)) { 132 return 0; 133 } 134 bn_set_minimal_width(r); 135 return 1; 136 } 137 138 int BN_add_word(BIGNUM *a, BN_ULONG w) { 139 BN_ULONG l; 140 int i; 141 142 // degenerate case: w is zero 143 if (!w) { 144 return 1; 145 } 146 147 // degenerate case: a is zero 148 if (BN_is_zero(a)) { 149 return BN_set_word(a, w); 150 } 151 152 // handle 'a' when negative 153 if (a->neg) { 154 a->neg = 0; 155 i = BN_sub_word(a, w); 156 if (!BN_is_zero(a)) { 157 a->neg = !(a->neg); 158 } 159 return i; 160 } 161 162 for (i = 0; w != 0 && i < a->width; i++) { 163 a->d[i] = l = a->d[i] + w; 164 w = (w > l) ? 1 : 0; 165 } 166 167 if (w && i == a->width) { 168 if (!bn_wexpand(a, a->width + 1)) { 169 return 0; 170 } 171 a->width++; 172 a->d[i] = w; 173 } 174 175 return 1; 176 } 177 178 int BN_sub(BIGNUM *r, const BIGNUM *a, const BIGNUM *b) { 179 int add = 0, neg = 0; 180 const BIGNUM *tmp; 181 182 // a - b a-b 183 // a - -b a+b 184 // -a - b -(a+b) 185 // -a - -b b-a 186 if (a->neg) { 187 if (b->neg) { 188 tmp = a; 189 a = b; 190 b = tmp; 191 } else { 192 add = 1; 193 neg = 1; 194 } 195 } else { 196 if (b->neg) { 197 add = 1; 198 neg = 0; 199 } 200 } 201 202 if (add) { 203 if (!BN_uadd(r, a, b)) { 204 return 0; 205 } 206 207 r->neg = neg; 208 return 1; 209 } 210 211 if (BN_ucmp(a, b) < 0) { 212 if (!BN_usub(r, b, a)) { 213 return 0; 214 } 215 r->neg = 1; 216 } else { 217 if (!BN_usub(r, a, b)) { 218 return 0; 219 } 220 r->neg = 0; 221 } 222 223 return 1; 224 } 225 226 int bn_usub_consttime(BIGNUM *r, const BIGNUM *a, const BIGNUM *b) { 227 // |b| may have more words than |a| given non-minimal inputs, but all words 228 // beyond |a->width| must then be zero. 229 int b_width = b->width; 230 if (b_width > a->width) { 231 if (!bn_fits_in_words(b, a->width)) { 232 OPENSSL_PUT_ERROR(BN, BN_R_ARG2_LT_ARG3); 233 return 0; 234 } 235 b_width = a->width; 236 } 237 238 if (!bn_wexpand(r, a->width)) { 239 return 0; 240 } 241 242 BN_ULONG borrow = bn_sub_words(r->d, a->d, b->d, b_width); 243 for (int i = b_width; i < a->width; i++) { 244 // |r| and |a| may alias, so use a temporary. 245 BN_ULONG tmp = a->d[i]; 246 r->d[i] = a->d[i] - borrow; 247 borrow = tmp < r->d[i]; 248 } 249 250 if (borrow) { 251 OPENSSL_PUT_ERROR(BN, BN_R_ARG2_LT_ARG3); 252 return 0; 253 } 254 255 r->width = a->width; 256 r->neg = 0; 257 return 1; 258 } 259 260 int BN_usub(BIGNUM *r, const BIGNUM *a, const BIGNUM *b) { 261 if (!bn_usub_consttime(r, a, b)) { 262 return 0; 263 } 264 bn_set_minimal_width(r); 265 return 1; 266 } 267 268 int BN_sub_word(BIGNUM *a, BN_ULONG w) { 269 int i; 270 271 // degenerate case: w is zero 272 if (!w) { 273 return 1; 274 } 275 276 // degenerate case: a is zero 277 if (BN_is_zero(a)) { 278 i = BN_set_word(a, w); 279 if (i != 0) { 280 BN_set_negative(a, 1); 281 } 282 return i; 283 } 284 285 // handle 'a' when negative 286 if (a->neg) { 287 a->neg = 0; 288 i = BN_add_word(a, w); 289 a->neg = 1; 290 return i; 291 } 292 293 if ((bn_minimal_width(a) == 1) && (a->d[0] < w)) { 294 a->d[0] = w - a->d[0]; 295 a->neg = 1; 296 return 1; 297 } 298 299 i = 0; 300 for (;;) { 301 if (a->d[i] >= w) { 302 a->d[i] -= w; 303 break; 304 } else { 305 a->d[i] -= w; 306 i++; 307 w = 1; 308 } 309 } 310 311 if ((a->d[i] == 0) && (i == (a->width - 1))) { 312 a->width--; 313 } 314 315 return 1; 316 } 317