legacy-libs/grpc/deps/grpc/third_party/boringssl/crypto/bn_extra/convert.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 <assert.h>
  60 #include <ctype.h>
  61 #include <limits.h>
  62 #include <stdio.h>
  63
  64 #include <openssl/bio.h>
  65 #include <openssl/bytestring.h>
  66 #include <openssl/err.h>
  67 #include <openssl/mem.h>
  68
  69 #include "../fipsmodule/bn/internal.h"
  70
  71
  72 int BN_bn2cbb_padded(CBB *out, size_t len, const BIGNUM *in) {
  73   uint8_t *ptr;
  74   return CBB_add_space(out, &ptr, len) && BN_bn2bin_padded(ptr, len, in);
  75 }
  76
  77 static const char hextable[] = "0123456789abcdef";
  78
  79 char *BN_bn2hex(const BIGNUM *bn) {
  80   int width = bn_minimal_width(bn);
  81   char *buf = OPENSSL_malloc(1 /* leading '-' */ + 1 /* zero is non-empty */ +
  82                              width * BN_BYTES * 2 + 1 /* trailing NUL */);
  83   if (buf == NULL) {
  84     OPENSSL_PUT_ERROR(BN, ERR_R_MALLOC_FAILURE);
  85     return NULL;
  86   }
  87
  88   char *p = buf;
  89   if (bn->neg) {
  90     *(p++) = '-';
  91   }
  92
  93   if (BN_is_zero(bn)) {
  94     *(p++) = '0';
  95   }
  96
  97   int z = 0;
  98   for (int i = width - 1; i >= 0; i--) {
  99     for (int j = BN_BITS2 - 8; j >= 0; j -= 8) {
 100       // strip leading zeros
 101       int v = ((int)(bn->d[i] >> (long)j)) & 0xff;
 102       if (z || v != 0) {
 103         *(p++) = hextable[v >> 4];
 104         *(p++) = hextable[v & 0x0f];
 105         z = 1;
 106       }
 107     }
 108   }
 109   *p = '\0';
 110
 111   return buf;
 112 }
 113
 114 // decode_hex decodes |in_len| bytes of hex data from |in| and updates |bn|.
 115 static int decode_hex(BIGNUM *bn, const char *in, int in_len) {
 116   if (in_len > INT_MAX/4) {
 117     OPENSSL_PUT_ERROR(BN, BN_R_BIGNUM_TOO_LONG);
 118     return 0;
 119   }
 120   // |in_len| is the number of hex digits.
 121   if (!bn_expand(bn, in_len * 4)) {
 122     return 0;
 123   }
 124
 125   int i = 0;
 126   while (in_len > 0) {
 127     // Decode one |BN_ULONG| at a time.
 128     int todo = BN_BYTES * 2;
 129     if (todo > in_len) {
 130       todo = in_len;
 131     }
 132
 133     BN_ULONG word = 0;
 134     int j;
 135     for (j = todo; j > 0; j--) {
 136       char c = in[in_len - j];
 137
 138       BN_ULONG hex;
 139       if (c >= '0' && c <= '9') {
 140         hex = c - '0';
 141       } else if (c >= 'a' && c <= 'f') {
 142         hex = c - 'a' + 10;
 143       } else if (c >= 'A' && c <= 'F') {
 144         hex = c - 'A' + 10;
 145       } else {
 146         hex = 0;
 147         // This shouldn't happen. The caller checks |isxdigit|.
 148         assert(0);
 149       }
 150       word = (word << 4) | hex;
 151     }
 152
 153     bn->d[i++] = word;
 154     in_len -= todo;
 155   }
 156   assert(i <= bn->dmax);
 157   bn->width = i;
 158   return 1;
 159 }
 160
 161 // decode_dec decodes |in_len| bytes of decimal data from |in| and updates |bn|.
 162 static int decode_dec(BIGNUM *bn, const char *in, int in_len) {
 163   int i, j;
 164   BN_ULONG l = 0;
 165
 166   // Decode |BN_DEC_NUM| digits at a time.
 167   j = BN_DEC_NUM - (in_len % BN_DEC_NUM);
 168   if (j == BN_DEC_NUM) {
 169     j = 0;
 170   }
 171   l = 0;
 172   for (i = 0; i < in_len; i++) {
 173     l *= 10;
 174     l += in[i] - '0';
 175     if (++j == BN_DEC_NUM) {
 176       if (!BN_mul_word(bn, BN_DEC_CONV) ||
 177           !BN_add_word(bn, l)) {
 178         return 0;
 179       }
 180       l = 0;
 181       j = 0;
 182     }
 183   }
 184   return 1;
 185 }
 186
 187 typedef int (*decode_func) (BIGNUM *bn, const char *in, int in_len);
 188 typedef int (*char_test_func) (int c);
 189
 190 static int bn_x2bn(BIGNUM **outp, const char *in, decode_func decode, char_test_func want_char) {
 191   BIGNUM *ret = NULL;
 192   int neg = 0, i;
 193   int num;
 194
 195   if (in == NULL || *in == 0) {
 196     return 0;
 197   }
 198
 199   if (*in == '-') {
 200     neg = 1;
 201     in++;
 202   }
 203
 204   for (i = 0; want_char((unsigned char)in[i]) && i + neg < INT_MAX; i++) {}
 205
 206   num = i + neg;
 207   if (outp == NULL) {
 208     return num;
 209   }
 210
 211   // in is the start of the hex digits, and it is 'i' long
 212   if (*outp == NULL) {
 213     ret = BN_new();
 214     if (ret == NULL) {
 215       return 0;
 216     }
 217   } else {
 218     ret = *outp;
 219     BN_zero(ret);
 220   }
 221
 222   if (!decode(ret, in, i)) {
 223     goto err;
 224   }
 225
 226   bn_set_minimal_width(ret);
 227   if (!BN_is_zero(ret)) {
 228     ret->neg = neg;
 229   }
 230
 231   *outp = ret;
 232   return num;
 233
 234 err:
 235   if (*outp == NULL) {
 236     BN_free(ret);
 237   }
 238
 239   return 0;
 240 }
 241
 242 int BN_hex2bn(BIGNUM **outp, const char *in) {
 243   return bn_x2bn(outp, in, decode_hex, isxdigit);
 244 }
 245
 246 char *BN_bn2dec(const BIGNUM *a) {
 247   // It is easier to print strings little-endian, so we assemble it in reverse
 248   // and fix at the end.
 249   BIGNUM *copy = NULL;
 250   CBB cbb;
 251   if (!CBB_init(&cbb, 16) ||
 252       !CBB_add_u8(&cbb, 0 /* trailing NUL */)) {
 253     goto cbb_err;
 254   }
 255
 256   if (BN_is_zero(a)) {
 257     if (!CBB_add_u8(&cbb, '0')) {
 258       goto cbb_err;
 259     }
 260   } else {
 261     copy = BN_dup(a);
 262     if (copy == NULL) {
 263       goto err;
 264     }
 265
 266     while (!BN_is_zero(copy)) {
 267       BN_ULONG word = BN_div_word(copy, BN_DEC_CONV);
 268       if (word == (BN_ULONG)-1) {
 269         goto err;
 270       }
 271
 272       const int add_leading_zeros = !BN_is_zero(copy);
 273       for (int i = 0; i < BN_DEC_NUM && (add_leading_zeros || word != 0); i++) {
 274         if (!CBB_add_u8(&cbb, '0' + word % 10)) {
 275           goto cbb_err;
 276         }
 277         word /= 10;
 278       }
 279       assert(word == 0);
 280     }
 281   }
 282
 283   if (BN_is_negative(a) &&
 284       !CBB_add_u8(&cbb, '-')) {
 285     goto cbb_err;
 286   }
 287
 288   uint8_t *data;
 289   size_t len;
 290   if (!CBB_finish(&cbb, &data, &len)) {
 291     goto cbb_err;
 292   }
 293
 294   // Reverse the buffer.
 295   for (size_t i = 0; i < len/2; i++) {
 296     uint8_t tmp = data[i];
 297     data[i] = data[len - 1 - i];
 298     data[len - 1 - i] = tmp;
 299   }
 300
 301   BN_free(copy);
 302   return (char *)data;
 303
 304 cbb_err:
 305   OPENSSL_PUT_ERROR(BN, ERR_R_MALLOC_FAILURE);
 306 err:
 307   BN_free(copy);
 308   CBB_cleanup(&cbb);
 309   return NULL;
 310 }
 311
 312 int BN_dec2bn(BIGNUM **outp, const char *in) {
 313   return bn_x2bn(outp, in, decode_dec, isdigit);
 314 }
 315
 316 int BN_asc2bn(BIGNUM **outp, const char *in) {
 317   const char *const orig_in = in;
 318   if (*in == '-') {
 319     in++;
 320   }
 321
 322   if (in[0] == '0' && (in[1] == 'X' || in[1] == 'x')) {
 323     if (!BN_hex2bn(outp, in+2)) {
 324       return 0;
 325     }
 326   } else {
 327     if (!BN_dec2bn(outp, in)) {
 328       return 0;
 329     }
 330   }
 331
 332   if (*orig_in == '-' && !BN_is_zero(*outp)) {
 333     (*outp)->neg = 1;
 334   }
 335
 336   return 1;
 337 }
 338
 339 int BN_print(BIO *bp, const BIGNUM *a) {
 340   int i, j, v, z = 0;
 341   int ret = 0;
 342
 343   if (a->neg && BIO_write(bp, "-", 1) != 1) {
 344     goto end;
 345   }
 346
 347   if (BN_is_zero(a) && BIO_write(bp, "0", 1) != 1) {
 348     goto end;
 349   }
 350
 351   for (i = bn_minimal_width(a) - 1; i >= 0; i--) {
 352     for (j = BN_BITS2 - 4; j >= 0; j -= 4) {
 353       // strip leading zeros
 354       v = ((int)(a->d[i] >> (long)j)) & 0x0f;
 355       if (z || v != 0) {
 356         if (BIO_write(bp, &hextable[v], 1) != 1) {
 357           goto end;
 358         }
 359         z = 1;
 360       }
 361     }
 362   }
 363   ret = 1;
 364
 365 end:
 366   return ret;
 367 }
 368
 369 int BN_print_fp(FILE *fp, const BIGNUM *a) {
 370   BIO *b;
 371   int ret;
 372
 373   b = BIO_new(BIO_s_file());
 374   if (b == NULL) {
 375     return 0;
 376   }
 377   BIO_set_fp(b, fp, BIO_NOCLOSE);
 378   ret = BN_print(b, a);
 379   BIO_free(b);
 380
 381   return ret;
 382 }
 383
 384
 385 size_t BN_bn2mpi(const BIGNUM *in, uint8_t *out) {
 386   const size_t bits = BN_num_bits(in);
 387   const size_t bytes = (bits + 7) / 8;
 388   // If the number of bits is a multiple of 8, i.e. if the MSB is set,
 389   // prefix with a zero byte.
 390   int extend = 0;
 391   if (bytes != 0 && (bits & 0x07) == 0) {
 392     extend = 1;
 393   }
 394
 395   const size_t len = bytes + extend;
 396   if (len < bytes ||
 397       4 + len < len ||
 398       (len & 0xffffffff) != len) {
 399     // If we cannot represent the number then we emit zero as the interface
 400     // doesn't allow an error to be signalled.
 401     if (out) {
 402       OPENSSL_memset(out, 0, 4);
 403     }
 404     return 4;
 405   }
 406
 407   if (out == NULL) {
 408     return 4 + len;
 409   }
 410
 411   out[0] = len >> 24;
 412   out[1] = len >> 16;
 413   out[2] = len >> 8;
 414   out[3] = len;
 415   if (extend) {
 416     out[4] = 0;
 417   }
 418   BN_bn2bin(in, out + 4 + extend);
 419   if (in->neg && len > 0) {
 420     out[4] |= 0x80;
 421   }
 422   return len + 4;
 423 }
 424
 425 BIGNUM *BN_mpi2bn(const uint8_t *in, size_t len, BIGNUM *out) {
 426   if (len < 4) {
 427     OPENSSL_PUT_ERROR(BN, BN_R_BAD_ENCODING);
 428     return NULL;
 429   }
 430   const size_t in_len = ((size_t)in[0] << 24) |
 431                         ((size_t)in[1] << 16) |
 432                         ((size_t)in[2] << 8) |
 433                         ((size_t)in[3]);
 434   if (in_len != len - 4) {
 435     OPENSSL_PUT_ERROR(BN, BN_R_BAD_ENCODING);
 436     return NULL;
 437   }
 438
 439   int out_is_alloced = 0;
 440   if (out == NULL) {
 441     out = BN_new();
 442     if (out == NULL) {
 443       OPENSSL_PUT_ERROR(BN, ERR_R_MALLOC_FAILURE);
 444       return NULL;
 445     }
 446     out_is_alloced = 1;
 447   }
 448
 449   if (in_len == 0) {
 450     BN_zero(out);
 451     return out;
 452   }
 453
 454   in += 4;
 455   if (BN_bin2bn(in, in_len, out) == NULL) {
 456     if (out_is_alloced) {
 457       BN_free(out);
 458     }
 459     return NULL;
 460   }
 461   out->neg = ((*in) & 0x80) != 0;
 462   if (out->neg) {
 463     BN_clear_bit(out, BN_num_bits(out) - 1);
 464   }
 465   return out;
 466 }