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 <limits.h> 60 #include <string.h> 61 62 #include <openssl/err.h> 63 #include <openssl/mem.h> 64 65 #include "internal.h" 66 #include "../delocate.h" 67 68 69 BIGNUM *BN_new(void) { 70 BIGNUM *bn = OPENSSL_malloc(sizeof(BIGNUM)); 71 72 if (bn == NULL) { 73 OPENSSL_PUT_ERROR(BN, ERR_R_MALLOC_FAILURE); 74 return NULL; 75 } 76 77 OPENSSL_memset(bn, 0, sizeof(BIGNUM)); 78 bn->flags = BN_FLG_MALLOCED; 79 80 return bn; 81 } 82 83 void BN_init(BIGNUM *bn) { 84 OPENSSL_memset(bn, 0, sizeof(BIGNUM)); 85 } 86 87 void BN_free(BIGNUM *bn) { 88 if (bn == NULL) { 89 return; 90 } 91 92 if ((bn->flags & BN_FLG_STATIC_DATA) == 0) { 93 OPENSSL_free(bn->d); 94 } 95 96 if (bn->flags & BN_FLG_MALLOCED) { 97 OPENSSL_free(bn); 98 } else { 99 bn->d = NULL; 100 } 101 } 102 103 void BN_clear_free(BIGNUM *bn) { 104 char should_free; 105 106 if (bn == NULL) { 107 return; 108 } 109 110 if (bn->d != NULL) { 111 if ((bn->flags & BN_FLG_STATIC_DATA) == 0) { 112 OPENSSL_free(bn->d); 113 } else { 114 OPENSSL_cleanse(bn->d, bn->dmax * sizeof(bn->d[0])); 115 } 116 } 117 118 should_free = (bn->flags & BN_FLG_MALLOCED) != 0; 119 if (should_free) { 120 OPENSSL_free(bn); 121 } else { 122 OPENSSL_cleanse(bn, sizeof(BIGNUM)); 123 } 124 } 125 126 BIGNUM *BN_dup(const BIGNUM *src) { 127 BIGNUM *copy; 128 129 if (src == NULL) { 130 return NULL; 131 } 132 133 copy = BN_new(); 134 if (copy == NULL) { 135 return NULL; 136 } 137 138 if (!BN_copy(copy, src)) { 139 BN_free(copy); 140 return NULL; 141 } 142 143 return copy; 144 } 145 146 BIGNUM *BN_copy(BIGNUM *dest, const BIGNUM *src) { 147 if (src == dest) { 148 return dest; 149 } 150 151 if (!bn_wexpand(dest, src->top)) { 152 return NULL; 153 } 154 155 OPENSSL_memcpy(dest->d, src->d, sizeof(src->d[0]) * src->top); 156 157 dest->top = src->top; 158 dest->neg = src->neg; 159 return dest; 160 } 161 162 void BN_clear(BIGNUM *bn) { 163 if (bn->d != NULL) { 164 OPENSSL_memset(bn->d, 0, bn->dmax * sizeof(bn->d[0])); 165 } 166 167 bn->top = 0; 168 bn->neg = 0; 169 } 170 171 DEFINE_METHOD_FUNCTION(BIGNUM, BN_value_one) { 172 static const BN_ULONG kOneLimbs[1] = { 1 }; 173 out->d = (BN_ULONG*) kOneLimbs; 174 out->top = 1; 175 out->dmax = 1; 176 out->neg = 0; 177 out->flags = BN_FLG_STATIC_DATA; 178 } 179 180 // BN_num_bits_word returns the minimum number of bits needed to represent the 181 // value in |l|. 182 unsigned BN_num_bits_word(BN_ULONG l) { 183 // |BN_num_bits| is often called on RSA prime factors. These have public bit 184 // lengths, but all bits beyond the high bit are secret, so count bits in 185 // constant time. 186 BN_ULONG x, mask; 187 int bits = (l != 0); 188 189 #if BN_BITS2 > 32 190 x = l >> 32; 191 mask = 0u - x; 192 mask = (0u - (mask >> (BN_BITS2 - 1))); 193 bits += 32 & mask; 194 l ^= (x ^ l) & mask; 195 #endif 196 197 x = l >> 16; 198 mask = 0u - x; 199 mask = (0u - (mask >> (BN_BITS2 - 1))); 200 bits += 16 & mask; 201 l ^= (x ^ l) & mask; 202 203 x = l >> 8; 204 mask = 0u - x; 205 mask = (0u - (mask >> (BN_BITS2 - 1))); 206 bits += 8 & mask; 207 l ^= (x ^ l) & mask; 208 209 x = l >> 4; 210 mask = 0u - x; 211 mask = (0u - (mask >> (BN_BITS2 - 1))); 212 bits += 4 & mask; 213 l ^= (x ^ l) & mask; 214 215 x = l >> 2; 216 mask = 0u - x; 217 mask = (0u - (mask >> (BN_BITS2 - 1))); 218 bits += 2 & mask; 219 l ^= (x ^ l) & mask; 220 221 x = l >> 1; 222 mask = 0u - x; 223 mask = (0u - (mask >> (BN_BITS2 - 1))); 224 bits += 1 & mask; 225 226 return bits; 227 } 228 229 unsigned BN_num_bits(const BIGNUM *bn) { 230 const int width = bn_minimal_width(bn); 231 if (width == 0) { 232 return 0; 233 } 234 235 return (width - 1) * BN_BITS2 + BN_num_bits_word(bn->d[width - 1]); 236 } 237 238 unsigned BN_num_bytes(const BIGNUM *bn) { 239 return (BN_num_bits(bn) + 7) / 8; 240 } 241 242 void BN_zero(BIGNUM *bn) { 243 bn->top = bn->neg = 0; 244 } 245 246 int BN_one(BIGNUM *bn) { 247 return BN_set_word(bn, 1); 248 } 249 250 int BN_set_word(BIGNUM *bn, BN_ULONG value) { 251 if (value == 0) { 252 BN_zero(bn); 253 return 1; 254 } 255 256 if (!bn_wexpand(bn, 1)) { 257 return 0; 258 } 259 260 bn->neg = 0; 261 bn->d[0] = value; 262 bn->top = 1; 263 return 1; 264 } 265 266 int BN_set_u64(BIGNUM *bn, uint64_t value) { 267 #if BN_BITS2 == 64 268 return BN_set_word(bn, value); 269 #elif BN_BITS2 == 32 270 if (value <= BN_MASK2) { 271 return BN_set_word(bn, (BN_ULONG)value); 272 } 273 274 if (!bn_wexpand(bn, 2)) { 275 return 0; 276 } 277 278 bn->neg = 0; 279 bn->d[0] = (BN_ULONG)value; 280 bn->d[1] = (BN_ULONG)(value >> 32); 281 bn->top = 2; 282 return 1; 283 #else 284 #error "BN_BITS2 must be 32 or 64." 285 #endif 286 } 287 288 int bn_set_words(BIGNUM *bn, const BN_ULONG *words, size_t num) { 289 if (!bn_wexpand(bn, num)) { 290 return 0; 291 } 292 OPENSSL_memmove(bn->d, words, num * sizeof(BN_ULONG)); 293 // |bn_wexpand| verified that |num| isn't too large. 294 bn->top = (int)num; 295 bn_correct_top(bn); 296 bn->neg = 0; 297 return 1; 298 } 299 300 int bn_fits_in_words(const BIGNUM *bn, size_t num) { 301 // All words beyond |num| must be zero. 302 BN_ULONG mask = 0; 303 for (size_t i = num; i < (size_t)bn->top; i++) { 304 mask |= bn->d[i]; 305 } 306 return mask == 0; 307 } 308 309 int bn_copy_words(BN_ULONG *out, size_t num, const BIGNUM *bn) { 310 if (bn->neg) { 311 OPENSSL_PUT_ERROR(BN, BN_R_NEGATIVE_NUMBER); 312 return 0; 313 } 314 315 size_t width = (size_t)bn->top; 316 if (width > num) { 317 if (!bn_fits_in_words(bn, num)) { 318 OPENSSL_PUT_ERROR(BN, BN_R_BIGNUM_TOO_LONG); 319 return 0; 320 } 321 width = num; 322 } 323 324 OPENSSL_memset(out, 0, sizeof(BN_ULONG) * num); 325 OPENSSL_memcpy(out, bn->d, sizeof(BN_ULONG) * width); 326 return 1; 327 } 328 329 int BN_is_negative(const BIGNUM *bn) { 330 return bn->neg != 0; 331 } 332 333 void BN_set_negative(BIGNUM *bn, int sign) { 334 if (sign && !BN_is_zero(bn)) { 335 bn->neg = 1; 336 } else { 337 bn->neg = 0; 338 } 339 } 340 341 int bn_wexpand(BIGNUM *bn, size_t words) { 342 BN_ULONG *a; 343 344 if (words <= (size_t)bn->dmax) { 345 return 1; 346 } 347 348 if (words > (INT_MAX / (4 * BN_BITS2))) { 349 OPENSSL_PUT_ERROR(BN, BN_R_BIGNUM_TOO_LONG); 350 return 0; 351 } 352 353 if (bn->flags & BN_FLG_STATIC_DATA) { 354 OPENSSL_PUT_ERROR(BN, BN_R_EXPAND_ON_STATIC_BIGNUM_DATA); 355 return 0; 356 } 357 358 a = OPENSSL_malloc(sizeof(BN_ULONG) * words); 359 if (a == NULL) { 360 OPENSSL_PUT_ERROR(BN, ERR_R_MALLOC_FAILURE); 361 return 0; 362 } 363 364 OPENSSL_memcpy(a, bn->d, sizeof(BN_ULONG) * bn->top); 365 366 OPENSSL_free(bn->d); 367 bn->d = a; 368 bn->dmax = (int)words; 369 370 return 1; 371 } 372 373 int bn_expand(BIGNUM *bn, size_t bits) { 374 if (bits + BN_BITS2 - 1 < bits) { 375 OPENSSL_PUT_ERROR(BN, BN_R_BIGNUM_TOO_LONG); 376 return 0; 377 } 378 return bn_wexpand(bn, (bits+BN_BITS2-1)/BN_BITS2); 379 } 380 381 int bn_resize_words(BIGNUM *bn, size_t words) { 382 if ((size_t)bn->top <= words) { 383 if (!bn_wexpand(bn, words)) { 384 return 0; 385 } 386 OPENSSL_memset(bn->d + bn->top, 0, (words - bn->top) * sizeof(BN_ULONG)); 387 bn->top = words; 388 return 1; 389 } 390 391 // All words beyond the new width must be zero. 392 if (!bn_fits_in_words(bn, words)) { 393 OPENSSL_PUT_ERROR(BN, BN_R_BIGNUM_TOO_LONG); 394 return 0; 395 } 396 bn->top = words; 397 return 1; 398 } 399 400 int bn_minimal_width(const BIGNUM *bn) { 401 int ret = bn->top; 402 while (ret > 0 && bn->d[ret - 1] == 0) { 403 ret--; 404 } 405 return ret; 406 } 407 408 void bn_correct_top(BIGNUM *bn) { 409 bn->top = bn_minimal_width(bn); 410 if (bn->top == 0) { 411 bn->neg = 0; 412 } 413 } 414