legacy-libs/grpc-cloned/deps/grpc/third_party/boringssl/crypto/fipsmodule/bn/bn.c

   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
  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->width)) {
 152     return NULL;
 153   }
 154
 155   OPENSSL_memcpy(dest->d, src->d, sizeof(src->d[0]) * src->width);
 156
 157   dest->width = src->width;
 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->width = 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->width = 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   // Look at the upper half of |x|. |x| is at most 64 bits long.
 191   x = l >> 32;
 192   // Set |mask| to all ones if |x| (the top 32 bits of |l|) is non-zero and all
 193   // all zeros otherwise.
 194   mask = 0u - x;
 195   mask = (0u - (mask >> (BN_BITS2 - 1)));
 196   // If |x| is non-zero, the lower half is included in the bit count in full,
 197   // and we count the upper half. Otherwise, we count the lower half.
 198   bits += 32 & mask;
 199   l ^= (x ^ l) & mask;  // |l| is |x| if |mask| and remains |l| otherwise.
 200 #endif
 201
 202   // The remaining blocks are analogous iterations at lower powers of two.
 203   x = l >> 16;
 204   mask = 0u - x;
 205   mask = (0u - (mask >> (BN_BITS2 - 1)));
 206   bits += 16 & mask;
 207   l ^= (x ^ l) & mask;
 208
 209   x = l >> 8;
 210   mask = 0u - x;
 211   mask = (0u - (mask >> (BN_BITS2 - 1)));
 212   bits += 8 & mask;
 213   l ^= (x ^ l) & mask;
 214
 215   x = l >> 4;
 216   mask = 0u - x;
 217   mask = (0u - (mask >> (BN_BITS2 - 1)));
 218   bits += 4 & mask;
 219   l ^= (x ^ l) & mask;
 220
 221   x = l >> 2;
 222   mask = 0u - x;
 223   mask = (0u - (mask >> (BN_BITS2 - 1)));
 224   bits += 2 & mask;
 225   l ^= (x ^ l) & mask;
 226
 227   x = l >> 1;
 228   mask = 0u - x;
 229   mask = (0u - (mask >> (BN_BITS2 - 1)));
 230   bits += 1 & mask;
 231
 232   return bits;
 233 }
 234
 235 unsigned BN_num_bits(const BIGNUM *bn) {
 236   const int width = bn_minimal_width(bn);
 237   if (width == 0) {
 238     return 0;
 239   }
 240
 241   return (width - 1) * BN_BITS2 + BN_num_bits_word(bn->d[width - 1]);
 242 }
 243
 244 unsigned BN_num_bytes(const BIGNUM *bn) {
 245   return (BN_num_bits(bn) + 7) / 8;
 246 }
 247
 248 void BN_zero(BIGNUM *bn) {
 249   bn->width = bn->neg = 0;
 250 }
 251
 252 int BN_one(BIGNUM *bn) {
 253   return BN_set_word(bn, 1);
 254 }
 255
 256 int BN_set_word(BIGNUM *bn, BN_ULONG value) {
 257   if (value == 0) {
 258     BN_zero(bn);
 259     return 1;
 260   }
 261
 262   if (!bn_wexpand(bn, 1)) {
 263     return 0;
 264   }
 265
 266   bn->neg = 0;
 267   bn->d[0] = value;
 268   bn->width = 1;
 269   return 1;
 270 }
 271
 272 int BN_set_u64(BIGNUM *bn, uint64_t value) {
 273 #if BN_BITS2 == 64
 274   return BN_set_word(bn, value);
 275 #elif BN_BITS2 == 32
 276   if (value <= BN_MASK2) {
 277     return BN_set_word(bn, (BN_ULONG)value);
 278   }
 279
 280   if (!bn_wexpand(bn, 2)) {
 281     return 0;
 282   }
 283
 284   bn->neg = 0;
 285   bn->d[0] = (BN_ULONG)value;
 286   bn->d[1] = (BN_ULONG)(value >> 32);
 287   bn->width = 2;
 288   return 1;
 289 #else
 290 #error "BN_BITS2 must be 32 or 64."
 291 #endif
 292 }
 293
 294 int bn_set_words(BIGNUM *bn, const BN_ULONG *words, size_t num) {
 295   if (!bn_wexpand(bn, num)) {
 296     return 0;
 297   }
 298   OPENSSL_memmove(bn->d, words, num * sizeof(BN_ULONG));
 299   // |bn_wexpand| verified that |num| isn't too large.
 300   bn->width = (int)num;
 301   bn->neg = 0;
 302   return 1;
 303 }
 304
 305 int bn_fits_in_words(const BIGNUM *bn, size_t num) {
 306   // All words beyond |num| must be zero.
 307   BN_ULONG mask = 0;
 308   for (size_t i = num; i < (size_t)bn->width; i++) {
 309     mask |= bn->d[i];
 310   }
 311   return mask == 0;
 312 }
 313
 314 int bn_copy_words(BN_ULONG *out, size_t num, const BIGNUM *bn) {
 315   if (bn->neg) {
 316     OPENSSL_PUT_ERROR(BN, BN_R_NEGATIVE_NUMBER);
 317     return 0;
 318   }
 319
 320   size_t width = (size_t)bn->width;
 321   if (width > num) {
 322     if (!bn_fits_in_words(bn, num)) {
 323       OPENSSL_PUT_ERROR(BN, BN_R_BIGNUM_TOO_LONG);
 324       return 0;
 325     }
 326     width = num;
 327   }
 328
 329   OPENSSL_memset(out, 0, sizeof(BN_ULONG) * num);
 330   OPENSSL_memcpy(out, bn->d, sizeof(BN_ULONG) * width);
 331   return 1;
 332 }
 333
 334 int BN_is_negative(const BIGNUM *bn) {
 335   return bn->neg != 0;
 336 }
 337
 338 void BN_set_negative(BIGNUM *bn, int sign) {
 339   if (sign && !BN_is_zero(bn)) {
 340     bn->neg = 1;
 341   } else {
 342     bn->neg = 0;
 343   }
 344 }
 345
 346 int bn_wexpand(BIGNUM *bn, size_t words) {
 347   BN_ULONG *a;
 348
 349   if (words <= (size_t)bn->dmax) {
 350     return 1;
 351   }
 352
 353   if (words > (INT_MAX / (4 * BN_BITS2))) {
 354     OPENSSL_PUT_ERROR(BN, BN_R_BIGNUM_TOO_LONG);
 355     return 0;
 356   }
 357
 358   if (bn->flags & BN_FLG_STATIC_DATA) {
 359     OPENSSL_PUT_ERROR(BN, BN_R_EXPAND_ON_STATIC_BIGNUM_DATA);
 360     return 0;
 361   }
 362
 363   a = OPENSSL_malloc(sizeof(BN_ULONG) * words);
 364   if (a == NULL) {
 365     OPENSSL_PUT_ERROR(BN, ERR_R_MALLOC_FAILURE);
 366     return 0;
 367   }
 368
 369   OPENSSL_memcpy(a, bn->d, sizeof(BN_ULONG) * bn->width);
 370
 371   OPENSSL_free(bn->d);
 372   bn->d = a;
 373   bn->dmax = (int)words;
 374
 375   return 1;
 376 }
 377
 378 int bn_expand(BIGNUM *bn, size_t bits) {
 379   if (bits + BN_BITS2 - 1 < bits) {
 380     OPENSSL_PUT_ERROR(BN, BN_R_BIGNUM_TOO_LONG);
 381     return 0;
 382   }
 383   return bn_wexpand(bn, (bits+BN_BITS2-1)/BN_BITS2);
 384 }
 385
 386 int bn_resize_words(BIGNUM *bn, size_t words) {
 387   if ((size_t)bn->width <= words) {
 388     if (!bn_wexpand(bn, words)) {
 389       return 0;
 390     }
 391     OPENSSL_memset(bn->d + bn->width, 0,
 392                    (words - bn->width) * sizeof(BN_ULONG));
 393     bn->width = words;
 394     return 1;
 395   }
 396
 397   // All words beyond the new width must be zero.
 398   if (!bn_fits_in_words(bn, words)) {
 399     OPENSSL_PUT_ERROR(BN, BN_R_BIGNUM_TOO_LONG);
 400     return 0;
 401   }
 402   bn->width = words;
 403   return 1;
 404 }
 405
 406 void bn_select_words(BN_ULONG *r, BN_ULONG mask, const BN_ULONG *a,
 407                      const BN_ULONG *b, size_t num) {
 408   for (size_t i = 0; i < num; i++) {
 409     OPENSSL_COMPILE_ASSERT(sizeof(BN_ULONG) <= sizeof(crypto_word_t),
 410                            crypto_word_t_too_small);
 411     r[i] = constant_time_select_w(mask, a[i], b[i]);
 412   }
 413 }
 414
 415 int bn_minimal_width(const BIGNUM *bn) {
 416   int ret = bn->width;
 417   while (ret > 0 && bn->d[ret - 1] == 0) {
 418     ret--;
 419   }
 420   return ret;
 421 }
 422
 423 void bn_set_minimal_width(BIGNUM *bn) {
 424   bn->width = bn_minimal_width(bn);
 425   if (bn->width == 0) {
 426     bn->neg = 0;
 427   }
 428 }