diff options
| -rw-r--r-- | ChangeLog | 38 | ||||
| -rw-r--r-- | ecc-192.c | 5 | ||||
| -rw-r--r-- | ecc-224.c | 5 | ||||
| -rw-r--r-- | ecc-25519.c | 7 | ||||
| -rw-r--r-- | ecc-256.c | 5 | ||||
| -rw-r--r-- | ecc-384.c | 5 | ||||
| -rw-r--r-- | ecc-521.c | 5 | ||||
| -rw-r--r-- | ecc-eh-to-a.c | 9 | ||||
| -rw-r--r-- | ecc-internal.h | 21 | ||||
| -rw-r--r-- | ecc-mul-a-eh.c | 12 | ||||
| -rw-r--r-- | ecc-mul-g-eh.c | 4 | ||||
| -rw-r--r-- | eccdata.c | 301 | ||||
| -rw-r--r-- | eddsa-sign.c | 2 | ||||
| -rw-r--r-- | testsuite/ecc-add-test.c | 71 | ||||
| -rw-r--r-- | testsuite/ecc-dup-test.c | 29 |
15 files changed, 285 insertions, 234 deletions
@@ -1,3 +1,41 @@ +2019-11-21 Niels Möller <nisse@lysator.liu.se> + + * Merge curve448 preparations, from September 2017. + +2017-09-23 Niels Möller <nisse@lysator.liu.se> + + * eccdata.c: Reorganize curve25519 precomputation to work directly + with the twisted Edwards curve, with new point addition based on a + patch from Daiki Ueno. + * ecc-25519.c (_nettle_curve25519): Update for removed Montgomery + curve constant. + + * ecc-internal.h (struct ecc_curve): Delete unused pointer + edwards_root. Update all instances. + * eccdata.c (output_curve): Don't output it. + + * testsuite/ecc-add-test.c (test_main): Reduce test duplication. + Use ecc->add_hhh_itch. + * testsuite/ecc-dup-test.c (test_main): Reduce test duplication. + Use ecc->dup_itch. + +2017-09-23 Daiki Ueno <dueno@redhat.com> + + * ecc-eh-to-a.c (ecc_eh_to_a): Use ecc->q.bit_size, instead of + hard-coded value for curve25519. + * eddsa-sign.c (_eddsa_sign): Likewise. + + * ecc-internal.h (ecc_dup_func): New typedef. + (struct ecc_curve): New constants add_hh_itch and dup_itch, new + function pointers add_hh and dup. + * ecc-192.c, ecc-224.c, ecc-256.c, ecc-384.c, ecc-521.c, + ecc-25519.c: Update accordingly. + * ecc-mul-g-eh.c (ecc_mul_g_eh): Use new function pointers. + * ecc-mul-a-eh.c (ecc_mul_a_eh, table_init, ecc_mul_a_eh): + Likewise. + * testsuite/ecc-dup-test.c (test_main): Likewise. + * testsuite/ecc-add-test.c (test_main): Likewise. + 2019-10-01 Niels Möller <nisse@lysator.liu.se> * testsuite/testutils.c (test_cipher_cfb8): Reset destination area @@ -155,19 +155,22 @@ const struct ecc_curve _nettle_secp_192r1 = ECC_PIPPENGER_K, ECC_PIPPENGER_C, + ECC_ADD_JJA_ITCH (ECC_LIMB_SIZE), ECC_ADD_JJJ_ITCH (ECC_LIMB_SIZE), + ECC_DUP_JJ_ITCH (ECC_LIMB_SIZE), ECC_MUL_A_ITCH (ECC_LIMB_SIZE), ECC_MUL_G_ITCH (ECC_LIMB_SIZE), ECC_J_TO_A_ITCH (ECC_LIMB_SIZE), + ecc_add_jja, ecc_add_jjj, + ecc_dup_jj, ecc_mul_a, ecc_mul_g, ecc_j_to_a, ecc_b, ecc_g, - NULL, ecc_unit, ecc_table }; @@ -107,19 +107,22 @@ const struct ecc_curve _nettle_secp_224r1 = ECC_PIPPENGER_K, ECC_PIPPENGER_C, + ECC_ADD_JJA_ITCH (ECC_LIMB_SIZE), ECC_ADD_JJJ_ITCH (ECC_LIMB_SIZE), + ECC_DUP_JJ_ITCH (ECC_LIMB_SIZE), ECC_MUL_A_ITCH (ECC_LIMB_SIZE), ECC_MUL_G_ITCH (ECC_LIMB_SIZE), ECC_J_TO_A_ITCH (ECC_LIMB_SIZE), + ecc_add_jja, ecc_add_jjj, + ecc_dup_jj, ecc_mul_a, ecc_mul_g, ecc_j_to_a, ecc_b, ecc_g, - NULL, ecc_unit, ecc_table }; diff --git a/ecc-25519.c b/ecc-25519.c index bb71a36b..105ce0f4 100644 --- a/ecc-25519.c +++ b/ecc-25519.c @@ -335,19 +335,22 @@ const struct ecc_curve _nettle_curve25519 = ECC_PIPPENGER_K, ECC_PIPPENGER_C, + ECC_ADD_EH_ITCH (ECC_LIMB_SIZE), ECC_ADD_EHH_ITCH (ECC_LIMB_SIZE), + ECC_DUP_EH_ITCH (ECC_LIMB_SIZE), ECC_MUL_A_EH_ITCH (ECC_LIMB_SIZE), ECC_MUL_G_EH_ITCH (ECC_LIMB_SIZE), ECC_EH_TO_A_ITCH (ECC_LIMB_SIZE, ECC_25519_INV_ITCH), + ecc_add_eh, ecc_add_ehh, + ecc_dup_eh, ecc_mul_a_eh, ecc_mul_g_eh, ecc_eh_to_a, - ecc_d, /* Use the Edwards curve constant. */ + ecc_b, /* Edwards curve constant. */ ecc_g, - ecc_edwards, ecc_unit, ecc_table }; @@ -284,19 +284,22 @@ const struct ecc_curve _nettle_secp_256r1 = ECC_PIPPENGER_K, ECC_PIPPENGER_C, + ECC_ADD_JJA_ITCH (ECC_LIMB_SIZE), ECC_ADD_JJJ_ITCH (ECC_LIMB_SIZE), + ECC_DUP_JJ_ITCH (ECC_LIMB_SIZE), ECC_MUL_A_ITCH (ECC_LIMB_SIZE), ECC_MUL_G_ITCH (ECC_LIMB_SIZE), ECC_J_TO_A_ITCH (ECC_LIMB_SIZE), + ecc_add_jja, ecc_add_jjj, + ecc_dup_jj, ecc_mul_a, ecc_mul_g, ecc_j_to_a, ecc_b, ecc_g, - NULL, ecc_unit, ecc_table }; @@ -192,19 +192,22 @@ const struct ecc_curve _nettle_secp_384r1 = ECC_PIPPENGER_K, ECC_PIPPENGER_C, + ECC_ADD_JJA_ITCH (ECC_LIMB_SIZE), ECC_ADD_JJJ_ITCH (ECC_LIMB_SIZE), + ECC_DUP_JJ_ITCH (ECC_LIMB_SIZE), ECC_MUL_A_ITCH (ECC_LIMB_SIZE), ECC_MUL_G_ITCH (ECC_LIMB_SIZE), ECC_J_TO_A_ITCH (ECC_LIMB_SIZE), + ecc_add_jja, ecc_add_jjj, + ecc_dup_jj, ecc_mul_a, ecc_mul_g, ecc_j_to_a, ecc_b, ecc_g, - NULL, ecc_unit, ecc_table }; @@ -120,19 +120,22 @@ const struct ecc_curve _nettle_secp_521r1 = ECC_PIPPENGER_K, ECC_PIPPENGER_C, + ECC_ADD_JJA_ITCH (ECC_LIMB_SIZE), ECC_ADD_JJJ_ITCH (ECC_LIMB_SIZE), + ECC_DUP_JJ_ITCH (ECC_LIMB_SIZE), ECC_MUL_A_ITCH (ECC_LIMB_SIZE), ECC_MUL_G_ITCH (ECC_LIMB_SIZE), ECC_J_TO_A_ITCH (ECC_LIMB_SIZE), + ecc_add_jja, ecc_add_jjj, + ecc_dup_jj, ecc_mul_a, ecc_mul_g, ecc_j_to_a, ecc_b, ecc_g, - NULL, ecc_unit, ecc_table }; diff --git a/ecc-eh-to-a.c b/ecc-eh-to-a.c index 2acaacb1..8173b887 100644 --- a/ecc-eh-to-a.c +++ b/ecc-eh-to-a.c @@ -68,12 +68,13 @@ ecc_eh_to_a (const struct ecc_curve *ecc, /* Skip y coordinate */ if (op > 1) { - /* Reduce modulo q. FIXME: Hardcoded for curve25519, - duplicates end of ecc_25519_modq. FIXME: Is this needed - at all? Full reduction mod p is maybe sufficient. */ + /* Reduce modulo q. Hardcoded for curve25519, duplicates end + of ecc_25519_modq. FIXME: Is this needed at all? op > 0 + is only used by ecdsa code, and ecdsa on Edwards curves + makes little sense and is is only used by tests. */ unsigned shift; assert (ecc->p.bit_size == 255); - shift = 252 - GMP_NUMB_BITS * (ecc->p.size - 1); + shift = ecc->q.bit_size - 1 - GMP_NUMB_BITS * (ecc->p.size - 1); cy = mpn_submul_1 (r, ecc->q.m, ecc->p.size, r[ecc->p.size-1] >> shift); assert (cy < 2); diff --git a/ecc-internal.h b/ecc-internal.h index 7d961f11..18c1bf7d 100644 --- a/ecc-internal.h +++ b/ecc-internal.h @@ -118,6 +118,10 @@ typedef void ecc_add_func (const struct ecc_curve *ecc, const mp_limb_t *p, const mp_limb_t *q, mp_limb_t *scratch); +typedef void ecc_dup_func (const struct ecc_curve *ecc, + mp_limb_t *r, const mp_limb_t *p, + mp_limb_t *scratch); + typedef void ecc_mul_g_func (const struct ecc_curve *ecc, mp_limb_t *r, const mp_limb_t *np, mp_limb_t *scratch); @@ -174,12 +178,16 @@ struct ecc_curve unsigned short pippenger_k; unsigned short pippenger_c; + unsigned short add_hh_itch; unsigned short add_hhh_itch; + unsigned short dup_itch; unsigned short mul_itch; unsigned short mul_g_itch; unsigned short h_to_a_itch; + ecc_add_func *add_hh; ecc_add_func *add_hhh; + ecc_dup_func *dup; ecc_mul_func *mul; ecc_mul_g_func *mul_g; ecc_h_to_a_func *h_to_a; @@ -189,9 +197,6 @@ struct ecc_curve /* Generator, x coordinate followed by y (affine coordinates). Currently used only by the test suite. */ const mp_limb_t *g; - /* If non-NULL, the constant needed for transformation to the - equivalent Edwards curve. */ - const mp_limb_t *edwards_root; /* For redc, same as B mod p, otherwise 1. */ const mp_limb_t *unit; @@ -281,18 +286,16 @@ ecc_a_to_j (const struct ecc_curve *ecc, /* Converts a point P in jacobian coordinates into a point R in affine coordinates. If op == 1, produce x coordinate only. If op == 2, - produce the x coordinate only, and also reduce it modulo q. FIXME: - For the public interface, have separate functions for the three - cases, and use this flag argument only for the internal ecc->h_to_a - function. */ + produce the x coordinate only, and also reduce it modulo q. */ void ecc_j_to_a (const struct ecc_curve *ecc, int op, mp_limb_t *r, const mp_limb_t *p, mp_limb_t *scratch); -/* Converts a point P on an Edwards curve to affine coordinates on - the corresponding Montgomery curve. */ +/* Converts a point P in homogeneous coordinates on an Edwards curve + to affine coordinates. Meaning of op is the same as for + ecc_j_to_a. */ void ecc_eh_to_a (const struct ecc_curve *ecc, int op, diff --git a/ecc-mul-a-eh.c b/ecc-mul-a-eh.c index cf743236..e9b22cd4 100644 --- a/ecc-mul-a-eh.c +++ b/ecc-mul-a-eh.c @@ -75,8 +75,8 @@ ecc_mul_a_eh (const struct ecc_curve *ecc, { int digit; - ecc_dup_eh (ecc, r, r, scratch_out); - ecc_add_ehh (ecc, tp, r, pe, scratch_out); + ecc->dup (ecc, r, r, scratch_out); + ecc->add_hhh (ecc, tp, r, pe, scratch_out); digit = (w & bit) > 0; /* If we had a one-bit, use the sum. */ @@ -107,8 +107,8 @@ table_init (const struct ecc_curve *ecc, for (j = 2; j < size; j += 2) { - ecc_dup_eh (ecc, TABLE(j), TABLE(j/2), scratch); - ecc_add_ehh (ecc, TABLE(j+1), TABLE(j), TABLE(1), scratch); + ecc->dup (ecc, TABLE(j), TABLE(j/2), scratch); + ecc->add_hhh (ecc, TABLE(j+1), TABLE(j), TABLE(1), scratch); } } @@ -163,11 +163,11 @@ ecc_mul_a_eh (const struct ecc_curve *ecc, bits |= w >> shift; } for (j = 0; j < ECC_MUL_A_EH_WBITS; j++) - ecc_dup_eh (ecc, r, r, scratch_out); + ecc->dup (ecc, r, r, scratch_out); bits &= TABLE_MASK; sec_tabselect (tp, 3*ecc->p.size, table, TABLE_SIZE, bits); - ecc_add_ehh (ecc, r, tp, r, scratch_out); + ecc->add_hhh (ecc, r, tp, r, scratch_out); } #undef table #undef tp diff --git a/ecc-mul-g-eh.c b/ecc-mul-g-eh.c index a945494d..971bc6c5 100644 --- a/ecc-mul-g-eh.c +++ b/ecc-mul-g-eh.c @@ -64,7 +64,7 @@ ecc_mul_g_eh (const struct ecc_curve *ecc, mp_limb_t *r, for (i = k; i-- > 0; ) { - ecc_dup_eh (ecc, r, r, scratch); + ecc->dup (ecc, r, r, scratch); for (j = 0; j * c < bit_rows; j++) { unsigned bits; @@ -93,7 +93,7 @@ ecc_mul_g_eh (const struct ecc_curve *ecc, mp_limb_t *r, + (2*ecc->p.size * (mp_size_t) j << c)), 1<<c, bits); - ecc_add_eh (ecc, r, r, tp, scratch_out); + ecc->add_hh (ecc, r, r, tp, scratch_out); } } #undef tp @@ -2,7 +2,9 @@ Generate compile time constant (but machine dependent) tables. - Copyright (C) 2013, 2014 Niels Möller + Copyright (C) 2013, 2014, 2017 Niels Möller + Copyright (C) 2017 Daiki Ueno + Copyright (C) 2017 Red Hat, Inc. This file is part of GNU Nettle. @@ -53,8 +55,12 @@ enum ecc_type { /* y^2 = x^3 - 3x + b (mod p) */ ECC_TYPE_WEIERSTRASS, - /* y^2 = x^3 + b x^2 + x */ - ECC_TYPE_MONTGOMERY +#if 0 + /* x^2 + y^2 = 1 - d x^2 y^2 */ + ECC_TYPE_EDWARDS, +#endif + /* -x^2 + y^2 = 1 - d x^2 y^2 */ + ECC_TYPE_TWISTED_EDWARDS, }; struct ecc_curve @@ -73,16 +79,6 @@ struct ecc_curve mpz_t q; struct ecc_point g; - /* Non-zero if we want elements represented as point s(u, v) on an - equivalent Edwards curve, using - - u = t x / y - v = (x-1) / (x+1) - */ - int use_edwards; - mpz_t d; - mpz_t t; - /* Table for pippenger's algorithm. Element @@ -127,9 +123,11 @@ ecc_equal_p (const struct ecc_point *p, const struct ecc_point *q) } static void -ecc_set_zero (struct ecc_point *r) +ecc_set_zero (const struct ecc_curve *ecc, struct ecc_point *r) { r->is_zero = 1; + mpz_set_ui (r->x, 0); + mpz_set_ui (r->y, ecc->type != ECC_TYPE_WEIERSTRASS); } static void @@ -140,13 +138,22 @@ ecc_set (struct ecc_point *r, const struct ecc_point *p) mpz_set (r->y, p->y); } +static void +ecc_add (const struct ecc_curve *ecc, struct ecc_point *r, + const struct ecc_point *p, const struct ecc_point *q); + /* Needs to support in-place operation. */ static void ecc_dup (const struct ecc_curve *ecc, struct ecc_point *r, const struct ecc_point *p) { + if (ecc->type != ECC_TYPE_WEIERSTRASS) + { + ecc_add (ecc, r, p, p); + return; + } if (ecc_zero_p (p)) - ecc_set_zero (r); + ecc_set_zero (ecc, r); else { @@ -161,32 +168,18 @@ ecc_dup (const struct ecc_curve *ecc, mpz_mul_ui (m, p->y, 2); mpz_invert (m, m, ecc->p); - switch (ecc->type) - { - case ECC_TYPE_WEIERSTRASS: - /* t = 3 (x^2 - 1) * m */ - mpz_mul (t, p->x, p->x); - mpz_mod (t, t, ecc->p); - mpz_sub_ui (t, t, 1); - mpz_mul_ui (t, t, 3); - break; - case ECC_TYPE_MONTGOMERY: - /* t = (3 x^2 + 2 b x + 1) m = [x(3x+2b)+1] m */ - mpz_mul_ui (t, ecc->b, 2); - mpz_addmul_ui (t, p->x, 3); - mpz_mul (t, t, p->x); - mpz_mod (t, t, ecc->p); - mpz_add_ui (t, t, 1); - break; - } + /* t = 3 (x^2 - 1) * m */ + mpz_mul (t, p->x, p->x); + mpz_mod (t, t, ecc->p); + mpz_sub_ui (t, t, 1); + mpz_mul_ui (t, t, 3); + mpz_mul (t, t, m); mpz_mod (t, t, ecc->p); /* x' = t^2 - 2 x */ mpz_mul (x, t, t); mpz_submul_ui (x, p->x, 2); - if (ecc->type == ECC_TYPE_MONTGOMERY) - mpz_sub (x, x, ecc->b); mpz_mod (x, x, ecc->p); @@ -208,55 +201,114 @@ ecc_dup (const struct ecc_curve *ecc, } static void -ecc_add (const struct ecc_curve *ecc, - struct ecc_point *r, const struct ecc_point *p, const struct ecc_point *q) +ecc_add (const struct ecc_curve *ecc, struct ecc_point *r, + const struct ecc_point *p, const struct ecc_point *q) { - if (ecc_zero_p (p)) - ecc_set (r, q); + if (ecc->type == ECC_TYPE_WEIERSTRASS) + { + if (ecc_zero_p (p)) + ecc_set (r, q); - else if (ecc_zero_p (q)) - ecc_set (r, p); + else if (ecc_zero_p (q)) + ecc_set (r, p); - else if (mpz_cmp (p->x, q->x) == 0) - { - if (mpz_cmp (p->y, q->y) == 0) - ecc_dup (ecc, r, p); + else if (mpz_cmp (p->x, q->x) == 0) + { + if (mpz_cmp (p->y, q->y) == 0) + ecc_dup (ecc, r, p); + else + ecc_set_zero (ecc, r); + } else - ecc_set_zero (r); + { + mpz_t s, t, x, y; + mpz_init (s); + mpz_init (t); + mpz_init (x); + mpz_init (y); + + /* t = (q_y - p_y) / (q_x - p_x) */ + mpz_sub (t, q->x, p->x); + mpz_invert (t, t, ecc->p); + mpz_sub (s, q->y, p->y); + mpz_mul (t, t, s); + mpz_mod (t, t, ecc->p); + + /* x' = t^2 - p_x - q_x */ + mpz_mul (x, t, t); + mpz_sub (x, x, p->x); + mpz_sub (x, x, q->x); + mpz_mod (x, x, ecc->p); + + /* y' = (x - x') * t - y */ + mpz_sub (y, p->x, x); + mpz_mul (y, y, t); + mpz_sub (y, y, p->y); + mpz_mod (y, y, ecc->p); + + r->is_zero = 0; + mpz_swap (x, r->x); + mpz_swap (y, r->y); + + mpz_clear (s); + mpz_clear (t); + mpz_clear (x); + mpz_clear (y); + } } else { + /* Untwisted: + x = (p_x q_y + p_y q_x) / (1 - d p_x p_y q_x q_y) + y = (p_y q_y - p_x q_x) / (1 + d p_x p_y q_x q_y) + + Twisted: + x = (p_x q_y + p_y q_x) / (1 - d p_x p_y q_x q_y) + y = (p_y q_y + p_x q_x) / (1 + d p_x p_y q_x q_y) + + So they differ only by a sign in the expression for the new y + coordinate. + */ + mpz_t s, t, x, y; mpz_init (s); mpz_init (t); mpz_init (x); mpz_init (y); - /* t = (q_y - p_y) / (q_x - p_x) */ - mpz_sub (t, q->x, p->x); - mpz_invert (t, t, ecc->p); - mpz_sub (s, q->y, p->y); - mpz_mul (t, t, s); + /* t = d p_x p_y q_x q_y */ + mpz_mul (t, ecc->b, p->x); + mpz_mod (t, t, ecc->p); + mpz_mul (t, t, p->y); + mpz_mod (t, t, ecc->p); + mpz_mul (t, t, q->x); + mpz_mod (t, t, ecc->p); + mpz_mul (t, t, q->y); mpz_mod (t, t, ecc->p); - /* x' = t^2 - p_x - q_x */ - mpz_mul (x, t, t); - mpz_sub (x, x, p->x); - mpz_sub (x, x, q->x); - /* This appears to be the only difference between formulas. */ - if (ecc->type == ECC_TYPE_MONTGOMERY) - mpz_sub (x, x, ecc->b); + /* x' = (p_x q_y + q_x p_y) / (1 - t) */ + mpz_mul (x, p->x, q->y); + mpz_mod (x, x, ecc->p); + mpz_addmul (x, q->x, p->y); + mpz_mod (x, x, ecc->p); + mpz_ui_sub (s, 1, t); + mpz_invert (s, s, ecc->p); + mpz_mul (x, x, s); mpz_mod (x, x, ecc->p); - /* y' = (x - x') * t - y */ - mpz_sub (y, p->x, x); - mpz_mul (y, y, t); - mpz_sub (y, y, p->y); + /* y' = (p_y q_y - p_x q_x) / (1 + t) */ + mpz_mul (y, p->y, q->y); + mpz_mod (y, y, ecc->p); + mpz_addmul (y, p->x, q->x); + mpz_mod (y, y, ecc->p); + mpz_add_ui (s, t, 1); + mpz_invert (s, s, ecc->p); + mpz_mul (y, y, s); mpz_mod (y, y, ecc->p); - r->is_zero = 0; mpz_swap (x, r->x); mpz_swap (y, r->y); + r->is_zero = (mpz_cmp_ui (r->x, 0) == 0 && mpz_cmp_ui (r->y, 1) == 0); mpz_clear (s); mpz_clear (t); @@ -332,16 +384,6 @@ ecc_curve_init_str (struct ecc_curve *ecc, enum ecc_type type, ecc->table = NULL; ecc->ref = NULL; - - mpz_init (ecc->d); - mpz_init (ecc->t); - - ecc->use_edwards = (t != NULL); - if (ecc->use_edwards) - { - mpz_set_str (ecc->t, t, 16); - mpz_set_str (ecc->d, d, 16); - } } static void @@ -533,43 +575,37 @@ ecc_curve_init (struct ecc_curve *ecc, unsigned bit_size) break; case 255: - /* curve25519, y^2 = x^3 + 486662 x^2 + x (mod p), with p = 2^{255} - 19. - - According to http://cr.yp.to/papers.html#newelliptic, this - is birationally equivalent to the Edwards curve - - x^2 + y^2 = 1 + (121665/121666) x^2 y^2 (mod p). + /* Edwards curve used for eddsa25519 and curve25519, - And since the constant is not a square, the Edwards formulas - should be "complete", with no special cases needed for - doubling, neutral element, negatives, etc. + -x^2 + y^2 = 1 - (121665/121666) x^2 y^2, with p = 2^{255} - 19. - Generator is x = 9, with y coordinate - 14781619447589544791020593568409986887264606134616475288964881837755586237401, - according to + The generator is + x = 0x216936d3cd6e53fec0a4e231fdd6dc5c692cc7609525a7b2c9562d608f25d51a + y = 0x6666666666666666666666666666666666666666666666666666666666666658 - x = Mod(9, 2^255-19); sqrt(x^3 + 486662*x^2 + x) + Also birationally equivalent to the curve25519 Montgomery curve, - in PARI/GP. Also, in PARI notation, - - curve25519 = Mod([0, 486662, 0, 1, 0], 2^255-19) - */ - ecc_curve_init_str (ecc, ECC_TYPE_MONTGOMERY, + y^2 = x^3 + 486662 x^2 + x (mod p) + */ + ecc_curve_init_str (ecc, ECC_TYPE_TWISTED_EDWARDS, "7fffffffffffffffffffffffffffffff" "ffffffffffffffffffffffffffffffed", - "76d06", + /* (121665/121666) mod p, from PARI/GP + c = Mod(121665, p); c / (c+1) + */ + "2dfc9311d490018c7338bf8688861767" + "ff8ff5b2bebe27548a14b235eca6874a", /* Order of the subgroup is 2^252 + q_0, where q_0 = 27742317777372353535851937790883648493, 125 bits. */ "10000000000000000000000000000000" "14def9dea2f79cd65812631a5cf5d3ed", - "9", - /* y coordinate from PARI/GP - x = Mod(9, 2^255-19); sqrt(x^3 + 486662*x^2 + x) - */ - "20ae19a1b8a086b4e01edd2c7748d14c" - "923d4d7e6d7c61b229e9c5a27eced3d9", + /* Generator */ + "216936d3cd6e53fec0a4e231fdd6dc5c" + "692cc7609525a7b2c9562d608f25d51a", + "66666666666666666666666666666666" + "66666666666666666666666666666658", /* (121665/121666) mod p, from PARI/GP c = Mod(121665, p); c / (c+1) */ @@ -586,22 +622,21 @@ ecc_curve_init (struct ecc_curve *ecc, unsigned bit_size) ); ecc->ref = ecc_alloc (3); ecc_set_str (&ecc->ref[0], /* 2 g */ - "20d342d51873f1b7d9750c687d157114" - "8f3f5ced1e350b5c5cae469cdd684efb", - "13b57e011700e8ae050a00945d2ba2f3" - "77659eb28d8d391ebcd70465c72df563"); + "36ab384c9f5a046c3d043b7d1833e7ac" + "080d8e4515d7a45f83c5a14e2843ce0e", + "2260cdf3092329c21da25ee8c9a21f56" + "97390f51643851560e5f46ae6af8a3c9"); ecc_set_str (&ecc->ref[1], /* 3 g */ - "1c12bc1a6d57abe645534d91c21bba64" - "f8824e67621c0859c00a03affb713c12", - "2986855cbe387eaeaceea446532c338c" - "536af570f71ef7cf75c665019c41222b"); + "67ae9c4a22928f491ff4ae743edac83a" + "6343981981624886ac62485fd3f8e25c", + "1267b1d177ee69aba126a18e60269ef7" + "9f16ec176724030402c3684878f5b4d4"); ecc_set_str (&ecc->ref[2], /* 4 g */ - "79ce98b7e0689d7de7d1d074a15b315f" - "fe1805dfcd5d2a230fee85e4550013ef", - "75af5bf4ebdc75c8fe26873427d275d7" - "3c0fb13da361077a565539f46de1c30"); - + "203da8db56cff1468325d4b87a3520f9" + "1a739ec193ce1547493aa657c4c9f870", + "47d0e827cb1595e1470eb88580d5716c" + "4cf22832ea2f0ff0df38ab61ca32112f"); break; default: @@ -618,8 +653,6 @@ ecc_curve_clear (struct ecc_curve *ecc) mpz_clear (ecc->b); mpz_clear (ecc->q); ecc_clear (&ecc->g); - mpz_clear (ecc->d); - mpz_clear (ecc->t); if (ecc->table) { size_t i; @@ -668,7 +701,7 @@ ecc_pippenger_precompute (struct ecc_curve *ecc, unsigned k, unsigned c) ecc->table = ecc_alloc (ecc->table_size); /* Compute the first 2^c entries */ - ecc_set_zero (&ecc->table[0]); + ecc_set_zero (ecc, &ecc->table[0]); ecc_set (&ecc->table[1], &ecc->g); for (j = 2; j < (1U<<c); j <<= 1) @@ -706,7 +739,7 @@ ecc_mul_pippenger (const struct ecc_curve *ecc, mpz_init (n); mpz_mod (n, n_input, ecc->q); - ecc_set_zero (r); + ecc_set_zero (ecc, r); k = ecc->pippenger_k; c = ecc->pippenger_c; @@ -904,38 +937,9 @@ output_point (const char *name, const struct ecc_curve *ecc, if (name) printf("static const mp_limb_t %s[%u] = {", name, 2*size); - if (ecc->use_edwards) - { - if (ecc_zero_p (p)) - { - mpz_set_si (x, 0); - mpz_set_si (y, 1); - } - else if (!mpz_sgn (p->y)) - { - assert (!mpz_sgn (p->x)); - mpz_set_si (x, 0); - mpz_set_si (y, -1); - } - else - { - mpz_invert (x, p->y, ecc->p); - mpz_mul (x, x, p->x); - mpz_mul (x, x, ecc->t); - mpz_mod (x, x, ecc->p); + mpz_set (x, p->x); + mpz_set (y, p->y); - mpz_sub_ui (y, p->x, 1); - mpz_add_ui (t, p->x, 1); - mpz_invert (t, t, ecc->p); - mpz_mul (y, y, t); - mpz_mod (y, y, ecc->p); - } - } - else - { - mpz_set (x, p->x); - mpz_set (y, p->y); - } if (use_redc) { mpz_mul_2exp (x, x, size * bits_per_limb); @@ -993,8 +997,6 @@ output_curve (const struct ecc_curve *ecc, unsigned bits_per_limb) output_bignum ("ecc_p", ecc->p, limb_size, bits_per_limb); output_bignum ("ecc_b", ecc->b, limb_size, bits_per_limb); - if (ecc->use_edwards) - output_bignum ("ecc_d", ecc->d, limb_size, bits_per_limb); output_bignum ("ecc_q", ecc->q, limb_size, bits_per_limb); output_point ("ecc_g", ecc, &ecc->g, 0, limb_size, bits_per_limb); @@ -1084,9 +1086,6 @@ output_curve (const struct ecc_curve *ecc, unsigned bits_per_limb) mpz_fdiv_q_2exp (t, t, 1); output_bignum ("ecc_qp1h", t, limb_size, bits_per_limb); - if (ecc->use_edwards) - output_bignum ("ecc_edwards", ecc->t, limb_size, bits_per_limb); - /* Trailing zeros in p+1 correspond to trailing ones in p. */ redc_limbs = mpz_scan0 (ecc->p, 0) / bits_per_limb; if (redc_limbs > 0) diff --git a/eddsa-sign.c b/eddsa-sign.c index 5832c23a..13ae4799 100644 --- a/eddsa-sign.c +++ b/eddsa-sign.c @@ -93,7 +93,7 @@ _eddsa_sign (const struct ecc_curve *ecc, unsigned shift; mp_limb_t cy; assert (ecc->p.bit_size == 255); - shift = 252 - GMP_NUMB_BITS * (ecc->p.size - 1); + shift = ecc->q.bit_size - 1 - GMP_NUMB_BITS * (ecc->p.size - 1); cy = mpn_submul_1 (sp, ecc->q.m, ecc->p.size, sp[ecc->p.size-1] >> shift); assert (cy < 2); diff --git a/testsuite/ecc-add-test.c b/testsuite/ecc-add-test.c index 54fae31f..ad2bd292 100644 --- a/testsuite/ecc-add-test.c +++ b/testsuite/ecc-add-test.c @@ -1,4 +1,5 @@ #include "testutils.h" +#include <assert.h> void test_main (void) @@ -12,74 +13,68 @@ test_main (void) mp_limb_t *g2 = xalloc_limbs (ecc_size_j (ecc)); mp_limb_t *g3 = xalloc_limbs (ecc_size_j (ecc)); mp_limb_t *p = xalloc_limbs (ecc_size_j (ecc)); - mp_limb_t *scratch = xalloc_limbs (ECC_ADD_JJJ_ITCH(ecc->p.size)); + mp_limb_t *scratch = xalloc_limbs (ecc->add_hhh_itch); + + ASSERT (ecc->dup_itch <= ecc->add_hhh_itch); + + ecc_a_to_j (ecc, g, ecc->g); if (ecc->p.bit_size == 255) { mp_limb_t *z = xalloc_limbs (ecc_size_j (ecc)); + + ASSERT (ecc->add_hh == ecc_add_eh); + ASSERT (ecc->add_hhh == ecc_add_ehh); + ASSERT (ecc->add_hh_itch <= ecc->add_hhh_itch); + /* Zero point has x = 0, y = 1, z = 1 */ mpn_zero (z, 3*ecc->p.size); z[ecc->p.size] = z[2*ecc->p.size] = 1; - - ecc_a_to_j (ecc, g, ecc->g); - ecc_add_ehh (ecc, p, z, z, scratch); + ecc->add_hhh (ecc, p, z, z, scratch); test_ecc_mul_h (i, 0, p); - ecc_add_eh (ecc, p, z, z, scratch); + ecc->add_hh (ecc, p, z, z, scratch); test_ecc_mul_h (i, 0, p); - ecc_add_ehh (ecc, p, g, p, scratch); + ecc->add_hhh (ecc, p, g, p, scratch); test_ecc_mul_h (i, 1, p); - ecc_add_eh (ecc, p, z, g, scratch); + ecc->add_hh (ecc, p, z, g, scratch); test_ecc_mul_h (i, 1, p); - ecc_add_ehh (ecc, g2, g, p, scratch); + ecc->add_hhh (ecc, g2, g, p, scratch); test_ecc_mul_h (i, 2, g2); - ecc_add_eh (ecc, g2, g, g, scratch); + ecc->add_hh (ecc, g2, g, g, scratch); test_ecc_mul_h (i, 2, g2); - ecc_add_ehh (ecc, g3, g, g2, scratch); - test_ecc_mul_h (i, 3, g3); - - ecc_add_eh (ecc, g3, g2, g, scratch); - test_ecc_mul_h (i, 3, g3); - - ecc_add_ehh (ecc, p, g, g3, scratch); - test_ecc_mul_h (i, 4, p); - - ecc_add_eh (ecc, p, g3, g, scratch); - test_ecc_mul_h (i, 4, p); - - ecc_add_ehh (ecc, p, g2, g2, scratch); - test_ecc_mul_h (i, 4, p); - free (z); } else { - ecc_a_to_j (ecc, g, ecc->g); + ASSERT (ecc->add_hhh == ecc_add_jjj); + ASSERT (ecc->dup == ecc_dup_jj); + } - ecc_dup_jj (ecc, g2, g, scratch); - test_ecc_mul_h (i, 2, g2); + ecc->dup (ecc, g2, g, scratch); + test_ecc_mul_h (i, 2, g2); - ecc_add_jjj (ecc, g3, g, g2, scratch); - test_ecc_mul_h (i, 3, g3); + ecc->add_hhh (ecc, g3, g, g2, scratch); + test_ecc_mul_h (i, 3, g3); - ecc_add_jjj (ecc, g3, g2, g, scratch); - test_ecc_mul_h (i, 3, g3); + ecc->add_hhh (ecc, g3, g2, g, scratch); + test_ecc_mul_h (i, 3, g3); - ecc_add_jjj (ecc, p, g, g3, scratch); - test_ecc_mul_h (i, 4, p); + ecc->add_hhh (ecc, p, g, g3, scratch); + test_ecc_mul_h (i, 4, p); - ecc_add_jjj (ecc, p, g3, g, scratch); - test_ecc_mul_h (i, 4, p); + ecc->add_hhh (ecc, p, g3, g, scratch); + test_ecc_mul_h (i, 4, p); + + ecc->dup (ecc, p, g2, scratch); + test_ecc_mul_h (i, 4, p); - ecc_dup_jj (ecc, p, g2, scratch); - test_ecc_mul_h (i, 4, p); - } free (g); free (g2); free (g3); diff --git a/testsuite/ecc-dup-test.c b/testsuite/ecc-dup-test.c index b92352c1..0ae4444a 100644 --- a/testsuite/ecc-dup-test.c +++ b/testsuite/ecc-dup-test.c @@ -10,37 +10,34 @@ test_main (void) const struct ecc_curve *ecc = ecc_curves[i]; mp_limb_t *g = xalloc_limbs (ecc_size_j (ecc)); mp_limb_t *p = xalloc_limbs (ecc_size_j (ecc)); - mp_limb_t *scratch = xalloc_limbs (ECC_DUP_EH_ITCH(ecc->p.size));; + mp_limb_t *scratch = xalloc_limbs (ecc->dup_itch); + + ecc_a_to_j (ecc, g, ecc->g); if (ecc->p.bit_size == 255) { mp_limb_t *z = xalloc_limbs (ecc_size_j (ecc)); + + ASSERT (ecc->dup == ecc_dup_eh); + /* Zero point has x = 0, y = 1, z = 1 */ mpn_zero (z, 3*ecc->p.size); z[ecc->p.size] = z[2*ecc->p.size] = 1; - ecc_a_to_j (ecc, g, ecc->g); - - ecc_dup_eh (ecc, p, z, scratch); + ecc->dup (ecc, p, z, scratch); test_ecc_mul_h (i, 0, p); - ecc_dup_eh (ecc, p, g, scratch); - test_ecc_mul_h (i, 2, p); - - ecc_dup_eh (ecc, p, p, scratch); - test_ecc_mul_h (i, 4, p); free (z); } else - { - ecc_a_to_j (ecc, g, ecc->g); + ASSERT (ecc->dup == ecc_dup_jj); - ecc_dup_jj (ecc, p, g, scratch); - test_ecc_mul_h (i, 2, p); + ecc->dup (ecc, p, g, scratch); + test_ecc_mul_h (i, 2, p); + + ecc->dup (ecc, p, p, scratch); + test_ecc_mul_h (i, 4, p); - ecc_dup_jj (ecc, p, p, scratch); - test_ecc_mul_h (i, 4, p); - } free (p); free (g); free (scratch); |