ec_field.c

加密算法实现 Pegwit is a program for performing public key file encryption and authentication. Encr

/*
 * Algebraic operations on the finite field GF(2^m)
 *
 * This public domain software was written by Paulo S.L.M. Barreto
 * <[e-mail]> based on original C++ software written by
 * George Barwood <[e-mail]>
 *
 * THIS SOFTWARE IS PROVIDED BY THE AUTHORS ''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 AUTHORS 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.
 *
 * References:
 *
 * 1.	Erik De Win <[e-mail]> et alii:
 *		"A Fast Software Implementation for Arithmetic Operations in GF(2^n)",
 *		presented at Asiacrypt96 (preprint).
 *
 */

#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

#include "ec_field.h"
#include "ec_param.h"
#include "ec_vlong.h"

#define BASE	(1U << GF_L)
#define TOGGLE	(BASE-1)

static lunit *expt = NULL; /* index range is [0..(BASE-2)] */
static lunit *logt = NULL; /* index range is [1..(BASE-1)], but logt[0] is set to (BASE-1) */


int gfInit (void)
	/* initialize the library ---> MUST be called before any other gf-function */
{
	ltemp root, i, j;

	if (logt != NULL && expt != NULL) {
		/* already initialized */
		return 0;
	}
	if (logt != NULL && expt == NULL ||
		logt == NULL && expt != NULL) {
		return 2; /* logic error: half initialized (?!) */
	}
	if ((logt = (lunit *) malloc (BASE * sizeof (lunit))) == NULL) {
		return 1; /* not enough memory */
	}
	if ((expt = (lunit *) malloc (BASE * sizeof (lunit))) == NULL) {
		free (logt); logt = NULL;
		return 1; /* not enough memory */
	}
	root = BASE | GF_RP;
	expt[0] = 1;
	for (i = 1; i < BASE; i++) { 
		j = (ltemp)expt[i-1] << 1;
		if (j & BASE) {
			j ^= root;
		}
		expt[i] = (lunit)j;
	}
	for (i = 0; i < TOGGLE; i++) {
		logt[expt[i]] = (lunit)i;
	}
	logt[0] = TOGGLE; /* a trick used by gfMultiply, gfSquare, gfAddMul */

#ifdef PRECOMPUTE_TABLES
	printf ("static const lunit logt[%u] = {\n", 1 << BASE);
	for(i = 0; i < 16; i++) {
		for (j = 0; j < 16; j++) {
			printf ("0x%03xU, ", logt[i*16+j]);
		}
		printf ("\n");
	}
	printf ("};\n\n");

	printf ("static const lunit expt[%u] = {\n", 1 << BASE);
	for(i = 0; i < 16; i++) {
		for (j = 0; j < 16; j++) {
			printf ("0x%03xU, ", expt[i*16+j]);
		}
		printf ("\n");
	}
	printf ("};\n\n");
#endif /* ?PRECOMPUTE_TABLES */

	return 0;
} /* gfInit */


void gfQuit (void)
	/* perform housekeeping for library termination */
{
	if (expt) {
		free (expt); expt = NULL;
	}
	if (logt) {
		free (logt); logt = NULL;
	}
} /* gfQuit */

#ifdef SELF_TESTING

void gfPrint (FILE *fOut, const char *tag, const gfPoint p)
	/* prints tag and the contents of p to file fOut */
{
	ltemp i, bNeedsPlus = 0;

	assert (p != NULL);
	fprintf (fOut, "%s = ", tag);
	for (i = p[0]; i > 0; i--) {
		if (p[i]) {
			if (bNeedsPlus) {
				fprintf (fOut, " + ");
			}
			if (i > 2) {
				fprintf (fOut, "%04Xx^%d", p[i], i-1);
			} else if (i == 2) {
				fprintf (fOut, "%04Xx", p[2]);
			} else { /* i == 1 */
				fprintf (fOut, "%04X", p[1]);
			}
			bNeedsPlus = 1;
		}
	}
	if (!bNeedsPlus) {
		/* null polynomial */
		fprintf (fOut, "0");
	}
	fprintf (fOut, "\n");
} /* gfPrint */


void gfRandom (gfPoint p)
	/* sets p := <random field element> */
{
	int i;

	assert (p != NULL);
	p[0] = GF_K;
	for (i = 1; i <= GF_K; i++) {
		p[i] = (lunit) (rand() & TOGGLE); /* this weak PRNG should be replaced */
	}
	while (p[0] && p[p[0]] == 0) {
		p[0]--;
	}
} /* gfRandom */


static int gfSlowTrace (const gfPoint p)
	/* slowly evaluates to the trace of p (or an error code) */
{
	int i;
	gfPoint t;

	assert (logt != NULL && expt != NULL);
	assert (p != NULL);
	gfCopy (t, p);
	for (i = 1; i < GF_M; i++) {
		gfSquare (t, t);
		gfAdd (t, t, p);
	}
	return t[0] != 0;
} /* gfSlowTrace */

#endif /* ?SELF_TESTING */

int gfEqual (const gfPoint p, const gfPoint q)
	/* evaluates to 1 if p == q, otherwise 0 (or an error code) */
{
	assert (p != NULL);
	assert (q != NULL);
	return memcmp (p, q, p[0] + 1) ? 0 : 1;
} /* gfEqual */


void gfClear (gfPoint p)
	/* sets p := 0, clearing entirely the content of p */
{
	assert (p != NULL);
	memset (p, 0, sizeof (gfPoint));
} /* gfClear */


void gfCopy (gfPoint p, const gfPoint q)
	/* sets p := q */
{
	assert (p != NULL);
	assert (q != NULL);
	memcpy (p, q, (q[0] + 1) * sizeof (lunit));
} /* gfCopy */


void gfAdd (gfPoint p, const gfPoint q, const gfPoint r)
	/* sets p := q + r */
{
	ltemp i;

	assert (logt != NULL && expt != NULL);
	assert (p != NULL);
	assert (q != NULL);
	assert (r != NULL);
	if (q[0] > r[0]) {
		/* xor the the common-degree coefficients: */
		for (i = 1; i <= r[0]; i++) {
			p[i] = q[i] ^ r[i];
		}
		/* invariant: i == r[0] + 1 */
		memcpy (&p[i], &q[i], (q[0] - r[0]) * sizeof (lunit));
		/* deg(p) inherits the value of deg(q): */
		p[0] = q[0];
	} else if (q[0] < r[0]) {
		/* xor the the common-degree coefficients: */
		for (i = 1; i <= q[0]; i++) {
			p[i] = q[i] ^ r[i];
		}
		/* invariant: i == q[0] + 1 */
		memcpy (&p[i], &r[i], (r[0] - q[0]) * sizeof (lunit));
		/* deg(p) inherits the value of deg(r): */
		p[0] = r[0];
	} else { /* deg(q) == deg(r) */
		/* scan to determine deg(p): */
		for (i = q[0]; i > 0; i--) {
			if (q[i] ^ r[i]) {
				break;
			}
		}
		/* xor the the common-degree coefficients, if any is left: */
		for (p[0] = (lunit)i; i > 0; i--) {
			p[i] = q[i] ^ r[i];
		}
	}
} /* gfAdd */


static void gfReduce (gfPoint p)
	/* reduces p mod the irreducible trinomial x^GF_K + x^GF_T + 1 */
{
	int i;

	for (i = p[0]; i > GF_K; i--) {
		p[i - GF_K] ^= p[i];
		p[i + GF_T - GF_K] ^= p[i];
		p[i] = 0;
	}
	if (p[0] > GF_K) {
		/* scan to update deg(p): */
		p[0] = GF_K;
		while (p[0] && p[p[0]]==0) {
			p[0]--;
		}
	}
} /* gfReduce */


void gfMultiply (gfPoint r, const gfPoint p, const gfPoint q)
	/* sets r := p * q mod (x^GF_K + x^GF_T + 1) */
{
	int i, j;
	ltemp x, log_pi, log_qj;
	lunit lg[GF_K + 2]; /* this table should be cleared after use */

	assert (logt != NULL && expt != NULL);
	assert (p != NULL);
	assert (q != NULL);
	assert (r != p);
	assert (r != q);
	if (p[0] && q[0]) {
		/* precompute logt[q[j]] to reduce table lookups: */
		for (j = q[0]; j; j--) {
			lg[j] = logt[q[j]];
		}
		/* perform multiplication: */
		gfClear (r);
		for (i = p[0]; i; i--) {
			if ((log_pi = logt[p[i]]) != TOGGLE) { /* p[i] != 0 */
				for (j = q[0]; j; j--) {
					if ((log_qj = lg[j]) != TOGGLE) { /* q[j] != 0 */
					/*	r[i+j-1] ^= expt[(logt[p[i]] + logt[q[j]]) % TOGGLE]; */
						r[i+j-1] ^= expt[(x = log_pi + log_qj) >= TOGGLE ? x - TOGGLE : x];
					}
				}
			}
		}
		r[0] = p[0] + q[0] - 1;
		/* reduce r mod (x^GF_K + x^GF_T + 1): */
		gfReduce (r);
	} else {
		/* set r to the null polynomial: */
		r[0] = 0;
	}
	/* destroy potentially sensitive data: */
	x = log_pi = log_qj = 0;
	memset (lg, 0, sizeof (lg));
} /* gfMultiply */


void gfSquare (gfPoint r, const gfPoint p)
	/* sets r := p^2 mod (x^GF_K + x^GF_T + 1) */
{
	int i;
	ltemp x;

	assert (logt != NULL && expt != NULL);
	assert (r != NULL);
	assert (p != NULL);
	if (p[0]) {
		/* in what follows, note that (x != 0) => (x^2 = exp((2 * log(x)) % TOGGLE)): */
		i = p[0];
		if ((x = logt[p[i]]) != TOGGLE) { /* p[i] != 0 */
			r[2*i - 1] = expt[(x += x) >= TOGGLE ? x - TOGGLE : x];
		} else {
			r[2*i - 1] = 0;
		}
		for (i = p[0] - 1; i; i--) {
			r[2*i] = 0;
			if ((x = logt[p[i]]) != TOGGLE) { /* p[i] != 0 */
				r[2*i - 1] = expt[(x += x) >= TOGGLE ? x - TOGGLE : x];
			} else {
				r[2*i - 1] = 0;
			}
		}
		r[0] = 2*p[0] - 1;
		/* reduce r mod (x^GF_K + x^GF_T + 1): */
		gfReduce (r);
	} else {
		r[0] = 0;
	}
} /* gfSquare */


void gfSmallDiv (gfPoint p, lunit b)
	/* sets p := (b^(-1))*p mod (x^GF_K + x^GF_T + 1) */
{
	int i;
	ltemp x, lb = logt[b];

	assert (logt != NULL && expt != NULL);
	assert (p != NULL);
	assert (b != 0);
	for (i = p[0]; i; i--) {
		if ((x = logt[p[i]]) != TOGGLE) { /* p[i] != 0 */
			p[i] = expt[(x += TOGGLE - lb) >= TOGGLE ? x - TOGGLE : x];
		}
	}
} /* gfSmallDiv */