7 files changed, 2370 insertions, 2370 deletions

diff --git a/crypto/bn/bn_modfs.c b/crypto/bn/bn_modfs.c
index 2697d54303..c6986fb2e7 100644
--- a/crypto/bn/bn_modfs.c
+++ b/crypto/bn/bn_modfs.c
@@ -1,258 +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;

-}

+/*
+ *
+ *	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
index b7ae4964d8..c596ca3973 100644
--- a/crypto/bn/bn_modfs.h
+++ b/crypto/bn/bn_modfs.h
@@ -1,32 +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);

-

+/*
+ *
+ *	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
index 9f6222fb13..871282400c 100644
--- a/crypto/bn/bn_mont2.c
+++ b/crypto/bn/bn_mont2.c
@@ -1,374 +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;

-}

+/*
+ *
+ *	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)
+{
+	i