From 7e0c5264e76963b691221082ddb50152c8fc2c75 Mon Sep 17 00:00:00 2001 From: =?utf8?q?Bodo=20M=C3=B6ller?= Date: Sun, 26 Nov 2000 12:12:35 +0000 Subject: [PATCH] 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 --- crypto/bn/bn_modfs.c | 258 ++++++++ crypto/bn/bn_modfs.h | 32 + crypto/bn/bn_mont2.c | 374 +++++++++++ crypto/bn/bn_mont2.h | 41 ++ crypto/ec/ec.c | 121 ++++ crypto/ec/ec.h | 86 +++ crypto/ec/ec_point.c | 1461 ++++++++++++++++++++++++++++++++++++++++++ 7 files changed, 2373 insertions(+) create mode 100644 crypto/bn/bn_modfs.c create mode 100644 crypto/bn/bn_modfs.h create mode 100644 crypto/bn/bn_mont2.c create mode 100644 crypto/bn/bn_mont2.h create mode 100644 crypto/ec/ec.c create mode 100644 crypto/ec/ec.h create mode 100644 crypto/ec/ec_point.c diff --git a/crypto/bn/bn_modfs.c b/crypto/bn/bn_modfs.c new file mode 100644 index 0000000000..2697d54303 --- /dev/null +++ b/crypto/bn/bn_modfs.c @@ -0,0 +1,258 @@ +/* + * + * bn_modfs.c + * + * Some Modular Arithmetic Functions. + * + * Copyright (C) Lenka Fibikova 2000 + * + * + */ + + +#include +#include +#include + +#include "bn_modfs.h" + +#define MAX_ROUNDS 10 + +int BN_smod(BIGNUM *rem, BIGNUM *m, BIGNUM *d, BN_CTX *ctx) +{ + int r_sign; + + assert(rem != NULL && m != NULL && d != NULL && ctx != NULL); + + if (d->neg) return 0; + r_sign = m->neg; + + if (r_sign) m->neg = 0; + if (!(BN_div(NULL,rem,m,d,ctx))) return 0; + if (r_sign) + { + m->neg = r_sign; + if (!BN_is_zero(rem)) + { + rem->neg = r_sign; + BN_add(rem, rem, d); + } + } + return 1; +} + +int BN_mod_sub(BIGNUM *r, BIGNUM *a, BIGNUM *b, BIGNUM *m, BN_CTX *ctx) +{ + assert(r != NULL && a != NULL && b != NULL && m != NULL && ctx != NULL); + + if (!BN_sub(r, a, b)) return 0; + return BN_smod(r, r, m, ctx); + +} + +int BN_mod_add(BIGNUM *r, BIGNUM *a, BIGNUM *b, BIGNUM *m, BN_CTX *ctx) +{ + assert(r != NULL && a != NULL && b != NULL && m != NULL && ctx != NULL); + + if (!BN_add(r, a, b)) return 0; + return BN_smod(r, r, m, ctx); + +} + +int BN_mod_sqr(BIGNUM *r, BIGNUM *a, BIGNUM *p, BN_CTX *ctx) +{ + assert(r != NULL && a != NULL && p != NULL && ctx != NULL); + + if (!BN_sqr(r, a, ctx)) return 0; + return BN_div(NULL, r, r, p, ctx); +} + +int BN_swap(BIGNUM *x, BIGNUM *y) +{ + BIGNUM *c; + + assert(x != NULL && y != NULL); + + if ((c = BN_dup(x)) == NULL) goto err; + if ((BN_copy(x, y)) == NULL) goto err; + if ((BN_copy(y, c)) == NULL) goto err; + BN_clear_free(c); + return 1; + +err: + if (c != NULL) BN_clear_free(c); + return 0; +} + + +int BN_legendre(BIGNUM *a, BIGNUM *p, BN_CTX *ctx) +{ + BIGNUM *x, *y, *y2; + BN_ULONG m; + int L; + + assert(a != NULL && p != NULL && ctx != NULL); + + x = ctx->bn[ctx->tos]; + y = ctx->bn[ctx->tos + 1]; + y2 = ctx->bn[ctx->tos + 2]; + + ctx->tos += 3; + + if (!BN_smod(x, a, p, ctx)) goto err; + if (BN_is_zero(x)) + { + + ctx->tos -= 3; + return 0; + } + + if (BN_copy(y, p) == NULL) goto err; + L = 1; + + while (1) + { + if (!BN_rshift1(y2, y)) goto err; + if (BN_cmp(x, y2) > 0) + { + if (!BN_sub(x, y, x)) goto err; + if (BN_mod_word(y, 4) == 3) + L = -L; + } + while (BN_mod_word(x, 4) == 0) + BN_div_word(x, 4); + if (BN_mod_word(x, 2) == 0) + { + BN_div_word(x, 2); + m = BN_mod_word(y, 8); + if (m == 3 || m == 5) L = -L; + } + if (BN_is_one(x)) + { + ctx->tos -= 3; + return L; + } + + if (BN_mod_word(x, 4) == 3 && BN_mod_word(y, 4) == 3) L = -L; + if (!BN_swap(x, y)) goto err; + + if (!BN_smod(x, x, y, ctx)) goto err; + + } + + +err: + ctx->tos -= 3; + return -2; + +} + +int BN_mod_sqrt(BIGNUM *x, BIGNUM *a, BIGNUM *p, BN_CTX *ctx) +/* x^2 = a (mod p) */ +{ + int ret; + BIGNUM *n0, *n1, *r, *b, *m; + int max; + + assert(x != NULL && a != NULL && p != NULL && ctx != NULL); + assert(BN_cmp(a, p) < 0); + + ret = BN_legendre(a, p, ctx); + if (ret < 0 || ret > 1) return 0; + if (ret == 0) + { + if (!BN_zero(x)) return 0; + return 1; + } + + n0 = ctx->bn[ctx->tos]; + n1 = ctx->bn[ctx->tos + 1]; + ctx->tos += 2; + + if ((r = BN_new()) == NULL) goto err; + if ((b = BN_new()) == NULL) goto err; + if ((m = BN_new()) == NULL) goto err; + + + if (!BN_zero(n0)) goto err; + if (!BN_zero(n1)) goto err; + if (!BN_zero(r)) goto err; + if (!BN_zero(b)) goto err; + if (!BN_zero(m)) goto err; + + max = 0; + + do{ + if (max++ > MAX_ROUNDS) goto err; /* if p is not prime could never stop*/ + if (!BN_add_word(m, 1)) goto err; + ret = BN_legendre(m, p, ctx); + if (ret < -1 || ret > 1) goto err; + + }while(ret != -1); + + if (BN_copy(n1, p) == NULL) goto err; + if (!BN_sub_word(n1, 1)) goto err; + + while (!BN_is_odd(n1)) + { + if (!BN_add_word(r, 1)) goto err; + if (!BN_rshift1(n1, n1)) goto err; + } + + if (!BN_mod_exp_simple(n0, m, n1, p, ctx)) goto err; + + if (!BN_sub_word(n1, 1)) goto err; + if (!BN_rshift1(n1, n1)) goto err; + if (!BN_mod_exp_simple(x, a, n1, p, ctx)) goto err; + + if (!BN_mod_sqr(b, x, p, ctx)) goto err; + if (!BN_mod_mul(b, b, a, p, ctx)) goto err; + + if (!BN_mod_mul(x, x, a, p, ctx)) goto err; + + while (!BN_is_one(b)) + { + + if (!BN_one(m)) goto err; + if (!BN_mod_sqr(n1, b, p, ctx)) goto err; + while(!BN_is_one(n1)) + { + if (!BN_mod_mul(n1, n1, n1, p, ctx)) goto err; + if (!BN_add_word(m, 1)) goto err; + } + + if (!BN_sub(r, r, m)) goto err; + if (!BN_sub_word(r, 1)) goto err; + if (r->neg) goto err; + + if (BN_copy(n1, n0) == NULL) goto err; + while(!BN_is_zero(r)) + { + if (!BN_mod_mul(n1, n1, n1, p, ctx)) goto err; + if (!BN_sub_word(r, 1)) goto err; + } + + if (!BN_mod_mul(n0, n1, n1, p, ctx)) goto err; + if (BN_copy(r, m) == NULL) goto err; + if (!BN_mod_mul(x, x, n1, p, ctx)) goto err; + if (!BN_mod_mul(b, b, n0, p, ctx)) goto err; + } + + +#ifdef TEST + BN_mod_sqr(n0, x, p, ctx); + if (BN_cmp(n0, a)) goto err; +#endif + + if (r != NULL) BN_clear_free(r); + if (b != NULL) BN_clear_free(b); + if (m != NULL) BN_clear_free(m); + ctx->tos -= 2; + return 1; +err: + if (r != NULL) BN_clear_free(r); + if (b != NULL) BN_clear_free(b); + if (m != NULL) BN_clear_free(m); + ctx->tos -= 2; + return 0; +} diff --git a/crypto/bn/bn_modfs.h b/crypto/bn/bn_modfs.h new file mode 100644 index 0000000000..b7ae4964d8 --- /dev/null +++ b/crypto/bn/bn_modfs.h @@ -0,0 +1,32 @@ +/* + * + * bn_modfs.h + * + * Some Modular Arithmetic Functions. + * + * Copyright (C) Lenka Fibikova 2000 + * + * + */ + +#ifndef HEADER_BN_MODFS_H +#define HEADER_BN_MODFS_H + + +#include "bn.h" + +#ifdef BN_is_zero +#undef BN_is_zero +#define BN_is_zero(a) (((a)->top == 0) || (((a)->top == 1) && ((a)->d[0] == (BN_ULONG)0))) +#endif /*BN_is_zero(a)*/ + + +int BN_smod(BIGNUM *rem, BIGNUM *m, BIGNUM *d, BN_CTX *ctx); +int BN_mod_sub(BIGNUM *r, BIGNUM *a, BIGNUM *b, BIGNUM *m, BN_CTX *ctx); +int BN_mod_add(BIGNUM *r, BIGNUM *a, BIGNUM *b, BIGNUM *m, BN_CTX *ctx); +int BN_mod_sqr(BIGNUM *r, BIGNUM *a, BIGNUM *p, BN_CTX *ctx); +int BN_swap(BIGNUM *x, BIGNUM *y); +int BN_legendre(BIGNUM *a, BIGNUM *p, BN_CTX *ctx); +int BN_mod_sqrt(BIGNUM *x, BIGNUM *a, BIGNUM *p, BN_CTX *ctx); + +#endif \ No newline at end of file diff --git a/crypto/bn/bn_mont2.c b/crypto/bn/bn_mont2.c new file mode 100644 index 0000000000..9f6222fb13 --- /dev/null +++ b/crypto/bn/bn_mont2.c @@ -0,0 +1,374 @@ +/* + * + * bn_mont2.c + * + * Montgomery Modular Arithmetic Functions. + * + * Copyright (C) Lenka Fibikova 2000 + * + * + */ + + +#include +#include +#include + +#include "bn.h" +#include "bn_modfs.h" +#include "bn_mont2.h" + +#define BN_mask_word(x, m) ((x->d[0]) & (m)) + +BN_MONTGOMERY *BN_mont_new() +{ + BN_MONTGOMERY *ret; + + ret=(BN_MONTGOMERY *)malloc(sizeof(BN_MONTGOMERY)); + + if (ret == NULL) return NULL; + + if ((ret->p = BN_new()) == NULL) + { + free(ret); + return NULL; + } + + return ret; +} + + +void BN_mont_clear_free(BN_MONTGOMERY *mont) +{ + if (mont == NULL) return; + + if (mont->p != NULL) BN_clear_free(mont->p); + + mont->p_num_bytes = 0; + mont->R_num_bits = 0; + mont->p_inv_b_neg = 0; +} + +int BN_to_mont(BIGNUM *x, BN_MONTGOMERY *mont, BN_CTX *ctx) +{ + assert(x != NULL); + + assert(mont != NULL); + assert(mont->p != NULL); + + assert(ctx != NULL); + + if (!BN_lshift(x, x, mont->R_num_bits)) return 0; + if (!BN_mod(x, x, mont->p, ctx)) return 0; + + return 1; +} + + +static BN_ULONG BN_mont_inv(BIGNUM *a, int e, BN_CTX *ctx) +/* y = a^{-1} (mod 2^e) for an odd number a */ +{ + BN_ULONG y, exp, mask; + BIGNUM *x, *xy, *x_sh; + int i; + + assert(a != NULL && ctx != NULL); + assert(e <= BN_BITS2); + assert(BN_is_odd(a)); + assert(!BN_is_zero(a) && !a->neg); + + + y = 1; + exp = 2; + mask = 3; + if((x = BN_dup(a)) == NULL) return 0; + if(!BN_mask_bits(x, e)) return 0; + + xy = ctx->bn[ctx->tos]; + x_sh = ctx->bn[ctx->tos + 1]; + ctx->tos += 2; + + if (BN_copy(xy, x) == NULL) goto err; + if (!BN_lshift1(x_sh, x)) goto err; + + + for (i = 2; i <= e; i++) + { + if (exp < BN_mask_word(xy, mask)) + { + y = y + exp; + if (!BN_add(xy, xy, x_sh)) goto err; + } + + exp <<= 1; + if (!BN_lshift1(x_sh, x_sh)) goto err; + mask <<= 1; + mask++; + } + + +#ifdef TEST + if (xy->d[0] != 1) goto err; +#endif + + if (x != NULL) BN_clear_free(x); + ctx->tos -= 2; + return y; + + +err: + if (x != NULL) BN_clear_free(x); + ctx->tos -= 2; + return 0; + +} + +int BN_mont_set(BIGNUM *p, BN_MONTGOMERY *mont, BN_CTX *ctx) +{ + assert(p != NULL && ctx != NULL); + assert(mont != NULL); + assert(mont->p != NULL); + assert(!BN_is_zero(p) && !p->neg); + + + mont->p_num_bytes = p->top; + mont->R_num_bits = (mont->p_num_bytes) * BN_BITS2; + + if (BN_copy(mont->p, p) == NULL); + + mont->p_inv_b_neg = BN_mont_inv(p, BN_BITS2, ctx); + mont->p_inv_b_neg = 0 - mont->p_inv_b_neg; + + return 1; +} + +static int BN_cpy_mul_word(BIGNUM *ret, BIGNUM *a, BN_ULONG w) +/* ret = a * w */ +{ + if (BN_copy(ret, a) == NULL) return 0; + + if (!BN_mul_word(ret, w)) return 0; + + return 1; +} + + +int BN_mont_red(BIGNUM *y, BN_MONTGOMERY *mont, BN_CTX *ctx) +/* yR^{-1} (mod p) */ +{ + int i; + BIGNUM *up, *p; + BN_ULONG u; + + assert(y != NULL && mont != NULL && ctx != NULL); + assert(mont->p != NULL); + assert(BN_cmp(y, mont->p) < 0); + assert(!y->neg); + + + if (BN_is_zero(y)) return 1; + + p = mont->p; + up = ctx->bn[ctx->tos]; + ctx->tos += 1; + + + for (i = 0; i < mont->p_num_bytes; i++) + { + u = (y->d[0]) * mont->p_inv_b_neg; /* u = y_0 * p' */ + + if (!BN_cpy_mul_word(up, p, u)) goto err; /* up = u * p */ + + if (!BN_add(y, y, up)) goto err; +#ifdef TEST + if (y->d[0]) goto err; +#endif + if (!BN_rshift(y, y, BN_BITS2)) goto err; /* y = (y + up)/b */ + } + + + if (BN_cmp(y, mont->p) >= 0) + { + if (!BN_sub(y, y, mont->p)) goto err; + } + + ctx->tos -= 1; + return 1; + +err: + ctx->tos -= 1; + return 0; + +} + + +int BN_mont_mod_mul(BIGNUM *r, BIGNUM *x, BIGNUM *y, BN_MONTGOMERY *mont, BN_CTX *ctx) +/* r = x * y mod p */ +/* r != x && r! = y !!! */ +{ + BIGNUM *xiy, *up; + BN_ULONG u; + int i; + + + assert(r != x && r != y); + assert(r != NULL && x != NULL && y != NULL && mont != NULL && ctx != NULL); + assert(mont->p != NULL); + assert(BN_cmp(x, mont->p) < 0); + assert(BN_cmp(y, mont->p) < 0); + assert(!x->neg); + assert(!y->neg); + + if (BN_is_zero(x) || BN_is_zero(y)) + { + if (!BN_zero(r)) return 0; + return 1; + } + + + + xiy = ctx->bn[ctx->tos]; + up = ctx->bn[ctx->tos + 1]; + ctx->tos += 2; + + if (!BN_zero(r)) goto err; + + for (i = 0; i < x->top; i++) + { + u = (r->d[0] + x->d[i] * y->d[0]) * mont->p_inv_b_neg; + + if (!BN_cpy_mul_word(xiy, y, x->d[i])) goto err; + if (!BN_cpy_mul_word(up, mont->p, u)) goto err; + + if (!BN_add(r, r, xiy)) goto err; + if (!BN_add(r, r, up)) goto err; + +#ifdef TEST + if (r->d[0]) goto err; +#endif + if (!BN_rshift(r, r, BN_BITS2)) goto err; + } + + for (i = x->top; i < mont->p_num_bytes; i++) + { + u = (r->d[0]) * mont->p_inv_b_neg; + + if (!BN_cpy_mul_word(up, mont->p, u)) goto err; + + if (!BN_add(r, r, up)) goto err; + +#ifdef TEST + if (r->d[0]) goto err; +#endif + if (!BN_rshift(r, r, BN_BITS2)) goto err; + } + + + if (BN_cmp(r, mont->p) >= 0) + { + if (!BN_sub(r, r, mont->p)) goto err; + } + + + ctx->tos -= 2; + return 1; + +err: + ctx->tos -= 2; + return 0; +} + +int BN_mont_mod_add(BIGNUM *r, BIGNUM *x, BIGNUM *y, BN_MONTGOMERY *mont) +{ + assert(r != NULL && x != NULL && y != NULL && mont != NULL); + assert(mont->p != NULL); + assert(BN_cmp(x, mont->p) < 0); + assert(BN_cmp(y, mont->p) < 0); + assert(!x->neg); + assert(!y->neg); + + if (!BN_add(r, x, y)) return 0; + if (BN_cmp(r, mont->p) >= 0) + { + if (!BN_sub(r, r, mont->p)) return 0; + } + + return 1; +} + + +int BN_mont_mod_sub(BIGNUM *r, BIGNUM *x, BIGNUM *y, BN_MONTGOMERY *mont) +{ + assert(r != NULL && x != NULL && y != NULL && mont != NULL); + assert(mont->p != NULL); + assert(BN_cmp(x, mont->p) < 0); + assert(BN_cmp(y, mont->p) < 0); + assert(!x->neg); + assert(!y->neg); + + if (!BN_sub(r, x, y)) return 0; + if (r->neg) + { + if (!BN_add(r, r, mont->p)) return 0; + } + + return 1; +} + +int BN_mont_mod_lshift1(BIGNUM *r, BIGNUM *x, BN_MONTGOMERY *mont) +{ + assert(r != NULL && x != NULL && mont != NULL); + assert(mont->p != NULL); + assert(BN_cmp(x, mont->p) < 0); + assert(!x->neg); + + if (!BN_lshift1(r, x)) return 0; + + if (BN_cmp(r, mont->p) >= 0) + { + if (!BN_sub(r, r, mont->p)) return 0; + } + + return 1; +} + +int BN_mont_mod_lshift(BIGNUM *r, BIGNUM *x, int n, BN_MONTGOMERY *mont) +{ + int sh_nb; + + assert(r != NULL && x != NULL && mont != NULL); + assert(mont->p != NULL); + assert(BN_cmp(x, mont->p) < 0); + assert(!x->neg); + assert(n > 0); + + if (r != x) + { + if (BN_copy(r, x) == NULL) return 0; + } + + while (n) + { + sh_nb = BN_num_bits(mont->p) - BN_num_bits(r); + if (sh_nb > n) sh_nb = n; + + if (sh_nb) + { + if(!BN_lshift(r, r, sh_nb)) return 0; + } + else + { + sh_nb = 1; + if (!BN_lshift1(r, r)) return 0; + } + + if (BN_cmp(r, mont->p) >= 0) + { + if (!BN_sub(r, r, mont->p)) return 0; + } + + n -= sh_nb; + } + + return 1; +} diff --git a/crypto/bn/bn_mont2.h b/crypto/bn/bn_mont2.h new file mode 100644 index 0000000000..1bce6d71f1 --- /dev/null +++ b/crypto/bn/bn_mont2.h @@ -0,0 +1,41 @@ +/* + * + * bn_mont2.h + * + * Montgomery Modular Arithmetic Functions. + * + * Copyright (C) Lenka Fibikova 2000 + * + * + */ + +#ifndef HEADER_MONT2_H +#define HEADER_MONT2_H + +#define MONTGOMERY + +#include "bn.h" + +typedef struct bn_mont_st{ + int R_num_bits; + int p_num_bytes; + BIGNUM *p; + BN_ULONG p_inv_b_neg; /* p' = p^{-1} mod b; b = 2^BN_BITS */ +} BN_MONTGOMERY; + +#define BN_from_mont(x, mont, ctx) (BN_mont_red((x), (mont), (ctx))) + + +BN_MONTGOMERY *BN_mont_new(); +int BN_to_mont(BIGNUM *x, BN_MONTGOMERY *mont, BN_CTX *ctx); +void BN_mont_clear_free(BN_MONTGOMERY *mont); +int BN_mont_set(BIGNUM *p, BN_MONTGOMERY *mont, BN_CTX *ctx); +int BN_mont_red(BIGNUM *y, BN_MONTGOMERY *mont, BN_CTX *ctx); +BN_ULONG BN_mont_inv(BIGNUM *x, int e, BN_CTX *ctx); +int BN_mont_mod_mul(BIGNUM *r, BIGNUM *x, BIGNUM *y, BN_MONTGOMERY *mont, BN_CTX *ctx); +int BN_mont_mod_add(BIGNUM *r, BIGNUM *x, BIGNUM *y, BN_MONTGOMERY *mont); +int BN_mont_mod_sub(BIGNUM *r, BIGNUM *x, BIGNUM *y, BN_MONTGOMERY *mont); +int BN_mont_mod_lshift1(BIGNUM *r, BIGNUM *x, BN_MONTGOMERY *mont); +int BN_mont_mod_lshift(BIGNUM *r, BIGNUM *x, int n, BN_MONTGOMERY *mont); + +#endif \ No newline at end of file diff --git a/crypto/ec/ec.c b/crypto/ec/ec.c new file mode 100644 index 0000000000..bc689e74f2 --- /dev/null +++ b/crypto/ec/ec.c @@ -0,0 +1,121 @@ +/* + * + * ec.c + * + * Elliptic Curve Arithmetic Functions + * + * Copyright (C) Lenka Fibikova 2000 + * + * + */ + + +#include +#include +#include + +#include "ec.h" +#include "bn_modfs.h" + + + +EC *EC_new() +{ + EC *ret; + + ret=(EC *)malloc(sizeof(EC)); + if (ret == NULL) return NULL; + ret->A = BN_new(); + ret->B = BN_new(); + ret->p = BN_new(); + ret->h = BN_new(); + ret->is_in_mont = 0; + + if (ret->A == NULL || ret->B == NULL || ret->p == NULL || ret->h == NULL) + { + if (ret->A != NULL) BN_free(ret->A); + if (ret->B != NULL) BN_free(ret->B); + if (ret->p != NULL) BN_free(ret->p); + if (ret->h != NULL) BN_free(ret->h); + free(ret); + return(NULL); + } + return(ret); +} + + +void EC_clear_free(EC *E) +{ + if (E == NULL) return; + + if (E->A != NULL) BN_clear_free(E->A); + if (E->B != NULL) BN_clear_free(E->B); + if (E->p != NULL) BN_clear_free(E->p); + if (E->h != NULL) BN_clear_free(E->h); + E->is_in_mont = 0; + free(E); +} + + +#ifdef MONTGOMERY +int EC_to_montgomery(EC *E, BN_MONTGOMERY *mont, BN_CTX *ctx) +{ + assert(E != NULL); + assert(E->A != NULL && E->B != NULL && E->p != NULL && E->h != NULL); + + assert(mont != NULL); + assert(mont->p != NULL); + + assert(ctx != NULL); + + if (E->is_in_mont) return 1; + + if (!BN_lshift(E->A, E->A, mont->R_num_bits)) return 0; + if (!BN_mod(E->A, E->A, mont->p, ctx)) return 0; + + if (!BN_lshift(E->B, E->B, mont->R_num_bits)) return 0; + if (!BN_mod(E->B, E->B, mont->p, ctx)) return 0; + + if (!BN_lshift(E->h, E->h, mont->R_num_bits)) return 0; + if (!BN_mod(E->h, E->h, mont->p, ctx)) return 0; + + E->is_in_mont = 1; + return 1; + +} + + +int EC_from_montgomery(EC *E, BN_MONTGOMERY *mont, BN_CTX *ctx) +{ + assert(E != NULL); + assert(E->A != NULL && E->B != NULL && E->p != NULL && E->h != NULL); + + assert(mont != NULL); + assert(mont->p != NULL); + + assert(ctx != NULL); + + if (!E->is_in_mont) return 1; + + if (!BN_mont_red(E->A, mont, ctx)) return 0; + if (!BN_mont_red(E->B, mont, ctx)) return 0; + if (!BN_mont_red(E->h, mont, ctx)) return 0; + + E->is_in_mont = 0; + return 1; +} +#endif /* MONTGOMERY */ + +int EC_set_half(EC *E) +/* h <- 1/2 mod p = (p + 1)/2 */ +{ + assert(E != NULL); + assert(E->p != NULL); + assert(E->h != NULL); + assert(!E->is_in_mont); + + if (BN_copy(E->h, E->p) == NULL) return 0; + if (!BN_add_word(E->h, 1)) return 0; + if (!BN_rshift1(E->h, E->h)) return 0; + return 1; +} diff --git a/crypto/ec/ec.h b/crypto/ec/ec.h new file mode 100644 index 0000000000..97d55cb2cc --- /dev/null +++ b/crypto/ec/ec.h @@ -0,0 +1,86 @@ +/* + * + * ec.h + * + * Elliptic Curve Arithmetic Functions + * + * Copyright (C) Lenka Fibikova 2000 + * + * + */ + + +#ifndef HEADER_EC_H +#define HEADER_EC_H + + +#include "bn.h" +#include "bn_mont2.h" + +typedef struct bn_ec_struct /* E: y^2 = x^3 + Ax + B (mod p) */ +{ + BIGNUM *A, *B, *p, *h; /* h = 1/2 mod p = (p + 1)/2 */ + int is_in_mont; +} EC; + +typedef struct bn_ec_point_struct /* P = [X, Y, Z] */ +{ + BIGNUM *X, *Y, *Z; + int is_in_mont; +} EC_POINT; + +typedef struct bn_ecp_precompute_struct /* Pi[i] = [2i + 1]P i = 0..2^{r-1} - 1 */ +{ + int r; + EC_POINT **Pi; +} ECP_PRECOMPUTE; + + +#define ECP_is_infty(P) (BN_is_zero(P->Z)) +#define ECP_is_norm(P) (BN_is_one(P->Z)) + +#define ECP_mont_minus(P, mont) (ECP_minus((P), (mont)->p)) + + +EC *EC_new(); +void EC_clear_free(EC *E); +int EC_set_half(EC *E); +#ifdef MONTGOMERY +int EC_to_montgomery(EC *E, BN_MONTGOMERY *mont, BN_CTX *ctx); +int EC_from_montgomery(EC *E, BN_MONTGOMERY *mont, BN_CTX *ctx); +#endif /* MONTGOMERY */ + + +EC_POINT *ECP_new(); +void ECP_clear_free(EC_POINT *P); +void ECP_clear_free_precompute(ECP_PRECOMPUTE *prec); + +EC_POINT *ECP_generate(BIGNUM *x, BIGNUM *z, EC *E, BN_CTX *ctx); +EC_POINT *ECP_dup(EC_POINT *P); +int ECP_copy(EC_POINT *R, EC_POINT *P); +int ECP_normalize(EC_POINT *P, EC *E, BN_CTX *ctx); +EC_POINT *ECP_minus(EC_POINT *P, BIGNUM *p); +int ECP_is_on_ec(EC_POINT *P, EC *E, BN_CTX *ctx); +int ECP_ecp2bin(EC_POINT *P, unsigned char *to, int form); /* form(ANSI 9.62): 1-compressed; 2-uncompressed; 3-hybrid */ +int ECP_bin2ecp(unsigned char *from, int len, EC_POINT *P, EC *E, BN_CTX *ctx); + +#ifdef SIMPLE +int ECP_cmp(EC_POINT *P, EC_POINT *Q, BIGNUM *p, BN_CTX *ctx); +int ECP_double(EC_POINT *R, EC_POINT *P, EC *E, BN_CTX *ctx); +int ECP_add(EC_POINT *R, EC_POINT *P, EC_POINT *Q, EC *E, BN_CTX *ctx); +ECP_PRECOMPUTE *ECP_precompute(int r, EC_POINT *P, EC *E, BN_CTX *ctx); +int ECP_multiply(EC_POINT *R, BIGNUM *k, ECP_PRECOMPUTE *prec, EC *E, BN_CTX *ctx); +#endif /* SIMPLE */ + +#ifdef MONTGOMERY +int ECP_to_montgomery(EC_POINT *P, BN_MONTGOMERY *mont, BN_CTX *ctx); +int ECP_from_montgomery(EC_POINT *P, BN_MONTGOMERY *mont, BN_CTX *ctx); +int ECP_mont_cmp(EC_POINT *P, EC_POINT *Q, BN_MONTGOMERY *mont, BN_CTX *ctx); +int ECP_mont_double(EC_POINT *R, EC_POINT *P, EC *E, BN_MONTGOMERY *mont, BN_CTX *ctx); +int ECP_mont_add(EC_POINT *R, EC_POINT *P, EC_POINT *Q, EC *E, BN_MONTGOMERY *mont, BN_CTX *ctx); +ECP_PRECOMPUTE *ECP_mont_precompute(int r, EC_POINT *P, EC *E, BN_MONTGOMERY *mont, BN_CTX *ctx); +int ECP_mont_multiply(EC_POINT *R, BIGNUM *k, ECP_PRECOMPUTE *prec, EC *E, BN_MONTGOMERY *mont, BN_CTX *ctx); +int ECP_mont_multiply2(EC_POINT *R, BIGNUM *k, EC_POINT *P, EC *E, BN_MONTGOMERY *mont, BN_CTX *ctx); +#endif /* MONTGOMERY */ + +#endif \ No newline at end of file diff --git a/crypto/ec/ec_point.c b/crypto/ec/ec_point.c new file mode 100644 index 0000000000..fee5078bf8 --- /dev/null +++ b/crypto/ec/ec_point.c @@ -0,0 +1,1461 @@ +/* + * + * ec_point.c + * + * Elliptic Curve Arithmetic Functions + * + * Copyright (C) Lenka Fibikova 2000 + * + * + */ + +#include +#include +#include +#include + +#include "bn.h" + +#include "bn_modfs.h" +#include "bn_mont2.h" +#include "ec.h" + +EC_POINT *ECP_new() +{ + EC_POINT *ret; + + ret=(EC_POINT *)malloc(sizeof(EC_POINT)); + if (ret == NULL) return NULL; + ret->X = BN_new(); + ret->Y = BN_new(); + ret->Z = BN_new(); + ret->is_in_mont = 0; + + if (ret->X == NULL || ret->Y == NULL || ret->Z == NULL) + { + if (ret->X != NULL) BN_free(ret->X); + if (ret->Y != NULL) BN_free(ret->Y); + if (ret->Z != NULL) BN_free(ret->Z); + free(ret); + return(NULL); + } + return(ret); +} + +void ECP_clear_free(EC_POINT *P) +{ + if (P == NULL) return; + + P->is_in_mont = 0; + if (P->X != NULL) BN_clear_free(P->X); + if (P->Y != NULL) BN_clear_free(P->Y); + if (P->Z != NULL) BN_clear_free(P->Z); + free(P); +} + +void ECP_clear_free_precompute(ECP_PRECOMPUTE *prec) +{ + int i; + int max; + + if (prec == NULL) return; + if (prec->Pi != NULL) + { + max = 1; + max <<= (prec->r - 1); + + for (i = 0; i < max; i++) + { + if (prec->Pi[i] != NULL) ECP_clear_free(prec->Pi[i]); + } + } + free(prec); +} + +int ECP_is_on_ec(EC_POINT *P, EC *E, BN_CTX *ctx) +{ + BIGNUM *n0, *n1, *n2, *p; + int Pnorm; + + assert(P != NULL); + assert(P->X != NULL && P->Y != NULL && P->Z != NULL); + + assert(E != NULL); + assert(E->A != NULL && E->B != NULL && E->p != NULL); + + assert(ctx != NULL); + + assert(!P->is_in_mont); + + if (ECP_is_infty(P)) return 1; + + n0 = ctx->bn[ctx->tos]; + n1 = ctx->bn[ctx->tos + 1]; + n2 = ctx->bn[ctx->tos + 2]; + ctx->tos += 3; + + + p = E->p; + + Pnorm = (ECP_is_norm(P)); + + if (!Pnorm) + { + if (!BN_mod_mul(n0, P->Z, P->Z, p, ctx)) goto err; + if (!BN_mod_mul(n1, n0, n0, p, ctx)) goto err; + if (!BN_mod_mul(n2, n0, n1, p, ctx)) goto err; + } + + if (!BN_mod_mul(n0, P->X, P->X, p, ctx)) goto err; + if (!BN_mod_mul(n0, n0, P->X, p, ctx)) goto err; + + if (Pnorm) + { + if (!BN_mod_mul(n1, P->X, E->A, p, ctx)) goto err; + } + else + { + if (!BN_mod_mul(n1, n1, P->X, p, ctx)) goto err; + if (!BN_mod_mul(n1, n1, E->A, p, ctx)) goto err; + } + if (!BN_mod_add(n0, n0, n1, p, ctx)) goto err; + + if (Pnorm) + { + if (!BN_mod_add(n0, n0, E->B, p, ctx)) goto err; + } + else + { + if (!BN_mod_mul(n2, n2, E->B, p, ctx)) goto err; + if (!BN_mod_add(n0, n0, n2, p, ctx)) goto err; + } + + if (!BN_mod_mul(n1, P->Y, P->Y, p, ctx)) goto err; + + if (BN_cmp(n0, n1)) + { + ctx->tos -= 3; + return 0; + } + + ctx->tos -= 3; + return 1; + +err: + ctx->tos -= 3; + return -1; +} + + +EC_POINT *ECP_generate(BIGNUM *x, BIGNUM *z,EC *E, BN_CTX *ctx) +/* x == NULL || z = 0 -> point of infinity */ +/* z == NULL || z = 1 -> normalized */ +{ + BIGNUM *n0, *n1; + EC_POINT *ret; + int Pnorm, Pinfty, X0, A0; + + assert(E != NULL); + assert(E->A != NULL && E->B != NULL && E->p != NULL && E->h != NULL); + + assert(ctx != NULL); + + Pinfty = (x == NULL); + Pnorm = (z == NULL); + if (!Pnorm) + { + Pnorm = BN_is_one(z); + Pinfty = (Pinfty || BN_is_zero(z)); + } + + if (Pinfty) + { + if ((ret = ECP_new()) == NULL) return NULL; + if (!BN_zero(ret->Z)) + { + ECP_clear_free(ret); + return NULL; + } + return ret; + } + + X0 = BN_is_zero(x); + A0 = BN_is_zero(E->A); + + if ((ret = ECP_new()) == NULL) return NULL; + + ret->is_in_mont = 0; + + n0 = ctx->bn[ctx->tos]; + n1 = ctx->bn[ctx->tos + 1]; + if (!BN_zero(n0)) return NULL; + if (!BN_zero(n1)) return NULL; + + ctx->tos += 2; + + if (!X0) + { + if (!BN_mod_sqr(n0, x, E->p, ctx)) goto err; + if (!BN_mod_mul(n0, n0, x, E->p, ctx)) goto err; /* x^3 */ + } + + if (!X0 && !A0) + { + if (!BN_mod_mul(n1, E->A, x, E->p, ctx)) goto err; /* Ax */ + if (!BN_mod_add(n0, n0, n1, E->p, ctx)) goto err; /* x^3 + Ax */ + } + + if (!BN_is_zero(E->B)) + if (!BN_mod_add(n0, n0, E->B, E->p, ctx)) goto err; /* x^3 + Ax +B */ + + if (!BN_mod_sqrt(ret->Y, n0, E->p, ctx)) goto err; + if (BN_copy(ret->X, x) == NULL) goto err; + + if (Pnorm) + { + if (!BN_one(ret->Z)) goto err; + } + else + { + if (BN_copy(ret->Z, z) == NULL) goto err; + if (!BN_mod_sqr(n0, z, E->p, ctx)) goto err; + if (!BN_mod_mul(ret->X, ret->X, n0, E->p, ctx)) goto err; + if (!BN_mod_mul(n0, n0, z, E->p, ctx)) goto err; + if (!BN_mod_mul(ret->Y, ret->Y, n0, E->p, ctx)) goto err; + } + +#ifdef TEST + if (!ECP_is_on_ec(ret, E, ctx)) goto err; +#endif + + ctx->tos -= 2; + return ret; + +err: + if (ret != NULL) ECP_clear_free(ret); + ctx->tos -= 2; + return NULL; +} + +int ECP_ecp2bin(EC_POINT *P, unsigned char *to, int form) +/* form = 1 ... compressed + 2 ... uncompressed + 3 ... hybrid */ +{ + int bytes, bx, by; + + assert (P != NULL); + assert (P->X != NULL && P->Y != NULL && P->Z != NULL); + assert (!P->is_in_mont); + assert (ECP_is_norm(P) || ECP_is_infty(P)); + assert (to != NULL); + assert (form > 0 && form < 4); + + if (BN_is_zero(P->Z)) + { + to[0] = 0; + return 1; + } + + bx = BN_num_bytes(P->X); + if (form == 1 ) bytes = bx + 1; + else + { + by = BN_num_bytes(P->Y); + bytes = (bx > by ? bx : by); + bytes = bytes * 2 + 1; + } + memset(to, 0, bytes); + + switch (form) + { + case 1: to[0] = 2; break; + case 2: to[0] = 4; break; + case 3: to[0] = 6; break; + } + if (form != 2) to[0] += BN_is_bit_set(P->Y, 0); + + + if ((BN_bn2bin(P->X, to + 1)) != bx) return 0; + if (form != 1) + { + if ((BN_bn2bin(P->Y, to + bx + 1)) != by) return 0; + } + + return bytes; +} + +int ECP_bin2ecp(unsigned char *from, int len, EC_POINT *P, EC *E, BN_CTX *ctx) +{ + int y; + BIGNUM *x; + EC_POINT *pp; + + assert (E != NULL); + assert (E->A != NULL && E->B != NULL && E->p != NULL); + assert (!E->is_in_mont); + + assert (ctx != NULL); + assert (from != NULL); + assert (P != NULL); + assert (P->X != NULL && P->Y != NULL && P->Z != NULL); + + if (len == 1 && from[0] != 0) return 0; + + if (len == 0 || len == 1) + { + if (!BN_zero(P->Z)) return 0; + return 1; + } + + switch (from[0]) + { + case 2: + case 3: + y = from[0] - 2; + if ((x = BN_new()) == NULL) return 0; + if (BN_bin2bn(from + 1, len - 1, x) == NULL) return 0; + + pp = ECP_generate(x, NULL, E, ctx); + BN_clear_free(x); + if (pp == NULL) return 0; + + ECP_copy(P, pp); + ECP_clear_free(pp); + + if (BN_is_bit_set(P->Y, 0) != y) + if (!BN_sub(P->Y, E->p, P->Y)) return 0; + break; + + case 4: + case 6: + case 7: + y = (len - 1)/2; + if (BN_bin2bn(from + 1, y, P->X) == NULL) return 0; + if (BN_bin2bn(from + y + 1, y, P->Y) == NULL) return 0; + if (!BN_set_word(P->Z, 1)) return 0; + break; + + default: + assert(0); + + } + + if (!ECP_is_on_ec(P, E, ctx)) return 0; + return 1; +} + +int ECP_normalize(EC_POINT *P, EC *E, BN_CTX *ctx) +{ + BIGNUM *z, *zm; + + assert (P != NULL); + assert (P->X != NULL && P->Y != NULL && P->Z != NULL); + + assert (E != NULL); + assert (E->A != NULL && E->B != NULL && E->p != NULL); + + assert (ctx != NULL); + + 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; + + assert(!P->is_in_mont); + + + z = ctx->bn[ctx->tos]; + ctx->tos++; + + if (!BN_mod_mul(z, zm, zm, E->p, ctx)) goto err; + if (!BN_mod_mul(P->X, P->X, z, E->p, ctx)) goto err; + + if (!BN_mod_mul(z, z, zm, E->p, ctx)) goto err; + if (!BN_mod_mul(P->Y, P->Y, z, E->p, ctx)) goto err; + + if (!BN_one(P->Z)) goto err; + + if (zm != NULL) BN_clear_free(zm); + + ctx->tos--; + return 1; + +err: + if (zm != NULL) BN_clear_free(zm); + ctx->tos--; + return 0; +} + +int ECP_copy(EC_POINT *R, EC_POINT *P) +{ + assert(P != NULL); + assert(P->X != NULL && P->Y != NULL && P->Z != NULL); + + assert(R != NULL); + assert(R->X != NULL && R->Y != NULL && R->Z != NULL); + + if (BN_copy(R->X, P->X) == NULL) return 0; + if (BN_copy(R->Y, P->Y) == NULL) return 0; + if (BN_copy(R->Z, P->Z) == NULL) return 0; + R->is_in_mont = P->is_in_mont; + + return 1; +} + +EC_POINT *ECP_dup(EC_POINT *P) +{ + EC_POINT *ret; + + ret = ECP_new(); + if (ret == NULL) return NULL; + + if (!ECP_copy(ret, P)) + { + ECP_clear_free(ret); + return(NULL); + } + + return(ret); +} + + +EC_POINT *ECP_minus(EC_POINT *P, BIGNUM *p) /* mont || non-mont */ +{ + EC_POINT *ret; + + assert(P != NULL); + assert(P->X != NULL && P->Y != NULL && P->Z != NULL); + + assert(p != NULL); + + assert(BN_cmp(P->Y, p) < 0); + + ret = ECP_dup(P); + if (ret == NULL) return NULL; + + if (BN_is_zero(ret->Y)) return ret; + + if (!BN_sub(ret->Y, p, ret->Y)) + { + ECP_clear_free(ret); + return NULL; + } + + return ret; +} + + +#ifdef SIMPLE +int ECP_cmp(EC_POINT *P, EC_POINT *Q, BIGNUM *p, BN_CTX *ctx) +/* return values: + -2 ... error + 0 ... P = Q + -1 ... P = -Q + 1 ... else +*/ +{ + BIGNUM *n0, *n1, *n2, *n3, *n4; + int Pnorm, Qnorm; + + assert(P != NULL); + assert(P->X != NULL && P->Y != NULL && P->Z != NULL); + + assert(Q != NULL); + assert(Q->X != NULL && Q->Y != NULL && Q->Z != NULL); + + assert(p != NULL); + assert(ctx != NULL); + + assert(!P->is_in_mont); + assert(!Q->is_in_mont); + + if (ECP_is_infty(P) && ECP_is_infty(Q)) return 0; + if (ECP_is_infty(P) || ECP_is_infty(Q)) return 1; + + + Pnorm = (ECP_is_norm(P)); + Qnorm = (ECP_is_norm(Q)); + + n0 = ctx->bn[ctx->tos]; + n1 = ctx->bn[ctx->tos + 1]; + n2 = ctx->bn[ctx->tos + 2]; + n3 = ctx->bn[ctx->tos + 3]; + n4 = ctx->bn[ctx->tos + 4]; + ctx->tos += 5; + + if (Qnorm) + { + if (BN_copy(n1, P->X) == NULL) goto err; /* L1 = x_p */ + if (BN_copy(n2, P->Y) == NULL) goto err; /* L2 = y_p */ + } + else + { + if (!BN_sqr(n0, Q->Z, ctx)) goto err; + if (!BN_mod_mul(n1, P->X, n0, p, ctx)) goto err; /* L1 = x_p * z_q^2 */ + + if (!BN_mod_mul(n0, n0, Q->Z, p, ctx)) goto err; + if (!BN_mod_mul(n2, P->Y, n0, p, ctx)) goto err; /* L2 = y_p * z_q^3 */ + } + + if (Pnorm) + { + if (BN_copy(n3, Q->X) == NULL) goto err; /* L3 = x_q */ + if (BN_copy(n4, Q->Y) == NULL) goto err; /* L4 = y_q */ + } + else + { + if (!BN_sqr(n0, P->Z, ctx)) goto err; + if (!BN_mod_mul(n3, Q->X, n0, p, ctx)) goto err; /* L3 = x_q * z_p^2 */ + + if (!BN_mod_mul(n0, n0, P->Z, p, ctx)) goto err; + if (!BN_mod_mul(n4, Q->Y, n0, p, ctx)) goto err; /* L4 = y_q * z_p^3 */ + } + + if (!BN_mod_sub(n0, n1, n3, p, ctx)) goto err; /* L5 = L1 - L3 */ + + if (!BN_is_zero(n0)) + { + ctx->tos -= 5; + return 1; + } + + if (!BN_mod_sub(n0, n2, n4, p, ctx)) goto err; /* L6 = L2 - L4 */ + + if (!BN_is_zero(n0)) + { + ctx->tos -= 5; + return -1; + } + + ctx->tos -= 5; + return 0; + +err: + ctx->tos -= 5; + return -2; +} + +int ECP_double(EC_POINT *R, EC_POINT *P, EC *E, BN_CTX *ctx) +/* R <- 2P (on E) */ +{ + BIGNUM *n0, *n1, *n2, *n3, *p; + int Pnorm, A0; + + assert(P != NULL); + assert(P->X != NULL && P->Y != NULL && P->Z != NULL); + + assert(R != NULL); + assert(R->X != NULL && R->Y != NULL && R->Z != NULL); + + assert(E != NULL); + assert(E->A != NULL && E->B != NULL && E->p != NULL && E->h != NULL); + + assert(ctx != NULL); + + assert(!P->is_in_mont); + + if (ECP_is_infty(P)) + { + if (!BN_zero(R->Z)) return 0; + return 1; + } + + Pnorm = (ECP_is_norm(P)); + A0 = (BN_is_zero(E->A)); + + n0 = ctx->bn[ctx->tos]; + n1 = ctx->bn[ctx->tos + 1]; + n2 = ctx->bn[ctx->tos + 2]; + n3 = ctx->bn[ctx->tos + 3]; + ctx->tos += 4; + + p = E->p; + + /* L1 */ + if (Pnorm || A0) + { + if (!BN_mod_sqr(n1, P->X, p, ctx)) goto err; + if (!BN_mul_word(n1, 3)) goto err; + if (!A0) /* if A = 0: L1 = 3 * x^2 + a * z^4 = 3 * x ^2 */ + if (!BN_mod_add(n1, n1, E->A, p, ctx)) goto err; /* L1 = 3 * x^2 + a * z^4 = 3 * x^2 + a */ + } + else + { + if (!BN_mod_sqr(n0, P->Z, p, ctx)) goto err; + if (!BN_mod_mul(n0, n0, n0, p, ctx)) goto err; + if (!BN_mod_mul(n0, n0, E->A, p, ctx)) goto err; + if (!BN_mod_sqr(n1, P->X, p, ctx)) goto err; + if (!BN_mul_word(n1, 3)) goto err; + if (!BN_mod_add(n1, n1, n0, p, ctx)) goto err; /* L1 = 3 * x^2 + a * z^4 */ + } + + /* Z */ + if (Pnorm) + { + if (BN_copy(n0, P->Y) == NULL) goto err; + } + else + { + if (!BN_mod_mul(n0, P->Y, P->Z, p, ctx)) goto err; + } + if (!BN_lshift1(n0, n0)) goto err; + if (!BN_smod(R->Z, n0, p, ctx)) goto err; /* Z = 2 * y * z */ + + /* L2 */ + if (!BN_mod_sqr(n3, P->Y, p, ctx)) goto err; + if (!BN_mod_mul(n2, P->X, n3, p, ctx)) goto err; + if (!BN_lshift(n2, n2, 2)) goto err; + if (!BN_smod(n2, n2, p, ctx)) goto err; /* L2 = 4 * x * y^2 */ + + /* X */ + if (!BN_lshift1(n0, n2)) goto err; + if (!BN_mod_sqr(R->X, n1, p, ctx)) goto err; + if (!BN_mod_sub(R->X, R->X, n0, p, ctx)) goto err; /* X = L1^2 - 2 * L2 */ + + /* L3 */ + if (!BN_mod_sqr(n0, n3, p, ctx)) goto err; + if (!BN_lshift(n3, n0, 3)) goto err; + if (!BN_smod(n3, n3, p, ctx)) goto err; /* L3 = 8 * y^4 */ + + /* Y */ + if (!BN_mod_sub(n0, n2, R->X, p, ctx)) goto err; + if (!BN_mod_mul(n0, n1, n0, p, ctx)) goto err; + if (!BN_mod_sub(R->Y, n0, n3, p, ctx)) goto err; /* Y = L1 * (L2 - X) - L3 */ + + +#ifdef TEST + if (!ECP_is_on_ec(R, E, ctx)) return 0; +#endif + + ctx->tos -= 4; + return 1; + +err: + ctx->tos -= 4; + return 0; +} + +int ECP_add(EC_POINT *R, EC_POINT *P, EC_POINT *Q, EC *E, BN_CTX *ctx) +/* R <- P + Q (on E) */ +{ + BIGNUM *n0, *n1, *n2, *n3, *n4, *n5, *n6, *p; + int Pnorm, Qnorm; + + assert(P != NULL); + assert(P->X != NULL && P->Y != NULL && P->Z != NULL); + + assert(Q != NULL); + assert(Q->X != NULL && Q->Y != NULL && Q->Z != NULL); + + assert(R != NULL); + assert(R->X != NULL && R->Y != NULL && R->Z != NULL); + + assert(E != NULL); + assert(E->A != NULL && E->B != NULL && E->p != NULL && E->h != NULL); + assert(!BN_is_zero(E->h));; + + assert(ctx != NULL); + + assert(!P->is_in_mont); + assert(!Q->is_in_mont); + + if (P == Q) return ECP_double(R, P, E, ctx); + + if (ECP_is_infty(P)) return ECP_copy(R, Q); + if (ECP_is_infty(Q)) return ECP_copy(R, P); + + Pnorm = (ECP_is_norm(P)); + Qnorm = (ECP_is_norm(Q)); + + n0 = ctx->bn[ctx->tos]; + n1 = ctx->bn[ctx->tos + 1]; + n2 = ctx->bn[ctx->tos + 2]; + n3 = ctx->bn[ctx->tos + 3]; + n4 = ctx->bn[ctx->tos + 4]; + n5 = ctx->bn[ctx->tos + 5]; + n6 = ctx->bn[ctx->tos + 6]; + ctx->tos += 7; + p = E->p; + + /* L1; L2 */ + if (Qnorm) + { + if (BN_copy(n1, P->X) == NULL) goto err; /* L1 = x_p */ + if (BN_copy(n2, P->Y) == NULL) goto err; /* L2 = y_p */ + } + else + { + if (!BN_sqr(n0, Q->Z, ctx)) goto err; + if (!BN_mod_mul(n1, P->X, n0, p, ctx)) goto err; /* L1 = x_p * z_q^2 */ + + if (!BN_mod_mul(n0, n0, Q->Z, p, ctx)) goto err; + if (!BN_mod_mul(n2, P->Y, n0, p, ctx)) goto err; /* L2 = y_p * z_q^3 */ + } + + /* L3; L4 */ + if (Pnorm) + { + if (BN_copy(n3, Q->X) == NULL) goto err; /* L3 = x_q */ + if (BN_copy(n4, Q->Y) == NULL) goto err; /* L4 = y_q */ + } + else + { + if (!BN_sqr(n0, P->Z, ctx)) goto err; + if (!BN_mod_mul(n3, Q->X, n0, p, ctx)) goto err; /* L3 = x_q * z_p^2 */ + + if (!BN_mod_mul(n0, n0, P->Z, p, ctx)) goto err; + if (!BN_mod_mul(n4, Q->Y, n0, p, ctx)) goto err; /* L4 = y_q * z_p^3 */ + } + + /* L5; L6 */ + if (!BN_mod_sub(n5, n1, n3, p, ctx)) goto err; /* L5 = L1 - L3 */ + if (!BN_mod_sub(n6, n2, n4, p, ctx)) goto err; /* L6 = L2 - L4 */ + + /* pata */ + if (BN_is_zero(n5)) + { + if (BN_is_zero(n6)) /* P = Q => P + Q = 2P */ + { + ctx->tos -= 7; + return ECP_double(R, P, E, ctx); + } + else /* P = -Q => P + Q = \infty */ + { + ctx->tos -= 7; + if (!BN_zero(R->Z)) return 0; + return 1; + } + } + + /* L7; L8 */ + if (!BN_mod_add(n1, n1, n3, p, ctx)) goto err; /* L7 = L1 + L3 */ + if (!BN_mod_add(n2, n2, n4, p, ctx)) goto err; /* L8 = L2 + L4 */ + + /* Z */ + if (Pnorm) + { + if (BN_copy(n0, Q->Z) == NULL) goto err; + } + else + { + if (!BN_mod_mul(n0, P->Z, Q->Z, p, ctx)) goto err; + } + if (!BN_mod_mul(R->Z, n0, n5, p, ctx)) goto err; /* Z = z_p * z_q * L_5 */ + + /* X */ + if (!BN_mod_sqr(n0, n6, p, ctx)) goto err; + if (!BN_mod_sqr(n4, n5, p, ctx)) goto err; + if (!BN_mod_mul(n3, n1, n4, p, ctx)) goto err; + if (!BN_mod_sub(R->X, n0, n3, p, ctx)) goto err; /* X = L6^2 - L5^2 * L7 */ + + /* L9 */ + if (!BN_lshift1(n0, R->X)) goto err; + if (!BN_mod_sub(n0, n3, n0, p, ctx)) goto err; /* L9 = L5^2 * L7 - 2X */ + + /* Y */ + if (!BN_mod_mul(n0, n0, n6, p, ctx)) goto err; + if (!BN_mod_mul(n5, n4, n5, p, ctx)) goto err; + if (!BN_mod_mul(n1, n2, n5, p, ctx)) goto err; + if (!BN_mod_sub(n0, n0, n1, p, ctx)) goto err; + if (!BN_mod_mul(R->Y, n0, E->h, p, ctx)) goto err; /* Y = (L6 * L9 - L8 * L5^3) / 2 */ + + + +#ifdef TEST + if (!ECP_is_on_ec(R, E, ctx)) return 0; +#endif + + ctx->tos -= 7; + return 1; + +err: + ctx->tos -= 7; + return 0; +} + + +ECP_PRECOMPUTE *ECP_precompute(int r, EC_POINT *P, EC *E, BN_CTX *ctx) +{ + ECP_PRECOMPUTE *ret; + EC_POINT *P2; + int i, max; + + assert(r > 2); + assert(!P->is_in_mont); + assert(!E->is_in_mont); + + ret=(ECP_PRECOMPUTE *)malloc(sizeof(ECP_PRECOMPUTE)); + if (ret == NULL) return NULL; + + max = 1; + max <<= (r - 1); + + ret->r = 0; + + ret->Pi=(EC_POINT **)malloc(sizeof(EC_POINT *) * max); + if (ret->Pi == NULL) goto err; + + + /* P2 = [2]P */ + if ((P2 = ECP_new()) == NULL) goto err; + if (!ECP_double(P2, P, E, ctx)) goto err; + + /* P_0 = P */ + if((ret->Pi[0] = ECP_dup(P)) == NULL) goto err; + + + /* P_i = P_(i-1) + P2 */ + for (i = 1; i < max; i++) + { + if ((ret->Pi[i] = ECP_new()) == NULL) goto err; + + if (!ECP_add(ret->Pi[i], P2, ret->Pi[i - 1], E, ctx)) goto err; + } + + ret->r = r; + ECP_clear_free(P2); + + return ret; + +err: + ECP_clear_free(P2); + ECP_clear_free_precompute(ret); + return NULL; +} + +int ECP_multiply(EC_POINT *R, BIGNUM *k, ECP_PRECOMPUTE *prec, EC *E, BN_CTX *ctx) +/* R = [k]P */ +{ + int j; + int t, nextw, h, r; + + assert(R != NULL); + assert(R->X != NULL && R->Y != NULL && R->Z != NULL); + + assert(E != NULL); + assert(E->A != NULL && E->B != NULL && E->p != NULL && E->h != NULL); + + assert(k != NULL); + assert(!k->neg); + + assert(ctx != NULL); + assert(prec != NULL); + + assert(!E->is_in_mont); + + if (BN_is_zero(k)) + { + if (!BN_zero(R->Z)) return 0; + R->is_in_mont = 0; + return 1; + } + + + j = BN_num_bits(k); + j--; + + r = prec->r; + + if (!BN_zero(R->Z)) return 0; + R->is_in_mont = 0; + + while(j >= 0) + { + if (!BN_is_bit_set(k, j)) + { + if (!ECP_double(R, R, E, ctx)) return 0; + j--; + } + else + { + nextw = j - r; + if (nextw < -1) nextw = -1; + t = nextw + 1; + while(!BN_is_bit_set(k, t)) + { + t++; + } + + if (!ECP_double(R, R, E, ctx)) return 0; + + j--; + if (j < t) h = 0; + else + { + h = 1; + for(; j > t; j--) + { + h <<= 1; + if (BN_is_bit_set(k, j)) h++; + if (!ECP_double(R, R, E, ctx)) return 0; + } + if (!ECP_double(R, R, E, ctx)) return 0; + j--; + } + + if (!ECP_add(R, R, prec->Pi[h], E, ctx)) return 0; + + for (; j > nextw; j--) + { + if (!ECP_double(R, R, E, ctx)) return 0; + } + + } + } + + return 1; +} + +#endif /* SIMPLE */ + +#ifdef MONTGOMERY + +int ECP_to_montgomery(EC_POINT *P, BN_MONTGOMERY *mont, BN_CTX *ctx) +{ + + assert(P != NULL); + assert(P->X != NULL && P->Y != NULL && P->Z != NULL); + + assert(mont != NULL); + assert(mont->p != NULL); + + assert(ctx != NULL); + + if (P->is_in_mont) return 1; + + if (!BN_lshift(P->X, P->X, mont->R_num_bits)) return 0; + if (!BN_mod(P->X, P->X, mont->p, ctx)) return 0; + + if (!BN_lshift(P->Y, P->Y, mont->R_num_bits)) return 0; + if (!BN_mod(P->Y, P->Y, mont->p, ctx)) return 0; + + if (!BN_lshift(P->Z, P->Z, mont->R_num_bits)) return 0; + if (!BN_mod(P->Z, P->Z, mont->p, ctx)) return 0; + + P->is_in_mont = 1; + return 1; +} + + +int ECP_from_montgomery(EC_POINT *P, BN_MONTGOMERY *mont, BN_CTX *ctx) +{ + + assert(P != NULL); + assert(P->X != NULL && P->Y != NULL && P->Z != NULL); + + assert(mont != NULL); + assert(mont->p != NULL); + + assert(ctx != NULL); + + if (!P->is_in_mont) return 1; + + if (!BN_mont_red(P->X, mont, ctx)) return 0; + if (!BN_mont_red(P->Y, mont, ctx)) return 0; + if (!BN_mont_red(P->Z, mont, ctx)) return 0; + + P->is_in_mont = 0; + return 1; +} + +int ECP_mont_cmp(EC_POINT *P, EC_POINT *Q, BN_MONTGOMERY *mont, BN_CTX *ctx) +/* return values: + -2 ... error + 0 ... P = Q + -1 ... P = -Q + 1 ... else +*/ +{ + BIGNUM *n0, *n1, *n2, *n3, *n4, *n5, *p; + + assert(P != NULL); + assert(P->X != NULL && P->Y != NULL && P->Z != NULL); + + assert(Q != NULL); + assert(Q->X != NULL && Q->Y != NULL && Q->Z != NULL); + + assert(mont != NULL); + assert(mont->p != NULL); + + assert(ctx != NULL); + + if (!P->is_in_mont) + if (!ECP_to_montgomery(P, mont, ctx)) return 0; + + if (!Q->is_in_mont) + if (!ECP_to_montgomery(Q, mont, ctx)) return 0; + + + if (ECP_is_infty(P) && ECP_is_infty(Q)) return 0; + if (ECP_is_infty(P) || ECP_is_infty(Q)) return 1; + + + n0 = ctx->bn[ctx->tos]; + n1 = ctx->bn[ctx->tos + 1]; + n2 = ctx->bn[ctx->tos + 2]; + n3 = ctx->bn[ctx->tos + 3]; + n4 = ctx->bn[ctx->tos + 4]; + n5 = ctx->bn[ctx->tos + 5]; + ctx->tos += 6; + + p = mont->p; + + + if (!BN_mont_mod_mul(n5, Q->Z, Q->Z, mont, ctx)) goto err; + if (!BN_mont_mod_mul(n1, P->X, n5, mont, ctx)) goto err; /* L1 = x_p * z_q^2 */ + + if (!BN_mont_mod_mul(n0, n5, Q->Z, mont, ctx)) goto err; + if (!BN_mont_mod_mul(n2, P->Y, n0, mont, ctx)) goto err; /* L2 = y_p * z_q^3 */ + + if (!BN_mont_mod_mul(n5, P->Z, P->Z, mont, ctx)) goto err; + if (!BN_mont_mod_mul(n3, Q->X, n5, mont, ctx)) goto err; /* L3 = x_q * z_p^2 */ + + if (!BN_mont_mod_mul(n0, n5, P->Z, mont, ctx)) goto err; + 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_is_zero(n0)) + { + ctx->tos -= 6; + return 1; + } + + if (!BN_mont_mod_sub(n0, n2, n4, mont)) goto err; /* L6 = L2 - L4 */ + + if (!BN_is_zero(n0)) + { + ctx->tos -= 6; + return -1; + } + + ctx->tos -= 6; + return 0; + +err: + ctx->tos -= 6; + return -2; +} + + +int ECP_mont_double(EC_POINT *R, EC_POINT *P, EC *E, BN_MONTGOMERY *mont, BN_CTX *ctx) +/* R <- 2P (on E) */ +{ + BIGNUM *n0, *n1, *n2, *n3, *p; + + assert(P != NULL); + assert(P->X != NULL && P->Y != NULL && P->Z != NULL); + + assert(R != NULL); + assert(R->X != NULL && R->Y != NULL && R->Z != NULL); + + assert(E != NULL); + assert(E->A != NULL && E->B != NULL && E->p != NULL && E->h != NULL); + + assert(ctx != NULL); + + if (!P->is_in_mont) + if (!ECP_to_montgomery(P, mont, ctx)) return 0; + + if (!E->is_in_mont) + if (!EC_to_montgomery(E, mont, ctx)) return 0; + + R->is_in_mont = 1; + + if (ECP_is_infty(P)) + { + if (!BN_zero(R->Z)) return 0; + return 1; + } + + + n0 = ctx->bn[ctx->tos]; + n1 = ctx->bn[ctx->tos + 1]; + n2 = ctx->bn[ctx->tos + 2]; + n3 = ctx->bn[ctx->tos + 3]; + + ctx->tos += 4; + + p = E->p; + + /* L1 */ + if (!BN_mont_mod_mul(n0, P->Z, P->Z, mont, ctx)) goto err; + 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 */ + + /* 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 */ + + /* 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 */ + + /* X */ + if (!BN_mont_mod_lshift1(n0, n2, mont)) 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 */ + + /* 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 */ + + + /* Y */ + if (!BN_mont_mod_sub(n2, n2, R->X, mont)) 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 */ + + ctx->tos -= 4; + return 1; + +err: + ctx->tos -= 4; + return 0; +} + + +int ECP_mont_add(EC_POINT *R, EC_POINT *P, EC_POINT *Q, EC *E, BN_MONTGOMERY *mont, BN_CTX *ctx) +/* R <- P + Q (on E) */ +{ + BIGNUM *n0, *n1, *n2, *n3, *n4, *n5, *n6, *p; + + assert(P != NULL); + assert(P->X != NULL && P->Y != NULL && P->Z != NULL); + + assert(Q != NULL); + assert(Q->X != NULL && Q->Y != NULL && Q->Z != NULL); + + assert(R != NULL); + assert(R->X != NULL && R->Y != NULL && R->Z != NULL); + + assert(E != NULL); + assert(E->A != NULL && E->B != NULL && E->p != NULL && E->h != NULL); + assert(!BN_is_zero(E->h));; + + assert(ctx != NULL); + + if (!Q->is_in_mont) + if (!ECP_to_montgomery(Q, mont, ctx)) return 0; + + if (!P->is_in_mont) + if (!ECP_to_montgomery(P, mont, ctx)) return 0; + + if (!E->is_in_mont) + if (!EC_to_montgomery(E, mont, ctx)) return 0; + + if (P == Q) return ECP_mont_double(R, P, E, mont, ctx); + + if (ECP_is_infty(P)) return ECP_copy(R, Q); + if (ECP_is_infty(Q)) return ECP_copy(R, P); + + + n0 = ctx->bn[ctx->tos]; + n1 = ctx->bn[ctx->tos + 1]; + n2 = ctx->bn[ctx->tos + 2]; + n3 = ctx->bn[ctx->tos + 3]; + n4 = ctx->bn[ctx->tos + 4]; + n5 = ctx->bn[ctx->tos + 5]; + n6 = ctx->bn[ctx->tos + 6]; + ctx->tos += 7; + + + p = E->p; + + R->is_in_mont = 1; + + /* L1; L2 */ + if (!BN_mont_mod_mul(n6, Q->Z, Q->Z, mont, ctx)) goto err; + if (!BN_mont_mod_mul(n1, P->X, n6, mont, ctx)) goto err; /* L1 = x_p * z_q^2 */ + + if (!BN_mont_mod_mul(n0, n6, Q->Z, mont, ctx)) goto err; + if (!BN_mont_mod_mul(n2, P->Y, n0, mont, ctx)) goto err; /* L2 = y_p * z_q^3 */ + + + /* L3; L4 */ + if (!BN_mont_mod_mul(n6, P->Z, P->Z, mont, ctx)) goto err; + if (!BN_mont_mod_mul(n3, Q->X, n6, mont, ctx)) goto err; /* L3 = x_q * z_p^2 */ + + if (!BN_mont_mod_mul(n0, n6, P->Z, mont, ctx)) goto err; + if (!BN_mont_mod_mul(n4, Q->Y, n0, mont, ctx)) goto err; /* L4 = y_q * z_p^3 */ + + + /* 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 */ + + + /* pata */ + if (BN_is_zero(n5)) + { + if (BN_is_zero(n6)) /* P = Q => P + Q = 2P */ + { + ctx->tos -= 7; + return ECP_mont_double(R, P, E, mont, ctx); + } + else /* P = -Q => P + Q = \infty */ + { + ctx->tos -= 7; + if (!BN_zero(R->Z)) return 0; + return 1; + } + } + + /* 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 */ + + + /* Z */ + if (!BN_mont_mod_mul(n0, P->Z, Q->Z, mont, ctx)) goto err; + if (!BN_mont_mod_mul(R->Z, n0, n5, mont, ctx)) goto err; /* Z = z_p * z_q * L_5 */ + + + /* X */ + 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 */ + + + /* 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 */ + + + /* 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_mont_mod_mul(R->Y, n0, E->h, mont, ctx)) goto err; /* Y = (L6 * L9 - L8 * L5^3) / 2 */ + + + ctx->tos -= 7; + return 1; + +err: + ctx->tos -= 7; + return 0; +} + + +ECP_PRECOMPUTE *ECP_mont_precompute(int r, EC_POINT *P, EC *E, BN_MONTGOMERY *mont, BN_CTX *ctx) +{ + ECP_PRECOMPUTE *ret; + EC_POINT *P2; + int i, max; + + assert(r > 2); + assert(r < sizeof(unsigned int) * 8 - 1); + + assert(mont != NULL); + assert(mont->p != NULL); + + if (!P->is_in_mont) + if (!ECP_to_montgomery(P, mont, ctx)) return 0; + + if (!E->is_in_mont) + if (!EC_to_montgomery(E, mont, ctx)) return 0; + + ret=(ECP_PRECOMPUTE *)malloc(sizeof(ECP_PRECOMPUTE)); + if (ret == NULL) return NULL; + + max = 1; + max <<= (r - 1); + + ret->r = 0; + + ret->Pi=(EC_POINT **)malloc(sizeof(EC_POINT *) * max); + if (ret->Pi == NULL) goto err; + + + /* P2 = [2]P */ + if ((P2 = ECP_new()) == NULL) goto err; + if (!ECP_mont_double(P2, P, E, mont, ctx)) goto err; + + /* P_0 = P */ + if((ret->Pi[0] = ECP_dup(P)) == NULL) goto err; + + + /* P_i = P_(i-1) + P2 */ + for (i = 1; i < max; i++) + { + if ((ret->Pi[i] = ECP_new()) == NULL) goto err; + if (!ECP_mont_add(ret->Pi[i], P2, ret->Pi[i - 1], E, mont, ctx)) goto err; + } + + ret->r = r; + ECP_clear_free(P2); + + return ret; + +err: + ECP_clear_free(P2); + ECP_clear_free_precompute(ret); + return NULL; +} + +int ECP_mont_multiply(EC_POINT *R, BIGNUM *k, ECP_PRECOMPUTE *prec, EC *E, BN_MONTGOMERY *mont, BN_CTX *ctx) +/* R = [k]P P = prec->Pi[0]*/ +{ + int j; + int t, nextw, h, r; + + assert(R != NULL); + assert(R->X != NULL && R->Y != NULL && R->Z != NULL); + + assert(E != NULL); + assert(E->A != NULL && E->B != NULL && E->p != NULL && E->h != NULL); + + assert(k != NULL); + assert(!k->neg); + + assert(ctx != NULL); + assert(prec != NULL); + + assert(mont != NULL); + assert(mont->p != NULL); + + if (!E->is_in_mont) + if (!EC_to_montgomery(E, mont, ctx)) return 0; + + + if (BN_is_zero(k)) + { + if (!BN_zero(R->Z)) return 0; + R->is_in_mont = 1; + return 1; + } + + j = BN_num_bits(k); + j--; + + r = prec->r; + + if (!BN_zero(R->Z)) return 0; + R->is_in_mont = 1; + + while(j >= 0) + { + if (!BN_is_bit_set(k, j)) + { + if (!ECP_mont_double(R, R, E, mont, ctx)) return 0; + j--; + } + else + { + nextw = j - r; + if (nextw < -1) nextw = -1; + t = nextw + 1; + while(!BN_is_bit_set(k, t)) + { + t++; + } + + if (!ECP_mont_double(R, R, E, mont, ctx)) return 0; + + j--; + if (j < t) h = 0; + else + { + h = 1; + for(; j > t; j--) + { + h <<= 1; + if (BN_is_bit_set(k, j)) h++; + if (!ECP_mont_double(R, R, E, mont, ctx)) return 0; + } + if (!ECP_mont_double(R, R, E, mont, ctx)) return 0; + j--; + } + + if (!ECP_mont_add(R, R, prec->Pi[h], E, mont, ctx)) return 0; + + for (; j > nextw; j--) + { + if (!ECP_mont_double(R, R, E, mont, ctx)) return 0; + } + + } + } + + return 1; +} + + +int ECP_mont_multiply2(EC_POINT *R, BIGNUM *k, EC_POINT *P, EC *E, BN_MONTGOMERY *mont, BN_CTX *ctx) +/* R = [k]P */ +{ + int j, hj, kj; + BIGNUM *h; + EC_POINT *mP; + + assert(R != NULL); + assert(R->X != NULL && R->Y != NULL && R->Z != NULL); + + assert(P != NULL); + assert(P->X != NULL && P->Y != NULL && P->Z != NULL); + + assert(E != NULL); + assert(E->A != NULL && E->B != NULL && E->p != NULL && E->h != NULL); + + assert(k != NULL); + assert(!k->neg); + + assert(ctx != NULL); + + assert(mont != NULL); + assert(mont->p != NULL); + + if (!E->is_in_mont) + if (!EC_to_montgomery(E, mont, ctx)) return 0; + + if (!P->is_in_mont) + if (!ECP_to_montgomery(P, mont, ctx)) return 0; + + + if (BN_is_zero(k)) + { + if (!BN_zero(R->Z)) return 0; + R->is_in_mont = 1; + return 1; + } + + if ((h = BN_dup(k)) == NULL) return 0; + + if (!BN_lshift1(h, h)) goto err; + if (!BN_add(h, h, k)) goto err; + + if (!ECP_copy(R, P)) goto err; + if ((mP = ECP_mont_minus(P, mont)) == NULL) goto err; + + for(j = BN_num_bits(h) - 2; j > 0; j--) + { + if (!ECP_mont_double(R, R, E, mont, ctx)) goto err; + kj = BN_is_bit_set(k, j); + hj = BN_is_bit_set(h, j); + if (hj == 1 && kj == 0) + if (!ECP_mont_add(R, R, P, E, mont, ctx)) goto err; + if (hj == 0 && kj == 1) + if (!ECP_mont_add(R, R, mP, E, mont, ctx)) goto err; + } + + if (h != NULL) BN_free(h); + if (mP != NULL) ECP_clear_free(mP); + return 1; + +err: + if (h != NULL) BN_free(h); + if (mP != NULL) ECP_clear_free(mP); + return 0; +} + +#endif /* MONTGOMERY */ -- 2.25.1