source4/heimdal/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 #ifdef HAVE_CONFIG_H
  35 #include <config.h>
  36 #endif
  37
  38 RCSID("$Id: bn.c 22261 2007-12-09 06:24:18Z lha $");
  39
  40 #include <stdio.h>
  41 #include <stdlib.h>
  42 #include <string.h>
  43 #include <limits.h>
  44
  45 #include <krb5-types.h>
  46 #include <rfc2459_asn1.h> /* XXX */
  47 #include <der.h>
  48
  49 #include <bn.h>
  50 #include <rand.h>
  51 #include <hex.h>
  52
  53 BIGNUM *
  54 BN_new(void)
  55 {
  56     heim_integer *hi;
  57     hi = calloc(1, sizeof(*hi));
  58     return (BIGNUM *)hi;
  59 }
  60
  61 void
  62 BN_free(BIGNUM *bn)
  63 {
  64     BN_clear(bn);
  65     free(bn);
  66 }
  67
  68 void
  69 BN_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
  79 void
  80 BN_clear_free(BIGNUM *bn)
  81 {
  82     BN_free(bn);
  83 }
  84
  85 BIGNUM *
  86 BN_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  */
 101 int
 102 BN_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
 120 int
 121 BN_num_bytes(const BIGNUM *bn)
 122 {
 123     return ((const heim_integer *)bn)->length;
 124 }
 125
 126 /*
 127  * Ignore negative flag.
 128  */
 129
 130 BIGNUM *
 131 BN_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
 157 int
 158 BN_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
 165 int
 166 BN_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
 198 char *
 199 BN_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
 221 int
 222 BN_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
 228 void
 229 BN_set_negative(BIGNUM *bn, int flag)
 230 {
 231     ((heim_integer *)bn)->negative = (flag ? 1 : 0);
 232 }
 233
 234 int
 235 BN_is_negative(const BIGNUM *bn)
 236 {
 237     return ((const heim_integer *)bn)->negative ? 1 : 0;
 238 }
 239
 240 static const unsigned char is_set[8] = { 1, 2, 4, 8, 16, 32, 64, 128 };
 241
 242 int
 243 BN_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
 254 int
 255 BN_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
 276 int
 277 BN_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
 290 int
 291 BN_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 - 1;
 301     for (; i > 0; i--) {
 302         p[i - 1] = (num & 0xff);
 303         num = num >> 8;
 304     }
 305
 306     bn = BN_bin2bn(p, len + 1, bn);
 307     return bn != NULL;
 308 }
 309
 310 unsigned long
 311 BN_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
 325 int
 326 BN_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
 375 int
 376 BN_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
 431 void
 432 BN_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
 439 int
 440 BN_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 }