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 <ctype.h> 60 #include <stdio.h> 61 62 #include <openssl/bio.h> 63 #include <openssl/err.h> 64 #include <openssl/mem.h> 65 66 #include "internal.h" 67 68 BIGNUM *BN_bin2bn(const uint8_t *in, size_t len, BIGNUM *ret) { 69 unsigned num_words, m; 70 BN_ULONG word = 0; 71 BIGNUM *bn = NULL; 72 73 if (ret == NULL) { 74 ret = bn = BN_new(); 75 } 76 77 if (ret == NULL) { 78 return NULL; 79 } 80 81 if (len == 0) { 82 ret->top = 0; 83 return ret; 84 } 85 86 num_words = ((len - 1) / BN_BYTES) + 1; 87 m = (len - 1) % BN_BYTES; 88 if (bn_wexpand(ret, num_words) == NULL) { 89 if (bn) { 90 BN_free(bn); 91 } 92 return NULL; 93 } 94 95 ret->top = num_words; 96 ret->neg = 0; 97 98 while (len--) { 99 word = (word << 8) | *(in++); 100 if (m-- == 0) { 101 ret->d[--num_words] = word; 102 word = 0; 103 m = BN_BYTES - 1; 104 } 105 } 106 107 /* need to call this due to clear byte at top if avoiding having the top bit 108 * set (-ve number) */ 109 bn_correct_top(ret); 110 return ret; 111 } 112 113 size_t BN_bn2bin(const BIGNUM *in, uint8_t *out) { 114 size_t n, i; 115 BN_ULONG l; 116 117 n = i = BN_num_bytes(in); 118 while (i--) { 119 l = in->d[i / BN_BYTES]; 120 *(out++) = (unsigned char)(l >> (8 * (i % BN_BYTES))) & 0xff; 121 } 122 return n; 123 } 124 125 /* constant_time_select_ulong returns |x| if |v| is 1 and |y| if |v| is 0. Its 126 * behavior is undefined if |v| takes any other value. */ 127 static BN_ULONG constant_time_select_ulong(int v, BN_ULONG x, BN_ULONG y) { 128 BN_ULONG mask = v; 129 mask--; 130 131 return (~mask & x) | (mask & y); 132 } 133 134 /* constant_time_le_size_t returns 1 if |x| <= |y| and 0 otherwise. |x| and |y| 135 * must not have their MSBs set. */ 136 static int constant_time_le_size_t(size_t x, size_t y) { 137 return ((x - y - 1) >> (sizeof(size_t) * 8 - 1)) & 1; 138 } 139 140 /* read_word_padded returns the |i|'th word of |in|, if it is not out of 141 * bounds. Otherwise, it returns 0. It does so without branches on the size of 142 * |in|, however it necessarily does not have the same memory access pattern. If 143 * the access would be out of bounds, it reads the last word of |in|. |in| must 144 * not be zero. */ 145 static BN_ULONG read_word_padded(const BIGNUM *in, size_t i) { 146 /* Read |in->d[i]| if valid. Otherwise, read the last word. */ 147 BN_ULONG l = in->d[constant_time_select_ulong( 148 constant_time_le_size_t(in->dmax, i), in->dmax - 1, i)]; 149 150 /* Clamp to zero if above |d->top|. */ 151 return constant_time_select_ulong(constant_time_le_size_t(in->top, i), 0, l); 152 } 153 154 int BN_bn2bin_padded(uint8_t *out, size_t len, const BIGNUM *in) { 155 size_t i; 156 BN_ULONG l; 157 158 /* Special case for |in| = 0. Just branch as the probability is negligible. */ 159 if (BN_is_zero(in)) { 160 memset(out, 0, len); 161 return 1; 162 } 163 164 /* Check if the integer is too big. This case can exit early in non-constant 165 * time. */ 166 if (in->top > (len + (BN_BYTES - 1)) / BN_BYTES) { 167 return 0; 168 } 169 if ((len % BN_BYTES) != 0) { 170 l = read_word_padded(in, len / BN_BYTES); 171 if (l >> (8 * (len % BN_BYTES)) != 0) { 172 return 0; 173 } 174 } 175 176 /* Write the bytes out one by one. Serialization is done without branching on 177 * the bits of |in| or on |in->top|, but if the routine would otherwise read 178 * out of bounds, the memory access pattern can't be fixed. However, for an 179 * RSA key of size a multiple of the word size, the probability of BN_BYTES 180 * leading zero octets is low. 181 * 182 * See Falko Stenzke, "Manger's Attack revisited", ICICS 2010. */ 183 i = len; 184 while (i--) { 185 l = read_word_padded(in, i / BN_BYTES); 186 *(out++) = (uint8_t)(l >> (8 * (i % BN_BYTES))) & 0xff; 187 } 188 return 1; 189 } 190 191 static const char hextable[] = "0123456789abcdef"; 192 193 char *BN_bn2hex(const BIGNUM *bn) { 194 int i, j, v, z = 0; 195 char *buf; 196 char *p; 197 198 buf = (char *)OPENSSL_malloc(bn->top * BN_BYTES * 2 + 2); 199 if (buf == NULL) { 200 OPENSSL_PUT_ERROR(BN, BN_bn2hex, ERR_R_MALLOC_FAILURE); 201 return NULL; 202 } 203 204 p = buf; 205 if (bn->neg) { 206 *(p++) = '-'; 207 } 208 209 if (BN_is_zero(bn)) { 210 *(p++) = '0'; 211 } 212 213 for (i = bn->top - 1; i >= 0; i--) { 214 for (j = BN_BITS2 - 8; j >= 0; j -= 8) { 215 /* strip leading zeros */ 216 v = ((int)(bn->d[i] >> (long)j)) & 0xff; 217 if (z || v != 0) { 218 *(p++) = hextable[v >> 4]; 219 *(p++) = hextable[v & 0x0f]; 220 z = 1; 221 } 222 } 223 } 224 *p = '\0'; 225 226 return buf; 227 } 228 229 /* decode_hex decodes |i| bytes of hex data from |in| and updates |bn|. */ 230 static void decode_hex(BIGNUM *bn, const char *in, int i) { 231 int h, m, j, k, c; 232 BN_ULONG l=0; 233 234 j = i; /* least significant 'hex' */ 235 h = 0; 236 while (j > 0) { 237 m = ((BN_BYTES * 2) <= j) ? (BN_BYTES * 2) : j; 238 l = 0; 239 for (;;) { 240 c = in[j - m]; 241 if ((c >= '0') && (c <= '9')) { 242 k = c - '0'; 243 } else if ((c >= 'a') && (c <= 'f')) { 244 k = c - 'a' + 10; 245 } else if ((c >= 'A') && (c <= 'F')) { 246 k = c - 'A' + 10; 247 } else { 248 k = 0; /* paranoia */ 249 } 250 251 l = (l << 4) | k; 252 253 if (--m <= 0) { 254 bn->d[h++] = l; 255 break; 256 } 257 } 258 259 j -= (BN_BYTES * 2); 260 } 261 262 bn->top = h; 263 } 264 265 /* decode_dec decodes |i| bytes of decimal data from |in| and updates |bn|. */ 266 static void decode_dec(BIGNUM *bn, const char *in, int i) { 267 int j; 268 BN_ULONG l = 0; 269 270 j = BN_DEC_NUM - (i % BN_DEC_NUM); 271 if (j == BN_DEC_NUM) { 272 j = 0; 273 } 274 l = 0; 275 while (*in) { 276 l *= 10; 277 l += *in - '0'; 278 in++; 279 if (++j == BN_DEC_NUM) { 280 BN_mul_word(bn, BN_DEC_CONV); 281 BN_add_word(bn, l); 282 l = 0; 283 j = 0; 284 } 285 } 286 } 287 288 typedef void (*decode_func) (BIGNUM *bn, const char *in, int i); 289 typedef int (*char_test_func) (int c); 290 291 static int bn_x2bn(BIGNUM **outp, const char *in, decode_func decode, char_test_func want_char) { 292 BIGNUM *ret = NULL; 293 int neg = 0, i; 294 int num; 295 296 if (in == NULL || *in == 0) { 297 return 0; 298 } 299 300 if (*in == '-') { 301 neg = 1; 302 in++; 303 } 304 305 for (i = 0; want_char((unsigned char)in[i]); i++) {} 306 307 num = i + neg; 308 if (outp == NULL) { 309 return num; 310 } 311 312 /* in is the start of the hex digits, and it is 'i' long */ 313 if (*outp == NULL) { 314 ret = BN_new(); 315 if (ret == NULL) { 316 return 0; 317 } 318 } else { 319 ret = *outp; 320 BN_zero(ret); 321 } 322 ret->neg = neg; 323 324 /* i is the number of hex digests; */ 325 if (bn_expand(ret, i * 4) == NULL) { 326 goto err; 327 } 328 329 decode(ret, in, i); 330 331 bn_correct_top(ret); 332 333 *outp = ret; 334 return num; 335 336 err: 337 if (*outp == NULL) { 338 BN_free(ret); 339 } 340 341 return 0; 342 } 343 344 int BN_hex2bn(BIGNUM **outp, const char *in) { 345 return bn_x2bn(outp, in, decode_hex, isxdigit); 346 } 347 348 char *BN_bn2dec(const BIGNUM *a) { 349 int i = 0, num, ok = 0; 350 char *buf = NULL; 351 char *p; 352 BIGNUM *t = NULL; 353 BN_ULONG *bn_data = NULL, *lp; 354 355 /* get an upper bound for the length of the decimal integer 356 * num <= (BN_num_bits(a) + 1) * log(2) 357 * <= 3 * BN_num_bits(a) * 0.1001 + log(2) + 1 (rounding error) 358 * <= BN_num_bits(a)/10 + BN_num_bits/1000 + 1 + 1 359 */ 360 i = BN_num_bits(a) * 3; 361 num = i / 10 + i / 1000 + 1 + 1; 362 bn_data = 363 (BN_ULONG *)OPENSSL_malloc((num / BN_DEC_NUM + 1) * sizeof(BN_ULONG)); 364 buf = (char *)OPENSSL_malloc(num + 3); 365 if ((buf == NULL) || (bn_data == NULL)) { 366 OPENSSL_PUT_ERROR(BN, BN_bn2dec, ERR_R_MALLOC_FAILURE); 367 goto err; 368 } 369 t = BN_dup(a); 370 if (t == NULL) { 371 goto err; 372 } 373 374 #define BUF_REMAIN (num + 3 - (size_t)(p - buf)) 375 p = buf; 376 lp = bn_data; 377 if (BN_is_zero(t)) { 378 *(p++) = '0'; 379 *(p++) = '\0'; 380 } else { 381 if (BN_is_negative(t)) { 382 *p++ = '-'; 383 } 384 385 while (!BN_is_zero(t)) { 386 *lp = BN_div_word(t, BN_DEC_CONV); 387 lp++; 388 } 389 lp--; 390 /* We now have a series of blocks, BN_DEC_NUM chars 391 * in length, where the last one needs truncation. 392 * The blocks need to be reversed in order. */ 393 BIO_snprintf(p, BUF_REMAIN, BN_DEC_FMT1, *lp); 394 while (*p) { 395 p++; 396 } 397 while (lp != bn_data) { 398 lp--; 399 BIO_snprintf(p, BUF_REMAIN, BN_DEC_FMT2, *lp); 400 while (*p) { 401 p++; 402 } 403 } 404 } 405 ok = 1; 406 407 err: 408 if (bn_data != NULL) { 409 OPENSSL_free(bn_data); 410 } 411 if (t != NULL) { 412 BN_free(t); 413 } 414 if (!ok && buf) { 415 OPENSSL_free(buf); 416 buf = NULL; 417 } 418 419 return buf; 420 } 421 422 int BN_dec2bn(BIGNUM **outp, const char *in) { 423 return bn_x2bn(outp, in, decode_dec, isdigit); 424 } 425 426 int BN_asc2bn(BIGNUM **outp, const char *in) { 427 const char *const orig_in = in; 428 if (*in == '-') { 429 in++; 430 } 431 432 if (in[0] == '0' && (in[1] == 'X' || in[1] == 'x')) { 433 if (!BN_hex2bn(outp, in+2)) { 434 return 0; 435 } 436 } else { 437 if (!BN_dec2bn(outp, in)) { 438 return 0; 439 } 440 } 441 442 if (*orig_in == '-') { 443 (*outp)->neg = 1; 444 } 445 446 return 1; 447 } 448 449 int BN_print(BIO *bp, const BIGNUM *a) { 450 int i, j, v, z = 0; 451 int ret = 0; 452 453 if (a->neg && BIO_write(bp, "-", 1) != 1) { 454 goto end; 455 } 456 457 if (BN_is_zero(a) && BIO_write(bp, "0", 1) != 1) { 458 goto end; 459 } 460 461 for (i = a->top - 1; i >= 0; i--) { 462 for (j = BN_BITS2 - 4; j >= 0; j -= 4) { 463 /* strip leading zeros */ 464 v = ((int)(a->d[i] >> (long)j)) & 0x0f; 465 if (z || v != 0) { 466 if (BIO_write(bp, &hextable[v], 1) != 1) { 467 goto end; 468 } 469 z = 1; 470 } 471 } 472 } 473 ret = 1; 474 475 end: 476 return ret; 477 } 478 479 int BN_print_fp(FILE *fp, const BIGNUM *a) { 480 BIO *b; 481 int ret; 482 483 b = BIO_new(BIO_s_file()); 484 if (b == NULL) { 485 return 0; 486 } 487 BIO_set_fp(b, fp, BIO_NOCLOSE); 488 ret = BN_print(b, a); 489 BIO_free(b); 490 491 return ret; 492 } 493 494 BN_ULONG BN_get_word(const BIGNUM *bn) { 495 switch (bn->top) { 496 case 0: 497 return 0; 498 case 1: 499 return bn->d[0]; 500 default: 501 return BN_MASK2; 502 } 503 } 504
