lib/hcrypto/bn.c

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