1/* $NetBSD: bn.c,v 1.3 2023/06/19 21:41:43 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 47BIGNUM * 48BN_new(void) 49{ 50 heim_integer *hi; 51 hi = calloc(1, sizeof(*hi)); 52 return (BIGNUM *)hi; 53} 54 55void 56BN_free(BIGNUM *bn) 57{ 58 BN_clear(bn); 59 free(bn); 60} 61 62void 63BN_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 73void 74BN_clear_free(BIGNUM *bn) 75{ 76 BN_free(bn); 77} 78 79BIGNUM * 80BN_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 */ 95int 96BN_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 114int 115BN_num_bytes(const BIGNUM *bn) 116{ 117 return ((const heim_integer *)bn)->length; 118} 119 120/* 121 * Ignore negative flag. 122 */ 123 124BIGNUM * 125BN_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 if (len) 148 memcpy(hi->data, s, len); 149 return (BIGNUM *)hi; 150} 151 152int 153BN_bn2bin(const BIGNUM *bn, void *to) 154{ 155 const heim_integer *hi = (const void *)bn; 156 memcpy(to, hi->data, hi->length); 157 return hi->length; 158} 159 160int 161BN_hex2bn(BIGNUM **bnp, const char *in) 162{ 163 int negative; 164 ssize_t ret; 165 size_t len; 166 void *data; 167 168 len = strlen(in); 169 data = malloc(len); 170 if (data == NULL) 171 return 0; 172 173 if (*in == '-') { 174 negative = 1; 175 in++; 176 } else 177 negative = 0; 178 179 ret = hex_decode(in, data, len); 180 if (ret < 0) { 181 free(data); 182 return 0; 183 } 184 185 *bnp = BN_bin2bn(data, ret, NULL); 186 free(data); 187 if (*bnp == NULL) 188 return 0; 189 BN_set_negative(*bnp, negative); 190 return 1; 191} 192 193char * 194BN_bn2hex(const BIGNUM *bn) 195{ 196 ssize_t ret; 197 size_t len; 198 void *data; 199 char *str; 200 201 len = BN_num_bytes(bn); 202 data = malloc(len); 203 if (data == NULL) 204 return 0; 205 206 len = BN_bn2bin(bn, data); 207 208 ret = hex_encode(data, len, &str); 209 free(data); 210 if (ret < 0) 211 return 0; 212 213 return str; 214} 215 216int 217BN_cmp(const BIGNUM *bn1, const BIGNUM *bn2) 218{ 219 return der_heim_integer_cmp((const heim_integer *)bn1, 220 (const heim_integer *)bn2); 221} 222 223void 224BN_set_negative(BIGNUM *bn, int flag) 225{ 226 ((heim_integer *)bn)->negative = (flag ? 1 : 0); 227} 228 229int 230BN_is_negative(const BIGNUM *bn) 231{ 232 return ((const heim_integer *)bn)->negative ? 1 : 0; 233} 234 235static const unsigned char is_set[8] = { 1, 2, 4, 8, 16, 32, 64, 128 }; 236 237int 238BN_is_bit_set(const BIGNUM *bn, int bit) 239{ 240 heim_integer *hi = (heim_integer *)bn; 241 unsigned char *p = hi->data; 242 243 if ((bit / 8) >= hi->length || hi->length == 0) 244 return 0; 245 246 return p[hi->length - 1 - (bit / 8)] & is_set[bit % 8]; 247} 248 249int 250BN_set_bit(BIGNUM *bn, int bit) 251{ 252 heim_integer *hi = (heim_integer *)bn; 253 unsigned char *p; 254 255 if ((bit / 8) > hi->length || hi->length == 0) { 256 size_t len = bit == 0 ? 1 : (bit + 7) / 8; 257 void *d = realloc(hi->data, len); 258 if (d == NULL) 259 return 0; 260 hi->data = d; 261 p = hi->data; 262 memset(&p[hi->length], 0, len); 263 hi->length = len; 264 } else 265 p = hi->data; 266 267 p[hi->length - 1 - (bit / 8)] |= is_set[bit % 8]; 268 return 1; 269} 270 271int 272BN_clear_bit(BIGNUM *bn, int bit) 273{ 274 heim_integer *hi = (heim_integer *)bn; 275 unsigned char *p = hi->data; 276 277 if ((bit / 8) > hi->length || hi->length == 0) 278 return 0; 279 280 p[hi->length - 1 - (bit / 8)] &= (unsigned char)(~(is_set[bit % 8])); 281 282 return 1; 283} 284 285int 286BN_set_word(BIGNUM *bn, unsigned long num) 287{ 288 unsigned char p[sizeof(num)]; 289 unsigned long num2; 290 int i, len; 291 292 for (num2 = num, i = 0; num2 > 0; i++) 293 num2 = num2 >> 8; 294 295 len = i; 296 for (; i > 0; i--) { 297 p[i - 1] = (num & 0xff); 298 num = num >> 8; 299 } 300 301 bn = BN_bin2bn(p, len, bn); 302 return bn != NULL; 303} 304 305unsigned long 306BN_get_word(const BIGNUM *bn) 307{ 308 heim_integer *hi = (heim_integer *)bn; 309 unsigned long num = 0; 310 int i; 311 312 if (hi->negative || hi->length > sizeof(num)) 313 return ULONG_MAX; 314 315 for (i = 0; i < hi->length; i++) 316 num = ((unsigned char *)hi->data)[i] | (num << 8); 317 return num; 318} 319 320int 321BN_rand(BIGNUM *bn, int bits, int top, int bottom) 322{ 323 size_t len = (bits + 7) / 8; 324 heim_integer *i = (heim_integer *)bn; 325 326 BN_clear(bn); 327 328 i->negative = 0; 329 i->data = malloc(len); 330 if (i->data == NULL && len != 0) 331 return 0; 332 i->length = len; 333 334 if (RAND_bytes(i->data, i->length) != 1) { 335 free(i->data); 336 i->data = NULL; 337 return 0; 338 } 339 340 { 341 size_t j = len * 8; 342 while(j > bits) { 343 BN_clear_bit(bn, j - 1); 344 j--; 345 } 346 } 347 348 if (top == -1) { 349 ; 350 } else if (top == 0 && bits > 0) { 351 BN_set_bit(bn, bits - 1); 352 } else if (top == 1 && bits > 1) { 353 BN_set_bit(bn, bits - 1); 354 BN_set_bit(bn, bits - 2); 355 } else { 356 BN_clear(bn); 357 return 0; 358 } 359 360 if (bottom && bits > 0) 361 BN_set_bit(bn, 0); 362 363 return 1; 364} 365 366/* 367 * 368 */ 369 370int 371BN_uadd(BIGNUM *res, const BIGNUM *a, const BIGNUM *b) 372{ 373 const heim_integer *ai = (const heim_integer *)a; 374 const heim_integer *bi = (const heim_integer *)b; 375 const unsigned char *ap, *bp; 376 unsigned char *cp; 377 heim_integer ci; 378 int carry = 0; 379 ssize_t len; 380 381 if (ai->negative && bi->negative) 382 return 0; 383 if (ai->length < bi->length) { 384 const heim_integer *si = bi; 385 bi = ai; ai = si; 386 } 387 388 ci.negative = 0; 389 ci.length = ai->length + 1; 390 ci.data = malloc(ci.length); 391 if (ci.data == NULL) 392 return 0; 393 394 ap = &((const unsigned char *)ai->data)[ai->length - 1]; 395 bp = &((const unsigned char *)bi->data)[bi->length - 1]; 396 cp = &((unsigned char *)ci.data)[ci.length - 1]; 397 398 for (len = bi->length; len > 0; len--) { 399 carry = *ap + *bp + carry; 400 *cp = carry & 0xff; 401 carry = (carry & ~0xff) ? 1 : 0; 402 ap--; bp--; cp--; 403 } 404 for (len = ai->length - bi->length; len > 0; len--) { 405 carry = *ap + carry; 406 *cp = carry & 0xff; 407 carry = (carry & ~0xff) ? 1 : 0; 408 ap--; cp--; 409 } 410 if (!carry) 411 memmove(cp, cp + 1, --ci.length); 412 else 413 *cp = carry; 414 415 BN_clear(res); 416 *((heim_integer *)res) = ci; 417 418 return 1; 419} 420 421 422/* 423 * Callback when doing slow generation of numbers, like primes. 424 */ 425 426void 427BN_GENCB_set(BN_GENCB *gencb, int (*cb_2)(int, int, BN_GENCB *), void *ctx) 428{ 429 gencb->ver = 2; 430 gencb->cb.cb_2 = cb_2; 431 gencb->arg = ctx; 432} 433 434int 435BN_GENCB_call(BN_GENCB *cb, int a, int b) 436{ 437 if (cb == NULL || cb->cb.cb_2 == NULL) 438 return 1; 439 return cb->cb.cb_2(a, b, cb); 440} 441 442/* 443 * 444 */ 445 446struct BN_CTX { 447 struct { 448 BIGNUM **val; 449 size_t used; 450 size_t len; 451 } bn; 452 struct { 453 size_t *val; 454 size_t used; 455 size_t len; 456 } stack; 457}; 458 459BN_CTX * 460BN_CTX_new(void) 461{ 462 struct BN_CTX *c; 463 c = calloc(1, sizeof(*c)); 464 return c; 465} 466 467void 468BN_CTX_free(BN_CTX *c) 469{ 470 size_t i; 471 for (i = 0; i < c->bn.len; i++) 472 BN_free(c->bn.val[i]); 473 free(c->bn.val); 474 free(c->stack.val); 475} 476 477BIGNUM * 478BN_CTX_get(BN_CTX *c) 479{ 480 if (c->bn.used == c->bn.len) { 481 void *ptr; 482 size_t i; 483 c->bn.len += 16; 484 ptr = realloc(c->bn.val, c->bn.len * sizeof(c->bn.val[0])); 485 if (ptr == NULL) 486 return NULL; 487 c->bn.val = ptr; 488 for (i = c->bn.used; i < c->bn.len; i++) { 489 c->bn.val[i] = BN_new(); 490 if (c->bn.val[i] == NULL) { 491 c->bn.len = i; 492 return NULL; 493 } 494 } 495 } 496 return c->bn.val[c->bn.used++]; 497} 498 499void 500BN_CTX_start(BN_CTX *c) 501{ 502 if (c->stack.used == c->stack.len) { 503 void *ptr; 504 c->stack.len += 16; 505 ptr = realloc(c->stack.val, c->stack.len * sizeof(c->stack.val[0])); 506 if (ptr == NULL) 507 abort(); 508 c->stack.val = ptr; 509 } 510 c->stack.val[c->stack.used++] = c->bn.used; 511} 512 513void 514BN_CTX_end(BN_CTX *c) 515{ 516 const size_t prev = c->stack.val[c->stack.used - 1]; 517 size_t i; 518 519 if (c->stack.used == 0) 520 abort(); 521 522 for (i = prev; i < c->bn.used; i++) 523 BN_clear(c->bn.val[i]); 524 525 c->stack.used--; 526 c->bn.used = prev; 527} 528 529