Elliptic curves over GF(p), new BIGNUM functions, Montgomery re-implementation.

These new files will not be included literally in OpenSSL, but I intend
to integrate most of their contents.  Most file names will change,
and when the integration is done, the superfluous files will be deleted.

Submitted by: Lenka Fibikova <fibikova@exp-math.uni-essen.de>

7 files changed, 2373 insertions, 0 deletions

diff --git a/crypto/bn/bn_modfs.c b/crypto/bn/bn_modfs.c
new file mode 100644
index 0000000000..2697d54303
--- /dev/null
+++ b/crypto/bn/bn_modfs.c
@@ -0,0 +1,258 @@
+/*

+ *

+ *	bn_modfs.c

+ *

+ *	Some Modular Arithmetic Functions.

+ *

+ *	Copyright (C) Lenka Fibikova 2000

+ *

+ *

+ */

+

+

+#include <stdio.h>

+#include <stdlib.h>

+#include <assert.h>

+

+#include "bn_modfs.h"

+

+#define MAX_ROUNDS	10

+

+int BN_smod(BIGNUM *rem, BIGNUM *m, BIGNUM *d, BN_CTX *ctx)

+{

+	int r_sign;

+

+	assert(rem != NULL && m != NULL && d != NULL && ctx != NULL);

+

+	if (d->neg) return 0;

+	r_sign = m->neg;

+

+	if (r_sign) m->neg = 0;

+	if (!(BN_div(NULL,rem,m,d,ctx))) return 0;

+	if (r_sign) 

+	{

+		m->neg = r_sign;

+		if (!BN_is_zero(rem))

+		{

+			rem->neg = r_sign;

+			BN_add(rem, rem, d);

+		}

+	}

+	return 1;

+}

+

+int BN_mod_sub(BIGNUM *r, BIGNUM *a, BIGNUM *b, BIGNUM *m, BN_CTX *ctx) 

+{

+	assert(r != NULL && a != NULL && b != NULL && m != NULL && ctx != NULL);

+

+	if (!BN_sub(r, a, b)) return 0;

+	return BN_smod(r, r, m, ctx);

+

+}

+

+int BN_mod_add(BIGNUM *r, BIGNUM *a, BIGNUM *b, BIGNUM *m, BN_CTX *ctx) 

+{

+	assert(r != NULL && a != NULL && b != NULL && m != NULL && ctx != NULL);

+

+	if (!BN_add(r, a, b)) return 0;

+	return BN_smod(r, r, m, ctx);

+

+}

+

+int BN_mod_sqr(BIGNUM *r, BIGNUM *a, BIGNUM *p, BN_CTX *ctx)

+{

+	assert(r != NULL && a != NULL && p != NULL && ctx != NULL);

+

+	if (!BN_sqr(r, a, ctx)) return 0;

+	return BN_div(NULL, r, r, p, ctx);

+}

+

+int BN_swap(BIGNUM *x, BIGNUM *y)

+{

+	BIGNUM *c;

+

+	assert(x != NULL && y != NULL);

+

+	if ((c = BN_dup(x)) == NULL) goto err;

+	if ((BN_copy(x, y)) == NULL) goto err;

+	if ((BN_copy(y, c)) == NULL) goto err;

+	BN_clear_free(c);

+	return 1;

+

+err:

+	if (c != NULL) BN_clear_free(c);

+	return 0;

+}

+

+

+int BN_legendre(BIGNUM *a, BIGNUM *p, BN_CTX *ctx) 

+{

+	BIGNUM *x, *y, *y2;

+	BN_ULONG m;

+	int L;

+

+	assert(a != NULL && p != NULL && ctx != NULL);

+

+	x = ctx->bn[ctx->tos]; 

+	y = ctx->bn[ctx->tos + 1]; 

+	y2 = ctx->bn[ctx->tos + 2]; 

+

+	ctx->tos += 3;

+

+	if (!BN_smod(x, a, p, ctx)) goto err;

+	if (BN_is_zero(x)) 

+	{

+

+		ctx->tos -= 3;

+		return 0;

+	}

+

+	if (BN_copy(y, p) == NULL) goto err;

+	L = 1;

+

+	while (1)

+	{

+		if (!BN_rshift1(y2, y)) goto err;

+		if (BN_cmp(x, y2) > 0)

+		{

+			if (!BN_sub(x, y, x)) goto err;

+			if (BN_mod_word(y, 4) == 3)

+				L = -L;			

+		}

+		while (BN_mod_word(x, 4) == 0)

+			BN_div_word(x, 4);

+		if (BN_mod_word(x, 2) == 0)

+		{

+			BN_div_word(x, 2);

+			m = BN_mod_word(y, 8);

+			if (m == 3 || m == 5) L = -L;			

+		}

+		if (BN_is_one(x)) 

+		{

+			ctx->tos -= 3;

+			return L;

+		}

+		

+		if (BN_mod_word(x, 4) == 3 && BN_mod_word(y, 4) == 3) L = -L;

+		if (!BN_swap(x, y)) goto err;

+

+		if (!BN_smod(x, x, y, ctx)) goto err;

+

+	}

+

+

+err:

+	ctx->tos -= 3;

+	return -2;

+

+}

+

+int BN_mod_sqrt(BIGNUM *x, BIGNUM *a, BIGNUM *p, BN_CTX *ctx) 

+/* x^2 = a (mod p) */

+{

+	int ret;

+	BIGNUM *n0, *n1, *r, *b, *m;

+	int max;

+

+	assert(x != NULL && a != NULL && p != NULL && ctx != NULL);

+	assert(BN_cmp(a, p) < 0);

+

+	ret = BN_legendre(a, p, ctx);

+	if (ret < 0 || ret > 1) return 0;

+	if (ret == 0)

+	{

+		if (!BN_zero(x)) return 0;

+		return 1;

+	}

+

+	n0 = ctx->bn[ctx->tos]; 

+	n1 = ctx->bn[ctx->tos + 1]; 

+	ctx->tos += 2;

+

+	if ((r = BN_new()) == NULL) goto err;

+	if ((b = BN_new()) == NULL) goto err;

+	if ((m = BN_new()) == NULL) goto err;

+

+

+	if (!BN_zero(n0)) goto err;

+	if (!BN_zero(n1)) goto err;

+	if (!BN_zero(r)) goto err;

+	if (!BN_zero(b)) goto err;

+	if (!BN_zero(m)) goto err;

+

+	max = 0;

+

+	do{

+		if (max++ > MAX_ROUNDS) goto err; /* if p is not prime could never stop*/

+		if (!BN_add_word(m, 1)) goto err;

+		ret = BN_legendre(m, p, ctx);

+		if (ret < -1 || ret > 1) goto err;

+

+	}while(ret != -1);

+

+	if (BN_copy(n1, p) == NULL) goto err;

+	if (!BN_sub_word(n1, 1)) goto err;

+

+	while (!BN_is_odd(n1))

+	{

+		if (!BN_add_word(r, 1)) goto err;

+		if (!BN_rshift1(n1, n1)) goto err;

+	}

+

+	if (!BN_mod_exp_simple(n0, m, n1, p, ctx)) goto err;

+

+	if (!BN_sub_word(n1, 1)) goto err;

+	if (!BN_rshift1(n1, n1)) goto err;

+	if (!BN_mod_exp_simple(x, a, n1, p, ctx)) goto err;

+

+	if (!BN_mod_sqr(b, x, p, ctx)) goto err;

+	if (!BN_mod_mul(b, b, a, p, ctx)) goto err;

+

+	if (!BN_mod_mul(x, x, a, p, ctx)) goto err;

+

+	while (!BN_is_one(b))

+	{

+		

+		if (!BN_one(m)) goto err;

+		if (!BN_mod_sqr(n1, b, p, ctx)) goto err;

+		while(!BN_is_one(n1))

+		{

+			if (!BN_mod_mul(n1, n1, n1, p, ctx)) goto err;

+			if (!BN_add_word(m, 1)) goto err;

+		}

+

+		if (!BN_sub(r, r, m)) goto err;

+		if (!BN_sub_word(r, 1)) goto err;

+		if (r->neg) goto err;

+

+		if (BN_copy(n1, n0) == NULL) goto err;

+		while(!BN_is_zero(r))

+		{

+			if (!BN_mod_mul(n1, n1, n1, p, ctx)) goto err;

+			if (!BN_sub_word(r, 1)) goto err;

+		}

+

+		if (!BN_mod_mul(n0, n1, n1, p, ctx)) goto err;

+		if (BN_copy(r, m) == NULL) goto err;

+		if (!BN_mod_mul(x, x, n1, p, ctx)) goto err;

+		if (!BN_mod_mul(b, b, n0, p, ctx)) goto err;

+	}

+

+

+#ifdef TEST

+	BN_mod_sqr(n0, x, p, ctx);

+	if (BN_cmp(n0, a)) goto err;

+#endif

+

+	if (r != NULL) BN_clear_free(r);

+	if (b != NULL) BN_clear_free(b);

+	if (m != NULL) BN_clear_free(m);

+	ctx->tos -= 2;

+	return 1;

+err:

+	if (r != NULL) BN_clear_free(r);

+	if (b != NULL) BN_clear_free(b);

+	if (m != NULL) BN_clear_free(m);

+	ctx->tos -= 2;

+	return 0;

+}

diff --git a/crypto/bn/bn_modfs.h b/crypto/bn/bn_modfs.h
new file mode 100644
index 0000000000..b7ae4964d8
--- /dev/null
+++ b/crypto/bn/bn_modfs.h
@@ -0,0 +1,32 @@
+/*

+ *

+ *	bn_modfs.h

+ *

+ *	Some Modular Arithmetic Functions.

+ *

+ *	Copyright (C) Lenka Fibikova 2000

+ *

+ *

+ */

+

+#ifndef HEADER_BN_MODFS_H

+#define HEADER_BN_MODFS_H

+

+

+#include "bn.h"

+

+#ifdef BN_is_zero

+#undef BN_is_zero

+#define BN_is_zero(a)	(((a)->top == 0) || (((a)->top == 1) && ((a)->d[0] == (BN_ULONG)0)))

+#endif /*BN_is_zero(a)*/

+

+

+int BN_smod(BIGNUM *rem, BIGNUM *m, BIGNUM *d, BN_CTX *ctx);

+int BN_mod_sub(BIGNUM *r, BIGNUM *a, BIGNUM *b, BIGNUM *m, BN_CTX *ctx);

+int BN_mod_add(BIGNUM *r, BIGNUM *a, BIGNUM *b, BIGNUM *m, BN_CTX *ctx); 

+int BN_mod_sqr(BIGNUM *r, BIGNUM *a, BIGNUM *p, BN_CTX *ctx);

+int BN_swap(BIGNUM *x, BIGNUM *y);

+int BN_legendre(BIGNUM *a, BIGNUM *p, BN_CTX *ctx);

+int BN_mod_sqrt(BIGNUM *x, BIGNUM *a, BIGNUM *p, BN_CTX *ctx);

+

+#endif
\ No newline at end of file
diff --git a/crypto/bn/bn_mont2.c b/crypto/bn/bn_mont2.c
new file mode 100644
index 0000000000..9f6222fb13
--- /dev/null
+++ b/crypto/bn/bn_mont2.c
@@ -0,0 +1,374 @@
+/*

+ *

+ *	bn_mont2.c

+ *

+ *	Montgomery Modular Arithmetic Functions.

+ *

+ *	Copyright (C) Lenka Fibikova 2000

+ *

+ *

+ */

+

+

+#include <stdio.h>

+#include <stdlib.h>

+#include <assert.h>

+

+#include "bn.h"

+#include "bn_modfs.h"

+#include "bn_mont2.h"

+

+#define BN_mask_word(x, m) ((x->d[0]) & (m))

+

+BN_MONTGOMERY *BN_mont_new()

+{

+	BN_MONTGOMERY *ret;

+

+	ret=(BN_MONTGOMERY *)malloc(sizeof(BN_MONTGOMERY));

+

+	if (ret == NULL) return NULL;

+

+	if ((ret->p = BN_new()) == NULL)

+	{

+		free(ret);

+		return NULL;

+	}

+

+	return ret;

+}

+

+

+void BN_mont_clear_free(BN_MONTGOMERY *mont)

+{

+	if (mont == NULL) return;

+

+	if (mont->p != NULL) BN_clear_free(mont->p);

+

+	mont->p_num_bytes = 0;

+	mont->R_num_bits = 0;

+	mont->p_inv_b_neg = 0;

+}

+

+int BN_to_mont(BIGNUM *x, BN_MONTGOMERY *mont, BN_CTX *ctx)

+{

+	assert(x != NULL);

+

+	assert(mont != NULL);

+	assert(mont->p != NULL);

+

+	assert(ctx != NULL);

+

+	if (!BN_lshift(x, x, mont->R_num_bits)) return 0;

+	if (!BN_mod(x, x, mont->p, ctx)) return 0;

+

+	return 1;

+}

+

+

+static BN_ULONG BN_mont_inv(BIGNUM *a, int e, BN_CTX *ctx)

+/* y = a^{-1} (mod 2^e) for an odd number a */

+{

+	BN_ULONG y, exp, mask;

+	BIGNUM *x, *xy, *x_sh;

+	int i;

+

+	assert(a != NULL && ctx != NULL);

+	assert(e <= BN_BITS2);

+	assert(BN_is_odd(a));

+	assert(!BN_is_zero(a) && !a->neg);

+

+

+	y = 1;

+	exp = 2;

+	mask = 3;

+	if((x = BN_dup(a)) == NULL) return 0;

+	if(!BN_mask_bits(x, e)) return 0;

+

+	xy = ctx->bn[ctx->tos]; 

+	x_sh = ctx->bn[ctx->tos + 1]; 

+	ctx->tos += 2;

+

+	if (BN_copy(xy, x) == NULL) goto err;

+	if (!BN_lshift1(x_sh, x)) goto err;

+

+

+	for (i = 2; i <= e; i++)

+	{

+		if (exp < BN_mask_word(xy, mask))

+		{

+			y = y + exp;

+			if (!BN_add(xy, xy, x_sh)) goto err;

+		}

+

+		exp <<= 1;

+		if (!BN_lshift1(x_sh, x_sh)) goto err;

+		mask <<= 1;

+		mask++;

+	}

+

+

+#ifdef TEST

+	if (xy->d[0] != 1) goto err;

+#endif

+

+	if (x != NULL) BN_clear_free(x);

+	ctx->tos -= 2;

+	return y;

+

+

+err:

+	if (x != NULL) BN_clear_free(x);

+	ctx->tos -= 2;

+	return 0;

+

+}

+

+int BN_mont_set(BIGNUM *p, BN_MONTGOMERY *mont, BN_CTX *ctx)

+{

+	assert(p != NULL && ctx != NULL);

+	assert(mont != NULL);

+	assert(mont->p != NULL);

+	assert(!BN_is_zero(p) && !p->neg);

+

+

+	mont->p_num_bytes = p->top;

+	mont->R_num_bits = (mont->p_num_bytes) * BN_BITS2;

+

+	if (BN_copy(mont->p, p) == NULL);

+	

+	mont->p_inv_b_neg =  BN_mont_inv(p, BN_BITS2, ctx);

+	mont->p_inv_b_neg = 0 - mont->p_inv_b_neg;

+

+	return 1;

+}

+

+static int BN_cpy_mul_word(BIGNUM *ret, BIGNUM *a, BN_ULONG w)

+/* ret = a * w */

+{

+	if (BN_copy(ret, a) == NULL) return 0;

+

+	if (!BN_mul_word(ret, w)) return 0;

+

+	return 1;

+}

+

+

+int BN_mont_red(BIGNUM *y, BN_MONTGOMERY *mont, BN_CTX *ctx)

+/* yR^{-1} (mod p) */

+{

+	int i;

+	BIGNUM *up, *p;

+	BN_ULONG u;

+

+	assert(y != NULL && mont != NULL && ctx != NULL);

+	assert(mont->p != NULL);

+	assert(BN_cmp(y, mont->p) < 0);

+	assert(!y->neg);

+

+

+	if (BN_is_zero(y)) return 1;

+

+	p = mont->p;

+	up = ctx->bn[ctx->tos]; 

+	ctx->tos += 1;

+

+

+	for (i = 0; i < mont->p_num_bytes; i++)

+	{

+		u = (y->d[0]) * mont->p_inv_b_neg;			/* u = y_0 * p' */

+

+		if (!BN_cpy_mul_word(up, p, u)) goto err;	/* up = u * p */

+

+		if (!BN_add(y, y, up)) goto err;			

+#ifdef TEST

+		if (y->d[0]) goto err;

+#endif

+		if (!BN_rshift(y, y, BN_BITS2)) goto err;	/* y = (y + up)/b */

+	}

+

+

+	if (BN_cmp(y, mont->p) >= 0) 

+	{

+		if (!BN_sub(y, y, mont->p)) goto err;

+	}

+

+	ctx->tos -= 1;

+	return 1;

+

+err:

+	ctx->tos -= 1;

+	return 0;

+

+}

+

+

+int BN_mont_mod_mul(BIGNUM *r, BIGNUM *x, BIGNUM *y, BN_MONTGOMERY *mont, BN_CTX *ctx)

+/* r = x * y mod p */

+/* r != x && r! = y !!! */

+{

+	BIGNUM *xiy, *up;

+	BN_ULONG u;

+	int i;

+	

+

+	assert(r != x && r != y);

+	assert(r != NULL && x != NULL  && y != NULL && mont != NULL && ctx != NULL);

+	assert(mont->p != NULL);

+	assert(BN_cmp(x, mont->p) < 0);

+	assert(BN_cmp(y, mont->p) < 0);

+	assert(!x->neg);

+	assert(!y->neg);

+

+	if (BN_is_zero(x) || BN_is_zero(y))

+	{

+		if (!BN_zero(r)) return 0;

+		return 1;

+	}

+

+

+

+	xiy = ctx->bn[ctx->tos]; 

+	up = ctx->bn[ctx->tos + 1]; 

+	ctx->tos += 2;

+

+	if (!BN_zero(r)) goto err;

+

+	for (i = 0; i < x->top; i++)

+	{

+		u = (r->d[0] + x->d[i] * y->d[0]) * mont->p_inv_b_neg;

+

+		if (!BN_cpy_mul_word(xiy, y, x->d[i])) goto err;

+		if (!BN_cpy_mul_word(up, mont->p, u)) goto err;

+

+		if (!BN_add(r, r, xiy)) goto err;

+		if (!BN_add(r, r, up)) goto err;

+

+#ifdef TEST

+		if (r->d[0]) goto err;

+#endif

+		if (!BN_rshift(r, r, BN_BITS2)) goto err; 

+	}

+

+	for (i = x->top; i < mont->p_num_bytes; i++)

+	{

+		u = (r->d[0]) * mont->p_inv_b_neg;

+

+		if (!BN_cpy_mul_word(up, mont->p, u)) goto err;

+

+		if (!BN_add(r, r, up)) goto err;

+

+#ifdef TEST

+		if (r->d[0]) goto err;

+#endif

+		if (!BN_rshift(r, r, BN_BITS2)) goto err; 

+	}

+

+

+	if (BN_cmp(r, mont->p) >= 0) 

+	{

+		if (!BN_sub(r, r, mont->p)) goto err;

+	}

+

+

+	ctx->tos -= 2;

+	return 1;

+

+err:

+	ctx->tos -= 2;

+	return 0;

+}

+

+int BN_mont_mod_add(BIGNUM *r, BIGNUM *x, BIGNUM *y, BN_MONTGOMERY *mont)

+{

+	assert(r != NULL && x != NULL  && y != NULL && mont != NULL);

+	assert(mont->p != NULL);

+	assert(BN_cmp(x, mont->p) < 0);

+	assert(BN_cmp(y, mont->p) < 0);

+	assert(!x->neg);

+	assert(!y->neg);

+

+	if (!BN_add(r, x, y)) return 0;

+	if (BN_cmp(r, mont->p) >= 0) 

+	{

+		if (!BN_sub(r, r, mont->p)) return 0;

+	}

+

+	return 1;

+}

+

+

+int BN_mont_mod_sub(BIGNUM *r, BIGNUM *x, BIGNUM *y, BN_MONTGOMERY *mont)

+{

+	assert(r != NULL && x != NULL  && y != NULL && mont != NULL);

+	assert(mont->p != NULL);

+	assert(BN_cmp(x, mont->p) < 0);

+	assert(BN_cmp(y, mont->p) < 0);

+	assert(!x->neg);

+	assert(!y->neg);

+

+	if (!BN_sub(r, x, y)) return 0;

+	if (r->neg) 

+	{

+		if (!BN_add(r, r, mont->p)) return 0;

+	}

+

+	return 1;

+}

+

+int BN_mont_mod_lshift1(BIGNUM *r, BIGNUM *x, BN_MONTGOMERY *mont)

+{

+	assert(r != NULL && x != NULL && mont != NULL);

+	assert(mont->p != NULL);

+	assert(BN_cmp(x, mont->p) < 0);

+	assert(!x->neg);

+

+	if (!BN_lshift1(r, x)) return 0;

+

+	if (BN_cmp(r, mont->p) >= 0) 

+	{

+		if (!BN_sub(r, r, mont->p)) return 0;

+	}

+

+	return 1;

+}

+

+int BN_mont_mod_lshift(BIGNUM *r, BIGNUM *x, int n, BN_MONTGOMERY *mont)

+{

+	int sh_nb;

+

+	assert(r != NULL && x != NULL && mont != NULL);

+	assert(mont->p != NULL);

+	assert(BN_cmp(x, mont->p) < 0);

+	assert(!x->neg);

+	assert(n > 0);

+

+	if (r != x)

+	{

+		if (BN_copy(r, x) == NULL) return 0;

+	}

+

+	while (n)

+	{

+		sh_nb = BN_num_bits(mont->p) - BN_num_bits(r);

+		if (sh_nb > n) sh_nb = n;

+

+		if (sh_nb)

+		{

+			if(!BN_lshift(r, r, sh_nb)) return 0;

+		}

+		else 

+		{

+			sh_nb = 1;

+			if (!BN_lshift1(r, r)) return 0;

+		}

+

+		if (BN_cmp(r, mont->p) >= 0) 

+		{

+			if (!BN_sub(r, r, mont->p)) return 0;

+		}

+

+		n -= sh_nb;

+	}

+

+	return 1;

+}

diff --git a/crypto/bn/bn_mont2.h b/crypto/bn/bn_mont2.h
new file mode 100644
index 0000000000..1bce6d71f1
--- /dev/null
+++ b/crypto/bn/bn_mont2.h
@@ -0,0 +1,41 @@
+/*

+ *

+ *	bn_mont2.h

+ *

+ *	Montgomery Modular Arithmetic Functions.

+ *

+ *	Copyright (C) Lenka Fibikova 2000

+ *

+ *

+ */

+

+#ifndef HEADER_MONT2_H

+#define HEADER_MONT2_H

+

+#define MONTGOMERY

+

+#include "bn.h"

+

+typedef struct bn_mont_st{

+	int R_num_bits;

+	int p_num_bytes;

+	BIGNUM *p;

+	BN_ULONG p_inv_b_neg;	/* p' = p^{-1} mod b; b = 2^BN_BITS */

+} BN_MONTGOMERY;

+

+#define BN_from_mont(x, mont, ctx) (BN_mont_red((x), (mont), (ctx)))

+

+

+BN_MONTGOMERY *BN_mont_new();

+int BN_to_mont(BIGNUM *x, BN_MONTGOMERY *mont, BN_CTX *ctx); 

+void BN_mont_clear_free(BN_MONTGOMERY *mont);

+int BN_mont_set(BIGNUM *p, BN_MONTGOMERY *mont, BN_CTX *ctx);

+int BN_mont_red(BIGNUM *y, BN_MONTGOMERY *mont, BN_CTX *ctx);

+BN_ULONG BN_mont_inv(BIGNUM *x, int e, BN_CTX *ctx);

+int BN_mont_mod_mul(BIGNUM *r, BIGNUM *x, BIGNUM *y, BN_MONTGOMERY *mont, BN_CTX *ctx);

+int BN_mont_mod_add(BIGNUM *r, BIGNUM *x, BIGNUM *y, BN_MONTGOMERY *mont);

+int BN_mont_mod_sub(BIGNUM *r, BIGNUM *x, BIGNUM *y, BN_MONTGOMERY *mont);

+int BN_mont_mod_lshift1(BIGNUM *r, BIGNUM *x, BN_MONTGOMERY *mont);

+int BN_mont_mod_lshift(BIGNUM *r, BIGNUM *x, int n, BN_MONTGOMERY *mont);

+

+#endif
\ No newline at end of file
diff --git a/crypto/ec/ec.c b/crypto/ec/ec.c
new file mode 100644
index 0000000000..bc689e74f2
--- /dev/null
+++ b/crypto/ec/ec.c
@@ -0,0 +1,121 @@
+/*

+ *

+ *	ec.c

+ *

+ *	Elliptic Curve Arithmetic Functions

+ *

+ *	Copyright (C) Lenka Fibikova 2000

+ *

+ *

+ */

+

+

+#include <stdio.h>

+#include <stdlib.h>

+#include <assert.h>

+

+#include "ec.h"

+#include "bn_modfs.h"

+

+

+

+EC *EC_new()

+{

+	EC *ret;

+

+	ret=(EC *)malloc(sizeof(EC));

+	if (ret == NULL) return NULL;

+	ret->A = BN_new();

+	ret->B = BN_new();

+	ret->p = BN_new();

+	ret->h = BN_new();

+	ret->is_in_mont = 0;

+

+	if (ret->A == NULL || ret->B == NULL || ret->p == NULL || ret->h == NULL)

+	{

+		if (ret->A != NULL) BN_free(ret->A);

+		if (ret->B != NULL) BN_free(ret->B);

+		if (ret->p != NULL) BN_free(ret->p);

+		if (ret->h != NULL) BN_free(ret->h);

+		free(ret);

+		return(NULL);

+	}

+	return(ret);

+}

+

+

+void EC_clear_free(EC *E)

+{

+	if (E == NULL) return;

+

+	if (E->A != NULL) BN_clear_free(E->A);

+	if (E->B != NULL) BN_clear_free(E->B);

+	if (E->p != NULL) BN_clear_free(E->p);

+	if (E->h != NULL) BN_clear_free(E->h);

+	E->is_in_mont = 0;

+	free(E);

+}

+

+

+#ifdef MONTGOMERY

+int EC_to_montgomery(EC *E, BN_MONTGOMERY *mont, BN_CTX *ctx)

+{

+	assert(E != NULL);

+	assert(E->A != NULL && E->B != NULL && E->p != NULL && E->h != NULL);

+

+	assert(mont != NULL);

+	assert(mont->p != NULL);

+

+	assert(ctx != NULL);

+

+	if (E->is_in_mont) return 1;

+

+	if (!BN_lshift(E->A, E->A, mont->R_num_bits)) return 0;

+	if (!BN_mod(E->A, E->A, mont->p, ctx)) return 0;

+

+	if (!BN_lshift(E->B, E->B, mont->R_num_bits)) return 0;

+	if (!BN_mod(E->B, E->B, mont->p, ctx)) return 0;

+

+	if (!BN_lshift(E->h, E->h, mont->R_num_bits)) return 0;

+	if (!BN_mod(E->h, E->h, mont->p, ctx)) return 0;

+

+	E->is_in_mont = 1;

+	return 1;

+

+}

+

+

+int EC_from_montgomery(EC *E, BN_MONTGOMERY *mont, BN_CTX *ctx)

+{

+	assert(E != NULL);

+	assert(E->A != NULL && E->B != NULL && E->p != NULL && E->h != NULL);

+

+	assert(mont != NULL);

+	assert(mont->p != NULL);

+

+	assert(ctx != NULL);

+

+	if (!E->is_in_mont) return 1;

+

+	if (!BN_mont_red(E->A, mont, ctx)) return 0;

+	if (!BN_mont_red(E->B, mont, ctx)) return 0;

+	if (!BN_mont_red(E->h, mont, ctx)) return 0;

+

+	E->is_in_mont = 0;

+	return 1;

+}

+#endif /* MONTGOMERY */

+

+int EC_set_half(EC *E)

+/* h <- 1/2 mod p = (p + 1)/2 */

+{

+	assert(E != NULL);

+	assert(E->p != NULL);

+	assert(E->h != NULL);

+	assert(!E->is_in_mont);

+

+	if (BN_copy(E->h, E->p) == NULL) return 0; 

+	if (!BN_add_word(E->h, 1)) return 0;

+	if (!BN_rshift1(E->h, E->h)) return 0; 

+	return 1;

+}

diff --git a/crypto/ec/ec.h b/crypto/ec/ec.h
new file mode 100644
index 0000000000..97d55cb2cc
--- /dev/null
+++ b/crypto/ec/ec.h
@@ -0,0 +1,86 @@
+/*

+ *

+ *	ec.h

+ *

+ *	Elliptic Curve Arithmetic Functions

+ *

+ *	Copyright (C) Lenka Fibikova 2000

+ *

+ *

+ */

+

+

+#ifndef HEADER_EC_H

+#define HEADER_EC_H

+

+

+#include "bn.h"

+#include "bn_mont2.h"

+

+typedef struct bn_ec_struct		/* E: y^2 = x^3 + Ax + B  (mod p) */

+{

+	BIGNUM	*A, *B, *p, *h;		/* h = 1/2 mod p = (p + 1)/2 */

+	int is_in_mont;

+} EC;

+

+typedef struct bn_ec_point_struct /* P = [X, Y, Z] */

+{

+	BIGNUM	*X, *Y, *Z;

+	int is_in_mont;

+} EC_POINT;

+

+typedef struct bn_ecp_precompute_struct /* Pi[i] = [2i + 1]P	i = 0..2^{r-1} - 1 */

+{

+	int r;

+	EC_POINT **Pi;

+} ECP_PRECOMPUTE;

+

+

+#define ECP_is_infty(P) (BN_is_zero(P->Z))

+#define ECP_is_norm(P) (BN_is_one(P->Z))

+

+#define ECP_mont_minus(P, mont) (ECP_minus((P), (mont)->p))

+

+

+EC *EC_new();

+void EC_clear_free(EC *E);

+int EC_set_half(EC *E);

+#ifdef MONTGOMERY

+int EC_to_montgomery(EC *E, BN_MONTGOMERY *mont, BN_CTX *ctx);

+int EC_from_montgomery(EC *E, BN_MONTGOMERY *mont, BN_CTX *ctx);

+#endif /* MONTGOMERY */

+

+

+EC_POINT *ECP_new();

+void ECP_clear_free(EC_POINT *P);

+void ECP_clear_free_precompute(ECP_PRECOMPUTE *prec);

+

+EC_POINT *ECP_generate(BIGNUM *x, BIGNUM *z, EC *E, BN_CTX *ctx);

+EC_POINT *ECP_dup(EC_POINT *P);

+int ECP_copy(EC_POINT *R, EC_POINT *P);

+int ECP_normalize(EC_POINT *P, EC *E, BN_CTX *ctx);

+EC_POINT *ECP_minus(EC_POINT *P, BIGNUM *p);

+int ECP_is_on_ec(EC_POINT *P, EC *E, BN_CTX *ctx);

+int ECP_ecp2bin(EC_POINT *P, unsigned char *to, int form); /* form(ANSI 9.62): 1-compressed; 2-uncompressed; 3-hybrid */

+int ECP_bin2ecp(unsigned char *from, int len, EC_POINT *P, EC *E, BN_CTX *ctx);

+

+#ifdef SIMPLE

+int ECP_cmp(EC_POINT *P, EC_POINT *Q, BIGNUM *p, BN_CTX *ctx);

+int ECP_double(EC_POINT *R, EC_POINT *P, EC *E, BN_CTX *ctx);

+int ECP_add(EC_POINT *R, EC_POINT *P, EC_POINT *Q, EC *E, BN_CTX *ctx);

+ECP_PRECOMPUTE *ECP_precompute(int r, EC_POINT *P, EC *E, BN_CTX *ctx);

+int ECP_multiply(EC_POINT *R, BIGNUM *k, ECP_PRECOMPUTE *prec, EC *E, BN_CTX *ctx);

+#endif /* SIMPLE */

+

+#ifdef MONTGOMERY

+int ECP_to_montgomery(EC_POINT *P, BN_MONTGOMERY *mont, BN_CTX *ctx);

+int ECP_from_montgomery(EC_POINT *P, BN_MONTGOMERY *mont, BN_CTX *ctx);

+int ECP_mont_cmp(EC_POINT *P, EC_POINT *Q, BN_MONTGOMERY *mont, BN_CTX *ctx);

+int ECP_mont_double(EC_POINT *R, EC_POINT *P, EC *E, BN_MONTGOMERY *mont, BN_CTX *ctx);

+int ECP_mont_add(EC_POINT *R, EC_POINT *P, EC_POINT *Q, EC *E, BN_MONTGOMERY *mont, BN_CTX *ctx);

+ECP_PRECOMPUTE *ECP_mont_precompute(int r, EC_POINT *P, EC *E, BN_MONTGOMERY *mont, BN_CTX *ctx);

+int ECP_mont_multiply(EC_POINT *R, BIGNUM *k, ECP_PRECOMPUTE *prec, EC *E, BN_MONTGOMERY *mont, BN_CTX *ctx);

+int ECP_mont_multiply2(EC_POINT *R, BIGNUM *k, EC_POINT *P, EC *E, BN_MONTGOMERY *mont, BN_CTX *ctx);

+#endif /* MONTGOMERY */

+

+#endif
\ No newline at end of file
diff --git a/crypto/ec/ec_point.c b/crypto/ec/ec_point.c
new file mode 100644
index 0000000000..fee5078bf8
--- /dev/null
+++ b/crypto/ec/ec_point.c
@@ -0,0 +1,1461 @@
+/*

+ *

+ *	ec_point.c

+ *

+ *	Elliptic Curve Arithmetic Functions

+ *

+ *	Copyright (C) Lenka Fibikova 2000

+ *

+ *

+ */

+

+#include <stdio.h>

+#include <stdlib.h>

+#include <assert.h>

+#include <memory.h>

+

+#include "bn.h"

+

+#include "bn_modfs.h"

+#include "bn_mont2.h"

+#include "ec.h"

+

+EC_POINT *ECP_new()

+{

+	EC_POINT *ret;

+

+	ret=(EC_POINT *)malloc(sizeof(EC_POINT));

+	if (ret == NULL) return NULL;

+	ret->X = BN_new();

+	ret->Y = BN_new();

+	ret->Z = BN_new();

+	ret->is_in_mont = 0;

+

+	if (ret->X == NULL || ret->Y == NULL || ret->Z == NULL) 

+	{

+		if (ret->X != NULL) BN_free(ret->X);

+		if (ret->Y != NULL) BN_free(ret->Y);

+		if (ret->Z != NULL) BN_free(ret->Z);

+		free(ret);

+		return(NULL);

+	}

+	return(ret);

+}

+

+void ECP_clear_free(EC_POINT *P)

+{

+	if (P == NULL) return;

+	

+	P->is_in_mont = 0;

+	if (P->X != NULL) BN_clear_free(P->X);

+	if (P->Y != NULL) BN_clear_free(P->Y);

+	if (P->Z != NULL) BN_clear_free(P->Z);

+	free(P);

+}

+

+void ECP_clear_free_precompute(ECP_PRECOMPUTE *prec)

+{

+	int i;

+	int max;

+

+	if (prec == NULL) return;

+	if (prec->Pi != NULL)

+	{

+		max = 1;

+		max <<= (prec->r - 1);

+

+		for (i = 0; i < max; i++)

+		{

+			if (prec->Pi[i] != NULL) ECP_clear_free(prec->Pi[i]);

+		}

+	}

+	free(prec);

+}

+

+int ECP_is_on_ec(EC_POINT *P, EC *E, BN_CTX *ctx)

+{

+	BIGNUM *n0, *n1, *n2, *p;

+	int Pnorm;

+

+	assert(P != NULL);

+	assert(P->X != NULL && P->Y != NULL && P->Z != NULL);

+

+	assert(E != NULL);

+	assert(E->A != NULL && E->B != NULL && E->p != NULL);

+

+	assert(ctx != NULL);

+

+	assert(!P->is_in_mont);

+

+	if (ECP_is_infty(P)) return 1;

+	

+	n0 = ctx->bn[ctx->tos]; 

+	n1 = ctx->bn[ctx->tos + 1]; 

+	n2 = ctx->bn[ctx->tos + 2]; 

+	ctx->tos += 3;

+

+

+	p = E->p;

+

+	Pnorm = (ECP_is_norm(P));

+

+	if (!Pnorm)

+	{

+		if (!BN_mod_mul(n0, P->Z, P->Z, p, ctx)) goto err;

+		if (!BN_mod_mul(n1, n0, n0, p, ctx)) goto err;

+		if (!BN_mod_mul(n2, n0, n1, p, ctx)) goto err;

+	}

+

+	if (!BN_mod_mul(n0, P->X, P->X, p, ctx)) goto err;

+	if (!BN_mod_mul(n0, n0, P->X, p, ctx)) goto err;

+

+	if (Pnorm)

+	{

+		if (!BN_mod_mul(n1, P->X, E->A, p, ctx)) goto err;

+	}

+	else

+	{

+		if (!BN_mod_mul(n1, n1, P->X, p, ctx)) goto err;

+		if (!BN_mod_mul(n1, n1, E->A, p, ctx)) goto err;

+	}

+	if (!BN_mod_add(n0, n0, n1, p, ctx)) goto err;

+

+	if (Pnorm)

+	{

+		if (!BN_mod_add(n0, n0, E->B, p, ctx)) goto err;

+	}

+	else

+	{

+		if (!BN_mod_mul(n2, n2, E->B,  p, ctx)) goto err;

+		if (!BN_mod_add(n0, n0, n2, p, ctx)) goto err;

+	}

+

+	if (!BN_mod_mul(n1, P->Y, P->Y, p, ctx)) goto err;

+

+	if (BN_cmp(n0, n1)) 

+	{ 

+		ctx->tos -= 3;

+		return 0;

+	}

+

+	ctx->tos -= 3;

+	return 1;

+	

+err:

+	ctx->tos -= 3;

+	return -1;

+}

+

+

+EC_POINT *ECP_generate(BIGNUM *x, BIGNUM *z,EC *E, BN_CTX *ctx)

+/* x == NULL || z = 0  -> point of infinity	*/

+/* z == NULL || z = 1  -> normalized		*/

+{

+	BIGNUM *n0, *n1;

+	EC_POINT *ret;

+	int Pnorm, Pinfty, X0, A0;

+

+	assert(E != NULL);

+	assert(E->A != NULL && E->B != NULL && E->p != NULL && E->h != NULL);

+

+	assert(ctx != NULL);

+

+	Pinfty = (x == NULL);

+	Pnorm = (z == NULL);

+	if (!Pnorm) 

+	{

+		Pnorm = BN_is_one(z);

+		Pinfty = (Pinfty || BN_is_zero(z));

+	}

+

+	if (Pinfty) 

+	{

+		if ((ret = ECP_new()) == NULL) return NULL;

+		if (!BN_zero(ret->Z)) 

+		{ 

+			ECP_clear_free(ret);

+			return NULL;

+		}

+		return ret;

+	}

+

+	X0 = BN_is_zero(x);

+	A0 = BN_is_zero(E->A);

+

+	if ((ret = ECP_new()) == NULL) return NULL;

+

+	ret->is_in_mont = 0;

+

+	n0 = ctx->bn[ctx->tos]; 

+	n1 = ctx->bn[ctx->tos + 1]; 

+	if (!BN_zero(n0)) return NULL;

+	if (!BN_zero(n1)) return NULL;

+

+	ctx->tos += 2;

+

+	if (!X0)

+	{

+		if (!BN_mod_sqr(n0, x, E->p, ctx)) goto err;

+		if (!BN_mod_mul(n0, n0, x, E->p, ctx)) goto err;	/* x^3 */

+	}

+

+	if (!X0 && !A0)

+	{

+		if (!BN_mod_mul(n1, E->A, x, E->p, ctx)) goto err;	/* Ax */

+		if (!BN_mod_add(n0, n0, n1, E->p, ctx)) goto err;	/* x^3 + Ax */

+	}

+

+	if (!BN_is_zero(E->B))

+		if (!BN_mod_add(n0, n0, E->B, E->p, ctx)) goto err;	/* x^3 + Ax +B */

+

+	if (!BN_mod_sqrt(ret->Y, n0, E->p, ctx)) goto err;

+	if (BN_copy(ret->X, x) == NULL) goto err;

+	

+	if (Pnorm)

+	{

+		if (!BN_one(ret->Z)) goto err;

+	}

+	else

+	{

+		if (BN_copy(ret->Z, z) == NULL) goto err;

+		if (!BN_mod_sqr(n0, z, E->p, ctx)) goto err;

+		if (!BN_mod_mul(ret->X, ret->X, n0, E->p, ctx)) goto err;

+		if (!BN_mod_mul(n0, n0, z, E->p, ctx)) goto err;

+		if (!BN_mod_mul(ret->Y, ret->Y, n0, E->p, ctx)) goto err;

+	}

+

+#ifdef TEST

+	if (!ECP_is_on_ec(ret, E, ctx)) goto err;

+#endif

+	

+	ctx->tos -= 2;

+	return ret;

+

+err:

+	if (ret != NULL) ECP_clear_free(ret);

+	ctx->tos -= 2;

+	return NULL;

+}

+

+int ECP_ecp2bin(EC_POINT *P, unsigned char *to, int form)

+/* form =	1 ... compressed

+			2 ... uncompressed

+			3 ... hybrid */

+{

+	int bytes, bx, by;