From f84dc62cc602eacb0daee3e9918a68b711ba94f0 Mon Sep 17 00:00:00 2001 From: Othmar Gsenger Date: Sat, 8 Dec 2007 20:59:57 +0000 Subject: removed isakmpd --- keyexchange/isakmpd-20041012/math_2n.c | 1107 -------------------------------- 1 file changed, 1107 deletions(-) delete mode 100644 keyexchange/isakmpd-20041012/math_2n.c (limited to 'keyexchange/isakmpd-20041012/math_2n.c') diff --git a/keyexchange/isakmpd-20041012/math_2n.c b/keyexchange/isakmpd-20041012/math_2n.c deleted file mode 100644 index f8828ef..0000000 --- a/keyexchange/isakmpd-20041012/math_2n.c +++ /dev/null @@ -1,1107 +0,0 @@ -/* $OpenBSD: math_2n.c,v 1.16 2004/06/14 09:55:41 ho Exp $ */ -/* $EOM: math_2n.c,v 1.15 1999/04/20 09:23:30 niklas Exp $ */ - -/* - * Copyright (c) 1998 Niels Provos. All rights reserved. - * Copyright (c) 1999 Niklas Hallqvist. 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. - * - * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``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 AUTHOR 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. - */ - -/* - * This code was written under funding by Ericsson Radio Systems. - */ - -/* - * B2N is a module for doing arithmetic on the Field GF(2**n) which is - * isomorph to ring of polynomials GF(2)[x]/p(x) where p(x) is an - * irreduciable polynomial over GF(2)[x] with grade n. - * - * First we need functions which operate on GF(2)[x], operation - * on GF(2)[x]/p(x) can be done as for Z_p then. - */ - -#include -#include -#include - -#include "sysdep.h" - -#include "math_2n.h" -#include "util.h" - -static u_int8_t hex2int(char); - -static char int2hex[] = "0123456789abcdef"; -CHUNK_TYPE b2n_mask[CHUNK_BITS] = { - 0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40, 0x80, -#if CHUNK_BITS > 8 - 0x0100, 0x0200, 0x0400, 0x0800, 0x1000, 0x2000, 0x4000, 0x8000, -#if CHUNK_BITS > 16 - 0x00010000, 0x00020000, 0x00040000, 0x00080000, - 0x00100000, 0x00200000, 0x00400000, 0x00800000, - 0x01000000, 0x02000000, 0x04000000, 0x08000000, - 0x10000000, 0x20000000, 0x40000000, 0x80000000, -#endif -#endif -}; - -/* Convert a hex character to its integer value. */ -static u_int8_t -hex2int(char c) -{ - if (c <= '9') - return c - '0'; - if (c <= 'f') - return 10 + c - 'a'; - - return 0; -} - -int -b2n_random(b2n_ptr n, u_int32_t bits) -{ - if (b2n_resize(n, (CHUNK_MASK + bits) >> CHUNK_SHIFTS)) - return -1; - - getrandom((u_int8_t *) n->limp, CHUNK_BYTES * n->chunks); - - /* Get the number of significant bits right */ - if (bits & CHUNK_MASK) { - CHUNK_TYPE m = - (((1 << ((bits & CHUNK_MASK) - 1)) - 1) << 1) | 1; - n->limp[n->chunks - 1] &= m; - } - n->dirty = 1; - return 0; -} - -/* b2n management functions */ - -void -b2n_init(b2n_ptr n) -{ - n->chunks = 0; - n->limp = 0; -} - -void -b2n_clear(b2n_ptr n) -{ - if (n->limp) - free(n->limp); -} - -int -b2n_resize(b2n_ptr n, unsigned int chunks) -{ - size_t old = n->chunks; - size_t size; - CHUNK_TYPE *new; - - if (chunks == 0) - chunks = 1; - - if (chunks == old) - return 0; - - size = CHUNK_BYTES * chunks; - - new = realloc(n->limp, size); - if (!new) - return -1; - - n->limp = new; - n->chunks = chunks; - n->bits = chunks << CHUNK_SHIFTS; - n->dirty = 1; - - if (chunks > old) - memset(n->limp + old, 0, size - CHUNK_BYTES * old); - - return 0; -} - -/* Simple assignment functions. */ - -int -b2n_set(b2n_ptr d, b2n_ptr s) -{ - if (d == s) - return 0; - - b2n_sigbit(s); - if (b2n_resize(d, (CHUNK_MASK + s->bits) >> CHUNK_SHIFTS)) - return -1; - memcpy(d->limp, s->limp, CHUNK_BYTES * d->chunks); - d->bits = s->bits; - d->dirty = s->dirty; - return 0; -} - -int -b2n_set_null(b2n_ptr n) -{ - if (b2n_resize(n, 1)) - return -1; - n->limp[0] = n->bits = n->dirty = 0; - return 0; -} - -int -b2n_set_ui(b2n_ptr n, unsigned int val) -{ -#if CHUNK_BITS < 32 - int i, chunks; - - chunks = (CHUNK_BYTES - 1 + sizeof(val)) / CHUNK_BYTES; - - if (b2n_resize(n, chunks)) - return -1; - - for (i = 0; i < chunks; i++) { - n->limp[i] = val & CHUNK_BMASK; - val >>= CHUNK_BITS; - } -#else - if (b2n_resize(n, 1)) - return -1; - n->limp[0] = val; -#endif - n->dirty = 1; - return 0; -} - -/* XXX This one only takes hex at the moment. */ -int -b2n_set_str(b2n_ptr n, char *str) -{ - int i, j, w, len, chunks; - CHUNK_TYPE tmp; - - if (strncasecmp(str, "0x", 2)) - return -1; - - /* Make the hex string even lengthed */ - len = strlen(str) - 2; - if (len & 1) { - len++; - str++; - } else - str += 2; - - len /= 2; - - chunks = (CHUNK_BYTES - 1 + len) / CHUNK_BYTES; - if (b2n_resize(n, chunks)) - return -1; - memset(n->limp, 0, CHUNK_BYTES * n->chunks); - - for (w = 0, i = 0; i < chunks; i++) { - tmp = 0; - for (j = (i == 0 ? - ((len - 1) % CHUNK_BYTES) + 1 : CHUNK_BYTES); - j > 0; j--) { - tmp <<= 8; - tmp |= (hex2int(str[w]) << 4) | hex2int(str[w + 1]); - w += 2; - } - n->limp[chunks - 1 - i] = tmp; - } - - n->dirty = 1; - return 0; -} - -/* Output function, mainly for debugging purposes. */ -void -b2n_print(b2n_ptr n) -{ - int i, j, w, flag = 0; - int left; - char buffer[2 * CHUNK_BYTES]; - CHUNK_TYPE tmp; - - left = ((((7 + b2n_sigbit(n)) >> 3) - 1) % CHUNK_BYTES) + 1; - printf("0x"); - for (i = 0; i < n->chunks; i++) { - tmp = n->limp[n->chunks - 1 - i]; - memset(buffer, '0', sizeof(buffer)); - for (w = 0, j = (i == 0 ? left : CHUNK_BYTES); j > 0; j--) { - buffer[w++] = int2hex[(tmp >> 4) & 0xf]; - buffer[w++] = int2hex[tmp & 0xf]; - tmp >>= 8; - } - - for (j = (i == 0 ? left - 1 : CHUNK_BYTES - 1); j >= 0; j--) - if (flag || (i == n->chunks - 1 && j == 0) || - buffer[2 * j] != '0' || buffer[2 * j + 1] != '0') { - putchar(buffer[2 * j]); - putchar(buffer[2 * j + 1]); - flag = 1; - } - } - printf("\n"); -} - -int -b2n_snprint(char *buf, size_t sz, b2n_ptr n) -{ - int i, j, w, flag = 0; - size_t k; - int left; - char buffer[2 * CHUNK_BYTES]; - CHUNK_TYPE tmp; - - left = ((((7 + b2n_sigbit(n)) >> 3) - 1) % CHUNK_BYTES) + 1; - - k = strlcpy(buf, "0x", sz); - for (i = 0; i < n->chunks && k < sz - 1; i++) { - tmp = n->limp[n->chunks - 1 - i]; - memset(buffer, '0', sizeof(buffer)); - for (w = 0, j = (i == 0 ? left : CHUNK_BYTES); j > 0; j--) { - buffer[w++] = int2hex[(tmp >> 4) & 0xf]; - buffer[w++] = int2hex[tmp & 0xf]; - tmp >>= 8; - } - - for (j = (i == 0 ? left - 1 : CHUNK_BYTES - 1); j >= 0 - && k < sz - 3; j--) - if (flag || (i == n->chunks - 1 && j == 0) || - buffer[2 * j] != '0' || buffer[2 * j + 1] != '0') { - buf[k++] = buffer[2 * j]; - buf[k++] = buffer[2 * j + 1]; - flag = 1; - } - } - - buf[k++] = 0; - return k; -} - -/* Arithmetic functions. */ - -u_int32_t -b2n_sigbit(b2n_ptr n) -{ - int i, j; - - if (!n->dirty) - return n->bits; - - for (i = n->chunks - 1; i > 0; i--) - if (n->limp[i]) - break; - - if (!n->limp[i]) - return 0; - - for (j = CHUNK_MASK; j > 0; j--) - if (n->limp[i] & b2n_mask[j]) - break; - - n->bits = (i << CHUNK_SHIFTS) + j + 1; - n->dirty = 0; - return n->bits; -} - -/* Addition on GF(2)[x] is nice, its just an XOR. */ -int -b2n_add(b2n_ptr d, b2n_ptr a, b2n_ptr b) -{ - int i; - b2n_ptr bmin, bmax; - - if (!b2n_cmp_null(a)) - return b2n_set(d, b); - - if (!b2n_cmp_null(b)) - return b2n_set(d, a); - - bmin = B2N_MIN(a, b); - bmax = B2N_MAX(a, b); - - if (b2n_resize(d, bmax->chunks)) - return -1; - - for (i = 0; i < bmin->chunks; i++) - d->limp[i] = bmax->limp[i] ^ bmin->limp[i]; - - /* - * If d is not bmax, we have to copy the rest of the bytes, and also - * need to adjust to number of relevant bits. - */ - if (d != bmax) { - for (; i < bmax->chunks; i++) - d->limp[i] = bmax->limp[i]; - - d->bits = bmax->bits; - } - /* - * Help to converse memory. When the result of the addition is zero - * truncate the used amount of memory. - */ - if (d != bmax && !b2n_cmp_null(d)) - return b2n_set_null(d); - else - d->dirty = 1; - return 0; -} - -/* Compare two polynomials. */ -int -b2n_cmp(b2n_ptr n, b2n_ptr m) -{ - int sn, sm; - int i; - - sn = b2n_sigbit(n); - sm = b2n_sigbit(m); - - if (sn > sm) - return 1; - if (sn < sm) - return -1; - - for (i = n->chunks - 1; i >= 0; i--) - if (n->limp[i] > m->limp[i]) - return 1; - else if (n->limp[i] < m->limp[i]) - return -1; - - return 0; -} - -int -b2n_cmp_null(b2n_ptr a) -{ - int i = 0; - - do { - if (a->limp[i]) - return 1; - } - while (++i < a->chunks); - - return 0; -} - -/* Left shift, needed for polynomial multiplication. */ -int -b2n_lshift(b2n_ptr d, b2n_ptr n, unsigned int s) -{ - int i, maj, min, chunks; - u_int16_t bits = b2n_sigbit(n), add; - CHUNK_TYPE *p, *op; - - if (!s) - return b2n_set(d, n); - - maj = s >> CHUNK_SHIFTS; - min = s & CHUNK_MASK; - - add = (!(bits & CHUNK_MASK) || - ((bits & CHUNK_MASK) + min) > CHUNK_MASK) ? 1 : 0; - chunks = n->chunks; - if (b2n_resize(d, chunks + maj + add)) - return -1; - memmove(d->limp + maj, n->limp, CHUNK_BYTES * chunks); - - if (maj) - memset(d->limp, 0, CHUNK_BYTES * maj); - if (add) - d->limp[d->chunks - 1] = 0; - - /* If !min there are no bit shifts, we are done */ - if (!min) - return 0; - - op = p = &d->limp[d->chunks - 1]; - for (i = d->chunks - 2; i >= maj; i--) { - op--; - *p = (*p << min) | (*op >> (CHUNK_BITS - min)); - p--; - } - *p <<= min; - - d->dirty = 0; - d->bits = bits + (maj << CHUNK_SHIFTS) + min; - return 0; -} - -/* Right shift, needed for polynomial division. */ -int -b2n_rshift(b2n_ptr d, b2n_ptr n, unsigned int s) -{ - int maj, min, size = n->chunks, newsize; - b2n_ptr tmp; - - if (!s) - return b2n_set(d, n); - - maj = s >> CHUNK_SHIFTS; - - newsize = size - maj; - - if (size < maj) - return b2n_set_null(d); - - min = (CHUNK_BITS - (s & CHUNK_MASK)) & CHUNK_MASK; - if (min) { - if ((b2n_sigbit(n) & CHUNK_MASK) > (u_int32_t) min) - newsize++; - - if (b2n_lshift(d, n, min)) - return -1; - tmp = d; - } else - tmp = n; - - memmove(d->limp, tmp->limp + maj + (min ? 1 : 0), - CHUNK_BYTES * newsize); - if (b2n_resize(d, newsize)) - return -1; - - d->bits = tmp->bits - ((maj + (min ? 1 : 0)) << CHUNK_SHIFTS); - return 0; -} - -/* Normal polynomial multiplication. */ -int -b2n_mul(b2n_ptr d, b2n_ptr n, b2n_ptr m) -{ - int i, j; - b2n_t tmp, tmp2; - - if (!b2n_cmp_null(m) || !b2n_cmp_null(n)) - return b2n_set_null(d); - - if (b2n_sigbit(m) == 1) - return b2n_set(d, n); - - if (b2n_sigbit(n) == 1) - return b2n_set(d, m); - - b2n_init(tmp); - b2n_init(tmp2); - - if (b2n_set(tmp, B2N_MAX(n, m))) - goto fail; - if (b2n_set(tmp2, B2N_MIN(n, m))) - goto fail; - - if (b2n_set_null(d)) - goto fail; - - for (i = 0; i < tmp2->chunks; i++) - if (tmp2->limp[i]) - for (j = 0; j < CHUNK_BITS; j++) { - if (tmp2->limp[i] & b2n_mask[j]) - if (b2n_add(d, d, tmp)) - goto fail; - - if (b2n_lshift(tmp, tmp, 1)) - goto fail; - } - else if (b2n_lshift(tmp, tmp, CHUNK_BITS)) - goto fail; - - b2n_clear(tmp); - b2n_clear(tmp2); - return 0; - -fail: - b2n_clear(tmp); - b2n_clear(tmp2); - return -1; -} - -/* - * Squaring in this polynomial ring is more efficient than normal - * multiplication. - */ -int -b2n_square(b2n_ptr d, b2n_ptr n) -{ - int i, j, maj, min, bits, chunk; - b2n_t t; - - maj = b2n_sigbit(n); - min = maj & CHUNK_MASK; - maj = (maj + CHUNK_MASK) >> CHUNK_SHIFTS; - - b2n_init(t); - if (b2n_resize(t, - 2 * maj + ((CHUNK_MASK + 2 * min) >> CHUNK_SHIFTS))) { - b2n_clear(t); - return -1; - } - chunk = 0; - bits = 0; - - for (i = 0; i < maj; i++) - if (n->limp[i]) - for (j = 0; j < CHUNK_BITS; j++) { - if (n->limp[i] & b2n_mask[j]) - t->limp[chunk] ^= b2n_mask[bits]; - - bits += 2; - if (bits >= CHUNK_BITS) { - chunk++; - bits &= CHUNK_MASK; - } - } - else - chunk += 2; - - t->dirty = 1; - B2N_SWAP(d, t); - b2n_clear(t); - return 0; -} - -/* - * Normal polynomial division. - * These functions are far from optimal in speed. - */ -int -b2n_div_q(b2n_ptr d, b2n_ptr n, b2n_ptr m) -{ - b2n_t r; - int rv; - - b2n_init(r); - rv = b2n_div(d, r, n, m); - b2n_clear(r); - return rv; -} - -int -b2n_div_r(b2n_ptr r, b2n_ptr n, b2n_ptr m) -{ - b2n_t q; - int rv; - - b2n_init(q); - rv = b2n_div(q, r, n, m); - b2n_clear(q); - return rv; -} - -int -b2n_div(b2n_ptr q, b2n_ptr r, b2n_ptr n, b2n_ptr m) -{ - int i, j, len, bits; - u_int32_t sm, sn; - b2n_t nenn, div, shift, mask; - - /* If Teiler > Zaehler, the result is 0 */ - if ((sm = b2n_sigbit(m)) > (sn = b2n_sigbit(n))) { - if (b2n_set_null(q)) - return -1; - return b2n_set(r, n); - } - if (sm == 0) - /* Division by Zero */ - return -1; - else if (sm == 1) { - /* Division by the One-Element */ - if (b2n_set(q, n)) - return -1; - return b2n_set_null(r); - } - b2n_init(nenn); - b2n_init(div); - b2n_init(shift); - b2n_init(mask); - - if (b2n_set(nenn, n)) - goto fail; - if (b2n_set(div, m)) - goto fail; - if (b2n_set(shift, m)) - goto fail; - if (b2n_set_ui(mask, 1)) - goto fail; - - if (b2n_resize(q, (sn - sm + CHUNK_MASK) >> CHUNK_SHIFTS)) - goto fail; - memset(q->limp, 0, CHUNK_BYTES * q->chunks); - - if (b2n_lshift(shift, shift, sn - sm)) - goto fail; - if (b2n_lshift(mask, mask, sn - sm)) - goto fail; - - /* Number of significant octets */ - len = (sn - 1) >> CHUNK_SHIFTS; - /* The first iteration is done over the relevant bits */ - bits = (CHUNK_MASK + sn) & CHUNK_MASK; - for (i = len; i >= 0 && b2n_sigbit(nenn) >= sm; i--) - for (j = (i == len ? bits : CHUNK_MASK); j >= 0 - && b2n_sigbit(nenn) >= sm; j--) { - if (nenn->limp[i] & b2n_mask[j]) { - if (b2n_sub(nenn, nenn, shift)) - goto fail; - if (b2n_add(q, q, mask)) - goto fail; - } - if (b2n_rshift(shift, shift, 1)) - goto fail; - if (b2n_rshift(mask, mask, 1)) - goto fail; - } - - B2N_SWAP(r, nenn); - - b2n_clear(nenn); - b2n_clear(div); - b2n_clear(shift); - b2n_clear(mask); - return 0; - -fail: - b2n_clear(nenn); - b2n_clear(div); - b2n_clear(shift); - b2n_clear(mask); - return -1; -} - -/* Functions for Operation on GF(2**n) ~= GF(2)[x]/p(x). */ -int -b2n_mod(b2n_ptr m, b2n_ptr n, b2n_ptr p) -{ - int bits, size; - - if (b2n_div_r(m, n, p)) - return -1; - - bits = b2n_sigbit(m); - size = ((CHUNK_MASK + bits) >> CHUNK_SHIFTS); - if (size == 0) - size = 1; - if (m->chunks > size) - if (b2n_resize(m, size)) - return -1; - - m->bits = bits; - m->dirty = 0; - return 0; -} - -int -b2n_gcd(b2n_ptr e, b2n_ptr go, b2n_ptr ho) -{ - b2n_t g, h; - - b2n_init(g); - b2n_init(h); - if (b2n_set(g, go)) - goto fail; - if (b2n_set(h, ho)) - goto fail; - - while (b2n_cmp_null(h)) { - if (b2n_mod(g, g, h)) - goto fail; - B2N_SWAP(g, h); - } - - B2N_SWAP(e, g); - - b2n_clear(g); - b2n_clear(h); - return 0; - -fail: - b2n_clear(g); - b2n_clear(h); - return -1; -} - -int -b2n_mul_inv(b2n_ptr ga, b2n_ptr be, b2n_ptr p) -{ - b2n_t a; - - b2n_init(a); - if (b2n_set_ui(a, 1)) - goto fail; - - if (b2n_div_mod(ga, a, be, p)) - goto fail; - - b2n_clear(a); - return 0; - -fail: - b2n_clear(a); - return -1; -} - -int -b2n_div_mod(b2n_ptr ga, b2n_ptr a, b2n_ptr be, b2n_ptr p) -{ - b2n_t s0, s1, s2, q, r0, r1; - - /* There is no multiplicative inverse to Null. */ - if (!b2n_cmp_null(be)) - return b2n_set_null(ga); - - b2n_init(s0); - b2n_init(s1); - b2n_init(s2); - b2n_init(r0); - b2n_init(r1); - b2n_init(q); - - if (b2n_set(r0, p)) - goto fail; - if (b2n_set(r1, be)) - goto fail; - - if (b2n_set_null(s0)) - goto fail; - if (b2n_set(s1, a)) - goto fail; - - while (b2n_cmp_null(r1)) { - if (b2n_div(q, r0, r0, r1)) - goto fail; - B2N_SWAP(r0, r1); - - if (b2n_mul(s2, q, s1)) - goto fail; - if (b2n_mod(s2, s2, p)) - goto fail; - if (b2n_sub(s2, s0, s2)) - goto fail; - - B2N_SWAP(s0, s1); - B2N_SWAP(s1, s2); - } - B2N_SWAP(ga, s0); - - b2n_clear(s0); - b2n_clear(s1); - b2n_clear(s2); - b2n_clear(r0); - b2n_clear(r1); - b2n_clear(q); - return 0; - -fail: - b2n_clear(s0); - b2n_clear(s1); - b2n_clear(s2); - b2n_clear(r0); - b2n_clear(r1); - b2n_clear(q); - return -1; -} - -/* - * The trace tells us if there do exist any square roots - * for 'a' in GF(2)[x]/p(x). The number of square roots is - * 2 - 2*Trace. - * If z is a square root, z + 1 is the other. - */ -int -b2n_trace(b2n_ptr ho, b2n_ptr a, b2n_ptr p) -{ - int i, m = b2n_sigbit(p) - 1; - b2n_t h; - - b2n_init(h); - if (b2n_set(h, a)) - goto fail; - - for (i = 0; i < m - 1; i++) { - if (b2n_square(h, h)) - goto fail; - if (b2n_mod(h, h, p)) - goto fail; - - if (b2n_add(h, h, a)) - goto fail; - } - B2N_SWAP(ho, h); - - b2n_clear(h); - return 0; - -fail: - b2n_clear(h); - return -1; -} - -/* - * The halftrace yields the square root if the degree of the - * irreduceable polynomial is odd. - */ -int -b2n_halftrace(b2n_ptr ho, b2n_ptr a, b2n_ptr p) -{ - int i, m = b2n_sigbit(p) - 1; - b2n_t h; - - b2n_init(h); - if (b2n_set(h, a)) - goto fail; - - for (i = 0; i < (m - 1) / 2; i++) { - if (b2n_square(h, h)) - goto fail; - if (b2n_mod(h, h, p)) - goto fail; - if (b2n_square(h, h)) - goto fail; - if (b2n_mod(h, h, p)) - goto fail; - - if (b2n_add(h, h, a)) - goto fail; - } - - B2N_SWAP(ho, h); - - b2n_clear(h); - return 0; - -fail: - b2n_clear(h); - return -1; -} - -/* - * Solving the equation: y**2 + y = b in GF(2**m) where ip is the - * irreduceable polynomial. If m is odd, use the half trace. - */ -int -b2n_sqrt(b2n_ptr zo, b2n_ptr b, b2n_ptr ip) -{ - int i, m = b2n_sigbit(ip) - 1; - b2n_t w, p, temp, z; - - if (!b2n_cmp_null(b)) - return b2n_set_null(z); - - if (m & 1) - return b2n_halftrace(zo, b, ip); - - b2n_init(z); - b2n_init(w); - b2n_init(p); - b2n_init(temp); - - do { - if (b2n_random(p, m)) - goto fail; - if (b2n_set_null(z)) - goto fail; - if (b2n_set(w, p)) - goto fail; - - for (i = 1; i < m; i++) { - if (b2n_square(z, z)) /* z**2 */ - goto fail; - if (b2n_mod(z, z, ip)) - goto fail; - - if (b2n_square(w, w)) /* w**2 */ - goto fail; - if (b2n_mod(w, w, ip)) - goto fail; - - if (b2n_mul(temp, w, b)) /* w**2 * b */ - goto fail; - if (b2n_mod(temp, temp, ip)) - goto fail; - if (b2n_add(z, z, temp)) /* z**2 + w**2 + b */ - goto fail; - - if (b2n_add(w, w, p)) /* w**2 + p */ - goto fail; - } - } - while (!b2n_cmp_null(w)); - - B2N_SWAP(zo, z); - - b2n_clear(w); - b2n_clear(p); - b2n_clear(temp); - b2n_clear(z); - return 0; - -fail: - b2n_clear(w); - b2n_clear(p); - b2n_clear(temp); - b2n_clear(z); - return -1; -} - -/* Exponentiation modulo a polynomial. */ -int -b2n_exp_mod(b2n_ptr d, b2n_ptr b0, u_int32_t e, b2n_ptr p) -{ - b2n_t u, b; - - b2n_init(u); - b2n_init(b); - if (b2n_set_ui(u, 1)) - goto fail; - if (b2n_mod(b, b0, p)) - goto fail; - - while (e) { - if (e & 1) { - if (b2n_mul(u, u, b)) - goto fail; - if (b2n_mod(u, u, p)) - goto fail; - } - if (b2n_square(b, b)) - goto fail; - if (b2n_mod(b, b, p)) - goto fail; - e >>= 1; - } - - B2N_SWAP(d, u); - - b2n_clear(u); - b2n_clear(b); - return 0; - -fail: - b2n_clear(u); - b2n_clear(b); - return -1; -} - -/* - * Low-level function to speed up scalar multiplication with - * elliptic curves. - * Multiplies a normal number by 3. - */ - -/* Normal addition behaves as Z_{2**n} and not F_{2**n}. */ -int -b2n_nadd(b2n_ptr d0, b2n_ptr a0, b2n_ptr b0) -{ - int i, carry; - b2n_ptr a, b; - b2n_t d; - - if (!b2n_cmp_null(a0)) - return b2n_set(d0, b0); - - if (!b2n_cmp_null(b0)) - return b2n_set(d0, a0); - - b2n_init(d); - a = B2N_MAX(a0, b0); - b = B2N_MIN(a0, b0); - - if (b2n_resize(d, a->chunks + 1)) { - b2n_clear(d); - return -1; - } - for (carry = i = 0; i < b->chunks; i++) { - d->limp[i] = a->limp[i] + b->limp[i] + carry; - carry = (d->limp[i] < a->limp[i] ? 1 : 0); - } - - for (; i < a->chunks && carry; i++) { - d->limp[i] = a->limp[i] + carry; - carry = (d->limp[i] < a->limp[i] ? 1 : 0); - } - - if (i < a->chunks) - memcpy(d->limp + i, a->limp + i, - CHUNK_BYTES * (a->chunks - i)); - - d->dirty = 1; - B2N_SWAP(d0, d); - - b2n_clear(d); - return 0; -} - -/* Very special sub, a > b. */ -int -b2n_nsub(b2n_ptr d0, b2n_ptr a, b2n_ptr b) -{ - int i, carry; - b2n_t d; - - if (b2n_cmp(a, b) <= 0) - return b2n_set_null(d0); - - b2n_init(d); - if (b2n_resize(d, a->chunks)) { - b2n_clear(d); - return -1; - } - for (carry = i = 0; i < b->chunks; i++) { - d->limp[i] = a->limp[i] - b->limp[i] - carry; - carry = (d->limp[i] > a->limp[i] ? 1 : 0); - } - - for (; i < a->chunks && carry; i++) { - d->limp[i] = a->limp[i] - carry; - carry = (d->limp[i] > a->limp[i] ? 1 : 0); - } - - if (i < a->chunks) - memcpy(d->limp + i, a->limp + i, - CHUNK_BYTES * (a->chunks - i)); - - d->dirty = 1; - - B2N_SWAP(d0, d); - - b2n_clear(d); - return 0; -} - -int -b2n_3mul(b2n_ptr d0, b2n_ptr e) -{ - b2n_t d; - - b2n_init(d); - if (b2n_lshift(d, e, 1)) - goto fail; - - if (b2n_nadd(d0, d, e)) - goto fail; - - b2n_clear(d); - return 0; - -fail: - b2n_clear(d); - return -1; -} -- cgit v1.2.3