diff options
author | Bodo Möller <bodo@openssl.org> | 2002-08-02 14:57:53 +0000 |
---|---|---|
committer | Bodo Möller <bodo@openssl.org> | 2002-08-02 14:57:53 +0000 |
commit | 6fb60a84dd1ec81953917e0444dab50186617432 (patch) | |
tree | e3233b3c996e8e038c7bb5c2191484b03dbf5fed /crypto | |
parent | 5af7d1a3b8d3cfed3494460e20ad257dab4e4a0c (diff) |
Change BN_mod_sqrt() so that it verifies that the input value is
really the square of the return value.
Diffstat (limited to 'crypto')
-rw-r--r-- | crypto/bn/bn_sqrt.c | 49 | ||||
-rw-r--r-- | crypto/ec/ecp_smpl.c | 3 |
2 files changed, 32 insertions, 20 deletions
diff --git a/crypto/bn/bn_sqrt.c b/crypto/bn/bn_sqrt.c index e2a1105dc8..52dbc68a13 100644 --- a/crypto/bn/bn_sqrt.c +++ b/crypto/bn/bn_sqrt.c @@ -72,7 +72,7 @@ BIGNUM *BN_mod_sqrt(BIGNUM *in, const BIGNUM *a, const BIGNUM *p, BN_CTX *ctx) BIGNUM *ret = in; int err = 1; int r; - BIGNUM *b, *q, *t, *x, *y; + BIGNUM *A, *b, *q, *t, *x, *y; int e, i, j; if (!BN_is_odd(p) || BN_abs_is_word(p, 1)) @@ -120,6 +120,7 @@ BIGNUM *BN_mod_sqrt(BIGNUM *in, const BIGNUM *a, const BIGNUM *p, BN_CTX *ctx) #endif BN_CTX_start(ctx); + A = BN_CTX_get(ctx); b = BN_CTX_get(ctx); q = BN_CTX_get(ctx); t = BN_CTX_get(ctx); @@ -131,6 +132,9 @@ BIGNUM *BN_mod_sqrt(BIGNUM *in, const BIGNUM *a, const BIGNUM *p, BN_CTX *ctx) ret = BN_new(); if (ret == NULL) goto end; + /* A = a mod p */ + if (!BN_nnmod(A, a, p, ctx)) goto end; + /* now write |p| - 1 as 2^e*q where q is odd */ e = 1; while (!BN_is_bit_set(p, e)) @@ -149,9 +153,9 @@ BIGNUM *BN_mod_sqrt(BIGNUM *in, const BIGNUM *a, const BIGNUM *p, BN_CTX *ctx) if (!BN_rshift(q, p, 2)) goto end; q->neg = 0; if (!BN_add_word(q, 1)) goto end; - if (!BN_mod_exp(ret, a, q, p, ctx)) goto end; + if (!BN_mod_exp(ret, A, q, p, ctx)) goto end; err = 0; - goto end; + goto vrfy; } if (e == 2) @@ -182,15 +186,8 @@ BIGNUM *BN_mod_sqrt(BIGNUM *in, const BIGNUM *a, const BIGNUM *p, BN_CTX *ctx) * November 1992.) */ - /* make sure that a is reduced modulo p */ - if (a->neg || BN_ucmp(a, p) >= 0) - { - if (!BN_nnmod(x, a, p, ctx)) goto end; - a = x; /* use x as temporary variable */ - } - /* t := 2*a */ - if (!BN_mod_lshift1_quick(t, a, p)) goto end; + if (!BN_mod_lshift1_quick(t, A, p)) goto end; /* b := (2*a)^((|p|-5)/8) */ if (!BN_rshift(q, p, 3)) goto end; @@ -205,12 +202,12 @@ BIGNUM *BN_mod_sqrt(BIGNUM *in, const BIGNUM *a, const BIGNUM *p, BN_CTX *ctx) if (!BN_sub_word(t, 1)) goto end; /* x = a*b*t */ - if (!BN_mod_mul(x, a, b, p, ctx)) goto end; + if (!BN_mod_mul(x, A, b, p, ctx)) goto end; if (!BN_mod_mul(x, x, t, p, ctx)) goto end; if (!BN_copy(ret, x)) goto end; err = 0; - goto end; + goto vrfy; } /* e > 2, so we really have to use the Tonelli/Shanks algorithm. @@ -297,7 +294,7 @@ BIGNUM *BN_mod_sqrt(BIGNUM *in, const BIGNUM *a, const BIGNUM *p, BN_CTX *ctx) /* x := a^((q-1)/2) */ if (BN_is_zero(t)) /* special case: p = 2^e + 1 */ { - if (!BN_nnmod(t, a, p, ctx)) goto end; + if (!BN_nnmod(t, A, p, ctx)) goto end; if (BN_is_zero(t)) { /* special case: a == 0 (mod p) */ @@ -310,7 +307,7 @@ BIGNUM *BN_mod_sqrt(BIGNUM *in, const BIGNUM *a, const BIGNUM *p, BN_CTX *ctx) } else { - if (!BN_mod_exp(x, a, t, p, ctx)) goto end; + if (!BN_mod_exp(x, A, t, p, ctx)) goto end; if (BN_is_zero(x)) { /* special case: a == 0 (mod p) */ @@ -322,10 +319,10 @@ BIGNUM *BN_mod_sqrt(BIGNUM *in, const BIGNUM *a, const BIGNUM *p, BN_CTX *ctx) /* b := a*x^2 (= a^q) */ if (!BN_mod_sqr(b, x, p, ctx)) goto end; - if (!BN_mod_mul(b, b, a, p, ctx)) goto end; + if (!BN_mod_mul(b, b, A, p, ctx)) goto end; /* x := a*x (= a^((q+1)/2)) */ - if (!BN_mod_mul(x, x, a, p, ctx)) goto end; + if (!BN_mod_mul(x, x, A, p, ctx)) goto end; while (1) { @@ -342,7 +339,7 @@ BIGNUM *BN_mod_sqrt(BIGNUM *in, const BIGNUM *a, const BIGNUM *p, BN_CTX *ctx) { if (!BN_copy(ret, x)) goto end; err = 0; - goto end; + goto vrfy; } @@ -373,6 +370,22 @@ BIGNUM *BN_mod_sqrt(BIGNUM *in, const BIGNUM *a, const BIGNUM *p, BN_CTX *ctx) e = i; } + vrfy: + if (!err) + { + /* verify the result -- the input might have been not a square + * (test added in 0.9.8) */ + + if (!BN_mod_sqr(x, ret, p, ctx)) + err = 1; + + if (!err && 0 != BN_cmp(x, A)) + { + BNerr(BN_F_BN_MOD_SQRT, BN_R_NOT_A_SQUARE); + err = 1; + } + } + end: if (err) { diff --git a/crypto/ec/ecp_smpl.c b/crypto/ec/ecp_smpl.c index 70fed912a2..97ff8eb61a 100644 --- a/crypto/ec/ecp_smpl.c +++ b/crypto/ec/ecp_smpl.c @@ -705,8 +705,6 @@ int ec_GFp_simple_set_compressed_coordinates(const EC_GROUP *group, EC_POINT *po ECerr(EC_F_EC_GFP_SIMPLE_SET_COMPRESSED_COORDINATES, ERR_R_BN_LIB); goto err; } - /* If tmp1 is not a square (i.e. there is no point on the curve with - * our x), then y now is a nonsense value too */ if (y_bit != BN_is_odd(y)) { @@ -720,6 +718,7 @@ int ec_GFp_simple_set_compressed_coordinates(const EC_GROUP *group, EC_POINT *po if (kron == 1) ECerr(EC_F_EC_GFP_SIMPLE_SET_COMPRESSED_COORDINATES, EC_R_INVALID_COMPRESSION_BIT); else + /* BN_mod_sqrt() should have cought this error (not a square) */ ECerr(EC_F_EC_GFP_SIMPLE_SET_COMPRESSED_COORDINATES, EC_R_INVALID_COMPRESSED_POINT); goto err; } |