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