summaryrefslogtreecommitdiffstats
path: root/third_party/heimdal/lib/hcrypto/bn.c
diff options
context:
space:
mode:
Diffstat (limited to 'third_party/heimdal/lib/hcrypto/bn.c')
-rw-r--r--third_party/heimdal/lib/hcrypto/bn.c529
1 files changed, 529 insertions, 0 deletions
diff --git a/third_party/heimdal/lib/hcrypto/bn.c b/third_party/heimdal/lib/hcrypto/bn.c
new file mode 100644
index 0000000..62297b1
--- /dev/null
+++ b/third_party/heimdal/lib/hcrypto/bn.c
@@ -0,0 +1,529 @@
+/*
+ * Copyright (c) 2006 Kungliga Tekniska Högskolan
+ * (Royal Institute of Technology, Stockholm, Sweden).
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ *
+ * 1. Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ *
+ * 2. Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution.
+ *
+ * 3. Neither the name of the Institute nor the names of its contributors
+ * may be used to endorse or promote products derived from this software
+ * without specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE INSTITUTE AND CONTRIBUTORS ``AS IS'' AND
+ * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED. IN NO EVENT SHALL THE INSTITUTE OR CONTRIBUTORS BE LIABLE
+ * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
+ * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
+ * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
+ * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ */
+
+#include <config.h>
+#include <roken.h>
+
+#include <krb5-types.h>
+#include <rfc2459_asn1.h> /* XXX */
+#include <der.h>
+
+#include <bn.h>
+#include <rand.h>
+#include <hex.h>
+
+BIGNUM *
+BN_new(void)
+{
+ heim_integer *hi;
+ hi = calloc(1, sizeof(*hi));
+ return (BIGNUM *)hi;
+}
+
+void
+BN_free(BIGNUM *bn)
+{
+ BN_clear(bn);
+ free(bn);
+}
+
+void
+BN_clear(BIGNUM *bn)
+{
+ heim_integer *hi = (heim_integer *)bn;
+ if (hi->data) {
+ memset(hi->data, 0, hi->length);
+ free(hi->data);
+ }
+ memset(hi, 0, sizeof(*hi));
+}
+
+void
+BN_clear_free(BIGNUM *bn)
+{
+ BN_free(bn);
+}
+
+BIGNUM *
+BN_dup(const BIGNUM *bn)
+{
+ BIGNUM *b = BN_new();
+ if (der_copy_heim_integer((const heim_integer *)bn, (heim_integer *)b)) {
+ BN_free(b);
+ return NULL;
+ }
+ return b;
+}
+
+/*
+ * If the caller really want to know the number of bits used, subtract
+ * one from the length, multiply by 8, and then lookup in the table
+ * how many bits the hightest byte uses.
+ */
+int
+BN_num_bits(const BIGNUM *bn)
+{
+ static unsigned char num2bits[256] = {
+ 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,
+ 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,
+ 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,
+ 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,
+ 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,
+ 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,
+ 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,
+ 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,
+ };
+ const heim_integer *i = (const void *)bn;
+ if (i->length == 0)
+ return 0;
+ return (i->length - 1) * 8 + num2bits[((unsigned char *)i->data)[0]];
+}
+
+int
+BN_num_bytes(const BIGNUM *bn)
+{
+ return ((const heim_integer *)bn)->length;
+}
+
+/*
+ * Ignore negative flag.
+ */
+
+BIGNUM *
+BN_bin2bn(const void *s, int len, BIGNUM *bn)
+{
+ heim_integer *hi = (void *)bn;
+
+ if (len < 0)
+ return NULL;
+
+ if (hi == NULL) {
+ hi = (heim_integer *)BN_new();
+ if (hi == NULL)
+ return NULL;
+ }
+ if (hi->data)
+ BN_clear((BIGNUM *)hi);
+ hi->negative = 0;
+ hi->data = malloc(len);
+ if (hi->data == NULL && len != 0) {
+ if (bn == NULL)
+ BN_free((BIGNUM *)hi);
+ return NULL;
+ }
+ hi->length = len;
+ if (len)
+ memcpy(hi->data, s, len);
+ return (BIGNUM *)hi;
+}
+
+int
+BN_bn2bin(const BIGNUM *bn, void *to)
+{
+ const heim_integer *hi = (const void *)bn;
+ memcpy(to, hi->data, hi->length);
+ return hi->length;
+}
+
+int
+BN_hex2bn(BIGNUM **bnp, const char *in)
+{
+ int negative;
+ ssize_t ret;
+ size_t len;
+ void *data;
+
+ len = strlen(in);
+ data = malloc(len);
+ if (data == NULL)
+ return 0;
+
+ if (*in == '-') {
+ negative = 1;
+ in++;
+ } else
+ negative = 0;
+
+ ret = hex_decode(in, data, len);
+ if (ret < 0) {
+ free(data);
+ return 0;
+ }
+
+ *bnp = BN_bin2bn(data, ret, NULL);
+ free(data);
+ if (*bnp == NULL)
+ return 0;
+ BN_set_negative(*bnp, negative);
+ return 1;
+}
+
+char *
+BN_bn2hex(const BIGNUM *bn)
+{
+ ssize_t ret;
+ size_t len;
+ void *data;
+ char *str;
+
+ len = BN_num_bytes(bn);
+ data = malloc(len);
+ if (data == NULL)
+ return 0;
+
+ len = BN_bn2bin(bn, data);
+
+ ret = hex_encode(data, len, &str);
+ free(data);
+ if (ret < 0)
+ return 0;
+
+ return str;
+}
+
+int
+BN_cmp(const BIGNUM *bn1, const BIGNUM *bn2)
+{
+ return der_heim_integer_cmp((const heim_integer *)bn1,
+ (const heim_integer *)bn2);
+}
+
+void
+BN_set_negative(BIGNUM *bn, int flag)
+{
+ ((heim_integer *)bn)->negative = (flag ? 1 : 0);
+}
+
+int
+BN_is_negative(const BIGNUM *bn)
+{
+ return ((const heim_integer *)bn)->negative ? 1 : 0;
+}
+
+static const unsigned char is_set[8] = { 1, 2, 4, 8, 16, 32, 64, 128 };
+
+int
+BN_is_bit_set(const BIGNUM *bn, int bit)
+{
+ heim_integer *hi = (heim_integer *)bn;
+ unsigned char *p = hi->data;
+
+ if ((bit / 8) >= hi->length || hi->length == 0)
+ return 0;
+
+ return p[hi->length - 1 - (bit / 8)] & is_set[bit % 8];
+}
+
+int
+BN_set_bit(BIGNUM *bn, int bit)
+{
+ heim_integer *hi = (heim_integer *)bn;
+ unsigned char *p;
+
+ if ((bit / 8) > hi->length || hi->length == 0) {
+ size_t len = bit == 0 ? 1 : (bit + 7) / 8;
+ void *d = realloc(hi->data, len);
+ if (d == NULL)
+ return 0;
+ hi->data = d;
+ p = hi->data;
+ memset(&p[hi->length], 0, len);
+ hi->length = len;
+ } else
+ p = hi->data;
+
+ p[hi->length - 1 - (bit / 8)] |= is_set[bit % 8];
+ return 1;
+}
+
+int
+BN_clear_bit(BIGNUM *bn, int bit)
+{
+ heim_integer *hi = (heim_integer *)bn;
+ unsigned char *p = hi->data;
+
+ if ((bit / 8) > hi->length || hi->length == 0)
+ return 0;
+
+ p[hi->length - 1 - (bit / 8)] &= (unsigned char)(~(is_set[bit % 8]));
+
+ return 1;
+}
+
+int
+BN_set_word(BIGNUM *bn, unsigned long num)
+{
+ unsigned char p[sizeof(num)];
+ unsigned long num2;
+ int i, len;
+
+ if (bn == NULL)
+ return 0;
+
+ for (num2 = num, i = 0; num2 > 0; i++)
+ num2 = num2 >> 8;
+
+ len = i;
+ for (; i > 0; i--) {
+ p[i - 1] = (num & 0xff);
+ num = num >> 8;
+ }
+
+ bn = BN_bin2bn(p, len, bn);
+ return bn != NULL;
+}
+
+unsigned long
+BN_get_word(const BIGNUM *bn)
+{
+ heim_integer *hi = (heim_integer *)bn;
+ unsigned long num = 0;
+ int i;
+
+ if (hi->negative || hi->length > sizeof(num))
+ return ULONG_MAX;
+
+ for (i = 0; i < hi->length; i++)
+ num = ((unsigned char *)hi->data)[i] | (num << 8);
+ return num;
+}
+
+int
+BN_rand(BIGNUM *bn, int bits, int top, int bottom)
+{
+ size_t len = (bits + 7) / 8;
+ heim_integer *i = (heim_integer *)bn;
+
+ BN_clear(bn);
+
+ i->negative = 0;
+ i->data = malloc(len);
+ if (i->data == NULL && len != 0)
+ return 0;
+ i->length = len;
+
+ if (RAND_bytes(i->data, i->length) != 1) {
+ free(i->data);
+ i->data = NULL;
+ return 0;
+ }
+
+ {
+ size_t j = len * 8;
+ while(j > bits) {
+ BN_clear_bit(bn, j - 1);
+ j--;
+ }
+ }
+
+ if (top == -1) {
+ ;
+ } else if (top == 0 && bits > 0) {
+ BN_set_bit(bn, bits - 1);
+ } else if (top == 1 && bits > 1) {
+ BN_set_bit(bn, bits - 1);
+ BN_set_bit(bn, bits - 2);
+ } else {
+ BN_clear(bn);
+ return 0;
+ }
+
+ if (bottom && bits > 0)
+ BN_set_bit(bn, 0);
+
+ return 1;
+}
+
+/*
+ *
+ */
+
+int
+BN_uadd(BIGNUM *res, const BIGNUM *a, const BIGNUM *b)
+{
+ const heim_integer *ai = (const heim_integer *)a;
+ const heim_integer *bi = (const heim_integer *)b;
+ const unsigned char *ap, *bp;
+ unsigned char *cp;
+ heim_integer ci;
+ int carry = 0;
+ ssize_t len;
+
+ if (ai->negative && bi->negative)
+ return 0;
+ if (ai->length < bi->length) {
+ const heim_integer *si = bi;
+ bi = ai; ai = si;
+ }
+
+ ci.negative = 0;
+ ci.length = ai->length + 1;
+ ci.data = malloc(ci.length);
+ if (ci.data == NULL)
+ return 0;
+
+ ap = &((const unsigned char *)ai->data)[ai->length - 1];
+ bp = &((const unsigned char *)bi->data)[bi->length - 1];
+ cp = &((unsigned char *)ci.data)[ci.length - 1];
+
+ for (len = bi->length; len > 0; len--) {
+ carry = *ap + *bp + carry;
+ *cp = carry & 0xff;
+ carry = (carry & ~0xff) ? 1 : 0;
+ ap--; bp--; cp--;
+ }
+ for (len = ai->length - bi->length; len > 0; len--) {
+ carry = *ap + carry;
+ *cp = carry & 0xff;
+ carry = (carry & ~0xff) ? 1 : 0;
+ ap--; cp--;
+ }
+ if (!carry)
+ memmove(cp, cp + 1, --ci.length);
+ else
+ *cp = carry;
+
+ BN_clear(res);
+ *((heim_integer *)res) = ci;
+
+ return 1;
+}
+
+
+/*
+ * Callback when doing slow generation of numbers, like primes.
+ */
+
+void
+BN_GENCB_set(BN_GENCB *gencb, int (*cb_2)(int, int, BN_GENCB *), void *ctx)
+{
+ gencb->ver = 2;
+ gencb->cb.cb_2 = cb_2;
+ gencb->arg = ctx;
+}
+
+int
+BN_GENCB_call(BN_GENCB *cb, int a, int b)
+{
+ if (cb == NULL || cb->cb.cb_2 == NULL)
+ return 1;
+ return cb->cb.cb_2(a, b, cb);
+}
+
+/*
+ *
+ */
+
+struct BN_CTX {
+ struct {
+ BIGNUM **val;
+ size_t used;
+ size_t len;
+ } bn;
+ struct {
+ size_t *val;
+ size_t used;
+ size_t len;
+ } stack;
+};
+
+BN_CTX *
+BN_CTX_new(void)
+{
+ struct BN_CTX *c;
+ c = calloc(1, sizeof(*c));
+ return c;
+}
+
+void
+BN_CTX_free(BN_CTX *c)
+{
+ size_t i;
+ for (i = 0; i < c->bn.len; i++)
+ BN_free(c->bn.val[i]);
+ free(c->bn.val);
+ free(c->stack.val);
+}
+
+BIGNUM *
+BN_CTX_get(BN_CTX *c)
+{
+ if (c->bn.used == c->bn.len) {
+ void *ptr;
+ size_t i;
+ c->bn.len += 16;
+ ptr = realloc(c->bn.val, c->bn.len * sizeof(c->bn.val[0]));
+ if (ptr == NULL)
+ return NULL;
+ c->bn.val = ptr;
+ for (i = c->bn.used; i < c->bn.len; i++) {
+ c->bn.val[i] = BN_new();
+ if (c->bn.val[i] == NULL) {
+ c->bn.len = i;
+ return NULL;
+ }
+ }
+ }
+ return c->bn.val[c->bn.used++];
+}
+
+void
+BN_CTX_start(BN_CTX *c)
+{
+ if (c->stack.used == c->stack.len) {
+ void *ptr;
+ c->stack.len += 16;
+ ptr = realloc(c->stack.val, c->stack.len * sizeof(c->stack.val[0]));
+ if (ptr == NULL)
+ abort();
+ c->stack.val = ptr;
+ }
+ c->stack.val[c->stack.used++] = c->bn.used;
+}
+
+void
+BN_CTX_end(BN_CTX *c)
+{
+ const size_t prev = c->stack.val[c->stack.used - 1];
+ size_t i;
+
+ if (c->stack.used == 0)
+ abort();
+
+ for (i = prev; i < c->bn.used; i++)
+ BN_clear(c->bn.val[i]);
+
+ c->stack.used--;
+ c->bn.used = prev;
+}
+