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