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>

diff --git a/crypto/bn/bn_modfs.c b/crypto/bn/bn_modfs.c
new file mode 100644 (file)
index 0000000..2697d54
--- /dev/null
+++ b/crypto/bn/bn_modfs.c
@@ -0,0 +1,258 @@
+/*\r
+ *\r
+ *     bn_modfs.c\r
+ *\r
+ *     Some Modular Arithmetic Functions.\r
+ *\r
+ *     Copyright (C) Lenka Fibikova 2000\r
+ *\r
+ *\r
+ */\r
+\r
+\r
+#include <stdio.h>\r
+#include <stdlib.h>\r
+#include <assert.h>\r
+\r
+#include "bn_modfs.h"\r
+\r
+#define MAX_ROUNDS     10\r
+\r
+int BN_smod(BIGNUM *rem, BIGNUM *m, BIGNUM *d, BN_CTX *ctx)\r
+{\r
+       int r_sign;\r
+\r
+       assert(rem != NULL && m != NULL && d != NULL && ctx != NULL);\r
+\r
+       if (d->neg) return 0;\r
+       r_sign = m->neg;\r
+\r
+       if (r_sign) m->neg = 0;\r
+       if (!(BN_div(NULL,rem,m,d,ctx))) return 0;\r
+       if (r_sign) \r
+       {\r
+               m->neg = r_sign;\r
+               if (!BN_is_zero(rem))\r
+               {\r
+                       rem->neg = r_sign;\r
+                       BN_add(rem, rem, d);\r
+               }\r
+       }\r
+       return 1;\r
+}\r
+\r
+int BN_mod_sub(BIGNUM *r, BIGNUM *a, BIGNUM *b, BIGNUM *m, BN_CTX *ctx) \r
+{\r
+       assert(r != NULL && a != NULL && b != NULL && m != NULL && ctx != NULL);\r
+\r
+       if (!BN_sub(r, a, b)) return 0;\r
+       return BN_smod(r, r, m, ctx);\r
+\r
+}\r
+\r
+int BN_mod_add(BIGNUM *r, BIGNUM *a, BIGNUM *b, BIGNUM *m, BN_CTX *ctx) \r
+{\r
+       assert(r != NULL && a != NULL && b != NULL && m != NULL && ctx != NULL);\r
+\r
+       if (!BN_add(r, a, b)) return 0;\r
+       return BN_smod(r, r, m, ctx);\r
+\r
+}\r
+\r
+int BN_mod_sqr(BIGNUM *r, BIGNUM *a, BIGNUM *p, BN_CTX *ctx)\r
+{\r
+       assert(r != NULL && a != NULL && p != NULL && ctx != NULL);\r
+\r
+       if (!BN_sqr(r, a, ctx)) return 0;\r
+       return BN_div(NULL, r, r, p, ctx);\r
+}\r
+\r
+int BN_swap(BIGNUM *x, BIGNUM *y)\r
+{\r
+       BIGNUM *c;\r
+\r
+       assert(x != NULL && y != NULL);\r
+\r
+       if ((c = BN_dup(x)) == NULL) goto err;\r
+       if ((BN_copy(x, y)) == NULL) goto err;\r
+       if ((BN_copy(y, c)) == NULL) goto err;\r
+       BN_clear_free(c);\r
+       return 1;\r
+\r
+err:\r
+       if (c != NULL) BN_clear_free(c);\r
+       return 0;\r
+}\r
+\r
+\r
+int BN_legendre(BIGNUM *a, BIGNUM *p, BN_CTX *ctx) \r
+{\r
+       BIGNUM *x, *y, *y2;\r
+       BN_ULONG m;\r
+       int L;\r
+\r
+       assert(a != NULL && p != NULL && ctx != NULL);\r
+\r
+       x = ctx->bn[ctx->tos]; \r
+       y = ctx->bn[ctx->tos + 1]; \r
+       y2 = ctx->bn[ctx->tos + 2]; \r
+\r
+       ctx->tos += 3;\r
+\r
+       if (!BN_smod(x, a, p, ctx)) goto err;\r
+       if (BN_is_zero(x)) \r
+       {\r
+\r
+               ctx->tos -= 3;\r
+               return 0;\r
+       }\r
+\r
+       if (BN_copy(y, p) == NULL) goto err;\r
+       L = 1;\r
+\r
+       while (1)\r
+       {\r
+               if (!BN_rshift1(y2, y)) goto err;\r
+               if (BN_cmp(x, y2) > 0)\r
+               {\r
+                       if (!BN_sub(x, y, x)) goto err;\r
+                       if (BN_mod_word(y, 4) == 3)\r
+                               L = -L;                 \r
+               }\r
+               while (BN_mod_word(x, 4) == 0)\r
+                       BN_div_word(x, 4);\r
+               if (BN_mod_word(x, 2) == 0)\r
+               {\r
+                       BN_div_word(x, 2);\r
+                       m = BN_mod_word(y, 8);\r
+                       if (m == 3 || m == 5) L = -L;                   \r
+               }\r
+               if (BN_is_one(x)) \r
+               {\r
+                       ctx->tos -= 3;\r
+                       return L;\r
+               }\r
+               \r
+               if (BN_mod_word(x, 4) == 3 && BN_mod_word(y, 4) == 3) L = -L;\r
+               if (!BN_swap(x, y)) goto err;\r
+\r
+               if (!BN_smod(x, x, y, ctx)) goto err;\r
+\r
+       }\r
+\r
+\r
+err:\r
+       ctx->tos -= 3;\r
+       return -2;\r
+\r
+}\r
+\r
+int BN_mod_sqrt(BIGNUM *x, BIGNUM *a, BIGNUM *p, BN_CTX *ctx) \r
+/* x^2 = a (mod p) */\r
+{\r
+       int ret;\r
+       BIGNUM *n0, *n1, *r, *b, *m;\r
+       int max;\r
+\r
+       assert(x != NULL && a != NULL && p != NULL && ctx != NULL);\r
+       assert(BN_cmp(a, p) < 0);\r
+\r
+       ret = BN_legendre(a, p, ctx);\r
+       if (ret < 0 || ret > 1) return 0;\r
+       if (ret == 0)\r
+       {\r
+               if (!BN_zero(x)) return 0;\r
+               return 1;\r
+       }\r
+\r
+       n0 = ctx->bn[ctx->tos]; \r
+       n1 = ctx->bn[ctx->tos + 1]; \r
+       ctx->tos += 2;\r
+\r
+       if ((r = BN_new()) == NULL) goto err;\r
+       if ((b = BN_new()) == NULL) goto err;\r
+       if ((m = BN_new()) == NULL) goto err;\r
+\r
+\r
+       if (!BN_zero(n0)) goto err;\r
+       if (!BN_zero(n1)) goto err;\r
+       if (!BN_zero(r)) goto err;\r
+       if (!BN_zero(b)) goto err;\r
+       if (!BN_zero(m)) goto err;\r
+\r
+       max = 0;\r
+\r
+       do{\r
+               if (max++ > MAX_ROUNDS) goto err; /* if p is not prime could never stop*/\r
+               if (!BN_add_word(m, 1)) goto err;\r
+               ret = BN_legendre(m, p, ctx);\r
+               if (ret < -1 || ret > 1) goto err;\r
+\r
+       }while(ret != -1);\r
+\r
+       if (BN_copy(n1, p) == NULL) goto err;\r
+       if (!BN_sub_word(n1, 1)) goto err;\r
+\r
+       while (!BN_is_odd(n1))\r
+       {\r
+               if (!BN_add_word(r, 1)) goto err;\r
+               if (!BN_rshift1(n1, n1)) goto err;\r
+       }\r
+\r
+       if (!BN_mod_exp_simple(n0, m, n1, p, ctx)) goto err;\r
+\r
+       if (!BN_sub_word(n1, 1)) goto err;\r
+       if (!BN_rshift1(n1, n1)) goto err;\r
+       if (!BN_mod_exp_simple(x, a, n1, p, ctx)) goto err;\r
+\r
+       if (!BN_mod_sqr(b, x, p, ctx)) goto err;\r
+       if (!BN_mod_mul(b, b, a, p, ctx)) goto err;\r
+\r
+       if (!BN_mod_mul(x, x, a, p, ctx)) goto err;\r
+\r
+       while (!BN_is_one(b))\r
+       {\r
+               \r
+               if (!BN_one(m)) goto err;\r
+               if (!BN_mod_sqr(n1, b, p, ctx)) goto err;\r
+               while(!BN_is_one(n1))\r
+               {\r
+                       if (!BN_mod_mul(n1, n1, n1, p, ctx)) goto err;\r
+                       if (!BN_add_word(m, 1)) goto err;\r
+               }\r
+\r
+               if (!BN_sub(r, r, m)) goto err;\r
+               if (!BN_sub_word(r, 1)) goto err;\r
+               if (r->neg) goto err;\r
+\r
+               if (BN_copy(n1, n0) == NULL) goto err;\r
+               while(!BN_is_zero(r))\r
+               {\r
+                       if (!BN_mod_mul(n1, n1, n1, p, ctx)) goto err;\r
+                       if (!BN_sub_word(r, 1)) goto err;\r
+               }\r
+\r
+               if (!BN_mod_mul(n0, n1, n1, p, ctx)) goto err;\r
+               if (BN_copy(r, m) == NULL) goto err;\r
+               if (!BN_mod_mul(x, x, n1, p, ctx)) goto err;\r
+               if (!BN_mod_mul(b, b, n0, p, ctx)) goto err;\r
+       }\r
+\r
+\r
+#ifdef TEST\r
+       BN_mod_sqr(n0, x, p, ctx);\r
+       if (BN_cmp(n0, a)) goto err;\r
+#endif\r
+\r
+       if (r != NULL) BN_clear_free(r);\r
+       if (b != NULL) BN_clear_free(b);\r
+       if (m != NULL) BN_clear_free(m);\r
+       ctx->tos -= 2;\r
+       return 1;\r
+err:\r
+       if (r != NULL) BN_clear_free(r);\r
+       if (b != NULL) BN_clear_free(b);\r
+       if (m != NULL) BN_clear_free(m);\r
+       ctx->tos -= 2;\r
+       return 0;\r
+}\r

diff --git a/crypto/bn/bn_modfs.h b/crypto/bn/bn_modfs.h
new file mode 100644 (file)
index 0000000..b7ae496
--- /dev/null
+++ b/crypto/bn/bn_modfs.h
@@ -0,0 +1,32 @@
+/*\r
+ *\r
+ *     bn_modfs.h\r
+ *\r
+ *     Some Modular Arithmetic Functions.\r
+ *\r
+ *     Copyright (C) Lenka Fibikova 2000\r
+ *\r
+ *\r
+ */\r
+\r
+#ifndef HEADER_BN_MODFS_H\r
+#define HEADER_BN_MODFS_H\r
+\r
+\r
+#include "bn.h"\r
+\r
+#ifdef BN_is_zero\r
+#undef BN_is_zero\r
+#define BN_is_zero(a)  (((a)->top == 0) || (((a)->top == 1) && ((a)->d[0] == (BN_ULONG)0)))\r
+#endif /*BN_is_zero(a)*/\r
+\r
+\r
+int BN_smod(BIGNUM *rem, BIGNUM *m, BIGNUM *d, BN_CTX *ctx);\r
+int BN_mod_sub(BIGNUM *r, BIGNUM *a, BIGNUM *b, BIGNUM *m, BN_CTX *ctx);\r
+int BN_mod_add(BIGNUM *r, BIGNUM *a, BIGNUM *b, BIGNUM *m, BN_CTX *ctx); \r
+int BN_mod_sqr(BIGNUM *r, BIGNUM *a, BIGNUM *p, BN_CTX *ctx);\r
+int BN_swap(BIGNUM *x, BIGNUM *y);\r
+int BN_legendre(BIGNUM *a, BIGNUM *p, BN_CTX *ctx);\r
+int BN_mod_sqrt(BIGNUM *x, BIGNUM *a, BIGNUM *p, BN_CTX *ctx);\r
+\r
+#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 (file)
index 0000000..9f6222f
--- /dev/null
+++ b/crypto/bn/bn_mont2.c
@@ -0,0 +1,374 @@
+/*\r
+ *\r
+ *     bn_mont2.c\r
+ *\r
+ *     Montgomery Modular Arithmetic Functions.\r
+ *\r
+ *     Copyright (C) Lenka Fibikova 2000\r
+ *\r
+ *\r
+ */\r
+\r
+\r
+#include <stdio.h>\r
+#include <stdlib.h>\r
+#include <assert.h>\r
+\r
+#include "bn.h"\r
+#include "bn_modfs.h"\r
+#include "bn_mont2.h"\r
+\r
+#define BN_mask_word(x, m) ((x->d[0]) & (m))\r
+\r
+BN_MONTGOMERY *BN_mont_new()\r
+{\r
+       BN_MONTGOMERY *ret;\r
+\r
+       ret=(BN_MONTGOMERY *)malloc(sizeof(BN_MONTGOMERY));\r
+\r
+       if (ret == NULL) return NULL;\r
+\r
+       if ((ret->p = BN_new()) == NULL)\r
+       {\r
+               free(ret);\r
+               return NULL;\r
+       }\r
+\r
+       return ret;\r
+}\r
+\r
+\r
+void BN_mont_clear_free(BN_MONTGOMERY *mont)\r
+{\r
+       if (mont == NULL) return;\r
+\r
+       if (mont->p != NULL) BN_clear_free(mont->p);\r
+\r
+       mont->p_num_bytes = 0;\r
+       mont->R_num_bits = 0;\r
+       mont->p_inv_b_neg = 0;\r
+}\r
+\r
+int BN_to_mont(BIGNUM *x, BN_MONTGOMERY *mont, BN_CTX *ctx)\r
+{\r
+       assert(x != NULL);\r
+\r
+       assert(mont != NULL);\r
+       assert(mont->p != NULL);\r
+\r
+       assert(ctx != NULL);\r
+\r
+       if (!BN_lshift(x, x, mont->R_num_bits)) return 0;\r
+       if (!BN_mod(x, x, mont->p, ctx)) return 0;\r
+\r
+       return 1;\r
+}\r
+\r
+\r
+static BN_ULONG BN_mont_inv(BIGNUM *a, int e, BN_CTX *ctx)\r
+/* y = a^{-1} (mod 2^e) for an odd number a */\r
+{\r
+       BN_ULONG y, exp, mask;\r
+       BIGNUM *x, *xy, *x_sh;\r
+       int i;\r
+\r
+       assert(a != NULL && ctx != NULL);\r
+       assert(e <= BN_BITS2);\r
+       assert(BN_is_odd(a));\r
+       assert(!BN_is_zero(a) && !a->neg);\r
+\r
+\r
+       y = 1;\r
+       exp = 2;\r
+       mask = 3;\r
+       if((x = BN_dup(a)) == NULL) return 0;\r
+       if(!BN_mask_bits(x, e)) return 0;\r
+\r
+       xy = ctx->bn[ctx->tos]; \r
+       x_sh = ctx->bn[ctx->tos + 1]; \r
+       ctx->tos += 2;\r
+\r
+       if (BN_copy(xy, x) == NULL) goto err;\r
+       if (!BN_lshift1(x_sh, x)) goto err;\r
+\r
+\r
+       for (i = 2; i <= e; i++)\r
+       {\r
+               if (exp < BN_mask_word(xy, mask))\r
+               {\r
+                       y = y + exp;\r
+                       if (!BN_add(xy, xy, x_sh)) goto err;\r
+               }\r
+\r
+               exp <<= 1;\r
+               if (!BN_lshift1(x_sh, x_sh)) goto err;\r
+               mask <<= 1;\r
+               mask++;\r
+       }\r
+\r
+\r
+#ifdef TEST\r
+       if (xy->d[0] != 1) goto err;\r
+#endif\r
+\r
+       if (x != NULL) BN_clear_free(x);\r
+       ctx->tos -= 2;\r
+       return y;\r
+\r
+\r
+err:\r
+       if (x != NULL) BN_clear_free(x);\r
+       ctx->tos -= 2;\r
+       return 0;\r
+\r
+}\r
+\r
+int BN_mont_set(BIGNUM *p, BN_MONTGOMERY *mont, BN_CTX *ctx)\r
+{\r
+       assert(p != NULL && ctx != NULL);\r
+       assert(mont != NULL);\r
+       assert(mont->p != NULL);\r
+       assert(!BN_is_zero(p) && !p->neg);\r
+\r
+\r
+       mont->p_num_bytes = p->top;\r
+       mont->R_num_bits = (mont->p_num_bytes) * BN_BITS2;\r
+\r
+       if (BN_copy(mont->p, p) == NULL);\r
+       \r
+       mont->p_inv_b_neg =  BN_mont_inv(p, BN_BITS2, ctx);\r
+       mont->p_inv_b_neg = 0 - mont->p_inv_b_neg;\r
+\r
+       return 1;\r
+}\r
+\r
+static int BN_cpy_mul_word(BIGNUM *ret, BIGNUM *a, BN_ULONG w)\r
+/* ret = a * w */\r
+{\r
+       if (BN_copy(ret, a) == NULL) return 0;\r
+\r
+       if (!BN_mul_word(ret, w)) return 0;\r
+\r
+       return 1;\r
+}\r
+\r
+\r
+int BN_mont_red(BIGNUM *y, BN_MONTGOMERY *mont, BN_CTX *ctx)\r
+/* yR^{-1} (mod p) */\r
+{\r
+       int i;\r
+       BIGNUM *up, *p;\r
+       BN_ULONG u;\r
+\r
+       assert(y != NULL && mont != NULL && ctx != NULL);\r
+       assert(mont->p != NULL);\r
+       assert(BN_cmp(y, mont->p) < 0);\r
+       assert(!y->neg);\r
+\r
+\r
+       if (BN_is_zero(y)) return 1;\r
+\r
+       p = mont->p;\r
+       up = ctx->bn[ctx->tos]; \r
+       ctx->tos += 1;\r
+\r
+\r
+       for (i = 0; i < mont->p_num_bytes; i++)\r
+       {\r
+               u = (y->d[0]) * mont->p_inv_b_neg;                      /* u = y_0 * p' */\r
+\r
+               if (!BN_cpy_mul_word(up, p, u)) goto err;       /* up = u * p */\r
+\r
+               if (!BN_add(y, y, up)) goto err;                        \r
+#ifdef TEST\r
+               if (y->d[0]) goto err;\r
+#endif\r
+               if (!BN_rshift(y, y, BN_BITS2)) goto err;       /* y = (y + up)/b */\r
+       }\r
+\r
+\r
+       if (BN_cmp(y, mont->p) >= 0) \r
+       {\r
+               if (!BN_sub(y, y, mont->p)) goto err;\r
+       }\r
+\r
+       ctx->tos -= 1;\r
+       return 1;\r
+\r
+err:\r
+       ctx->tos -= 1;\r
+       return 0;\r
+\r
+}\r
+\r
+\r
+int BN_mont_mod_mul(BIGNUM *r, BIGNUM *x, BIGNUM *y, BN_MONTGOMERY *mont, BN_CTX *ctx)\r
+/* r = x * y mod p */\r
+/* r != x && r! = y !!! */\r
+{\r
+       BIGNUM *xiy, *up;\r
+       BN_ULONG u;\r
+       int i;\r
+       \r
+\r
+       assert(r != x && r != y);\r
+       assert(r != NULL && x != NULL  && y != NULL && mont != NULL && ctx != NULL);\r
+       assert(mont->p != NULL);\r
+       assert(BN_cmp(x, mont->p) < 0);\r
+       assert(BN_cmp(y, mont->p) < 0);\r
+       assert(!x->neg);\r
+       assert(!y->neg);\r
+\r
+       if (BN_is_zero(x) || BN_is_zero(y))\r
+       {\r
+               if (!BN_zero(r)) return 0;\r
+               return 1;\r
+       }\r
+\r
+\r
+\r
+       xiy = ctx->bn[ctx->tos]; \r
+       up = ctx->bn[ctx->tos + 1]; \r
+       ctx->tos += 2;\r
+\r
+       if (!BN_zero(r)) goto err;\r
+\r
+       for (i = 0; i < x->top; i++)\r
+       {\r
+               u = (r->d[0] + x->d[i] * y->d[0]) * mont->p_inv_b_neg;\r
+\r
+               if (!BN_cpy_mul_word(xiy, y, x->d[i])) goto err;\r
+               if (!BN_cpy_mul_word(up, mont->p, u)) goto err;\r
+\r
+               if (!BN_add(r, r, xiy)) goto err;\r
+               if (!BN_add(r, r, up)) goto err;\r
+\r
+#ifdef TEST\r
+               if (r->d[0]) goto err;\r
+#endif\r
+               if (!BN_rshift(r, r, BN_BITS2)) goto err; \r
+       }\r
+\r
+       for (i = x->top; i < mont->p_num_bytes; i++)\r
+       {\r
+               u = (r->d[0]) * mont->p_inv_b_neg;\r
+\r
+               if (!BN_cpy_mul_word(up, mont->p, u)) goto err;\r
+\r
+               if (!BN_add(r, r, up)) goto err;\r
+\r
+#ifdef TEST\r
+               if (r->d[0]) goto err;\r
+#endif\r
+               if (!BN_rshift(r, r, BN_BITS2)) goto err; \r
+       }\r
+\r
+\r
+       if (BN_cmp(r, mont->p) >= 0) \r
+       {\r
+               if (!BN_sub(r, r, mont->p)) goto err;\r
+       }\r
+\r
+\r
+       ctx->tos -= 2;\r
+       return 1;\r
+\r
+err:\r
+       ctx->tos -= 2;\r
+       return 0;\r
+}\r
+\r
+int BN_mont_mod_add(BIGNUM *r, BIGNUM *x, BIGNUM *y, BN_MONTGOMERY *mont)\r
+{\r
+       assert(r != NULL && x != NULL  && y != NULL && mont != NULL);\r
+       assert(mont->p != NULL);\r
+       assert(BN_cmp(x, mont->p) < 0);\r
+       assert(BN_cmp(y, mont->p) < 0);\r
+       assert(!x->neg);\r
+       assert(!y->neg);\r
+\r
+       if (!BN_add(r, x, y)) return 0;\r
+       if (BN_cmp(r, mont->p) >= 0) \r
+       {\r
+               if (!BN_sub(r, r, mont->p)) return 0;\r
+       }\r
+\r
+       return 1;\r
+}\r
+\r
+\r
+int BN_mont_mod_sub(BIGNUM *r, BIGNUM *x, BIGNUM *y, BN_MONTGOMERY *mont)\r
+{\r
+       assert(r != NULL && x != NULL  && y != NULL && mont != NULL);\r
+       assert(mont->p != NULL);\r
+       assert(BN_cmp(x, mont->p) < 0);\r
+       assert(BN_cmp(y, mont->p) < 0);\r
+       assert(!x->neg);\r
+       assert(!y->neg);\r
+\r
+       if (!BN_sub(r, x, y)) return 0;\r
+       if (r->neg) \r
+       {\r
+               if (!BN_add(r, r, mont->p)) return 0;\r
+       }\r
+\r
+       return 1;\r
+}\r
+\r
+int BN_mont_mod_lshift1(BIGNUM *r, BIGNUM *x, BN_MONTGOMERY *mont)\r
+{\r
+       assert(r != NULL && x != NULL && mont != NULL);\r
+       assert(mont->p != NULL);\r
+       assert(BN_cmp(x, mont->p) < 0);\r
+       assert(!x->neg);\r
+\r
+       if (!BN_lshift1(r, x)) return 0;\r
+\r
+       if (BN_cmp(r, mont->p) >= 0) \r
+       {\r
+               if (!BN_sub(r, r, mont->p)) return 0;\r
+       }\r
+\r
+       return 1;\r
+}\r
+\r
+int BN_mont_mod_lshift(BIGNUM *r, BIGNUM *x, int n, BN_MONTGOMERY *mont)\r
+{\r
+       int sh_nb;\r
+\r
+       assert(r != NULL && x != NULL && mont != NULL);\r
+       assert(mont->p != NULL);\r
+       assert(BN_cmp(x, mont->p) < 0);\r
+       assert(!x->neg);\r
+       assert(n > 0);\r
+\r
+       if (r != x)\r
+       {\r
+               if (BN_copy(r, x) == NULL) return 0;\r
+       }\r
+\r
+       while (n)\r
+       {\r
+               sh_nb = BN_num_bits(mont->p) - BN_num_bits(r);\r
+               if (sh_nb > n) sh_nb = n;\r
+\r
+               if (sh_nb)\r
+               {\r
+                       if(!BN_lshift(r, r, sh_nb)) return 0;\r
+               }\r
+               else \r
+               {\r
+                       sh_nb = 1;\r
+                       if (!BN_lshift1(r, r)) return 0;\r
+               }\r
+\r
+               if (BN_cmp(r, mont->p) >= 0) \r
+               {\r
+                       if (!BN_sub(r, r, mont->p)) return 0;\r
+               }\r
+\r
+               n -= sh_nb;\r
+       }\r
+\r
+       return 1;\r
+}\r

diff --git a/crypto/bn/bn_mont2.h b/crypto/bn/bn_mont2.h
new file mode 100644 (file)
index 0000000..1bce6d7
--- /dev/null
+++ b/crypto/bn/bn_mont2.h
@@ -0,0 +1,41 @@
+/*\r
+ *\r
+ *     bn_mont2.h\r
+ *\r
+ *     Montgomery Modular Arithmetic Functions.\r
+ *\r
+ *     Copyright (C) Lenka Fibikova 2000\r
+ *\r
+ *\r
+ */\r
+\r
+#ifndef HEADER_MONT2_H\r
+#define HEADER_MONT2_H\r
+\r
+#define MONTGOMERY\r
+\r
+#include "bn.h"\r
+\r
+typedef struct bn_mont_st{\r
+       int R_num_bits;\r
+       int p_num_bytes;\r
+       BIGNUM *p;\r
+       BN_ULONG p_inv_b_neg;   /* p' = p^{-1} mod b; b = 2^BN_BITS */\r
+} BN_MONTGOMERY;\r
+\r
+#define BN_from_mont(x, mont, ctx) (BN_mont_red((x), (mont), (ctx)))\r
+\r
+\r
+BN_MONTGOMERY *BN_mont_new();\r
+int BN_to_mont(BIGNUM *x, BN_MONTGOMERY *mont, BN_CTX *ctx); \r
+void BN_mont_clear_free(BN_MONTGOMERY *mont);\r
+int BN_mont_set(BIGNUM *p, BN_MONTGOMERY *mont, BN_CTX *ctx);\r
+int BN_mont_red(BIGNUM *y, BN_MONTGOMERY *mont, BN_CTX *ctx);\r
+BN_ULONG BN_mont_inv(BIGNUM *x, int e, BN_CTX *ctx);\r
+int BN_mont_mod_mul(BIGNUM *r, BIGNUM *x, BIGNUM *y, BN_MONTGOMERY *mont, BN_CTX *ctx);\r
+int BN_mont_mod_add(BIGNUM *r, BIGNUM *x, BIGNUM *y, BN_MONTGOMERY *mont);\r
+int BN_mont_mod_sub(BIGNUM *r, BIGNUM *x, BIGNUM *y, BN_MONTGOMERY *mont);\r
+int BN_mont_mod_lshift1(BIGNUM *r, BIGNUM *x, BN_MONTGOMERY *mont);\r
+int BN_mont_mod_lshift(BIGNUM *r, BIGNUM *x, int n, BN_MONTGOMERY *mont);\r
+\r
+#endif
\ No newline at end of file

diff --git a/crypto/ec/ec.c b/crypto/ec/ec.c
new file mode 100644 (file)
index 0000000..bc689e7
--- /dev/null
+++ b/crypto/ec/ec.c
@@ -0,0 +1,121 @@
+/*\r
+ *\r
+ *     ec.c\r
+ *\r
+ *     Elliptic Curve Arithmetic Functions\r
+ *\r
+ *     Copyright (C) Lenka Fibikova 2000\r
+ *\r
+ *\r
+ */\r
+\r
+\r
+#include <stdio.h>\r
+#include <stdlib.h>\r
+#include <assert.h>\r
+\r
+#include "ec.h"\r
+#include "bn_modfs.h"\r
+\r
+\r
+\r
+EC *EC_new()\r
+{\r
+       EC *ret;\r
+\r
+       ret=(EC *)malloc(sizeof(EC));\r
+       if (ret == NULL) return NULL;\r
+       ret->A = BN_new();\r
+       ret->B = BN_new();\r
+       ret->p = BN_new();\r
+       ret->h = BN_new();\r
+       ret->is_in_mont = 0;\r
+\r
+       if (ret->A == NULL || ret->B == NULL || ret->p == NULL || ret->h == NULL)\r
+       {\r
+               if (ret->A != NULL) BN_free(ret->A);\r
+               if (ret->B != NULL) BN_free(ret->B);\r
+               if (ret->p != NULL) BN_free(ret->p);\r
+               if (ret->h != NULL) BN_free(ret->h);\r
+               free(ret);\r
+               return(NULL);\r
+       }\r
+       return(ret);\r
+}\r
+\r
+\r
+void EC_clear_free(EC *E)\r
+{\r
+       if (E == NULL) return;\r
+\r
+       if (E->A != NULL) BN_clear_free(E->A);\r
+       if (E->B != NULL) BN_clear_free(E->B);\r
+       if (E->p != NULL) BN_clear_free(E->p);\r
+       if (E->h != NULL) BN_clear_free(E->h);\r
+       E->is_in_mont = 0;\r
+       free(E);\r
+}\r
+\r
+\r
+#ifdef MONTGOMERY\r
+int EC_to_montgomery(EC *E, BN_MONTGOMERY *mont, BN_CTX *ctx)\r
+{\r
+       assert(E != NULL);\r
+       assert(E->A != NULL && E->B != NULL && E->p != NULL && E->h != NULL);\r
+\r
+       assert(mont != NULL);\r
+       assert(mont->p != NULL);\r
+\r
+       assert(ctx != NULL);\r
+\r
+       if (E->is_in_mont) return 1;\r
+\r
+       if (!BN_lshift(E->A, E->A, mont->R_num_bits)) return 0;\r
+       if (!BN_mod(E->A, E->A, mont->p, ctx)) return 0;\r
+\r
+       if (!BN_lshift(E->B, E->B, mont->R_num_bits)) return 0;\r
+       if (!BN_mod(E->B, E->B, mont->p, ctx)) return 0;\r
+\r
+       if (!BN_lshift(E->h, E->h, mont->R_num_bits)) return 0;\r
+       if (!BN_mod(E->h, E->h, mont->p, ctx)) return 0;\r
+\r
+       E->is_in_mont = 1;\r
+       return 1;\r
+\r
+}\r
+\r
+\r
+int EC_from_montgomery(EC *E, BN_MONTGOMERY *mont, BN_CTX *ctx)\r
+{\r
+       assert(E != NULL);\r
+       assert(E->A != NULL && E->B != NULL && E->p != NULL && E->h != NULL);\r
+\r
+       assert(mont != NULL);\r
+       assert(mont->p != NULL);\r
+\r
+       assert(ctx != NULL);\r
+\r
+       if (!E->is_in_mont) return 1;\r
+\r
+       if (!BN_mont_red(E->A, mont, ctx)) return 0;\r
+       if (!BN_mont_red(E->B, mont, ctx)) return 0;\r
+       if (!BN_mont_red(E->h, mont, ctx)) return 0;\r
+\r
+       E->is_in_mont = 0;\r
+       return 1;\r
+}\r
+#endif /* MONTGOMERY */\r
+\r
+int EC_set_half(EC *E)\r
+/* h <- 1/2 mod p = (p + 1)/2 */\r
+{\r
+       assert(E != NULL);\r
+       assert(E->p != NULL);\r
+       assert(E->h != NULL);\r
+       assert(!E->is_in_mont);\r
+\r
+       if (BN_copy(E->h, E->p) == NULL) return 0; \r
+       if (!BN_add_word(E->h, 1)) return 0;\r
+       if (!BN_rshift1(E->h, E->h)) return 0; \r
+       return 1;\r
+}\r

diff --git a/crypto/ec/ec.h b/crypto/ec/ec.h
new file mode 100644 (file)
index 0000000..97d55cb
--- /dev/null
+++ b/crypto/ec/ec.h
@@ -0,0 +1,86 @@
+/*\r
+ *\r
+ *     ec.h\r
+ *\r
+ *     Elliptic Curve Arithmetic Functions\r
+ *\r
+ *     Copyright (C) Lenka Fibikova 2000\r
+ *\r
+ *\r
+ */\r
+\r
+\r
+#ifndef HEADER_EC_H\r
+#define HEADER_EC_H\r
+\r
+\r
+#include "bn.h"\r
+#include "bn_mont2.h"\r
+\r
+typedef struct bn_ec_struct            /* E: y^2 = x^3 + Ax + B  (mod p) */\r
+{\r
+       BIGNUM  *A, *B, *p, *h;         /* h = 1/2 mod p = (p + 1)/2 */\r
+       int is_in_mont;\r
+} EC;\r
+\r
+typedef struct bn_ec_point_struct /* P = [X, Y, Z] */\r
+{\r
+       BIGNUM  *X, *Y, *Z;\r
+       int is_in_mont;\r
+} EC_POINT;\r
+\r
+typedef struct bn_ecp_precompute_struct /* Pi[i] = [2i + 1]P   i = 0..2^{r-1} - 1 */\r
+{\r
+       int r;\r
+       EC_POINT **Pi;\r
+} ECP_PRECOMPUTE;\r
+\r
+\r
+#define ECP_is_infty(P) (BN_is_zero(P->Z))\r
+#define ECP_is_norm(P) (BN_is_one(P->Z))\r
+\r
+#define ECP_mont_minus(P, mont) (ECP_minus((P), (mont)->p))\r
+\r
+\r
+EC *EC_new();\r
+void EC_clear_free(EC *E);\r
+int EC_set_half(EC *E);\r
+#ifdef MONTGOMERY\r
+int EC_to_montgomery(EC *E, BN_MONTGOMERY *mont, BN_CTX *ctx);\r
+int EC_from_montgomery(EC *E, BN_MONTGOMERY *mont, BN_CTX *ctx);\r
+#endif /* MONTGOMERY */\r
+\r
+\r
+EC_POINT *ECP_new();\r
+void ECP_clear_free(EC_POINT *P);\r
+void ECP_clear_free_precompute(ECP_PRECOMPUTE *prec);\r
+\r
+EC_POINT *ECP_generate(BIGNUM *x, BIGNUM *z, EC *E, BN_CTX *ctx);\r
+EC_POINT *ECP_dup(EC_POINT *P);\r
+int ECP_copy(EC_POINT *R, EC_POINT *P);\r
+int ECP_normalize(EC_POINT *P, EC *E, BN_CTX *ctx);\r
+EC_POINT *ECP_minus(EC_POINT *P, BIGNUM *p);\r
+int ECP_is_on_ec(EC_POINT *P, EC *E, BN_CTX *ctx);\r
+int ECP_ecp2bin(EC_POINT *P, unsigned char *to, int form); /* form(ANSI 9.62): 1-compressed; 2-uncompressed; 3-hybrid */\r
+int ECP_bin2ecp(unsigned char *from, int len, EC_POINT *P, EC *E, BN_CTX *ctx);\r
+\r
+#ifdef SIMPLE\r
+int ECP_cmp(EC_POINT *P, EC_POINT *Q, BIGNUM *p, BN_CTX *ctx);\r
+int ECP_double(EC_POINT *R, EC_POINT *P, EC *E, BN_CTX *ctx);\r
+int ECP_add(EC_POINT *R, EC_POINT *P, EC_POINT *Q, EC *E, BN_CTX *ctx);\r
+ECP_PRECOMPUTE *ECP_precompute(int r, EC_POINT *P, EC *E, BN_CTX *ctx);\r
+int ECP_multiply(EC_POINT *R, BIGNUM *k, ECP_PRECOMPUTE *prec, EC *E, BN_CTX *ctx);\r
+#endif /* SIMPLE */\r
+\r
+#ifdef MONTGOMERY\r
+int ECP_to_montgomery(EC_POINT *P, BN_MONTGOMERY *mont, BN_CTX *ctx);\r
+int ECP_from_montgomery(EC_POINT *P, BN_MONTGOMERY *mont, BN_CTX *ctx);\r
+int ECP_mont_cmp(EC_POINT *P, EC_POINT *Q, BN_MONTGOMERY *mont, BN_CTX *ctx);\r
+int ECP_mont_double(EC_POINT *R, EC_POINT *P, EC *E, BN_MONTGOMERY *mont, BN_CTX *ctx);\r
+int ECP_mont_add(EC_POINT *R, EC_POINT *P, EC_POINT *Q, EC *E, BN_MONTGOMERY *mont, BN_CTX *ctx);\r
+ECP_PRECOMPUTE *ECP_mont_precompute(int r, EC_POINT *P, EC *E, BN_MONTGOMERY *mont, BN_CTX *ctx);\r
+int ECP_mont_multiply(EC_POINT *R, BIGNUM *k, ECP_PRECOMPUTE *prec, EC *E, BN_MONTGOMERY *mont, BN_CTX *ctx);\r
+int ECP_mont_multiply2(EC_POINT *R, BIGNUM *k, EC_POINT *P, EC *E, BN_MONTGOMERY *mont, BN_CTX *ctx);\r
+#endif /* MONTGOMERY */\r
+\r
+#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 (file)
index 0000000..fee5078
--- /dev/null
+++ b/crypto/ec/ec_point.c
@@ -0,0 +1,1461 @@
+/*\r
+ *\r
+ *     ec_point.c\r
+ *\r
+ *     Elliptic Curve Arithmetic Functions\r
+ *\r
+ *     Copyright (C) Lenka Fibikova 2000\r
+ *\r
+ *\r
+ */\r
+\r
+#include <stdio.h>\r
+#include <stdlib.h>\r
+#include <assert.h>\r
+#include <memory.h>\r
+\r
+#include "bn.h"\r
+\r
+#include "bn_modfs.h"\r
+#include "bn_mont2.h"\r
+#include "ec.h"\r
+\r
+EC_POINT *ECP_new()\r
+{\r
+       EC_POINT *ret;\r
+\r
+       ret=(EC_POINT *)malloc(sizeof(EC_POINT));\r
+       if (ret == NULL) return NULL;\r
+       ret->X = BN_new();\r
+       ret->Y = BN_new();\r
+       ret->Z = BN_new();\r
+       ret->is_in_mont = 0;\r
+\r
+       if (ret->X == NULL || ret->Y == NULL || ret->Z == NULL) \r
+       {\r
+               if (ret->X != NULL) BN_free(ret->X);\r
+               if (ret->Y != NULL) BN_free(ret->Y);\r
+               if (ret->Z != NULL) BN_free(ret->Z);\r
+               free(ret);\r
+               return(NULL);\r
+       }\r
+       return(ret);\r
+}\r
+\r
+void ECP_clear_free(EC_POINT *P)\r
+{\r
+       if (P == NULL) return;\r
+       \r
+       P->is_in_mont = 0;\r
+       if (P->X != NULL) BN_clear_free(P->X);\r
+       if (P->Y != NULL) BN_clear_free(P->Y);\r
+       if (P->Z != NULL) BN_clear_free(P->Z);\r
+       free(P);\r
+}\r
+\r
+void ECP_clear_free_precompute(ECP_PRECOMPUTE *prec)\r
+{\r
+       int i;\r
+       int max;\r
+\r
+       if (prec == NULL) return;\r
+       if (prec->Pi != NULL)\r
+       {\r
+               max = 1;\r
+               max <<= (prec->r - 1);\r
+\r
+               for (i = 0; i < max; i++)\r
+               {\r
+                       if (prec->Pi[i] != NULL) ECP_clear_free(prec->Pi[i]);\r
+               }\r
+       }\r
+       free(prec);\r
+}\r
+\r
+int ECP_is_on_ec(EC_POINT *P, EC *E, BN_CTX *ctx)\r
+{\r
+       BIGNUM *n0, *n1, *n2, *p;\r
+       int Pnorm;\r
+\r
+       assert(P != NULL);\r
+       assert(P->X != NULL && P->Y != NULL && P->Z != NULL);\r
+\r
+       assert(E != NULL);\r
+       assert(E->A != NULL && E->B != NULL && E->p != NULL);\r
+\r
+       assert(ctx != NULL);\r
+\r
+       assert(!P->is_in_mont);\r
+\r
+       if (ECP_is_infty(P)) return 1;\r
+       \r
+       n0 = ctx->bn[ctx->tos]; \r
+       n1 = ctx->bn[ctx->tos + 1]; \r
+       n2 = ctx->bn[ctx->tos + 2]; \r
+       ctx->tos += 3;\r
+\r
+\r
+       p = E->p;\r
+\r
+       Pnorm = (ECP_is_norm(P));\r
+\r
+       if (!Pnorm)\r
+       {\r
+               if (!BN_mod_mul(n0, P->Z, P->Z, p, ctx)) goto err;\r
+               if (!BN_mod_mul(n1, n0, n0, p, ctx)) goto err;\r
+               if (!BN_mod_mul(n2, n0, n1, p, ctx)) goto err;\r
+       }\r
+\r
+       if (!BN_mod_mul(n0, P->X, P->X, p, ctx)) goto err;\r
+       if (!BN_mod_mul(n0, n0, P->X, p, ctx)) goto err;\r
+\r
+       if (Pnorm)\r
+       {\r
+               if (!BN_mod_mul(n1, P->X, E->A, p, ctx)) goto err;\r
+       }\r
+       else\r
+       {\r
+               if (!BN_mod_mul(n1, n1, P->X, p, ctx)) goto err;\r
+               if (!BN_mod_mul(n1, n1, E->A, p, ctx)) goto err;\r
+       }\r
+       if (!BN_mod_add(n0, n0, n1, p, ctx)) goto err;\r
+\r
+       if (Pnorm)\r
+       {\r
+               if (!BN_mod_add(n0, n0, E->B, p, ctx)) goto err;\r
+       }\r
+       else\r
+       {\r
+               if (!BN_mod_mul(n2, n2, E->B,  p, ctx)) goto err;\r
+               if (!BN_mod_add(n0, n0, n2, p, ctx)) goto err;\r
+       }\r
+\r
+       if (!BN_mod_mul(n1, P->Y, P->Y, p, ctx)) goto err;\r
+\r
+       if (BN_cmp(n0, n1)) \r
+       { \r
+               ctx->tos -= 3;\r
+               return 0;\r
+       }\r
+\r
+       ctx->tos -= 3;\r
+       return 1;\r
+       \r
+err:\r
+       ctx->tos -= 3;\r
+       return -1;\r
+}\r
+\r
+\r
+EC_POINT *ECP_generate(BIGNUM *x, BIGNUM *z,EC *E, BN_CTX *ctx)\r
+/* x == NULL || z = 0  -> point of infinity    */\r
+/* z == NULL || z = 1  -> normalized           */\r
+{\r
+       BIGNUM *n0, *n1;\r
+       EC_POINT *ret;\r
+       int Pnorm, Pinfty, X0, A0;\r
+\r
+       assert(E != NULL);\r
+       assert(E->A != NULL && E->B != NULL && E->p != NULL && E->h != NULL);\r
+\r
+       assert(ctx != NULL);\r
+\r
+       Pinfty = (x == NULL);\r
+       Pnorm = (z == NULL);\r
+       if (!Pnorm) \r
+       {\r
+               Pnorm = BN_is_one(z);\r
+               Pinfty = (Pinfty || BN_is_zero(z));\r
+       }\r
+\r
+       if (Pinfty) \r
+       {\r
+               if ((ret = ECP_new()) == NULL) return NULL;\r
+               if (!BN_zero(ret->Z)) \r
+               { \r
+                       ECP_clear_free(ret);\r
+                       return NULL;\r
+               }\r
+               return ret;\r
+       }\r
+\r
+       X0 = BN_is_zero(x);\r
+       A0 = BN_is_zero(E->A);\r
+\r
+       if ((ret = ECP_new()) == NULL) return NULL;\r
+\r
+       ret->is_in_mont = 0;\r
+\r
+       n0 = ctx->bn[ctx->tos]; \r
+       n1 = ctx->bn[ctx->tos + 1]; \r
+       if (!BN_zero(n0)) return NULL;\r
+       if (!BN_zero(n1)) return NULL;\r
+\r
+       ctx->tos += 2;\r
+\r
+       if (!X0)\r
+       {\r
+               if (!BN_mod_sqr(n0, x, E->p, ctx)) goto err;\r
+               if (!BN_mod_mul(n0, n0, x, E->p, ctx)) goto err;        /* x^3 */\r
+       }\r
+\r
+       if (!X0 && !A0)\r
+       {\r
+               if (!BN_mod_mul(n1, E->A, x, E->p, ctx)) goto err;      /* Ax */\r
+               if (!BN_mod_add(n0, n0, n1, E->p, ctx)) goto err;       /* x^3 + Ax */\r
+       }\r
+\r
+       if (!BN_is_zero(E->B))\r
+               if (!BN_mod_add(n0, n0, E->B, E->p, ctx)) goto err;     /* x^3 + Ax +B */\r
+\r
+       if (!BN_mod_sqrt(ret->Y, n0, E->p, ctx)) goto err;\r
+       if (BN_copy(ret->X, x) == NULL) goto err;\r
+       \r
+       if (Pnorm)\r
+       {\r
+               if (!BN_one(ret->Z)) goto err;\r
+       }\r
+       else\r
+       {\r
+               if (BN_copy(ret->Z, z) == NULL) goto err;\r
+               if (!BN_mod_sqr(n0, z, E->p, ctx)) goto err;\r
+               if (!BN_mod_mul(ret->X, ret->X, n0, E->p, ctx)) goto err;\r
+               if (!BN_mod_mul(n0, n0, z, E->p, ctx)) goto err;\r
+               if (!BN_mod_mul(ret->Y, ret->Y, n0, E->p, ctx)) goto err;\r
+       }\r
+\r
+#ifdef TEST\r
+       if (!ECP_is_on_ec(ret, E, ctx)) goto err;\r
+#endif\r
+       \r
+       ctx->tos -= 2;\r
+       return ret;\r
+\r
+err:\r
+       if (ret != NULL) ECP_clear_free(ret);\r
+       ctx->tos -= 2;\r
+       return NULL;\r
+}\r
+\r
+int ECP_ecp2bin(EC_POINT *P, unsigned char *to, int form)\r
+/* form =      1 ... compressed\r
+                       2 ... uncompressed\r
+                       3 ... hybrid */\r
+{\r
+       int bytes, bx, by;\r
+\r
+       assert (P != NULL);\r
+       assert (P->X != NULL && P->Y != NULL && P->Z != NULL);\r
+       assert (!P->is_in_mont);\r
+       assert (ECP_is_norm(P) || ECP_is_infty(P));\r
+       assert (to != NULL);\r
+       assert (form > 0 && form < 4);\r
+\r
+       if (BN_is_zero(P->Z))\r
+       {\r
+               to[0] = 0;\r
+               return 1;\r
+       }\r
+\r
+       bx = BN_num_bytes(P->X);\r
+       if (form == 1 ) bytes = bx + 1;\r
+       else \r
+       {\r
+               by = BN_num_bytes(P->Y);\r
+               bytes = (bx > by ? bx : by);\r
+               bytes = bytes * 2 + 1;\r
+       }\r
+       memset(to, 0, bytes);\r
+\r
+       switch (form)\r
+       {\r
+       case 1: to[0] = 2;      break;\r
+       case 2: to[0] = 4;      break;\r
+       case 3: to[0] = 6;      break;\r
+       }\r
+       if (form != 2) to[0] += BN_is_bit_set(P->Y, 0);\r
+\r
+       \r
+       if ((BN_bn2bin(P->X, to + 1)) != bx) return 0;\r
+       if (form != 1)\r
+       {\r
+               if ((BN_bn2bin(P->Y, to + bx + 1)) != by) return 0;\r
+       }\r
+\r
+       return bytes;\r
+}\r
+\r
+int ECP_bin2ecp(unsigned char *from, int len, EC_POINT *P, EC *E, BN_CTX *ctx)\r
+{\r
+       int y;\r
+       BIGNUM *x;\r
+       EC_POINT *pp;\r
+\r
+       assert (E != NULL);\r
+       assert (E->A != NULL && E->B != NULL && E->p != NULL);\r
+       assert (!E->is_in_mont);\r
+\r
+       assert (ctx != NULL);\r
+       assert (from != NULL);\r
+       assert (P != NULL);\r
+       assert (P->X != NULL && P->Y != NULL && P->Z != NULL);\r
+\r
+       if (len == 1 && from[0] != 0) return 0;\r
+\r
+       if (len == 0 || len == 1)\r
+       { \r
+               if (!BN_zero(P->Z)) return 0;\r
+               return 1;\r
+       }\r
+\r
+       switch (from[0])\r
+       {\r
+       case 2:\r
+       case 3:\r
+               y = from[0] - 2;\r
+               if ((x = BN_new()) == NULL) return 0;\r
+               if (BN_bin2bn(from + 1, len - 1, x) == NULL) return 0;\r
+\r
+               pp = ECP_generate(x, NULL, E, ctx);\r
+               BN_clear_free(x);\r
+               if (pp == NULL) return 0;\r
+\r
+               ECP_copy(P, pp);\r
+               ECP_clear_free(pp);\r
+\r
+               if (BN_is_bit_set(P->Y, 0) != y)\r
+                       if (!BN_sub(P->Y, E->p, P->Y)) return 0;\r
+               break;\r
+\r
+       case 4:\r
+       case 6:\r
+       case 7:\r
+               y = (len - 1)/2;\r
+               if (BN_bin2bn(from + 1, y, P->X) == NULL) return 0;\r
+               if (BN_bin2bn(from + y + 1, y, P->Y) == NULL) return 0;\r
+               if (!BN_set_word(P->Z, 1)) return 0;\r
+               break;\r
+\r
+       default:\r
+               assert(0);\r
+\r
+       }\r
+\r
+       if (!ECP_is_on_ec(P, E, ctx)) return 0;\r
+       return 1;\r
+}\r
+\r
+int ECP_normalize(EC_POINT *P, EC *E, BN_CTX *ctx)\r
+{\r
+       BIGNUM *z, *zm;\r
+\r
+       assert (P != NULL);\r
+       assert (P->X != NULL && P->Y != NULL && P->Z != NULL);\r
+\r
+       assert (E != NULL);\r
+       assert (E->A != NULL && E->B != NULL && E->p != NULL);\r
+\r
+       assert (ctx != NULL);\r
+\r
+       if (ECP_is_norm(P)) return 1;\r
+       if (ECP_is_infty(P)) return 0;\r
+\r
+       if ((zm = BN_mod_inverse(P->Z, E->p, ctx)) == NULL) return 0;\r
+\r
+       assert(!P->is_in_mont);\r
+\r
+\r
+       z = ctx->bn[ctx->tos]; \r
+       ctx->tos++;\r
+\r
+       if (!BN_mod_mul(z, zm, zm, E->p, ctx)) goto err;\r
+       if (!BN_mod_mul(P->X, P->X, z, E->p, ctx)) goto err;\r
+\r
+       if (!BN_mod_mul(z, z, zm, E->p, ctx)) goto err;\r
+       if (!BN_mod_mul(P->Y, P->Y, z, E->p, ctx)) goto err;\r
+\r
+       if (!BN_one(P->Z)) goto err;\r
+\r
+       if (zm != NULL) BN_clear_free(zm);\r
+\r
+       ctx->tos--;\r
+       return 1;\r
+\r
+err:\r
+       if (zm != NULL) BN_clear_free(zm);\r
+       ctx->tos--;\r
+       return 0;\r
+}\r
+\r
+int ECP_copy(EC_POINT *R, EC_POINT *P)\r
+{\r
+       assert(P != NULL);\r
+       assert(P->X != NULL && P->Y != NULL && P->Z != NULL);\r
+\r
+       assert(R != NULL);\r
+       assert(R->X != NULL && R->Y != NULL && R->Z != NULL);\r
+\r
+       if (BN_copy(R->X, P->X) == NULL) return 0;\r
+       if (BN_copy(R->Y, P->Y) == NULL) return 0;\r
+       if (BN_copy(R->Z, P->Z) == NULL) return 0;\r
+       R->is_in_mont = P->is_in_mont;\r
+\r
+       return 1;\r
+}\r
+\r
+EC_POINT *ECP_dup(EC_POINT *P)\r
+{\r
+       EC_POINT *ret;\r
+\r
+       ret = ECP_new();\r
+       if (ret == NULL) return NULL;\r
+\r
+       if (!ECP_copy(ret, P))\r
+       {\r
+               ECP_clear_free(ret);\r
+               return(NULL);\r
+       }\r
+\r
+       return(ret);\r
+}\r
+\r
+\r
+EC_POINT *ECP_minus(EC_POINT *P, BIGNUM *p) /* mont || non-mont */\r
+{\r
+       EC_POINT *ret;\r
+\r
+       assert(P != NULL);\r
+       assert(P->X != NULL && P->Y != NULL && P->Z != NULL);\r
+\r
+       assert(p != NULL);\r
+\r
+       assert(BN_cmp(P->Y, p) < 0);\r
+\r
+       ret = ECP_dup(P);\r
+       if (ret == NULL) return NULL;\r
+\r
+       if (BN_is_zero(ret->Y)) return ret;\r
+\r
+       if (!BN_sub(ret->Y, p, ret->Y))\r
+       {\r
+               ECP_clear_free(ret);\r
+               return NULL;\r
+       }\r
+\r
+       return ret;\r
+}\r
+\r
+\r
+#ifdef SIMPLE\r
+int ECP_cmp(EC_POINT *P, EC_POINT *Q, BIGNUM *p, BN_CTX *ctx)\r
+/* return values: \r
+       -2 ... error\r
+        0 ... P = Q \r
+       -1 ... P = -Q\r
+        1 ... else\r
+*/\r
+{\r
+       BIGNUM *n0, *n1, *n2, *n3, *n4;\r
+       int Pnorm, Qnorm;\r
+\r
+       assert(P != NULL);\r
+       assert(P->X != NULL && P->Y != NULL && P->Z != NULL);\r
+\r
+       assert(Q != NULL);\r
+       assert(Q->X != NULL && Q->Y != NULL && Q->Z != NULL);\r
+\r
+       assert(p != NULL);\r
+       assert(ctx != NULL);\r
+\r
+       assert(!P->is_in_mont);\r
+       assert(!Q->is_in_mont);\r
+\r
+       if (ECP_is_infty(P) && ECP_is_infty(Q)) return 0;\r
+       if (ECP_is_infty(P) || ECP_is_infty(Q)) return 1;\r
+\r
+       \r
+       Pnorm = (ECP_is_norm(P));\r
+       Qnorm = (ECP_is_norm(Q));\r
+       \r
+       n0 = ctx->bn[ctx->tos]; \r
+       n1 = ctx->bn[ctx->tos + 1]; \r
+       n2 = ctx->bn[ctx->tos + 2]; \r
+       n3 = ctx->bn[ctx->tos + 3]; \r
+       n4 = ctx->bn[ctx->tos + 4]; \r
+       ctx->tos += 5;\r
+       \r
+       if (Qnorm)\r
+       {\r
+               if (BN_copy(n1, P->X) == NULL) goto err;                        /* L1 = x_p */\r
+               if (BN_copy(n2, P->Y) == NULL) goto err;                        /* L2 = y_p */\r
+       }\r
+       else\r
+       {\r
+               if (!BN_sqr(n0, Q->Z, ctx)) goto err;\r
+               if (!BN_mod_mul(n1, P->X, n0, p, ctx)) goto err;        /* L1 = x_p * z_q^2 */\r
+\r
+               if (!BN_mod_mul(n0, n0, Q->Z, p, ctx)) goto err; \r
+               if (!BN_mod_mul(n2, P->Y, n0, p, ctx)) goto err;        /* L2 = y_p * z_q^3 */\r
+       }\r
+\r
+       if (Pnorm)\r
+       {\r
+               if (BN_copy(n3, Q->X) == NULL) goto err;                        /* L3 = x_q */\r
+               if (BN_copy(n4, Q->Y) == NULL) goto err;                        /* L4 = y_q */\r
+       }\r
+       else\r
+       {\r
+               if (!BN_sqr(n0, P->Z, ctx)) goto err;\r
+               if (!BN_mod_mul(n3, Q->X, n0, p, ctx)) goto err;        /* L3 = x_q * z_p^2 */\r
+\r
+               if (!BN_mod_mul(n0, n0, P->Z, p, ctx)) goto err; \r
+               if (!BN_mod_mul(n4, Q->Y, n0, p, ctx)) goto err;        /* L4 = y_q * z_p^3 */\r
+       }\r
+\r
+       if (!BN_mod_sub(n0, n1, n3, p, ctx)) goto err;                  /* L5 = L1 - L3 */\r
+\r
+       if (!BN_is_zero(n0))\r
+       {\r
+               ctx->tos -= 5;\r
+               return 1;\r
+       }\r
+       \r
+       if (!BN_mod_sub(n0, n2, n4, p, ctx)) goto err;                  /* L6 = L2 - L4 */\r
+\r
+       if (!BN_is_zero(n0))\r
+       {\r
+               ctx->tos -= 5;\r
+               return -1;\r
+       }\r
+\r
+       ctx->tos -= 5;\r
+       return 0;\r
+\r
+err:\r
+       ctx->tos -= 5;\r
+       return -2;\r
+}\r
+\r
+int ECP_double(EC_POINT *R, EC_POINT *P, EC *E, BN_CTX *ctx)\r
+/* R <- 2P (on E) */\r
+{\r
+       BIGNUM *n0, *n1, *n2, *n3, *p;\r
+       int Pnorm, A0;\r
+\r
+       assert(P != NULL);\r
+       assert(P->X != NULL && P->Y != NULL && P->Z != NULL);\r
+\r
+       assert(R != NULL);\r
+       assert(R->X != NULL && R->Y != NULL && R->Z != NULL);\r
+\r
+       assert(E != NULL);\r
+       assert(E->A != NULL && E->B != NULL && E->p != NULL && E->h != NULL);\r
+\r
+       assert(ctx != NULL);\r
+\r
+       assert(!P->is_in_mont);\r
+\r
+       if (ECP_is_infty(P))\r
+       {\r
+               if (!BN_zero(R->Z)) return 0;\r
+               return 1;\r
+       }\r
+\r
+       Pnorm = (ECP_is_norm(P));\r
+       A0 = (BN_is_zero(E->A));\r
+\r
+       n0 = ctx->bn[ctx->tos]; \r
+       n1 = ctx->bn[ctx->tos + 1]; \r
+       n2 = ctx->bn[ctx->tos + 2]; \r
+       n3 = ctx->bn[ctx->tos + 3]; \r
+       ctx->tos += 4;\r
+\r
+       p = E->p;\r
+\r
+       /* L1 */\r
+       if (Pnorm || A0)\r
+       {\r
+               if (!BN_mod_sqr(n1, P->X, p, ctx)) goto err;\r
+               if (!BN_mul_word(n1, 3)) goto err;  \r
+               if (!A0)                                   /* if A = 0: L1 = 3 * x^2 + a * z^4 = 3 * x ^2    */\r
+                       if (!BN_mod_add(n1, n1, E->A, p, ctx)) goto err; /* L1 = 3 * x^2 + a * z^4 = 3 * x^2 + a */\r
+       }\r
+       else\r
+       {\r
+               if (!BN_mod_sqr(n0, P->Z, p, ctx)) goto err;\r
+               if (!BN_mod_mul(n0, n0, n0, p, ctx)) goto err;\r
+               if (!BN_mod_mul(n0, n0, E->A, p, ctx)) goto err; \r
+               if (!BN_mod_sqr(n1, P->X, p, ctx)) goto err;\r
+               if (!BN_mul_word(n1, 3)) goto err;  \r
+               if (!BN_mod_add(n1, n1, n0, p, ctx)) goto err;          /* L1 = 3 * x^2 + a * z^4 */\r
+       }\r
+\r
+       /* Z */\r
+       if (Pnorm)\r
+       {\r
+               if (BN_copy(n0, P->Y) == NULL) goto err;\r
+       }\r
+       else\r
+       {\r
+               if (!BN_mod_mul(n0, P->Y, P->Z, p, ctx)) goto err; \r
+       }\r
+       if (!BN_lshift1(n0, n0)) goto err; \r
+       if (!BN_smod(R->Z, n0, p, ctx)) goto err;                               /* Z = 2 * y * z */\r
+\r
+       /* L2 */\r
+       if (!BN_mod_sqr(n3, P->Y, p, ctx)) goto err;\r
+       if (!BN_mod_mul(n2, P->X, n3, p, ctx)) goto err; \r
+       if (!BN_lshift(n2, n2, 2)) goto err; \r
+       if (!BN_smod(n2, n2, p, ctx)) goto err;                                 /* L2 = 4 * x * y^2 */\r
+\r
+       /* X */\r
+       if (!BN_lshift1(n0, n2)) goto err; \r
+       if (!BN_mod_sqr(R->X, n1, p, ctx)) goto err;\r
+       if (!BN_mod_sub(R->X, R->X, n0, p, ctx)) goto err;              /* X = L1^2 - 2 * L2 */\r
+       \r
+       /* L3 */\r
+       if (!BN_mod_sqr(n0, n3, p, ctx)) goto err;\r
+       if (!BN_lshift(n3, n0, 3)) goto err; \r
+       if (!BN_smod(n3, n3, p, ctx)) goto err;                                 /* L3 = 8 * y^4 */\r
+       \r
+       /* Y */\r
+       if (!BN_mod_sub(n0, n2, R->X, p, ctx)) goto err; \r
+       if (!BN_mod_mul(n0, n1, n0, p, ctx)) goto err; \r
+       if (!BN_mod_sub(R->Y, n0, n3, p, ctx)) goto err;                /* Y = L1 * (L2 - X) - L3 */\r
+\r
+\r
+#ifdef TEST\r
+       if (!ECP_is_on_ec(R, E, ctx)) return 0;\r
+#endif\r
+\r
+       ctx->tos -= 4;\r
+       return 1;\r
+\r
+err:\r
+       ctx->tos -= 4;\r
+       return 0;\r
+}\r
+\r
+int ECP_add(EC_POINT *R, EC_POINT *P, EC_POINT *Q, EC *E, BN_CTX *ctx)\r
+/* R <- P + Q (on E) */\r
+{\r
+       BIGNUM *n0, *n1, *n2, *n3, *n4, *n5, *n6, *p;\r
+       int Pnorm, Qnorm;\r
+\r
+       assert(P != NULL);\r
+       assert(P->X != NULL && P->Y != NULL && P->Z != NULL);\r
+\r
+       assert(Q != NULL);\r
+       assert(Q->X != NULL && Q->Y != NULL && Q->Z != NULL);\r
+\r
+       assert(R != NULL);\r
+       assert(R->X != NULL && R->Y != NULL && R->Z != NULL);\r
+\r
+       assert(E != NULL);\r
+       assert(E->A != NULL && E->B != NULL && E->p != NULL && E->h != NULL);\r
+       assert(!BN_is_zero(E->h));;\r
+\r
+       assert(ctx != NULL);\r
+\r
+       assert(!P->is_in_mont);\r
+       assert(!Q->is_in_mont);\r
+\r
+       if (P == Q) return ECP_double(R, P, E, ctx);\r
+\r
+       if (ECP_is_infty(P)) return ECP_copy(R, Q);\r
+       if (ECP_is_infty(Q)) return ECP_copy(R, P);\r
+       \r
+       Pnorm = (ECP_is_norm(P));\r
+       Qnorm = (ECP_is_norm(Q));\r
+       \r
+       n0 = ctx->bn[ctx->tos]; \r
+       n1 = ctx->bn[ctx->tos + 1]; \r
+       n2 = ctx->bn[ctx->tos + 2]; \r
+       n3 = ctx->bn[ctx->tos + 3]; \r
+       n4 = ctx->bn[ctx->tos + 4]; \r
+       n5 = ctx->bn[ctx->tos + 5]; \r
+       n6 = ctx->bn[ctx->tos + 6]; \r
+       ctx->tos += 7;\r
+       p = E->p;\r
+       \r
+       /* L1; L2 */\r
+       if (Qnorm)\r
+       {\r
+               if (BN_copy(n1, P->X) == NULL) goto err;         /* L1 = x_p */\r
+               if (BN_copy(n2, P->Y) == NULL) goto err;         /* L2 = y_p */\r
+       }\r
+       else\r
+       {\r
+               if (!BN_sqr(n0, Q->Z, ctx)) goto err;\r
+               if (!BN_mod_mul(n1, P->X, n0, p, ctx)) goto err; /* L1 = x_p * z_q^2 */\r
+\r
+               if (!BN_mod_mul(n0, n0, Q->Z, p, ctx)) goto err; \r
+               if (!BN_mod_mul(n2, P->Y, n0, p, ctx)) goto err; /* L2 = y_p * z_q^3 */\r
+       }\r
+\r
+       /* L3; L4 */\r
+       if (Pnorm)\r
+       {\r
+               if (BN_copy(n3, Q->X) == NULL) goto err;         /* L3 = x_q */\r
+               if (BN_copy(n4, Q->Y) == NULL) goto err;         /* L4 = y_q */\r
+       }\r
+       else\r
+       {\r
+               if (!BN_sqr(n0, P->Z, ctx)) goto err;\r
+               if (!BN_mod_mul(n3, Q->X, n0, p, ctx)) goto err; /* L3 = x_q * z_p^2 */\r
+\r
+               if (!BN_mod_mul(n0, n0, P->Z, p, ctx)) goto err; \r
+               if (!BN_mod_mul(n4, Q->Y, n0, p, ctx)) goto err; /* L4 = y_q * z_p^3 */\r
+       }\r
+\r
+       /* L5; L6 */\r
+       if (!BN_mod_sub(n5, n1, n3, p, ctx)) goto err;          /* L5 = L1 - L3 */\r
+       if (!BN_mod_sub(n6, n2, n4, p, ctx)) goto err;          /* L6 = L2 - L4 */\r
+\r
+       /* pata */\r
+       if (BN_is_zero(n5))\r
+       {\r
+               if (BN_is_zero(n6))     /* P = Q => P + Q = 2P */\r
+               {\r
+                       ctx->tos -= 7;\r
+                       return ECP_double(R, P, E, ctx);\r
+               }\r
+               else                             /* P = -Q => P + Q = \infty */\r
+               { \r
+                       ctx->tos -= 7;\r
+                       if (!BN_zero(R->Z)) return 0;\r
+                       return 1;\r
+               }\r
+       }\r
+\r
+       /* L7; L8 */\r
+       if (!BN_mod_add(n1, n1, n3, p, ctx)) goto err;          /* L7 = L1 + L3 */\r
+       if (!BN_mod_add(n2, n2, n4, p, ctx)) goto err;          /* L8 = L2 + L4 */\r
+\r
+       /* Z */\r
+       if (Pnorm) \r
+       {\r
+               if (BN_copy(n0, Q->Z) == NULL) goto err;\r
+       }\r
+       else\r
+       {\r
+               if (!BN_mod_mul(n0, P->Z, Q->Z, p, ctx)) goto err;\r
+       }\r
+       if (!BN_mod_mul(R->Z, n0, n5, p, ctx)) goto err;        /* Z = z_p * z_q * L_5 */\r
+\r
+       /* X */\r
+       if (!BN_mod_sqr(n0, n6, p, ctx)) goto err;\r
+       if (!BN_mod_sqr(n4, n5, p, ctx)) goto err;\r
+       if (!BN_mod_mul(n3, n1, n4, p, ctx)) goto err; \r
+       if (!BN_mod_sub(R->X, n0, n3, p, ctx)) goto err;        /* X = L6^2 - L5^2 * L7 */\r
+       \r
+       /* L9 */\r
+       if (!BN_lshift1(n0, R->X)) goto err;\r
+       if (!BN_mod_sub(n0, n3, n0, p, ctx)) goto err;          /* L9 = L5^2 * L7 - 2X */\r
+\r
+       /* Y */\r
+       if (!BN_mod_mul(n0, n0, n6, p, ctx)) goto err; \r
+       if (!BN_mod_mul(n5, n4, n5, p, ctx)) goto err; \r
+       if (!BN_mod_mul(n1, n2, n5, p, ctx)) goto err; \r
+       if (!BN_mod_sub(n0, n0, n1, p, ctx)) goto err;   \r
+       if (!BN_mod_mul(R->Y, n0, E->h, p, ctx)) goto err;      /* Y = (L6 * L9 - L8 * L5^3) / 2 */\r
+\r
+\r
+\r
+#ifdef TEST\r
+       if (!ECP_is_on_ec(R, E, ctx)) return 0;\r
+#endif\r
+\r
+       ctx->tos -= 7;\r
+       return 1;\r
+\r
+err:\r
+       ctx->tos -= 7;\r
+       return 0;\r
+}\r
+\r
+\r
+ECP_PRECOMPUTE *ECP_precompute(int r, EC_POINT *P, EC *E, BN_CTX *ctx)\r
+{\r
+       ECP_PRECOMPUTE *ret;\r
+       EC_POINT *P2;\r
+       int i, max;\r
+\r
+       assert(r > 2);\r
+       assert(!P->is_in_mont);\r
+       assert(!E->is_in_mont);\r
+\r
+       ret=(ECP_PRECOMPUTE *)malloc(sizeof(ECP_PRECOMPUTE));\r
+       if (ret == NULL) return NULL;\r
+\r
+       max = 1;\r
+       max <<= (r - 1);\r
+\r
+       ret->r = 0;\r
+\r
+       ret->Pi=(EC_POINT **)malloc(sizeof(EC_POINT *) * max);\r
+       if (ret->Pi == NULL) goto err;\r
+\r
+       \r
+       /* P2 = [2]P */\r
+       if ((P2 = ECP_new()) == NULL) goto err;\r
+       if (!ECP_double(P2, P, E, ctx)) goto err;\r
+\r
+       /* P_0 = P */\r
+       if((ret->Pi[0] = ECP_dup(P)) == NULL) goto err;\r
+\r
+\r
+       /* P_i = P_(i-1) + P2 */\r
+       for (i = 1; i < max; i++)\r
+       {\r
+               if ((ret->Pi[i] = ECP_new()) == NULL) goto err;\r
+               \r
+               if (!ECP_add(ret->Pi[i], P2, ret->Pi[i - 1], E, ctx)) goto err;\r
+       }\r
+\r
+       ret->r = r;\r
+       ECP_clear_free(P2);\r
+\r
+       return ret;\r
+\r
+err:\r
+       ECP_clear_free(P2);\r
+       ECP_clear_free_precompute(ret);\r
+       return NULL;\r
+}\r
+\r
+int ECP_multiply(EC_POINT *R, BIGNUM *k, ECP_PRECOMPUTE *prec, EC *E, BN_CTX *ctx)\r
+/* R = [k]P */\r
+{\r
+       int j;\r
+       int t, nextw, h, r;\r
+\r
+       assert(R != NULL);\r
+       assert(R->X != NULL && R->Y != NULL && R->Z != NULL);\r
+\r
+       assert(E != NULL);\r
+       assert(E->A != NULL && E->B != NULL && E->p != NULL && E->h != NULL);\r
+\r
+       assert(k != NULL);\r
+       assert(!k->neg);\r
+\r
+       assert(ctx != NULL);\r
+       assert(prec != NULL);\r
+\r
+       assert(!E->is_in_mont);\r
+\r
+       if (BN_is_zero(k))\r
+       {\r
+               if (!BN_zero(R->Z)) return 0;\r
+               R->is_in_mont = 0;\r
+               return 1;\r
+       }\r
+\r
+\r
+       j = BN_num_bits(k);\r
+       j--;\r
+\r
+       r = prec->r;\r
+\r
+       if (!BN_zero(R->Z)) return 0;\r
+       R->is_in_mont = 0;\r
+\r
+       while(j >= 0)\r
+       {\r
+               if (!BN_is_bit_set(k, j))\r
+               {\r
+                       if (!ECP_double(R, R, E, ctx)) return 0;\r
+                       j--;\r
+               }\r
+               else\r
+               {\r
+                       nextw = j - r;\r
+                       if (nextw < -1) nextw = -1;\r
+                       t = nextw + 1;                  \r
+                       while(!BN_is_bit_set(k, t))\r
+                       {\r
+                               t++;\r
+                       }\r
+\r
+                       if (!ECP_double(R, R, E, ctx)) return 0;\r
+\r
+                       j--;\r
+                       if (j < t) h = 0;\r
+                       else \r
+                       {\r
+                               h = 1;\r
+                               for(; j > t; j--)\r
+                               {\r
+                                       h <<= 1;\r
+                                       if (BN_is_bit_set(k, j)) h++;\r
+                                       if (!ECP_double(R, R, E, ctx)) return 0;\r
+                               }\r
+                               if (!ECP_double(R, R, E, ctx)) return 0;\r
+                               j--;\r
+                       }\r
+\r
+                       if (!ECP_add(R, R, prec->Pi[h], E, ctx)) return 0;\r
+\r
+                       for (; j > nextw; j--)\r
+                       {\r
+                               if (!ECP_double(R, R, E, ctx)) return 0;\r
+                       }\r
+\r
+               }\r
+       }\r
+\r
+       return 1;\r
+}\r
+\r
+#endif /* SIMPLE */\r
+\r
+#ifdef MONTGOMERY\r
+\r
+int ECP_to_montgomery(EC_POINT *P, BN_MONTGOMERY *mont, BN_CTX *ctx)\r
+{\r
+\r
+       assert(P != NULL);\r
+       assert(P->X != NULL && P->Y != NULL && P->Z != NULL);\r
+\r
+       assert(mont != NULL);\r
+       assert(mont->p != NULL);\r
+\r
+       assert(ctx != NULL);\r
+\r
+       if (P->is_in_mont) return 1;\r
+\r
+       if (!BN_lshift(P->X, P->X, mont->R_num_bits)) return 0;\r
+       if (!BN_mod(P->X, P->X, mont->p, ctx)) return 0;\r
+\r
+       if (!BN_lshift(P->Y, P->Y, mont->R_num_bits)) return 0;\r
+       if (!BN_mod(P->Y, P->Y, mont->p, ctx)) return 0;\r
+\r
+       if (!BN_lshift(P->Z, P->Z, mont->R_num_bits)) return 0;\r
+       if (!BN_mod(P->Z, P->Z, mont->p, ctx)) return 0;\r
+\r
+       P->is_in_mont = 1;\r
+       return 1;\r
+}\r
+\r
+\r
+int ECP_from_montgomery(EC_POINT *P, BN_MONTGOMERY *mont, BN_CTX *ctx)\r
+{\r
+\r
+       assert(P != NULL);\r
+       assert(P->X != NULL && P->Y != NULL && P->Z != NULL);\r
+\r
+       assert(mont != NULL);\r
+       assert(mont->p != NULL);\r
+\r
+       assert(ctx != NULL);\r
+\r
+       if (!P->is_in_mont) return 1;\r
+\r
+       if (!BN_mont_red(P->X, mont, ctx)) return 0;\r
+       if (!BN_mont_red(P->Y, mont, ctx)) return 0;\r
+       if (!BN_mont_red(P->Z, mont, ctx)) return 0;\r
+\r
+       P->is_in_mont = 0;\r
+       return 1;\r
+}\r
+\r
+int ECP_mont_cmp(EC_POINT *P, EC_POINT *Q, BN_MONTGOMERY *mont, BN_CTX *ctx) \r
+/* return values: \r
+       -2 ... error\r
+        0 ... P = Q \r
+       -1 ... P = -Q\r
+        1 ... else\r
+*/\r
+{\r
+       BIGNUM *n0, *n1, *n2, *n3, *n4, *n5, *p;\r
+\r
+       assert(P != NULL);\r
+       assert(P->X != NULL && P->Y != NULL && P->Z != NULL);\r
+\r
+       assert(Q != NULL);\r
+       assert(Q->X != NULL && Q->Y != NULL && Q->Z != NULL);\r
+\r
+       assert(mont != NULL);\r
+       assert(mont->p != NULL);\r
+\r
+       assert(ctx != NULL);\r
+\r
+       if (!P->is_in_mont)\r
+               if (!ECP_to_montgomery(P, mont, ctx)) return 0;\r
+\r
+       if (!Q->is_in_mont)\r
+               if (!ECP_to_montgomery(Q, mont, ctx)) return 0;\r
+\r
+\r
+       if (ECP_is_infty(P) && ECP_is_infty(Q)) return 0;\r
+       if (ECP_is_infty(P) || ECP_is_infty(Q)) return 1;\r
+\r
+       \r
+       n0 = ctx->bn[ctx->tos]; \r
+       n1 = ctx->bn[ctx->tos + 1]; \r
+       n2 = ctx->bn[ctx->tos + 2]; \r
+       n3 = ctx->bn[ctx->tos + 3]; \r
+       n4 = ctx->bn[ctx->tos + 4]; \r
+       n5 = ctx->bn[ctx->tos + 5]; \r
+       ctx->tos += 6;\r
+\r
+       p = mont->p;\r
+       \r
+\r
+       if (!BN_mont_mod_mul(n5, Q->Z, Q->Z, mont, ctx)) goto err;\r
+       if (!BN_mont_mod_mul(n1, P->X, n5, mont, ctx)) goto err;        /* L1 = x_p * z_q^2 */\r
+\r
+       if (!BN_mont_mod_mul(n0, n5, Q->Z, mont, ctx)) goto err; \r
+       if (!BN_mont_mod_mul(n2, P->Y, n0, mont, ctx)) goto err;        /* L2 = y_p * z_q^3 */\r
+\r
+       if (!BN_mont_mod_mul(n5, P->Z, P->Z, mont, ctx)) goto err;\r
+       if (!BN_mont_mod_mul(n3, Q->X, n5, mont, ctx)) goto err;        /* L3 = x_q * z_p^2 */\r
+\r
+       if (!BN_mont_mod_mul(n0, n5, P->Z, mont, ctx)) goto err; \r
+       if (!BN_mont_mod_mul(n4, Q->Y, n0, mont, ctx)) goto err;        /* L4 = y_q * z_p^3 */\r
+\r
+\r
+       if (!BN_mont_mod_sub(n0, n1, n3, mont)) goto err;                       /* L5 = L1 - L3 */\r
+\r
+       if (!BN_is_zero(n0))\r
+       {\r
+               ctx->tos -= 6;\r
+               return 1;\r
+       }\r
+       \r
+       if (!BN_mont_mod_sub(n0, n2, n4, mont)) goto err;                       /* L6 = L2 - L4 */\r
+\r
+       if (!BN_is_zero(n0))\r
+       {\r
+               ctx->tos -= 6;\r
+               return -1;\r
+       }\r
+\r
+       ctx->tos -= 6;\r
+       return 0;\r
+\r
+err:\r
+       ctx->tos -= 6;\r
+       return -2;\r
+}\r
+\r
+\r
+int ECP_mont_double(EC_POINT *R, EC_POINT *P, EC *E, BN_MONTGOMERY *mont, BN_CTX *ctx)\r
+/* R <- 2P (on E) */\r
+{\r
+       BIGNUM *n0, *n1, *n2, *n3, *p;\r
+\r
+       assert(P != NULL);\r
+       assert(P->X != NULL && P->Y != NULL && P->Z != NULL);\r
+\r
+       assert(R != NULL);\r
+       assert(R->X != NULL && R->Y != NULL && R->Z != NULL);\r
+\r
+       assert(E != NULL);\r
+       assert(E->A != NULL && E->B != NULL && E->p != NULL && E->h != NULL);\r
+\r
+       assert(ctx != NULL);\r
+       \r
+       if (!P->is_in_mont)\r
+               if (!ECP_to_montgomery(P, mont, ctx)) return 0;\r
+\r
+       if (!E->is_in_mont) \r
+               if (!EC_to_montgomery(E, mont, ctx)) return 0;\r
+\r
+       R->is_in_mont = 1;\r
+\r
+       if (ECP_is_infty(P))\r
+       {\r
+               if (!BN_zero(R->Z)) return 0;\r
+               return 1;\r
+       }\r
+\r
+\r
+       n0 = ctx->bn[ctx->tos]; \r
+       n1 = ctx->bn[ctx->tos + 1]; \r
+       n2 = ctx->bn[ctx->tos + 2]; \r
+       n3 = ctx->bn[ctx->tos + 3]; \r
+\r
+       ctx->tos += 4;\r
+\r
+       p = E->p;\r
+\r
+       /* L1 */\r
+       if (!BN_mont_mod_mul(n0, P->Z, P->Z, mont, ctx)) goto err;\r
+       if (!BN_mont_mod_mul(n2, n0, n0, mont, ctx)) goto err;\r
+       if (!BN_mont_mod_mul(n0, n2, E->A, mont, ctx)) goto err; \r
+       if (!BN_mont_mod_mul(n1, P->X, P->X, mont, ctx)) goto err;\r
+       if (!BN_mont_mod_lshift1(n2, n1, mont)) goto err;\r
+       if (!BN_mont_mod_add(n1, n1, n2, mont)) goto err;\r
+       if (!BN_mont_mod_add(n1, n1, n0, mont)) goto err;               /* L1 = 3 * x^2 + a * z^4 */\r
+\r
+       /* Z */\r
+       if (!BN_mont_mod_mul(n0, P->Y, P->Z, mont, ctx)) goto err; \r
+       if (!BN_mont_mod_lshift1(R->Z, n0, mont)) goto err;             /* Z = 2 * y * z */\r
+\r
+       /* L2 */\r
+       if (!BN_mont_mod_mul(n3, P->Y, P->Y, mont, ctx)) goto err;\r
+       if (!BN_mont_mod_mul(n2, P->X, n3, mont, ctx)) goto err; \r
+       if (!BN_mont_mod_lshift(n2, n2, 2, mont)) goto err;             /* L2 = 4 * x * y^2 */\r
+\r
+       /* X */\r
+       if (!BN_mont_mod_lshift1(n0, n2, mont)) goto err; \r
+       if (!BN_mont_mod_mul(R->X, n1, n1, mont, ctx)) goto err;\r
+       if (!BN_mont_mod_sub(R->X, R->X, n0, mont)) goto err;   /* X = L1^2 - 2 * L2 */\r
+       \r
+       /* L3 */\r
+       if (!BN_mont_mod_mul(n0, n3, n3, mont, ctx)) goto err;\r
+       if (!BN_mont_mod_lshift(n3, n0, 3, mont)) goto err;             /* L3 = 8 * y^4 */\r
+\r
+       \r
+       /* Y */\r
+       if (!BN_mont_mod_sub(n2, n2, R->X, mont)) goto err; \r
+       if (!BN_mont_mod_mul(n0, n1, n2, mont, ctx)) goto err; \r
+       if (!BN_mont_mod_sub(R->Y, n0, n3, mont)) goto err;             /* Y = L1 * (L2 - X) - L3 */\r
+\r
+       ctx->tos -= 4;\r
+       return 1;\r
+\r
+err:\r
+       ctx->tos -= 4;\r
+       return 0;\r
+}\r
+\r
+\r
+int ECP_mont_add(EC_POINT *R, EC_POINT *P, EC_POINT *Q, EC *E, BN_MONTGOMERY *mont, BN_CTX *ctx)\r
+/* R <- P + Q (on E) */\r
+{\r
+       BIGNUM *n0, *n1, *n2, *n3, *n4, *n5, *n6, *p;\r
+\r
+       assert(P != NULL);\r
+       assert(P->X != NULL && P->Y != NULL && P->Z != NULL);\r
+\r
+       assert(Q != NULL);\r
+       assert(Q->X != NULL && Q->Y != NULL && Q->Z != NULL);\r
+\r
+       assert(R != NULL);\r
+       assert(R->X != NULL && R->Y != NULL && R->Z != NULL);\r
+\r
+       assert(E != NULL);\r
+       assert(E->A != NULL && E->B != NULL && E->p != NULL && E->h != NULL);\r
+       assert(!BN_is_zero(E->h));;\r
+\r
+       assert(ctx != NULL);\r
+\r
+       if (!Q->is_in_mont)\r
+               if (!ECP_to_montgomery(Q, mont, ctx)) return 0;\r
+\r
+       if (!P->is_in_mont)\r
+               if (!ECP_to_montgomery(P, mont, ctx)) return 0;\r
+\r
+       if (!E->is_in_mont) \r
+               if (!EC_to_montgomery(E, mont, ctx)) return 0;\r
+\r
+       if (P == Q) return ECP_mont_double(R, P, E, mont, ctx);\r
+\r
+       if (ECP_is_infty(P)) return ECP_copy(R, Q);\r
+       if (ECP_is_infty(Q)) return ECP_copy(R, P);\r
+       \r
+\r
+       n0 = ctx->bn[ctx->tos]; \r
+       n1 = ctx->bn[ctx->tos + 1]; \r
+       n2 = ctx->bn[ctx->tos + 2]; \r
+       n3 = ctx->bn[ctx->tos + 3]; \r
+       n4 = ctx->bn[ctx->tos + 4]; \r
+       n5 = ctx->bn[ctx->tos + 5]; \r
+       n6 = ctx->bn[ctx->tos + 6]; \r
+       ctx->tos += 7;\r
+\r
+\r
+       p = E->p;\r
+\r
+       R->is_in_mont = 1;\r
+       \r
+       /* L1; L2 */\r
+       if (!BN_mont_mod_mul(n6, Q->Z, Q->Z, mont, ctx)) goto err;\r
+       if (!BN_mont_mod_mul(n1, P->X, n6, mont, ctx)) goto err;        /* L1 = x_p * z_q^2 */\r
+\r
+       if (!BN_mont_mod_mul(n0, n6, Q->Z, mont, ctx)) goto err; \r
+       if (!BN_mont_mod_mul(n2, P->Y, n0, mont, ctx)) goto err;        /* L2 = y_p * z_q^3 */\r
+\r
+\r
+       /* L3; L4 */\r
+       if (!BN_mont_mod_mul(n6, P->Z, P->Z, mont, ctx)) goto err;\r
+       if (!BN_mont_mod_mul(n3, Q->X, n6, mont, ctx)) goto err;        /* L3 = x_q * z_p^2 */\r
+\r
+       if (!BN_mont_mod_mul(n0, n6, P->Z, mont, ctx)) goto err; \r
+       if (!BN_mont_mod_mul(n4, Q->Y, n0, mont, ctx)) goto err;        /* L4 = y_q * z_p^3 */\r
+\r
+\r
+       /* L5; L6 */\r
+       if (!BN_mont_mod_sub(n5, n1, n3, mont)) goto err;                       /* L5 = L1 - L3 */\r
+       if (!BN_mont_mod_sub(n6, n2, n4, mont)) goto err;                       /*L6 = L2 - L4 */\r
+\r
+\r
+       /* pata */\r
+       if (BN_is_zero(n5))\r
+       {\r
+               if (BN_is_zero(n6))  /* P = Q => P + Q = 2P */\r
+               {\r
+                       ctx->tos -= 7;\r
+                       return ECP_mont_double(R, P, E, mont, ctx);\r
+               }\r
+               else                             /* P = -Q => P + Q = \infty */\r
+               { \r
+                       ctx->tos -= 7;\r
+                       if (!BN_zero(R->Z)) return 0;\r
+                       return 1;\r
+               }\r
+       }\r
+\r
+       /* L7; L8 */\r
+       if (!BN_mont_mod_add(n1, n1, n3, mont)) goto err;                       /* L7 = L1 + L3 */\r
+       if (!BN_mont_mod_add(n2, n2, n4, mont)) goto err;                       /* L8 = L2 + L4 */\r
+\r
+\r
+       /* Z */\r
+       if (!BN_mont_mod_mul(n0, P->Z, Q->Z, mont, ctx)) goto err;\r
+       if (!BN_mont_mod_mul(R->Z, n0, n5, mont, ctx)) goto err;        /* Z = z_p * z_q * L_5 */\r
+\r
+\r
+       /* X */\r
+       if (!BN_mont_mod_mul(n0, n6, n6, mont, ctx)) goto err;\r
+       if (!BN_mont_mod_mul(n4, n5, n5, mont, ctx)) goto err;\r
+       if (!BN_mont_mod_mul(n3, n1, n4, mont, ctx)) goto err; \r
+       if (!BN_mont_mod_sub(R->X, n0, n3, mont)) goto err;                     /* X = L6^2 - L5^2 * L7 */\r
+\r
+       \r
+       /* L9 */\r
+       if (!BN_mont_mod_lshift1(n0, R->X, mont)) goto err;\r
+       if (!BN_mont_mod_sub(n3, n3, n0, mont)) goto err;                       /* L9 = L5^2 * L7 - 2X */\r
+\r
+\r
+       /* Y */\r
+       if (!BN_mont_mod_mul(n0, n3, n6, mont, ctx)) goto err; \r
+       if (!BN_mont_mod_mul(n6, n4, n5, mont, ctx)) goto err; \r
+       if (!BN_mont_mod_mul(n1, n2, n6, mont, ctx)) goto err; \r
+       if (!BN_mont_mod_sub(n0, n0, n1, mont)) goto err;   \r
+       if (!BN_mont_mod_mul(R->Y, n0, E->h, mont, ctx)) goto err;      /* Y = (L6 * L9 - L8 * L5^3) / 2 */\r
+\r
+\r
+       ctx->tos -= 7;\r
+       return 1;\r
+\r
+err:\r
+       ctx->tos -= 7;\r
+       return 0;\r
+}\r
+\r
+\r
+ECP_PRECOMPUTE *ECP_mont_precompute(int r, EC_POINT *P, EC *E, BN_MONTGOMERY *mont, BN_CTX *ctx)\r
+{\r
+       ECP_PRECOMPUTE *ret;\r
+       EC_POINT *P2;\r
+       int i, max;\r
+\r
+       assert(r > 2);\r
+       assert(r < sizeof(unsigned int) * 8 - 1);\r
+\r
+       assert(mont != NULL);\r
+       assert(mont->p != NULL);\r
+       \r
+       if (!P->is_in_mont)\r
+               if (!ECP_to_montgomery(P, mont, ctx)) return 0;\r
+\r
+       if (!E->is_in_mont) \r
+               if (!EC_to_montgomery(E, mont, ctx)) return 0;\r
+\r
+       ret=(ECP_PRECOMPUTE *)malloc(sizeof(ECP_PRECOMPUTE));\r
+       if (ret == NULL) return NULL;\r
+\r
+       max = 1;\r
+       max <<= (r - 1);\r
+\r
+       ret->r = 0;\r
+\r
+       ret->Pi=(EC_POINT **)malloc(sizeof(EC_POINT *) * max);\r
+       if (ret->Pi == NULL) goto err;\r
+\r
+       \r
+       /* P2 = [2]P */\r
+       if ((P2 = ECP_new()) == NULL) goto err;\r
+       if (!ECP_mont_double(P2, P, E, mont, ctx)) goto err;\r
+\r
+       /* P_0 = P */\r
+       if((ret->Pi[0] = ECP_dup(P)) == NULL) goto err;\r
+\r
+\r
+       /* P_i = P_(i-1) + P2 */\r
+       for (i = 1; i < max; i++)\r
+       {\r
+               if ((ret->Pi[i] = ECP_new()) == NULL) goto err;\r
+               if (!ECP_mont_add(ret->Pi[i], P2, ret->Pi[i - 1], E, mont, ctx)) goto err;\r
+       }\r
+\r
+       ret->r = r;\r
+       ECP_clear_free(P2);\r
+\r
+       return ret;\r
+\r
+err:\r
+       ECP_clear_free(P2);\r
+       ECP_clear_free_precompute(ret);\r
+       return NULL;\r
+}\r
+\r
+int ECP_mont_multiply(EC_POINT *R, BIGNUM *k, ECP_PRECOMPUTE *prec, EC *E, BN_MONTGOMERY *mont, BN_CTX *ctx)\r
+/* R = [k]P   P = prec->Pi[0]*/\r
+{\r
+       int j;\r
+       int t, nextw, h, r;\r
+\r
+       assert(R != NULL);\r
+       assert(R->X != NULL && R->Y != NULL && R->Z != NULL);\r
+\r
+       assert(E != NULL);\r
+       assert(E->A != NULL && E->B != NULL && E->p != NULL && E->h != NULL);\r
+\r
+       assert(k != NULL);\r
+       assert(!k->neg);\r
+\r
+       assert(ctx != NULL);\r
+       assert(prec != NULL);\r
+\r
+       assert(mont != NULL);\r
+       assert(mont->p != NULL);\r
+\r
+       if (!E->is_in_mont) \r
+               if (!EC_to_montgomery(E, mont, ctx)) return 0;\r
+\r
+\r
+       if (BN_is_zero(k))\r
+       {\r
+               if (!BN_zero(R->Z)) return 0;\r
+               R->is_in_mont = 1;\r
+               return 1;\r
+       }\r
+\r
+       j = BN_num_bits(k);\r
+       j--;\r
+\r
+       r = prec->r;\r
+\r
+       if (!BN_zero(R->Z)) return 0;\r
+       R->is_in_mont = 1;\r
+\r
+       while(j >= 0)\r
+       {\r
+               if (!BN_is_bit_set(k, j))\r
+               {\r
+                       if (!ECP_mont_double(R, R, E, mont, ctx)) return 0;\r
+                       j--;\r
+               }\r
+               else\r
+               {\r
+                       nextw = j - r;\r
+                       if (nextw < -1) nextw = -1;\r
+                       t = nextw + 1;                  \r
+                       while(!BN_is_bit_set(k, t))\r
+                       {\r
+                               t++;\r
+                       }\r
+\r
+                       if (!ECP_mont_double(R, R, E, mont, ctx)) return 0;\r
+\r
+                       j--;\r
+                       if (j < t) h = 0;\r
+                       else \r
+                       {\r
+                               h = 1;\r
+                               for(; j > t; j--)\r
+                               {\r
+                                       h <<= 1;\r
+                                       if (BN_is_bit_set(k, j)) h++;\r
+                                       if (!ECP_mont_double(R, R, E, mont, ctx)) return 0;\r
+                               }\r
+                               if (!ECP_mont_double(R, R, E, mont, ctx)) return 0;\r
+                               j--;\r
+                       }\r
+\r
+                       if (!ECP_mont_add(R, R, prec->Pi[h], E, mont, ctx)) return 0;\r
+\r
+                       for (; j > nextw; j--)\r
+                       {\r
+                               if (!ECP_mont_double(R, R, E, mont, ctx)) return 0;\r
+                       }\r
+\r
+               }\r
+       }\r
+\r
+       return 1;\r
+}\r
+\r
+\r
+int ECP_mont_multiply2(EC_POINT *R, BIGNUM *k, EC_POINT *P, EC *E, BN_MONTGOMERY *mont, BN_CTX *ctx)\r
+/* R = [k]P */\r
+{\r
+       int j, hj, kj;\r
+       BIGNUM *h;\r
+       EC_POINT *mP;\r
+\r
+       assert(R != NULL);\r
+       assert(R->X != NULL && R->Y != NULL && R->Z != NULL);\r
+\r
+       assert(P != NULL);\r
+       assert(P->X != NULL && P->Y != NULL && P->Z != NULL);\r
+\r
+       assert(E != NULL);\r
+       assert(E->A != NULL && E->B != NULL && E->p != NULL && E->h != NULL);\r
+\r
+       assert(k != NULL);\r
+       assert(!k->neg);\r
+\r
+       assert(ctx != NULL);\r
+\r
+       assert(mont != NULL);\r
+       assert(mont->p != NULL);\r
+\r
+       if (!E->is_in_mont) \r
+               if (!EC_to_montgomery(E, mont, ctx)) return 0;\r
+\r
+       if (!P->is_in_mont) \r
+               if (!ECP_to_montgomery(P, mont, ctx)) return 0;\r
+\r
+\r
+       if (BN_is_zero(k))\r
+       {\r
+               if (!BN_zero(R->Z)) return 0;\r
+               R->is_in_mont = 1;\r
+               return 1;\r
+       }\r
+\r
+       if ((h = BN_dup(k)) == NULL) return 0;\r
+       \r
+       if (!BN_lshift1(h, h)) goto err;\r
+       if (!BN_add(h, h, k)) goto err;\r
+\r
+       if (!ECP_copy(R, P)) goto err;\r
+       if ((mP = ECP_mont_minus(P, mont)) == NULL) goto err;\r
+\r
+       for(j = BN_num_bits(h) - 2; j > 0; j--)\r
+       {\r
+               if (!ECP_mont_double(R, R, E, mont, ctx)) goto err;\r
+               kj = BN_is_bit_set(k, j);\r
+               hj = BN_is_bit_set(h, j);\r
+               if (hj == 1 && kj == 0)\r
+                       if (!ECP_mont_add(R, R, P, E, mont, ctx)) goto err;\r
+               if (hj == 0 && kj == 1)\r
+                       if (!ECP_mont_add(R, R, mP, E, mont, ctx)) goto err;\r
+       }\r
+\r
+       if (h != NULL) BN_free(h);\r
+       if (mP != NULL) ECP_clear_free(mP);\r
+       return 1;\r
+\r
+err:\r
+       if (h != NULL) BN_free(h);\r
+       if (mP != NULL) ECP_clear_free(mP);\r
+       return 0;\r
+}\r
+\r
+#endif /* MONTGOMERY */\r