diff options
author | Niels Möller <nisse@lysator.liu.se> | 2014-08-28 11:25:48 +0200 |
---|---|---|
committer | Niels Möller <nisse@lysator.liu.se> | 2014-08-28 11:25:48 +0200 |
commit | 91784d65b7cd71a4128ee6d74043178f3aa2d09f (patch) | |
tree | 4b26e8fc37643f0f7c38bfd9a22433da947d55ca | |
parent | a67a7286c9ea748652d463160a5f863de10ae644 (diff) | |
download | nettle-91784d65b7cd71a4128ee6d74043178f3aa2d09f.tar.gz |
ecc_j_to_a interface change, optionally reduce x mod q.
-rw-r--r-- | ChangeLog | 10 | ||||
-rw-r--r-- | ecc-ecdsa-sign.c | 9 | ||||
-rw-r--r-- | ecc-ecdsa-verify.c | 6 | ||||
-rw-r--r-- | ecc-j-to-a.c | 34 | ||||
-rw-r--r-- | ecc-point-mul-g.c | 2 | ||||
-rw-r--r-- | ecc-point-mul.c | 2 | ||||
-rw-r--r-- | ecc.h | 21 | ||||
-rw-r--r-- | ecdsa-keygen.c | 2 | ||||
-rw-r--r-- | testsuite/ecc-mul-a-test.c | 8 | ||||
-rw-r--r-- | testsuite/ecc-mul-g-test.c | 4 | ||||
-rw-r--r-- | testsuite/testutils.c | 2 |
11 files changed, 55 insertions, 45 deletions
@@ -1,5 +1,15 @@ 2014-08-28 Niels Möller <nisse@lysator.liu.se> + * ecc-j-to-a.c (ecc_j_to_a): For curves using redc, always convert + back from redc form. When producing x coordiante only optionally + reduce it modulo q. Completely changes the meaning of the "flags" + argument, and renames it to "op". Update all users of this + function or ecc->h_to_a. + + * ecc-ecdsa-sign.c (ecc_ecdsa_sign): Use new ecc_j_to_a modulo q + feature. + * ecc-ecdsa-verify.c (ecc_ecdsa_verify): Likewise. + * testsuite/symbols-test: Regexp fixes, to better filter out get_pc_thunk functions. diff --git a/ecc-ecdsa-sign.c b/ecc-ecdsa-sign.c index 19f4338c..4e0fbafc 100644 --- a/ecc-ecdsa-sign.c +++ b/ecc-ecdsa-sign.c @@ -79,13 +79,8 @@ ecc_ecdsa_sign (const struct ecc_curve *ecc, */ ecc_mul_g (ecc, P, kp, P + 3*ecc->size); - /* x coordinate only */ - ecc_j_to_a (ecc, 3, rp, P, P + 3*ecc->size); - - /* We need to reduce x coordinate mod ecc->q. It should already - be < 2*ecc->q, so one subtraction should suffice. */ - cy = mpn_sub_n (scratch, rp, ecc->q, ecc->size); - cnd_copy (cy == 0, rp, scratch, ecc->size); + /* x coordinate only, modulo q */ + ecc_j_to_a (ecc, 2, rp, P, P + 3*ecc->size); /* Invert k, uses 5 * ecc->size including scratch */ mpn_copyi (hp, kp, ecc->size); diff --git a/ecc-ecdsa-verify.c b/ecc-ecdsa-verify.c index 1310b312..797e73cd 100644 --- a/ecc-ecdsa-verify.c +++ b/ecc-ecdsa-verify.c @@ -144,10 +144,8 @@ ecc_ecdsa_verify (const struct ecc_curve *ecc, /* Total storage: 6*ecc->size + ECC_ADD_JJJ_ITCH (ecc->size) */ ecc_add_jjj (ecc, P1, P1, P2, u1); } - ecc_j_to_a (ecc, 3, P2, P1, u1); - - if (mpn_cmp (P2, ecc->q, ecc->size) >= 0) - mpn_sub_n (P2, P2, ecc->q, ecc->size); + /* x coordinate only, modulo q */ + ecc_j_to_a (ecc, 2, P2, P1, u1); return (mpn_cmp (rp, P2, ecc->size) == 0); #undef P2 diff --git a/ecc-j-to-a.c b/ecc-j-to-a.c index 0c0c8485..e945929d 100644 --- a/ecc-j-to-a.c +++ b/ecc-j-to-a.c @@ -47,7 +47,7 @@ ecc_j_to_a_itch (const struct ecc_curve *ecc) void ecc_j_to_a (const struct ecc_curve *ecc, - int flags, + int op, mp_limb_t *r, const mp_limb_t *p, mp_limb_t *scratch) { @@ -79,17 +79,12 @@ ecc_j_to_a (const struct ecc_curve *ecc, ecc_modp_inv (ecc, izp, up, up + ecc->size); - if (flags & 1) - { - /* Divide this common factor by B */ - mpn_copyi (izBp, izp, ecc->size); - mpn_zero (izBp + ecc->size, ecc->size); - ecc->redc (ecc, izBp); + /* Divide this common factor by B */ + mpn_copyi (izBp, izp, ecc->size); + mpn_zero (izBp + ecc->size, ecc->size); + ecc->redc (ecc, izBp); - ecc_modp_mul (ecc, iz2p, izp, izBp); - } - else - ecc_modp_sqr (ecc, iz2p, izp); + ecc_modp_mul (ecc, iz2p, izp, izBp); } else { @@ -107,10 +102,19 @@ ecc_j_to_a (const struct ecc_curve *ecc, cy = mpn_sub_n (r, iz3p, ecc->p, ecc->size); cnd_copy (cy, r, iz3p, ecc->size); - if (flags & 2) - /* Skip y coordinate */ - return; - + if (op) + { + /* Skip y coordinate */ + if (op > 1) + { + /* Also reduce the x coordinate mod ecc->q. It should + already be < 2*ecc->q, so one subtraction should + suffice. */ + cy = mpn_sub_n (scratch, r, ecc->q, ecc->size); + cnd_copy (cy == 0, r, scratch, ecc->size); + } + return; + } ecc_modp_mul (ecc, iz3p, iz2p, izp); ecc_modp_mul (ecc, tp, iz3p, p + ecc->size); /* And a similar subtraction. */ diff --git a/ecc-point-mul-g.c b/ecc-point-mul-g.c index bb9a2d76..7485fa2c 100644 --- a/ecc-point-mul-g.c +++ b/ecc-point-mul-g.c @@ -54,5 +54,5 @@ ecc_point_mul_g (struct ecc_point *r, const struct ecc_scalar *n) TMP_ALLOC (scratch, itch); ecc->mul_g (ecc, scratch, n->p, scratch + 3*size); - ecc->h_to_a (ecc, 1, r->p, scratch, scratch + 3*size); + ecc->h_to_a (ecc, 0, r->p, scratch, scratch + 3*size); } diff --git a/ecc-point-mul.c b/ecc-point-mul.c index 2080b608..d2ba9e83 100644 --- a/ecc-point-mul.c +++ b/ecc-point-mul.c @@ -53,6 +53,6 @@ ecc_point_mul (struct ecc_point *r, const struct ecc_scalar *n, assert (p->ecc == ecc); ecc->mul (ecc, scratch, n->p, p->p, scratch + 3*size); - ecc->h_to_a (ecc, 1, r->p, scratch, scratch + 3*size); + ecc->h_to_a (ecc, 0, r->p, scratch, scratch + 3*size); gmp_free_limbs (scratch, itch); } @@ -146,11 +146,13 @@ ecc_point_mul_g (struct ecc_point *r, const struct ecc_scalar *n); /* Low-level interface */ -/* Points on a curve are represented as arrays of mp_limb_t. For some - curves, point coordinates are represented in montgomery form. We - use either affine coordinates x,y, or Jacobian coordinates X, Y, Z, - where x = X/Z^2 and y = X/Z^2. - +/* Points on a curve are represented as arrays of mp_limb_t, with + curve-specific representation. For the secp curves, we use Jacobian + coordinates (possibly in Montgomery for for mod multiplication). + For curve25519 we use homogeneous coordiantes on an equivalent + Edwards curve. The suffix "_h" denotes this internal + representation. + Since we use additive notation for the groups, the infinity point on the curve is denoted 0. The infinity point can be represented with x = y = 0 in affine coordinates, and Z = 0 in Jacobian @@ -185,14 +187,15 @@ ecc_a_to_j (const struct ecc_curve *ecc, mp_limb_t *r, const mp_limb_t *p); /* Converts a point P in jacobian coordinates into a point R in affine - coordinates. If FLAGS has bit 0 set, and the curve uses montgomery - coordinates, also undo the montgomery conversion. If flags has bit - 1 set, produce x coordinate only. */ + coordinates. If op == 1, produce x coordinate only. If op == 2, + produce the x coordiante only, and in also it modulo q. FIXME: For + the public interface, have separate for the three cases, and use + this flag argument only for the internal ecc->h_to_a function. */ mp_size_t ecc_j_to_a_itch (const struct ecc_curve *ecc); void ecc_j_to_a (const struct ecc_curve *ecc, - int flags, + int op, mp_limb_t *r, const mp_limb_t *p, mp_limb_t *scratch); diff --git a/ecdsa-keygen.c b/ecdsa-keygen.c index 613393db..d9f12405 100644 --- a/ecdsa-keygen.c +++ b/ecdsa-keygen.c @@ -56,5 +56,5 @@ ecdsa_generate_keypair (struct ecc_point *pub, ecc_modq_random (key->ecc, key->p, random_ctx, random, p); ecc_mul_g (pub->ecc, p, key->p, p + 3*pub->ecc->size); - ecc_j_to_a (pub->ecc, 1, pub->p, p, p + 3*pub->ecc->size); + ecc_j_to_a (pub->ecc, 0, pub->p, p, p + 3*pub->ecc->size); } diff --git a/testsuite/ecc-mul-a-test.c b/testsuite/ecc-mul-a-test.c index e182aacc..54421704 100644 --- a/testsuite/ecc-mul-a-test.c +++ b/testsuite/ecc-mul-a-test.c @@ -32,7 +32,7 @@ test_main (void) n[0] = 1; ecc_mul_a (ecc, p, n, ecc->g, scratch); - ecc_j_to_a (ecc, 1, p, p, scratch); + ecc_j_to_a (ecc, 0, p, p, scratch); if (mpn_cmp (p, ecc->g, 2*size != 0)) die ("curve %d: ecc_mul_a with n = 1 failed.\n", ecc->bit_size); @@ -46,7 +46,7 @@ test_main (void) /* (order - 1) * g = - g */ mpn_sub_1 (n, ecc->q, size, 1); ecc_mul_a (ecc, p, n, ecc->g, scratch); - ecc_j_to_a (ecc, 1, p, p, scratch); + ecc_j_to_a (ecc, 0, p, p, scratch); mpn_sub_n (p + size, ecc->p, p + size, size); if (mpn_cmp (p, ecc->g, 2*size) != 0) { @@ -68,10 +68,10 @@ test_main (void) n[size - 1] %= ecc->q[size - 1]; ecc_mul_a (ecc, p, n, ecc->g, scratch); - ecc_j_to_a (ecc, 1, p, p, scratch); + ecc_j_to_a (ecc, 0, p, p, scratch); ecc_mul_g (ecc, q, n, scratch); - ecc_j_to_a (ecc, 1, q, q, scratch); + ecc_j_to_a (ecc, 0, q, q, scratch); if (mpn_cmp (p, q, 2*size)) { diff --git a/testsuite/ecc-mul-g-test.c b/testsuite/ecc-mul-g-test.c index 9db5b9ef..2f5a9e79 100644 --- a/testsuite/ecc-mul-g-test.c +++ b/testsuite/ecc-mul-g-test.c @@ -31,7 +31,7 @@ test_main (void) n[0] = 1; ecc_mul_g (ecc, p, n, scratch); - ecc_j_to_a (ecc, 1, p, p, scratch); + ecc_j_to_a (ecc, 0, p, p, scratch); if (mpn_cmp (p, ecc->g, 2*size != 0)) { @@ -48,7 +48,7 @@ test_main (void) /* (order - 1) * g = - g */ mpn_sub_1 (n, ecc->q, size, 1); ecc_mul_g (ecc, p, n, scratch); - ecc_j_to_a (ecc, 1, p, p, scratch); + ecc_j_to_a (ecc, 0, p, p, scratch); mpn_sub_n (p + size, ecc->p, p + size, size); if (mpn_cmp (p, ecc->g, 2*size) != 0) { diff --git a/testsuite/testutils.c b/testsuite/testutils.c index 9739c9ed..33c3c40e 100644 --- a/testsuite/testutils.c +++ b/testsuite/testutils.c @@ -1376,7 +1376,7 @@ test_ecc_mul_j (unsigned curve, unsigned n, const mp_limb_t *p) const struct ecc_curve *ecc = ecc_curves[curve]; mp_limb_t *np = xalloc_limbs (ecc_size_a (ecc)); mp_limb_t *scratch = xalloc_limbs (ecc_j_to_a_itch(ecc)); - ecc_j_to_a (ecc, 1, np, p, scratch); + ecc_j_to_a (ecc, 0, np, p, scratch); test_ecc_mul_a (curve, n, np); |