[331] | 1 | /*
|
---|
| 2 | * Copyright 1995-2016 The OpenSSL Project Authors. All Rights Reserved.
|
---|
| 3 | *
|
---|
| 4 | * Licensed under the OpenSSL license (the "License"). You may not use
|
---|
| 5 | * this file except in compliance with the License. You can obtain a copy
|
---|
| 6 | * in the file LICENSE in the source distribution or at
|
---|
| 7 | * https://www.openssl.org/source/license.html
|
---|
| 8 | */
|
---|
| 9 |
|
---|
| 10 | #include <stdio.h>
|
---|
| 11 | #include <ctype.h>
|
---|
| 12 | #include <limits.h>
|
---|
| 13 | #include "internal/cryptlib.h"
|
---|
| 14 | #include <openssl/buffer.h>
|
---|
| 15 | #include "bn_lcl.h"
|
---|
| 16 |
|
---|
| 17 | static const char Hex[] = "0123456789ABCDEF";
|
---|
| 18 |
|
---|
| 19 | /* Must 'OPENSSL_free' the returned data */
|
---|
| 20 | char *BN_bn2hex(const BIGNUM *a)
|
---|
| 21 | {
|
---|
| 22 | int i, j, v, z = 0;
|
---|
| 23 | char *buf;
|
---|
| 24 | char *p;
|
---|
| 25 |
|
---|
| 26 | if (BN_is_zero(a))
|
---|
| 27 | return OPENSSL_strdup("0");
|
---|
| 28 | buf = OPENSSL_malloc(a->top * BN_BYTES * 2 + 2);
|
---|
| 29 | if (buf == NULL) {
|
---|
| 30 | BNerr(BN_F_BN_BN2HEX, ERR_R_MALLOC_FAILURE);
|
---|
| 31 | goto err;
|
---|
| 32 | }
|
---|
| 33 | p = buf;
|
---|
| 34 | if (a->neg)
|
---|
| 35 | *(p++) = '-';
|
---|
| 36 | if (BN_is_zero(a))
|
---|
| 37 | *(p++) = '0';
|
---|
| 38 | for (i = a->top - 1; i >= 0; i--) {
|
---|
| 39 | for (j = BN_BITS2 - 8; j >= 0; j -= 8) {
|
---|
| 40 | /* strip leading zeros */
|
---|
| 41 | v = ((int)(a->d[i] >> (long)j)) & 0xff;
|
---|
| 42 | if (z || (v != 0)) {
|
---|
| 43 | *(p++) = Hex[v >> 4];
|
---|
| 44 | *(p++) = Hex[v & 0x0f];
|
---|
| 45 | z = 1;
|
---|
| 46 | }
|
---|
| 47 | }
|
---|
| 48 | }
|
---|
| 49 | *p = '\0';
|
---|
| 50 | err:
|
---|
| 51 | return (buf);
|
---|
| 52 | }
|
---|
| 53 |
|
---|
| 54 | /* Must 'OPENSSL_free' the returned data */
|
---|
| 55 | char *BN_bn2dec(const BIGNUM *a)
|
---|
| 56 | {
|
---|
| 57 | int i = 0, num, ok = 0;
|
---|
| 58 | char *buf = NULL;
|
---|
| 59 | char *p;
|
---|
| 60 | BIGNUM *t = NULL;
|
---|
| 61 | BN_ULONG *bn_data = NULL, *lp;
|
---|
| 62 | int bn_data_num;
|
---|
| 63 |
|
---|
| 64 | /*-
|
---|
| 65 | * get an upper bound for the length of the decimal integer
|
---|
| 66 | * num <= (BN_num_bits(a) + 1) * log(2)
|
---|
| 67 | * <= 3 * BN_num_bits(a) * 0.101 + log(2) + 1 (rounding error)
|
---|
| 68 | * <= 3 * BN_num_bits(a) / 10 + 3 * BN_num_bits / 1000 + 1 + 1
|
---|
| 69 | */
|
---|
| 70 | i = BN_num_bits(a) * 3;
|
---|
| 71 | num = (i / 10 + i / 1000 + 1) + 1;
|
---|
| 72 | bn_data_num = num / BN_DEC_NUM + 1;
|
---|
| 73 | bn_data = OPENSSL_malloc(bn_data_num * sizeof(BN_ULONG));
|
---|
| 74 | buf = OPENSSL_malloc(num + 3);
|
---|
| 75 | if ((buf == NULL) || (bn_data == NULL)) {
|
---|
| 76 | BNerr(BN_F_BN_BN2DEC, ERR_R_MALLOC_FAILURE);
|
---|
| 77 | goto err;
|
---|
| 78 | }
|
---|
| 79 | if ((t = BN_dup(a)) == NULL)
|
---|
| 80 | goto err;
|
---|
| 81 |
|
---|
| 82 | #define BUF_REMAIN (num+3 - (size_t)(p - buf))
|
---|
| 83 | p = buf;
|
---|
| 84 | lp = bn_data;
|
---|
| 85 | if (BN_is_zero(t)) {
|
---|
| 86 | *(p++) = '0';
|
---|
| 87 | *(p++) = '\0';
|
---|
| 88 | } else {
|
---|
| 89 | if (BN_is_negative(t))
|
---|
| 90 | *p++ = '-';
|
---|
| 91 |
|
---|
| 92 | while (!BN_is_zero(t)) {
|
---|
| 93 | if (lp - bn_data >= bn_data_num)
|
---|
| 94 | goto err;
|
---|
| 95 | *lp = BN_div_word(t, BN_DEC_CONV);
|
---|
| 96 | if (*lp == (BN_ULONG)-1)
|
---|
| 97 | goto err;
|
---|
| 98 | lp++;
|
---|
| 99 | }
|
---|
| 100 | lp--;
|
---|
| 101 | /*
|
---|
| 102 | * We now have a series of blocks, BN_DEC_NUM chars in length, where
|
---|
| 103 | * the last one needs truncation. The blocks need to be reversed in
|
---|
| 104 | * order.
|
---|
| 105 | */
|
---|
| 106 | BIO_snprintf(p, BUF_REMAIN, BN_DEC_FMT1, *lp);
|
---|
| 107 | while (*p)
|
---|
| 108 | p++;
|
---|
| 109 | while (lp != bn_data) {
|
---|
| 110 | lp--;
|
---|
| 111 | BIO_snprintf(p, BUF_REMAIN, BN_DEC_FMT2, *lp);
|
---|
| 112 | while (*p)
|
---|
| 113 | p++;
|
---|
| 114 | }
|
---|
| 115 | }
|
---|
| 116 | ok = 1;
|
---|
| 117 | err:
|
---|
| 118 | OPENSSL_free(bn_data);
|
---|
| 119 | BN_free(t);
|
---|
| 120 | if (ok)
|
---|
| 121 | return buf;
|
---|
| 122 | OPENSSL_free(buf);
|
---|
| 123 | return NULL;
|
---|
| 124 | }
|
---|
| 125 |
|
---|
| 126 | int BN_hex2bn(BIGNUM **bn, const char *a)
|
---|
| 127 | {
|
---|
| 128 | BIGNUM *ret = NULL;
|
---|
| 129 | BN_ULONG l = 0;
|
---|
| 130 | int neg = 0, h, m, i, j, k, c;
|
---|
| 131 | int num;
|
---|
| 132 |
|
---|
| 133 | if ((a == NULL) || (*a == '\0'))
|
---|
| 134 | return (0);
|
---|
| 135 |
|
---|
| 136 | if (*a == '-') {
|
---|
| 137 | neg = 1;
|
---|
| 138 | a++;
|
---|
| 139 | }
|
---|
| 140 |
|
---|
| 141 | for (i = 0; i <= (INT_MAX/4) && isxdigit((unsigned char)a[i]); i++)
|
---|
| 142 | continue;
|
---|
| 143 |
|
---|
| 144 | if (i == 0 || i > INT_MAX/4)
|
---|
| 145 | goto err;
|
---|
| 146 |
|
---|
| 147 | num = i + neg;
|
---|
| 148 | if (bn == NULL)
|
---|
| 149 | return (num);
|
---|
| 150 |
|
---|
| 151 | /* a is the start of the hex digits, and it is 'i' long */
|
---|
| 152 | if (*bn == NULL) {
|
---|
| 153 | if ((ret = BN_new()) == NULL)
|
---|
| 154 | return (0);
|
---|
| 155 | } else {
|
---|
| 156 | ret = *bn;
|
---|
| 157 | BN_zero(ret);
|
---|
| 158 | }
|
---|
| 159 |
|
---|
| 160 | /* i is the number of hex digits */
|
---|
| 161 | if (bn_expand(ret, i * 4) == NULL)
|
---|
| 162 | goto err;
|
---|
| 163 |
|
---|
| 164 | j = i; /* least significant 'hex' */
|
---|
| 165 | m = 0;
|
---|
| 166 | h = 0;
|
---|
| 167 | while (j > 0) {
|
---|
| 168 | m = ((BN_BYTES * 2) <= j) ? (BN_BYTES * 2) : j;
|
---|
| 169 | l = 0;
|
---|
| 170 | for (;;) {
|
---|
| 171 | c = a[j - m];
|
---|
| 172 | k = OPENSSL_hexchar2int(c);
|
---|
| 173 | if (k < 0)
|
---|
| 174 | k = 0; /* paranoia */
|
---|
| 175 | l = (l << 4) | k;
|
---|
| 176 |
|
---|
| 177 | if (--m <= 0) {
|
---|
| 178 | ret->d[h++] = l;
|
---|
| 179 | break;
|
---|
| 180 | }
|
---|
| 181 | }
|
---|
| 182 | j -= (BN_BYTES * 2);
|
---|
| 183 | }
|
---|
| 184 | ret->top = h;
|
---|
| 185 | bn_correct_top(ret);
|
---|
| 186 |
|
---|
| 187 | *bn = ret;
|
---|
| 188 | bn_check_top(ret);
|
---|
| 189 | /* Don't set the negative flag if it's zero. */
|
---|
| 190 | if (ret->top != 0)
|
---|
| 191 | ret->neg = neg;
|
---|
| 192 | return (num);
|
---|
| 193 | err:
|
---|
| 194 | if (*bn == NULL)
|
---|
| 195 | BN_free(ret);
|
---|
| 196 | return (0);
|
---|
| 197 | }
|
---|
| 198 |
|
---|
| 199 | int BN_dec2bn(BIGNUM **bn, const char *a)
|
---|
| 200 | {
|
---|
| 201 | BIGNUM *ret = NULL;
|
---|
| 202 | BN_ULONG l = 0;
|
---|
| 203 | int neg = 0, i, j;
|
---|
| 204 | int num;
|
---|
| 205 |
|
---|
| 206 | if ((a == NULL) || (*a == '\0'))
|
---|
| 207 | return (0);
|
---|
| 208 | if (*a == '-') {
|
---|
| 209 | neg = 1;
|
---|
| 210 | a++;
|
---|
| 211 | }
|
---|
| 212 |
|
---|
| 213 | for (i = 0; i <= (INT_MAX/4) && isdigit((unsigned char)a[i]); i++)
|
---|
| 214 | continue;
|
---|
| 215 |
|
---|
| 216 | if (i == 0 || i > INT_MAX/4)
|
---|
| 217 | goto err;
|
---|
| 218 |
|
---|
| 219 | num = i + neg;
|
---|
| 220 | if (bn == NULL)
|
---|
| 221 | return (num);
|
---|
| 222 |
|
---|
| 223 | /*
|
---|
| 224 | * a is the start of the digits, and it is 'i' long. We chop it into
|
---|
| 225 | * BN_DEC_NUM digits at a time
|
---|
| 226 | */
|
---|
| 227 | if (*bn == NULL) {
|
---|
| 228 | if ((ret = BN_new()) == NULL)
|
---|
| 229 | return (0);
|
---|
| 230 | } else {
|
---|
| 231 | ret = *bn;
|
---|
| 232 | BN_zero(ret);
|
---|
| 233 | }
|
---|
| 234 |
|
---|
| 235 | /* i is the number of digits, a bit of an over expand */
|
---|
| 236 | if (bn_expand(ret, i * 4) == NULL)
|
---|
| 237 | goto err;
|
---|
| 238 |
|
---|
| 239 | j = BN_DEC_NUM - (i % BN_DEC_NUM);
|
---|
| 240 | if (j == BN_DEC_NUM)
|
---|
| 241 | j = 0;
|
---|
| 242 | l = 0;
|
---|
| 243 | while (--i >= 0) {
|
---|
| 244 | l *= 10;
|
---|
| 245 | l += *a - '0';
|
---|
| 246 | a++;
|
---|
| 247 | if (++j == BN_DEC_NUM) {
|
---|
| 248 | if (!BN_mul_word(ret, BN_DEC_CONV)
|
---|
| 249 | || !BN_add_word(ret, l))
|
---|
| 250 | goto err;
|
---|
| 251 | l = 0;
|
---|
| 252 | j = 0;
|
---|
| 253 | }
|
---|
| 254 | }
|
---|
| 255 |
|
---|
| 256 | bn_correct_top(ret);
|
---|
| 257 | *bn = ret;
|
---|
| 258 | bn_check_top(ret);
|
---|
| 259 | /* Don't set the negative flag if it's zero. */
|
---|
| 260 | if (ret->top != 0)
|
---|
| 261 | ret->neg = neg;
|
---|
| 262 | return (num);
|
---|
| 263 | err:
|
---|
| 264 | if (*bn == NULL)
|
---|
| 265 | BN_free(ret);
|
---|
| 266 | return (0);
|
---|
| 267 | }
|
---|
| 268 |
|
---|
| 269 | int BN_asc2bn(BIGNUM **bn, const char *a)
|
---|
| 270 | {
|
---|
| 271 | const char *p = a;
|
---|
| 272 |
|
---|
| 273 | if (*p == '-')
|
---|
| 274 | p++;
|
---|
| 275 |
|
---|
| 276 | if (p[0] == '0' && (p[1] == 'X' || p[1] == 'x')) {
|
---|
| 277 | if (!BN_hex2bn(bn, p + 2))
|
---|
| 278 | return 0;
|
---|
| 279 | } else {
|
---|
| 280 | if (!BN_dec2bn(bn, p))
|
---|
| 281 | return 0;
|
---|
| 282 | }
|
---|
| 283 | /* Don't set the negative flag if it's zero. */
|
---|
| 284 | if (*a == '-' && (*bn)->top != 0)
|
---|
| 285 | (*bn)->neg = 1;
|
---|
| 286 | return 1;
|
---|
| 287 | }
|
---|
| 288 |
|
---|
| 289 | # ifndef OPENSSL_NO_STDIO
|
---|
| 290 | int BN_print_fp(FILE *fp, const BIGNUM *a)
|
---|
| 291 | {
|
---|
| 292 | BIO *b;
|
---|
| 293 | int ret;
|
---|
| 294 |
|
---|
| 295 | if ((b = BIO_new(BIO_s_file())) == NULL)
|
---|
| 296 | return (0);
|
---|
| 297 | BIO_set_fp(b, fp, BIO_NOCLOSE);
|
---|
| 298 | ret = BN_print(b, a);
|
---|
| 299 | BIO_free(b);
|
---|
| 300 | return (ret);
|
---|
| 301 | }
|
---|
| 302 | # endif
|
---|
| 303 |
|
---|
| 304 | int BN_print(BIO *bp, const BIGNUM *a)
|
---|
| 305 | {
|
---|
| 306 | int i, j, v, z = 0;
|
---|
| 307 | int ret = 0;
|
---|
| 308 |
|
---|
| 309 | if ((a->neg) && (BIO_write(bp, "-", 1) != 1))
|
---|
| 310 | goto end;
|
---|
| 311 | if (BN_is_zero(a) && (BIO_write(bp, "0", 1) != 1))
|
---|
| 312 | goto end;
|
---|
| 313 | for (i = a->top - 1; i >= 0; i--) {
|
---|
| 314 | for (j = BN_BITS2 - 4; j >= 0; j -= 4) {
|
---|
| 315 | /* strip leading zeros */
|
---|
| 316 | v = ((int)(a->d[i] >> (long)j)) & 0x0f;
|
---|
| 317 | if (z || (v != 0)) {
|
---|
| 318 | if (BIO_write(bp, &(Hex[v]), 1) != 1)
|
---|
| 319 | goto end;
|
---|
| 320 | z = 1;
|
---|
| 321 | }
|
---|
| 322 | }
|
---|
| 323 | }
|
---|
| 324 | ret = 1;
|
---|
| 325 | end:
|
---|
| 326 | return (ret);
|
---|
| 327 | }
|
---|
| 328 |
|
---|
| 329 | char *BN_options(void)
|
---|
| 330 | {
|
---|
| 331 | static int init = 0;
|
---|
| 332 | static char data[16];
|
---|
| 333 |
|
---|
| 334 | if (!init) {
|
---|
| 335 | init++;
|
---|
| 336 | #ifdef BN_LLONG
|
---|
| 337 | BIO_snprintf(data, sizeof data, "bn(%d,%d)",
|
---|
| 338 | (int)sizeof(BN_ULLONG) * 8, (int)sizeof(BN_ULONG) * 8);
|
---|
| 339 | #else
|
---|
| 340 | BIO_snprintf(data, sizeof data, "bn(%d,%d)",
|
---|
| 341 | (int)sizeof(BN_ULONG) * 8, (int)sizeof(BN_ULONG) * 8);
|
---|
| 342 | #endif
|
---|
| 343 | }
|
---|
| 344 | return (data);
|
---|
| 345 | }
|
---|