From 786e0c2424bcc315d17ff71c454d8f73b1533e49 Mon Sep 17 00:00:00 2001 From: =?utf8?q?Bodo=20M=C3=B6ller?= Date: Sat, 3 Mar 2001 15:31:34 +0000 Subject: [PATCH] EC_set_half and the 'h' component of struct bn_ec_struct are unnecessary. The computations for which h was used can be done more efficiently by using BN_rshift1. --- crypto/ec/ec.c | 27 +++------------------------ crypto/ec/ec.h | 3 +-- crypto/ec/ec_point.c | 31 ++++++++++++++++--------------- 3 files changed, 20 insertions(+), 41 deletions(-) diff --git a/crypto/ec/ec.c b/crypto/ec/ec.c index df54b47c0b..c7a1bb013c 100644 --- a/crypto/ec/ec.c +++ b/crypto/ec/ec.c @@ -27,15 +27,13 @@ EC *EC_new() 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 || ret->B == NULL || ret->p == 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); } @@ -50,7 +48,6 @@ void EC_clear_free(EC *E) 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); } @@ -60,7 +57,7 @@ void EC_clear_free(EC *E) 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(E->A != NULL && E->B != NULL && E->p != NULL); assert(mont != NULL); assert(mont->p != NULL); @@ -75,9 +72,6 @@ int EC_to_montgomery(EC *E, BN_MONTGOMERY *mont, BN_CTX *ctx) 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; @@ -87,7 +81,7 @@ int EC_to_montgomery(EC *E, BN_MONTGOMERY *mont, BN_CTX *ctx) 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(E->A != NULL && E->B != NULL && E->p != NULL); assert(mont != NULL); assert(mont->p != NULL); @@ -98,23 +92,8 @@ int EC_from_montgomery(EC *E, BN_MONTGOMERY *mont, BN_CTX *ctx) if (!BN_mont_red(E->A, mont)) return 0; if (!BN_mont_red(E->B, mont)) return 0; - if (!BN_mont_red(E->h, mont)) 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 index dd7a4b892f..eb1ce0c494 100644 --- a/crypto/ec/ec.h +++ b/crypto/ec/ec.h @@ -19,7 +19,7 @@ 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 */ + BIGNUM *A, *B, *p; int is_in_mont; } EC; @@ -44,7 +44,6 @@ typedef struct bn_ecp_precompute_struct /* Pi[i] = [2i + 1]P i = 0..2^{r-1} - 1 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); diff --git a/crypto/ec/ec_point.c b/crypto/ec/ec_point.c index 5dd2da3b11..11c4aac332 100644 --- a/crypto/ec/ec_point.c +++ b/crypto/ec/ec_point.c @@ -157,7 +157,7 @@ EC_POINT *ECP_generate(BIGNUM *x, BIGNUM *z,EC *E, BN_CTX *ctx) int Pnorm, Pinfty, X0, A0; assert(E != NULL); - assert(E->A != NULL && E->B != NULL && E->p != NULL && E->h != NULL); + assert(E->A != NULL && E->B != NULL && E->p != NULL); assert(ctx != NULL); @@ -559,7 +559,7 @@ int ECP_double(EC_POINT *R, EC_POINT *P, EC *E, BN_CTX *ctx) 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(E->A != NULL && E->B != NULL && E->p != NULL); assert(ctx != NULL); @@ -664,8 +664,7 @@ int ECP_add(EC_POINT *R, EC_POINT *P, EC_POINT *Q, EC *E, BN_CTX *ctx) 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(E->A != NULL && E->B != NULL && E->p != NULL); assert(ctx != NULL); @@ -772,9 +771,10 @@ int ECP_add(EC_POINT *R, EC_POINT *P, EC_POINT *Q, EC *E, BN_CTX *ctx) 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 */ - - + if (BN_is_odd(n0)) + if (!BN_add(n0, n0, p)) goto err; + /* now 0 <= n0 < 2*p, and n0 is even */ + if (!BN_rshift1(R->Y, n0)) goto err; /* Y = (L6 * L9 - L8 * L5^3) / 2 */ #ifdef TEST if (!ECP_is_on_ec(R, E, ctx)) return 0; @@ -849,7 +849,7 @@ int ECP_multiply(EC_POINT *R, BIGNUM *k, ECP_PRECOMPUTE *prec, EC *E, BN_CTX *ct 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(E->A != NULL && E->B != NULL && E->p != NULL); assert(k != NULL); assert(!k->neg); @@ -1068,7 +1068,7 @@ int ECP_mont_double(EC_POINT *R, EC_POINT *P, EC *E, BN_MONTGOMERY *mont, BN_CTX 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(E->A != NULL && E->B != NULL && E->p != NULL); assert(ctx != NULL); @@ -1153,8 +1153,7 @@ int ECP_mont_add(EC_POINT *R, EC_POINT *P, EC_POINT *Q, EC *E, BN_MONTGOMERY *mo 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(E->A != NULL && E->B != NULL && E->p != NULL); assert(ctx != NULL); @@ -1252,8 +1251,10 @@ int ECP_mont_add(EC_POINT *R, EC_POINT *P, EC_POINT *Q, EC *E, BN_MONTGOMERY *mo if (!BN_mont_mod_mul(n6, n4, n5, mont)) goto err; if (!BN_mont_mod_mul(n1, n2, n6, mont)) goto err; if (!BN_mod_sub_quick(n0, n0, n1, p)) goto err; - if (!BN_mont_mod_mul(R->Y, n0, E->h, mont)) goto err; /* Y = (L6 * L9 - L8 * L5^3) / 2 */ - + if (BN_is_odd(n0)) + if (!BN_add(n0, n0, p)) goto err; + /* now 0 <= n0 < 2*p, and n0 is even */ + if (!BN_rshift1(R->Y, n0)) goto err; /* Y = (L6 * L9 - L8 * L5^3) / 2 */ BN_CTX_end(ctx); return 1; @@ -1331,7 +1332,7 @@ int ECP_mont_multiply(EC_POINT *R, BIGNUM *k, ECP_PRECOMPUTE *prec, EC *E, BN_MO 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(E->A != NULL && E->B != NULL && E->p != NULL); assert(k != NULL); assert(!k->neg); @@ -1421,7 +1422,7 @@ int ECP_mont_multiply2(EC_POINT *R, BIGNUM *k, EC_POINT *P, EC *E, BN_MONTGOMERY 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(E->A != NULL && E->B != NULL && E->p != NULL); assert(k != NULL); assert(!k->neg); -- 2.25.1