More BN_mod_... functions.

9 files changed, 210 insertions, 171 deletions

diff --git a/crypto/bn/bn.h b/crypto/bn/bn.h
index 0a665c2538..9e3bbf400a 100644
--- a/crypto/bn/bn.h
+++ b/crypto/bn/bn.h
@@ -341,12 +341,22 @@ int	BN_uadd(BIGNUM *r, const BIGNUM *a, const BIGNUM *b);
 int	BN_add(BIGNUM *r, const BIGNUM *a, const BIGNUM *b);
 int	BN_mul(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, BN_CTX *ctx);
 int	BN_sqr(BIGNUM *r, const BIGNUM *a,BN_CTX *ctx);
+
 int	BN_div(BIGNUM *dv, BIGNUM *rem, const BIGNUM *m, const BIGNUM *d,
 	BN_CTX *ctx);
 #define BN_mod(rem,m,d,ctx) BN_div(NULL,(rem),(m),(d),(ctx))
-int	BN_nnmod(BIGNUM *rem, const BIGNUM *m, const BIGNUM *d, BN_CTX *ctx);
-int	BN_mod_mul(BIGNUM *ret, const BIGNUM *a, const BIGNUM *b,
+int	BN_nnmod(BIGNUM *r, const BIGNUM *m, const BIGNUM *d, BN_CTX *ctx);
+int	BN_mod_add(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, const BIGNUM *m, BN_CTX *ctx);
+int	BN_mod_add_quick(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, const BIGNUM *m);
+int	BN_mod_sub(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, const BIGNUM *m, BN_CTX *ctx);
+int	BN_mod_sub_quick(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, const BIGNUM *m);
+int	BN_mod_mul(BIGNUM *r, const BIGNUM *a, const BIGNUM *b,
 	const BIGNUM *m, BN_CTX *ctx);
+int	BN_mod_lshift1(BIGNUM *r, const BIGNUM *a, const BIGNUM *m, BN_CTX *ctx);
+int	BN_mod_lshift1_quick(BIGNUM *r, const BIGNUM *a, const BIGNUM *m);
+int	BN_mod_lshift(BIGNUM *r, const BIGNUM *a, int n, const BIGNUM *m, BN_CTX *ctx);
+int	BN_mod_lshift_quick(BIGNUM *r, const BIGNUM *a, int n, const BIGNUM *m);
+
 BN_ULONG BN_mod_word(const BIGNUM *a, BN_ULONG w);
 BN_ULONG BN_div_word(BIGNUM *a, BN_ULONG w);
 int	BN_mul_word(BIGNUM *a, BN_ULONG w);
@@ -354,12 +364,14 @@ int	BN_add_word(BIGNUM *a, BN_ULONG w);
 int	BN_sub_word(BIGNUM *a, BN_ULONG w);
 int	BN_set_word(BIGNUM *a, BN_ULONG w);
 BN_ULONG BN_get_word(const BIGNUM *a);
+
 int	BN_cmp(const BIGNUM *a, const BIGNUM *b);
 void	BN_free(BIGNUM *a);
 int	BN_is_bit_set(const BIGNUM *a, int n);
 int	BN_lshift(BIGNUM *r, const BIGNUM *a, int n);
 int	BN_lshift1(BIGNUM *r, const BIGNUM *a);
 int	BN_exp(BIGNUM *r, const BIGNUM *a, const BIGNUM *p,BN_CTX *ctx);
+
 int	BN_mod_exp(BIGNUM *r, const BIGNUM *a, const BIGNUM *p,
 	const BIGNUM *m,BN_CTX *ctx);
 int	BN_mod_exp_mont(BIGNUM *r, const BIGNUM *a, const BIGNUM *p,
@@ -371,6 +383,7 @@ int	BN_mod_exp2_mont(BIGNUM *r, const BIGNUM *a1, const BIGNUM *p1,
 	BN_CTX *ctx,BN_MONT_CTX *m_ctx);
 int	BN_mod_exp_simple(BIGNUM *r, const BIGNUM *a, const BIGNUM *p,
 	const BIGNUM *m,BN_CTX *ctx);
+
 int	BN_mask_bits(BIGNUM *a,int n);
 #ifndef NO_FP_API
 int	BN_print_fp(FILE *fp, const BIGNUM *a);
@@ -495,6 +508,7 @@ void bn_dump1(FILE *o, const char *a, const BN_ULONG *b,int n);
 #define BN_F_BN_MOD_EXP_MONT				 109
 #define BN_F_BN_MOD_EXP_MONT_WORD			 117
 #define BN_F_BN_MOD_INVERSE				 110
+#define BN_F_BN_MOD_LSHIFT_QUICK			 119
 #define BN_F_BN_MOD_MUL_RECIPROCAL			 111
 #define BN_F_BN_MPI2BN					 112
 #define BN_F_BN_NEW					 113
@@ -508,6 +522,7 @@ void bn_dump1(FILE *o, const char *a, const BN_ULONG *b,int n);
 #define BN_R_DIV_BY_ZERO				 103
 #define BN_R_ENCODING_ERROR				 104
 #define BN_R_EXPAND_ON_STATIC_BIGNUM_DATA		 105
+#define BN_R_INPUT_NOT_REDUCED				 110
 #define BN_R_INVALID_LENGTH				 106
 #define BN_R_NOT_INITIALIZED				 107
 #define BN_R_NO_INVERSE					 108
@@ -517,3 +532,4 @@ void bn_dump1(FILE *o, const char *a, const BN_ULONG *b,int n);
 }
 #endif
 #endif
+
diff --git a/crypto/bn/bn_err.c b/crypto/bn/bn_err.c
index 86550c4c21..14bd8bbcba 100644
--- a/crypto/bn/bn_err.c
+++ b/crypto/bn/bn_err.c
@@ -80,6 +80,7 @@ static ERR_STRING_DATA BN_str_functs[]=
 {ERR_PACK(0,BN_F_BN_MOD_EXP_MONT,0),	"BN_mod_exp_mont"},
 {ERR_PACK(0,BN_F_BN_MOD_EXP_MONT_WORD,0),	"BN_mod_exp_mont_word"},
 {ERR_PACK(0,BN_F_BN_MOD_INVERSE,0),	"BN_mod_inverse"},
+{ERR_PACK(0,BN_F_BN_MOD_LSHIFT_QUICK,0),	"BN_mod_lshift_quick"},
 {ERR_PACK(0,BN_F_BN_MOD_MUL_RECIPROCAL,0),	"BN_mod_mul_reciprocal"},
 {ERR_PACK(0,BN_F_BN_MPI2BN,0),	"BN_mpi2bn"},
 {ERR_PACK(0,BN_F_BN_NEW,0),	"BN_new"},
@@ -96,6 +97,7 @@ static ERR_STRING_DATA BN_str_reasons[]=
 {BN_R_DIV_BY_ZERO                        ,"div by zero"},
 {BN_R_ENCODING_ERROR                     ,"encoding error"},
 {BN_R_EXPAND_ON_STATIC_BIGNUM_DATA       ,"expand on static bignum data"},
+{BN_R_INPUT_NOT_REDUCED                  ,"input not reduced"},
 {BN_R_INVALID_LENGTH                     ,"invalid length"},
 {BN_R_NOT_INITIALIZED                    ,"not initialized"},
 {BN_R_NO_INVERSE                         ,"no inverse"},
diff --git a/crypto/bn/bn_mod.c b/crypto/bn/bn_mod.c
index 72f09c2c2f..92fe11684c 100644
--- a/crypto/bn/bn_mod.c
+++ b/crypto/bn/bn_mod.c
@@ -124,40 +124,62 @@ int BN_mod(BIGNUM *rem, const BIGNUM *m, const BIGNUM *d, BN_CTX *ctx)
 #endif
 
 
-int BN_nnmod(BIGNUM *rem, const BIGNUM *m, const BIGNUM *d, BN_CTX *ctx)
+int BN_nnmod(BIGNUM *r, const BIGNUM *m, const BIGNUM *d, BN_CTX *ctx)
 	{
 	/* like BN_mod, but returns non-negative remainder
-	 * (i.e.,  0 <= rem < |d|  always holds) */
+	 * (i.e.,  0 <= r < |d|  always holds) */
 
-	if (!(BN_mod(rem,m,d,ctx)))
+	if (!(BN_mod(r,m,d,ctx)))
 		return 0;
-	if (!rem->neg)
+	if (!r->neg)
 		return 1;
-	/* now   -|d| < rem < 0,  so we have to set  rem := rem + |d| */
-	return (d->neg ? BN_sub : BN_add)(rem, rem, d);
+	/* now   -|d| < r < 0,  so we have to set  r := r + |d| */
+	return (d->neg ? BN_sub : BN_add)(r, r, d);
 }
 
 
-int BN_mod_add(BIGNUM *ret, const BIGNUM *a, const BIGNUM *b, const BIGNUM *m, BN_CTX *ctx) 
+int BN_mod_add(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, const BIGNUM *m, BN_CTX *ctx)
 	{
-	if (!BN_add(ret, a, b)) return 0;
-	return BN_nnmod(ret, ret, m, ctx);
+	if (!BN_add(r, a, b)) return 0;
+	return BN_nnmod(r, r, m, ctx);
 	}
 
 
-int BN_mod_sub(BIGNUM *ret, const BIGNUM *a, const BIGNUM *b, const BIGNUM *m, BN_CTX *ctx) 
+/* BN_mod_add variant that may be used if both  a  and  b  are non-negative
+ * and less than  m */
+int BN_mod_add_quick(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, const BIGNUM *m)
 	{
-	if (!BN_sub(ret, a, b)) return 0;
-	return BN_nnmod(ret, ret, m, ctx);
+	if (!BN_add(r, a, b)) return 0;
+	if (BN_cmp(r, m) >= 0)
+		return BN_sub(r, r, m);
+	return 1;
+	}
+
+
+int BN_mod_sub(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, const BIGNUM *m, BN_CTX *ctx)
+	{
+	if (!BN_sub(r, a, b)) return 0;
+	return BN_nnmod(r, r, m, ctx);
+	}
+
+
+/* BN_mod_sub variant that may be used if both  a  and  b  are non-negative
+ * and less than  m */
+int BN_mod_sub_quick(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, const BIGNUM *m)
+	{
+	if (!BN_sub(r, a, b)) return 0;
+	if (r->neg)
+		return BN_add(r, r, m);
+	return 1;
 	}
 
 
 /* slow but works */
-int BN_mod_mul(BIGNUM *ret, const BIGNUM *a, const BIGNUM *b, const BIGNUM *m,
+int BN_mod_mul(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, const BIGNUM *m,
 	BN_CTX *ctx)
 	{
 	BIGNUM *t;
-	int r=0;
+	int ret=0;
 
 	bn_check_top(a);
 	bn_check_top(b);
@@ -169,17 +191,106 @@ int BN_mod_mul(BIGNUM *ret, const BIGNUM *a, const BIGNUM *b, const BIGNUM *m,
 		{ if (!BN_sqr(t,a,ctx)) goto err; }
 	else
 		{ if (!BN_mul(t,a,b,ctx)) goto err; }
-	if (!BN_nnmod(ret,t,m,ctx)) goto err;
-	r=1;
+	if (!BN_nnmod(r,t,m,ctx)) goto err;
+	ret=1;
 err:
 	BN_CTX_end(ctx);
-	return(r);
+	return(ret);
 	}
 
 
-int BN_mod_sqr(BIGNUM *ret, const BIGNUM *a, const BIGNUM *m, BN_CTX *ctx)
+int BN_mod_sqr(BIGNUM *r, const BIGNUM *a, const BIGNUM *m, BN_CTX *ctx)
 	{
-	if (!BN_sqr(ret, a, ctx)) return 0;
-	/* ret->neg == 0,  thus we don't need BN_nnmod */
-	return BN_mod(ret, ret, m, ctx);
+	if (!BN_sqr(r, a, ctx)) return 0;
+	/* r->neg == 0,  thus we don't need BN_nnmod */
+	return BN_mod(r, r, m, ctx);
+	}
+
+
+int BN_mod_lshift1(BIGNUM *r, const BIGNUM *a, const BIGNUM *m, BN_CTX *ctx)
+	{
+	if (!BN_lshift1(r, a)) return 0;
+	return BN_nnmod(r, r, m, ctx);
+	}
+
+
+/* BN_mod_lshift1 variant that may be used if  a  is non-negative
+ * and less than  m */
+int BN_mod_lshift1_quick(BIGNUM *r, const BIGNUM *a, const BIGNUM *m)
+	{
+	if (!BN_lshift1(r, a)) return 0;
+	if (BN_cmp(r, m) >= 0)
+		return BN_sub(r, r, m);
+	return 1;
+	}
+
+
+int BN_mod_lshift(BIGNUM *r, const BIGNUM *a, int n, const BIGNUM *m, BN_CTX *ctx)
+	{
+	BIGNUM *abs_m = NULL;
+	int ret;
+
+	if (!BN_nnmod(r, a, m, ctx)) return 0;
+
+	if (m->neg)
+		{
+		abs_m = BN_dup(m);
+		if (abs_m == NULL) return 0;
+		abs_m->neg = 0;
+		}
+	
+	ret = BN_mod_lshift_quick(r, r, n, (abs_m ? abs_m : m));
+
+	if (abs_m)
+		BN_free(abs_m);
+	return ret;
+	}
+
+
+/* BN_mod_lshift variant that may be used if  a  is non-negative
+ * and less than  m */
+int BN_mod_lshift_quick(BIGNUM *r, const BIGNUM *a, int n, const BIGNUM *m)
+	{
+	if (r != a)
+		{
+		if (BN_copy(r, a) == NULL) return 0;
+		}
+
+	while (n > 0)
+		{
+		int max_shift;
+		
+		/* 0 < r < m */
+		max_shift = BN_num_bits(m) - BN_num_bits(r);
+		/* max_shift >= 0 */
+
+		if (max_shift < 0)
+			{
+			BNerr(BN_F_BN_MOD_LSHIFT_QUICK, BN_R_INPUT_NOT_REDUCED);
+			return 0;
+			}
+
+		if (max_shift > n)
+			max_shift = n;
+
+		if (max_shift)
+			{
+			if (!BN_lshift(r, r, max_shift)) return 0;
+			n -= max_shift;
+			}
+		else
+			{
+			if (!BN_lshift1(r, r)) return 0;
+			--n;
+			}
+
+		/* BN_num_bits(r) <= BN_num_bits(m) */
+
+		if (BN_cmp(r, m) >= 0) 
+			{
+			if (!BN_sub(r, r, m)) return 0;
+			}
+		}
+	
+	return 1;
 	}
diff --git a/crypto/bn/bn_modfs.h b/crypto/bn/bn_modfs.h
index f03e4de8dc..dd0677ed63 100644
--- a/crypto/bn/bn_modfs.h
+++ b/crypto/bn/bn_modfs.h
@@ -1,22 +1,22 @@
-/*

- *

- *	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"

-

-

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

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

-

-#endif

+/*
+ *
+ *	bn_modfs.h
+ *
+ *	Some Modular Arithmetic Functions.
+ *
+ *	Copyright (C) Lenka Fibikova 2000
+ *
+ *
+ */
+
+#ifndef HEADER_BN_MODFS_H
+#define HEADER_BN_MODFS_H
+
+
+#include <openssl/bn.h>
+
+
+int BN_legendre(BIGNUM *a, BIGNUM *p, BN_CTX *ctx);
+int BN_mod_sqrt(BIGNUM *x, BIGNUM *a, BIGNUM *p, BN_CTX *ctx);
+
+#endif
diff --git a/crypto/bn/bn_mont2.c b/crypto/bn/bn_mont2.c
index 871282400c..bd4c01f6cb 100644
--- a/crypto/bn/bn_mont2.c
+++ b/crypto/bn/bn_mont2.c
@@ -277,98 +277,3 @@ 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
index e33c65401e..59f2657b9f 100644
--- a/crypto/bn/bn_mont2.h
+++ b/crypto/bn/bn_mont2.h
@@ -14,7 +14,7 @@
 
 #define MONTGOMERY
 
-#include "bn.h"
+#include <openssl/bn.h>
 
 typedef struct bn_mont_st{
 	int R_num_bits;
@@ -32,10 +32,5 @@ 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
+#endif
diff --git a/crypto/bn/bntest.c b/crypto/bn/bntest.c
index 11e58f994a..0ade0c0012 100644
--- a/crypto/bn/bntest.c
+++ b/crypto/bn/bntest.c
@@ -761,6 +761,16 @@ int test_mod_mul(BIO *bp, BN_CTX *ctx)
 				BN_print(bp,b);
 				BIO_puts(bp," % ");
 				BN_print(bp,c);
+				if ((a->neg ^ b->neg) && !BN_is_zero(e))
+					{
+					/* If  (a*b) % c  is negative,  c  must be added
+					 * in order to obtain the normalized remainder
+					 * (new with OpenSSL 0.9.7, previous versions of
+					 * BN_mod_mul could generate negative results)
+					 */
+					BIO_puts(bp," + ");
+					BN_print(bp,c);
+					}
 				BIO_puts(bp," - ");
 				}
 			BN_print(bp,e);
diff --git a/crypto/ec/ec.h b/crypto/ec/ec.h
index 422cbebd10..9d46233967 100644
--- a/crypto/ec/ec.h
+++ b/crypto/ec/ec.h
@@ -14,7 +14,7 @@
 #define HEADER_EC_H
 
 
-#include "bn.h"
+#include <openssl/bn.h>
 #include "bn_mont2.h"
 
 typedef struct bn_ec_struct		/* E: y^2 = x^3 + Ax + B  (mod p) */
@@ -83,4 +83,4 @@ int ECP_mont_multiply(EC_POINT *R, BIGNUM *k, ECP_PRECOMPUTE *prec, EC *E, BN_MO
 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
+#endif
diff --git a/crypto/ec/ec_point.c b/crypto/ec/ec_point.c
index bbf8a92d3a..9e391f8ad3 100644
--- a/crypto/ec/ec_point.c
+++ b/crypto/ec/ec_point.c
@@ -14,7 +14,7 @@
 #include <assert.h>
 #include <memory.h>
 
-#include "bn.h"
+#include <openssl/bn.h>
 
 #include "bn_modfs.h"
 #include "bn_mont2.h"
@@ -360,7 +360,7 @@ int ECP_normalize(EC_POINT *P, EC *E, BN_CTX *ctx)
 	if (ECP_is_norm(P)) return 1;
 	if (ECP_is_infty(P)) return 0;
 
-	if ((zm = BN_mod_inverse(P->Z, E->p, ctx)) == NULL) return 0;
+	if ((zm = BN_mod_inverse(P->Z, P->Z, E->p, ctx)) == NULL) return 0;
 
 	assert(!P->is_in_mont);
 
@@ -1015,7 +1015,7 @@ int ECP_mont_cmp(EC_POINT *P, EC_POINT *Q, BN_MONTGOMERY *mont, BN_CTX *ctx)
 	if (!BN_mont_mod_mul(n4, Q->Y, n0, mont, ctx)) goto err;	/* L4 = y_q * z_p^3 */
 
 
-	if (!BN_mont_mod_sub(n0, n1, n3, mont)) goto err;			/* L5 = L1 - L3 */
+	if (!BN_mod_sub_quick(n0, n1, n3, p)) goto err;			/* L5 = L1 - L3 */
 
 	if (!BN_is_zero(n0))
 	{
@@ -1023,7 +1023,7 @@ int ECP_mont_cmp(EC_POINT *P, EC_POINT *Q, BN_MONTGOMERY *mont, BN_CTX *ctx)
 		return 1;
 	}
 	
-	if (!BN_mont_mod_sub(n0, n2, n4, mont)) goto err;			/* L6 = L2 - L4 */
+	if (!BN_mod_sub_quick(n0, n2, n4, p)) goto err;			/* L6 = L2 - L4 */
 
 	if (!BN_is_zero(n0))
 	{
@@ -1085,33 +1085,33 @@ int ECP_mont_double(EC_POINT *R, EC_POINT *P, EC *E, BN_MONTGOMERY *mont, BN_CTX
 	if (!BN_mont_mod_mul(n2, n0, n0, mont, ctx)) goto err;
 	if (!BN_mont_mod_mul(n0, n2, E->A, mont, ctx)) goto err; 
 	if (!BN_mont_mod_mul(n1, P->X, P->X, mont, ctx)) goto err;
-	if (!BN_mont_mod_lshift1(n2, n1, mont)) goto err;
-	if (!BN_mont_mod_add(n1, n1, n2, mont)) goto err;
-	if (!BN_mont_mod_add(n1, n1, n0, mont)) goto err;		/* L1 = 3 * x^2 + a * z^4 */
+	if (!BN_mod_lshift1_quick(n2, n1, p)) goto err;
+	if (!BN_mod_add_quick(n1, n1, n2, p)) goto err;
+	if (!BN_mod_add_quick(n1, n1, n0, p)) goto err;		/* L1 = 3 * x^2 + a * z^4 */
 
 	/* Z */
 	if (!BN_mont_mod_mul(n0, P->Y, P->Z, mont, ctx)) goto err; 
-	if (!BN_mont_mod_lshift1(R->Z, n0, mont)) goto err;		/* Z = 2 * y * z */
+	if (!BN_mod_lshift1_quick(R->Z, n0, p)) goto err;		/* Z = 2 * y * z */
 
 	/* L2 */
 	if (!BN_mont_mod_mul(n3, P->Y, P->Y, mont, ctx)) goto err;
 	if (!BN_mont_mod_mul(n2, P->X, n3, mont, ctx)) goto err; 
-	if (!BN_mont_mod_lshift(n2, n2, 2, mont)) goto err;		/* L2 = 4 * x * y^2 */
+	if (!BN_mod_lshift_quick(n2, n2, 2, p)) goto err;		/* L2 = 4 * x * y^2 */
 
 	/* X */
-	if (!BN_mont_mod_lshift1(n0, n2, mont)) goto err; 
+	if (!BN_mod_lshift1_quick(n0, n2, p)) goto err; 
 	if (!BN_mont_mod_mul(R->X, n1, n1, mont, ctx)) goto err;
-	if (!BN_mont_mod_sub(R->X, R->X, n0, mont)) goto err;	/* X = L1^2 - 2 * L2 */
+	if (!BN_mod_sub_quick(R->X, R->X, n0, p)) goto err;	/* X = L1^2 - 2 * L2 */
 	
 	/* L3 */
 	if (!BN_mont_mod_mul(n0, n3, n3, mont, ctx)) goto err;
-	if (!BN_mont_mod_lshift(n3, n0, 3, mont)) goto err;		/* L3 = 8 * y^4 */
+	if (!BN_mod_lshift_quick(n3, n0, 3, p)) goto err;		/* L3 = 8 * y^4 */
 
 	
 	/* Y */
-	if (!BN_mont_mod_sub(n2, n2, R->X, mont)) goto err; 
+	if (!BN_mod_sub_quick(n2, n2, R->X, p)) goto err; 
 	if (!BN_mont_mod_mul(n0, n1, n2, mont, ctx)) goto err; 
-	if (!BN_mont_mod_sub(R->Y, n0, n3, mont)) goto err;		/* Y = L1 * (L2 - X) - L3 */
+	if (!BN_mod_sub_quick(R->Y, n0, n3, p)) goto err;		/* Y = L1 * (L2 - X) - L3 */
 
 	ctx->tos -= 4;
 	return 1;
@@ -1188,8 +1188,8 @@ int ECP_mont_add(EC_POINT *R, EC_POINT *P, EC_POINT *Q, EC *E, BN_MONTGOMERY *mo
 
 
 	/* L5; L6 */
-	if (!BN_mont_mod_sub(n5, n1, n3, mont)) goto err;			/* L5 = L1 - L3 */
-	if (!BN_mont_mod_sub(n6, n2, n4, mont)) goto err;			/*L6 = L2 - L4 */
+	if (!BN_mod_sub_quick(n5, n1, n3, p)) goto err;			/* L5 = L1 - L3 */
+	if (!BN_mod_sub_quick(n6, n2, n4, p)) goto err;			/*L6 = L2 - L4 */
 
 
 	/* pata */
@@ -1209,8 +1209,8 @@ int ECP_mont_add(EC_POINT *R, EC_POINT *P, EC_POINT *Q, EC *E, BN_MONTGOMERY *mo
 	}
 
 	/* L7; L8 */
-	if (!BN_mont_mod_add(n1, n1, n3, mont)) goto err;			/* L7 = L1 + L3 */
-	if (!BN_mont_mod_add(n2, n2, n4, mont)) goto err;			/* L8 = L2 + L4 */
+	if (!BN_mod_add_quick(n1, n1, n3, p)) goto err;			/* L7 = L1 + L3 */
+	if (!BN_mod_add_quick(n2, n2, n4, p)) goto err;			/* L8 = L2 + L4 */
 
 
 	/* Z */
@@ -1222,19 +1222,19 @@ int ECP_mont_add(EC_POINT *R, EC_POINT *P, EC_POINT *Q, EC *E, BN_MONTGOMERY *mo
 	if (!BN_mont_mod_mul(n0, n6, n6, mont, ctx)) goto err;
 	if (!BN_mont_mod_mul(n4, n5, n5, mont, ctx)) goto err;
 	if (!BN_mont_mod_mul(n3, n1, n4, mont, ctx)) goto err; 
-	if (!BN_mont_mod_sub(R->X, n0, n3, mont)) goto err;			/* X = L6^2 - L5^2 * L7 */
+	if (!BN_mod_sub_quick(R->X, n0, n3, p)) goto err;			/* X = L6^2 - L5^2 * L7 */
 
 	
 	/* L9 */
-	if (!BN_mont_mod_lshift1(n0, R->X, mont)) goto err;
-	if (!BN_mont_mod_sub(n3, n3, n0, mont)) goto err;			/* L9 = L5^2 * L7 - 2X */
+	if (!BN_mod_lshift1_quick(n0, R->X, p)) goto err;
+	if (!BN_mod_sub_quick(n3, n3, n0, p)) goto err;			/* L9 = L5^2 * L7 - 2X */
 
 
 	/* Y */
 	if (!BN_mont_mod_mul(n0, n3, n6, mont, ctx)) goto err; 
 	if (!BN_mont_mod_mul(n6, n4, n5, mont, ctx)) goto err; 
 	if (!BN_mont_mod_mul(n1, n2, n6, mont, ctx)) goto err; 
-	if (!BN_mont_mod_sub(n0, n0, n1, mont)) goto err;   
+	if (!BN_mod_sub_quick(n0, n0, n1, p)) goto err;   
 	if (!BN_mont_mod_mul(R->Y, n0, E->h, mont, ctx)) goto err;	/* Y = (L6 * L9 - L8 * L5^3) / 2 */