1/* 2 * Copyright 1995-2017 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 "crypto/ctype.h" 12#include <limits.h> 13#include "internal/cryptlib.h" 14#include <openssl/buffer.h> 15#include "bn_local.h" 16 17static const char Hex[] = "0123456789ABCDEF"; 18 19/* Must 'OPENSSL_free' the returned data */ 20char *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 for (i = a->top - 1; i >= 0; i--) { 37 for (j = BN_BITS2 - 8; j >= 0; j -= 8) { 38 /* strip leading zeros */ 39 v = (int)((a->d[i] >> j) & 0xff); 40 if (z || v != 0) { 41 *p++ = Hex[v >> 4]; 42 *p++ = Hex[v & 0x0f]; 43 z = 1; 44 } 45 } 46 } 47 *p = '\0'; 48 err: 49 return buf; 50} 51 52/* Must 'OPENSSL_free' the returned data */ 53char *BN_bn2dec(const BIGNUM *a) 54{ 55 int i = 0, num, ok = 0, n, tbytes; 56 char *buf = NULL; 57 char *p; 58 BIGNUM *t = NULL; 59 BN_ULONG *bn_data = NULL, *lp; 60 int bn_data_num; 61 62 /*- 63 * get an upper bound for the length of the decimal integer 64 * num <= (BN_num_bits(a) + 1) * log(2) 65 * <= 3 * BN_num_bits(a) * 0.101 + log(2) + 1 (rounding error) 66 * <= 3 * BN_num_bits(a) / 10 + 3 * BN_num_bits / 1000 + 1 + 1 67 */ 68 i = BN_num_bits(a) * 3; 69 num = (i / 10 + i / 1000 + 1) + 1; 70 tbytes = num + 3; /* negative and terminator and one spare? */ 71 bn_data_num = num / BN_DEC_NUM + 1; 72 bn_data = OPENSSL_malloc(bn_data_num * sizeof(BN_ULONG)); 73 buf = OPENSSL_malloc(tbytes); 74 if (buf == NULL || bn_data == NULL) { 75 BNerr(BN_F_BN_BN2DEC, ERR_R_MALLOC_FAILURE); 76 goto err; 77 } 78 if ((t = BN_dup(a)) == NULL) 79 goto err; 80 81 p = buf; 82 lp = bn_data; 83 if (BN_is_zero(t)) { 84 *p++ = '0'; 85 *p++ = '\0'; 86 } else { 87 if (BN_is_negative(t)) 88 *p++ = '-'; 89 90 while (!BN_is_zero(t)) { 91 if (lp - bn_data >= bn_data_num) 92 goto err; 93 *lp = BN_div_word(t, BN_DEC_CONV); 94 if (*lp == (BN_ULONG)-1) 95 goto err; 96 lp++; 97 } 98 lp--; 99 /* 100 * We now have a series of blocks, BN_DEC_NUM chars in length, where 101 * the last one needs truncation. The blocks need to be reversed in 102 * order. 103 */ 104 n = BIO_snprintf(p, tbytes - (size_t)(p - buf), BN_DEC_FMT1, *lp); 105 if (n < 0) 106 goto err; 107 p += n; 108 while (lp != bn_data) { 109 lp--; 110 n = BIO_snprintf(p, tbytes - (size_t)(p - buf), BN_DEC_FMT2, *lp); 111 if (n < 0) 112 goto err; 113 p += n; 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 126int 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 && ossl_isxdigit(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 199int 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 && ossl_isdigit(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 269int 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 290int 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 304int 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] >> 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 329char *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(%zu,%zu)", 338 sizeof(BN_ULLONG) * 8, sizeof(BN_ULONG) * 8); 339#else 340 BIO_snprintf(data, sizeof(data), "bn(%zu,%zu)", 341 sizeof(BN_ULONG) * 8, sizeof(BN_ULONG) * 8); 342#endif 343 } 344 return data; 345} 346