1 /* $NetBSD: bn.c,v 1.2 2017/01/28 21:31:47 christos Exp $ */ 2 3 /* 4 * Copyright (c) 2006 Kungliga Tekniska Högskolan 5 * (Royal Institute of Technology, Stockholm, Sweden). 6 * All rights reserved. 7 * 8 * Redistribution and use in source and binary forms, with or without 9 * modification, are permitted provided that the following conditions 10 * are met: 11 * 12 * 1. Redistributions of source code must retain the above copyright 13 * notice, this list of conditions and the following disclaimer. 14 * 15 * 2. Redistributions in binary form must reproduce the above copyright 16 * notice, this list of conditions and the following disclaimer in the 17 * documentation and/or other materials provided with the distribution. 18 * 19 * 3. Neither the name of the Institute nor the names of its contributors 20 * may be used to endorse or promote products derived from this software 21 * without specific prior written permission. 22 * 23 * THIS SOFTWARE IS PROVIDED BY THE INSTITUTE AND CONTRIBUTORS ``AS IS'' AND 24 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 25 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 26 * ARE DISCLAIMED. IN NO EVENT SHALL THE INSTITUTE OR CONTRIBUTORS BE LIABLE 27 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 28 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 29 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 30 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 31 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 32 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 33 * SUCH DAMAGE. 34 */ 35 36 #include <config.h> 37 #include <krb5/roken.h> 38 39 #include <krb5/krb5-types.h> 40 #include <krb5/rfc2459_asn1.h> /* XXX */ 41 #include <krb5/der.h> 42 43 #include <bn.h> 44 #include <rand.h> 45 #include <krb5/hex.h> 46 47 BIGNUM * 48 BN_new(void) 49 { 50 heim_integer *hi; 51 hi = calloc(1, sizeof(*hi)); 52 return (BIGNUM *)hi; 53 } 54 55 void 56 BN_free(BIGNUM *bn) 57 { 58 BN_clear(bn); 59 free(bn); 60 } 61 62 void 63 BN_clear(BIGNUM *bn) 64 { 65 heim_integer *hi = (heim_integer *)bn; 66 if (hi->data) { 67 memset(hi->data, 0, hi->length); 68 free(hi->data); 69 } 70 memset(hi, 0, sizeof(*hi)); 71 } 72 73 void 74 BN_clear_free(BIGNUM *bn) 75 { 76 BN_free(bn); 77 } 78 79 BIGNUM * 80 BN_dup(const BIGNUM *bn) 81 { 82 BIGNUM *b = BN_new(); 83 if (der_copy_heim_integer((const heim_integer *)bn, (heim_integer *)b)) { 84 BN_free(b); 85 return NULL; 86 } 87 return b; 88 } 89 90 /* 91 * If the caller really want to know the number of bits used, subtract 92 * one from the length, multiply by 8, and then lookup in the table 93 * how many bits the hightest byte uses. 94 */ 95 int 96 BN_num_bits(const BIGNUM *bn) 97 { 98 static unsigned char num2bits[256] = { 99 0,1,2,2,3,3,3,3,4,4,4,4,4,4,4,4, 5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5, 100 6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6, 6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6, 101 7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7, 7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7, 102 7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7, 7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7, 103 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 104 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 105 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 106 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 107 }; 108 const heim_integer *i = (const void *)bn; 109 if (i->length == 0) 110 return 0; 111 return (i->length - 1) * 8 + num2bits[((unsigned char *)i->data)[0]]; 112 } 113 114 int 115 BN_num_bytes(const BIGNUM *bn) 116 { 117 return ((const heim_integer *)bn)->length; 118 } 119 120 /* 121 * Ignore negative flag. 122 */ 123 124 BIGNUM * 125 BN_bin2bn(const void *s, int len, BIGNUM *bn) 126 { 127 heim_integer *hi = (void *)bn; 128 129 if (len < 0) 130 return NULL; 131 132 if (hi == NULL) { 133 hi = (heim_integer *)BN_new(); 134 if (hi == NULL) 135 return NULL; 136 } 137 if (hi->data) 138 BN_clear((BIGNUM *)hi); 139 hi->negative = 0; 140 hi->data = malloc(len); 141 if (hi->data == NULL && len != 0) { 142 if (bn == NULL) 143 BN_free((BIGNUM *)hi); 144 return NULL; 145 } 146 hi->length = len; 147 memcpy(hi->data, s, len); 148 return (BIGNUM *)hi; 149 } 150 151 int 152 BN_bn2bin(const BIGNUM *bn, void *to) 153 { 154 const heim_integer *hi = (const void *)bn; 155 memcpy(to, hi->data, hi->length); 156 return hi->length; 157 } 158 159 int 160 BN_hex2bn(BIGNUM **bnp, const char *in) 161 { 162 int negative; 163 ssize_t ret; 164 size_t len; 165 void *data; 166 167 len = strlen(in); 168 data = malloc(len); 169 if (data == NULL) 170 return 0; 171 172 if (*in == '-') { 173 negative = 1; 174 in++; 175 } else 176 negative = 0; 177 178 ret = hex_decode(in, data, len); 179 if (ret < 0) { 180 free(data); 181 return 0; 182 } 183 184 *bnp = BN_bin2bn(data, ret, NULL); 185 free(data); 186 if (*bnp == NULL) 187 return 0; 188 BN_set_negative(*bnp, negative); 189 return 1; 190 } 191 192 char * 193 BN_bn2hex(const BIGNUM *bn) 194 { 195 ssize_t ret; 196 size_t len; 197 void *data; 198 char *str; 199 200 len = BN_num_bytes(bn); 201 data = malloc(len); 202 if (data == NULL) 203 return 0; 204 205 len = BN_bn2bin(bn, data); 206 207 ret = hex_encode(data, len, &str); 208 free(data); 209 if (ret < 0) 210 return 0; 211 212 return str; 213 } 214 215 int 216 BN_cmp(const BIGNUM *bn1, const BIGNUM *bn2) 217 { 218 return der_heim_integer_cmp((const heim_integer *)bn1, 219 (const heim_integer *)bn2); 220 } 221 222 void 223 BN_set_negative(BIGNUM *bn, int flag) 224 { 225 ((heim_integer *)bn)->negative = (flag ? 1 : 0); 226 } 227 228 int 229 BN_is_negative(const BIGNUM *bn) 230 { 231 return ((const heim_integer *)bn)->negative ? 1 : 0; 232 } 233 234 static const unsigned char is_set[8] = { 1, 2, 4, 8, 16, 32, 64, 128 }; 235 236 int 237 BN_is_bit_set(const BIGNUM *bn, int bit) 238 { 239 heim_integer *hi = (heim_integer *)bn; 240 unsigned char *p = hi->data; 241 242 if ((bit / 8) > hi->length || hi->length == 0) 243 return 0; 244 245 return p[hi->length - 1 - (bit / 8)] & is_set[bit % 8]; 246 } 247 248 int 249 BN_set_bit(BIGNUM *bn, int bit) 250 { 251 heim_integer *hi = (heim_integer *)bn; 252 unsigned char *p; 253 254 if ((bit / 8) > hi->length || hi->length == 0) { 255 size_t len = (bit + 7) / 8; 256 void *d = realloc(hi->data, len); 257 if (d == NULL) 258 return 0; 259 hi->data = d; 260 p = hi->data; 261 memset(&p[hi->length], 0, len); 262 hi->length = len; 263 } else 264 p = hi->data; 265 266 p[hi->length - 1 - (bit / 8)] |= is_set[bit % 8]; 267 return 1; 268 } 269 270 int 271 BN_clear_bit(BIGNUM *bn, int bit) 272 { 273 heim_integer *hi = (heim_integer *)bn; 274 unsigned char *p = hi->data; 275 276 if ((bit / 8) > hi->length || hi->length == 0) 277 return 0; 278 279 p[hi->length - 1 - (bit / 8)] &= (unsigned char)(~(is_set[bit % 8])); 280 281 return 1; 282 } 283 284 int 285 BN_set_word(BIGNUM *bn, unsigned long num) 286 { 287 unsigned char p[sizeof(num)]; 288 unsigned long num2; 289 int i, len; 290 291 for (num2 = num, i = 0; num2 > 0; i++) 292 num2 = num2 >> 8; 293 294 len = i; 295 for (; i > 0; i--) { 296 p[i - 1] = (num & 0xff); 297 num = num >> 8; 298 } 299 300 bn = BN_bin2bn(p, len, bn); 301 return bn != NULL; 302 } 303 304 unsigned long 305 BN_get_word(const BIGNUM *bn) 306 { 307 heim_integer *hi = (heim_integer *)bn; 308 unsigned long num = 0; 309 int i; 310 311 if (hi->negative || hi->length > sizeof(num)) 312 return ULONG_MAX; 313 314 for (i = 0; i < hi->length; i++) 315 num = ((unsigned char *)hi->data)[i] | (num << 8); 316 return num; 317 } 318 319 int 320 BN_rand(BIGNUM *bn, int bits, int top, int bottom) 321 { 322 size_t len = (bits + 7) / 8; 323 heim_integer *i = (heim_integer *)bn; 324 325 BN_clear(bn); 326 327 i->negative = 0; 328 i->data = malloc(len); 329 if (i->data == NULL && len != 0) 330 return 0; 331 i->length = len; 332 333 if (RAND_bytes(i->data, i->length) != 1) { 334 free(i->data); 335 i->data = NULL; 336 return 0; 337 } 338 339 { 340 size_t j = len * 8; 341 while(j > bits) { 342 BN_clear_bit(bn, j - 1); 343 j--; 344 } 345 } 346 347 if (top == -1) { 348 ; 349 } else if (top == 0 && bits > 0) { 350 BN_set_bit(bn, bits - 1); 351 } else if (top == 1 && bits > 1) { 352 BN_set_bit(bn, bits - 1); 353 BN_set_bit(bn, bits - 2); 354 } else { 355 BN_clear(bn); 356 return 0; 357 } 358 359 if (bottom && bits > 0) 360 BN_set_bit(bn, 0); 361 362 return 1; 363 } 364 365 /* 366 * 367 */ 368 369 int 370 BN_uadd(BIGNUM *res, const BIGNUM *a, const BIGNUM *b) 371 { 372 const heim_integer *ai = (const heim_integer *)a; 373 const heim_integer *bi = (const heim_integer *)b; 374 const unsigned char *ap, *bp; 375 unsigned char *cp; 376 heim_integer ci; 377 int carry = 0; 378 ssize_t len; 379 380 if (ai->negative && bi->negative) 381 return 0; 382 if (ai->length < bi->length) { 383 const heim_integer *si = bi; 384 bi = ai; ai = si; 385 } 386 387 ci.negative = 0; 388 ci.length = ai->length + 1; 389 ci.data = malloc(ci.length); 390 if (ci.data == NULL) 391 return 0; 392 393 ap = &((const unsigned char *)ai->data)[ai->length - 1]; 394 bp = &((const unsigned char *)bi->data)[bi->length - 1]; 395 cp = &((unsigned char *)ci.data)[ci.length - 1]; 396 397 for (len = bi->length; len > 0; len--) { 398 carry = *ap + *bp + carry; 399 *cp = carry & 0xff; 400 carry = (carry & ~0xff) ? 1 : 0; 401 ap--; bp--; cp--; 402 } 403 for (len = ai->length - bi->length; len > 0; len--) { 404 carry = *ap + carry; 405 *cp = carry & 0xff; 406 carry = (carry & ~0xff) ? 1 : 0; 407 ap--; cp--; 408 } 409 if (!carry) 410 memmove(cp, cp + 1, --ci.length); 411 else 412 *cp = carry; 413 414 BN_clear(res); 415 *((heim_integer *)res) = ci; 416 417 return 1; 418 } 419 420 421 /* 422 * Callback when doing slow generation of numbers, like primes. 423 */ 424 425 void 426 BN_GENCB_set(BN_GENCB *gencb, int (*cb_2)(int, int, BN_GENCB *), void *ctx) 427 { 428 gencb->ver = 2; 429 gencb->cb.cb_2 = cb_2; 430 gencb->arg = ctx; 431 } 432 433 int 434 BN_GENCB_call(BN_GENCB *cb, int a, int b) 435 { 436 if (cb == NULL || cb->cb.cb_2 == NULL) 437 return 1; 438 return cb->cb.cb_2(a, b, cb); 439 } 440 441 /* 442 * 443 */ 444 445 struct BN_CTX { 446 struct { 447 BIGNUM **val; 448 size_t used; 449 size_t len; 450 } bn; 451 struct { 452 size_t *val; 453 size_t used; 454 size_t len; 455 } stack; 456 }; 457 458 BN_CTX * 459 BN_CTX_new(void) 460 { 461 struct BN_CTX *c; 462 c = calloc(1, sizeof(*c)); 463 return c; 464 } 465 466 void 467 BN_CTX_free(BN_CTX *c) 468 { 469 size_t i; 470 for (i = 0; i < c->bn.len; i++) 471 BN_free(c->bn.val[i]); 472 free(c->bn.val); 473 free(c->stack.val); 474 } 475 476 BIGNUM * 477 BN_CTX_get(BN_CTX *c) 478 { 479 if (c->bn.used == c->bn.len) { 480 void *ptr; 481 size_t i; 482 c->bn.len += 16; 483 ptr = realloc(c->bn.val, c->bn.len * sizeof(c->bn.val[0])); 484 if (ptr == NULL) 485 return NULL; 486 c->bn.val = ptr; 487 for (i = c->bn.used; i < c->bn.len; i++) { 488 c->bn.val[i] = BN_new(); 489 if (c->bn.val[i] == NULL) { 490 c->bn.len = i; 491 return NULL; 492 } 493 } 494 } 495 return c->bn.val[c->bn.used++]; 496 } 497 498 void 499 BN_CTX_start(BN_CTX *c) 500 { 501 if (c->stack.used == c->stack.len) { 502 void *ptr; 503 c->stack.len += 16; 504 ptr = realloc(c->stack.val, c->stack.len * sizeof(c->stack.val[0])); 505 if (ptr == NULL) 506 abort(); 507 c->stack.val = ptr; 508 } 509 c->stack.val[c->stack.used++] = c->bn.used; 510 } 511 512 void 513 BN_CTX_end(BN_CTX *c) 514 { 515 const size_t prev = c->stack.val[c->stack.used - 1]; 516 size_t i; 517 518 if (c->stack.used == 0) 519 abort(); 520 521 for (i = prev; i < c->bn.used; i++) 522 BN_clear(c->bn.val[i]); 523 524 c->stack.used--; 525 c->bn.used = prev; 526 } 527 528