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