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