diff options
-rw-r--r-- | ChangeLog | 11 | ||||
-rw-r--r-- | Makefile.in | 4 | ||||
-rw-r--r-- | curve25519-eh-to-x.c | 2 | ||||
-rw-r--r-- | curve25519-mul.c | 2 | ||||
-rw-r--r-- | ecc-192.c | 8 | ||||
-rw-r--r-- | ecc-224.c | 8 | ||||
-rw-r--r-- | ecc-25519.c | 8 | ||||
-rw-r--r-- | ecc-256.c | 8 | ||||
-rw-r--r-- | ecc-384.c | 8 | ||||
-rw-r--r-- | ecc-521.c | 8 | ||||
-rw-r--r-- | ecc-ecdsa-sign.c | 2 | ||||
-rw-r--r-- | ecc-ecdsa-verify.c | 2 | ||||
-rw-r--r-- | ecc-eh-to-a.c | 2 | ||||
-rw-r--r-- | ecc-internal.h | 29 | ||||
-rw-r--r-- | ecc-j-to-a.c | 4 | ||||
-rw-r--r-- | ecc-mod-inv.c (renamed from sec-modinv.c) | 24 | ||||
-rw-r--r-- | ecc-modp.c | 8 | ||||
-rw-r--r-- | ecc-modq.c | 7 | ||||
-rw-r--r-- | examples/ecc-benchmark.c | 2 | ||||
-rw-r--r-- | testsuite/ecc-modinv-test.c | 16 |
20 files changed, 89 insertions, 74 deletions
@@ -1,5 +1,16 @@ 2014-09-22 Niels Möller <nisse@lysator.liu.se> + * ecc-internal.h (ecc_mod_inv_func): New typedef. + (struct ecc_modulo): Added mp1h constant and invert function + pointer. Updated all callers. + * ecc-modp.c (ecc_modp_inv): Deleted wrapper function. + * ecc-modq.c (ecc_modq_inv): Deleted wrapper function. + + * ecc-mod-inv.c (ecc_mod_inv): Renamed file and function. Also + take a struct ecc_modulo * as argument. + * sec-modinv.c (sec_modinv): ... the old names. Deleted. + * Makefile.in (hogweed_SOURCES): Updated accordingly. + * examples/ecc-benchmark.c (bench_modinv_powm, bench_curve): Updated benchmarking of mpn_sec_powm. diff --git a/Makefile.in b/Makefile.in index 8b04b101..aae7c1aa 100644 --- a/Makefile.in +++ b/Makefile.in @@ -160,9 +160,9 @@ hogweed_SOURCES = sexp.c sexp-format.c \ dsa2sexp.c sexp2dsa.c \ pgp-encode.c rsa2openpgp.c \ der-iterator.c der2rsa.c der2dsa.c \ - sec-add-1.c sec-sub-1.c sec-modinv.c sec-tabselect.c \ + sec-add-1.c sec-sub-1.c sec-tabselect.c \ gmp-glue.c cnd-copy.c \ - ecc-mod.c \ + ecc-mod.c ecc-mod-inv.c \ ecc-modp.c ecc-modq.c ecc-pp1-redc.c ecc-pm1-redc.c \ ecc-192.c ecc-224.c ecc-256.c ecc-384.c ecc-521.c \ ecc-25519.c \ diff --git a/curve25519-eh-to-x.c b/curve25519-eh-to-x.c index 4d05a6bf..47f07129 100644 --- a/curve25519-eh-to-x.c +++ b/curve25519-eh-to-x.c @@ -66,7 +66,7 @@ curve25519_eh_to_x (mp_limb_t *xp, const mp_limb_t *p, in this case. */ ecc_modp_sub (ecc, t0, wp, vp); /* Needs 3*size scratch, for a total of 5*size */ - ecc_modp_inv (ecc, t1, t0, t2); + ecc->p.invert (&ecc->p, t1, t0, t2); ecc_modp_add (ecc, t0, wp, vp); ecc_modp_mul (ecc, t2, t0, t1); diff --git a/curve25519-mul.c b/curve25519-mul.c index 263a33aa..f4e4fa7b 100644 --- a/curve25519-mul.c +++ b/curve25519-mul.c @@ -132,7 +132,7 @@ curve25519_mul (uint8_t *q, const uint8_t *n, const uint8_t *p) ecc_modp_addmul_1 (ecc, AA, E, 121665); ecc_modp_mul (ecc, z2, E, AA); } - ecc_modp_inv (ecc, x3, z2, z3); + ecc->p.invert (&ecc->p, x3, z2, z3); ecc_modp_mul (ecc, z3, x2, x3); cy = mpn_sub_n (x2, z3, ecc->p.m, ecc->p.size); cnd_copy (cy, x2, z3, ecc->p.size); @@ -121,8 +121,11 @@ const struct ecc_curve nettle_secp_192r1 = ecc_Bmodp, ecc_Bmodp_shifted, ecc_redc_ppm1, + ecc_pp1h, + ecc_192_modp, ecc_192_modp, + ecc_mod_inv, }, { 192, @@ -133,8 +136,11 @@ const struct ecc_curve nettle_secp_192r1 = ecc_Bmodq, ecc_Bmodq_shifted, NULL, + ecc_qp1h, + ecc_mod, ecc_mod, + ecc_mod_inv, }, USE_REDC, @@ -154,9 +160,7 @@ const struct ecc_curve nettle_secp_192r1 = ecc_b, ecc_g, NULL, - ecc_pp1h, ecc_unit, - ecc_qp1h, ecc_table }; @@ -73,8 +73,11 @@ const struct ecc_curve nettle_secp_224r1 = ecc_Bmodp, ecc_Bmodp_shifted, ecc_redc_ppm1, + ecc_pp1h, + ecc_224_modp, USE_REDC ? ecc_224_redc : ecc_224_modp, + ecc_mod_inv, }, { 224, @@ -85,8 +88,11 @@ const struct ecc_curve nettle_secp_224r1 = ecc_Bmodq, ecc_Bmodq_shifted, NULL, + ecc_qp1h, + ecc_mod, ecc_mod, + ecc_mod_inv, }, USE_REDC, @@ -106,8 +112,6 @@ const struct ecc_curve nettle_secp_224r1 = ecc_b, ecc_g, NULL, - ecc_pp1h, ecc_unit, - ecc_qp1h, ecc_table }; diff --git a/ecc-25519.c b/ecc-25519.c index c557ae41..5416b74f 100644 --- a/ecc-25519.c +++ b/ecc-25519.c @@ -241,8 +241,11 @@ const struct ecc_curve nettle_curve25519 = ecc_Bmodp, ecc_Bmodp_shifted, NULL, + ecc_pp1h, + ecc_25519_modp, ecc_25519_modp, + ecc_mod_inv, }, { 253, @@ -253,8 +256,11 @@ const struct ecc_curve nettle_curve25519 = ecc_Bmodq, ecc_mBmodq_shifted, /* Use q - 2^{252} instead. */ NULL, + ecc_qp1h, + ecc_25519_modq, ecc_25519_modq, + ecc_mod_inv, }, 0, /* No redc */ @@ -274,8 +280,6 @@ const struct ecc_curve nettle_curve25519 = ecc_d, /* Use the Edwards curve constant. */ ecc_g, ecc_edwards, - ecc_pp1h, ecc_unit, - ecc_qp1h, ecc_table }; @@ -236,8 +236,11 @@ const struct ecc_curve nettle_secp_256r1 = ecc_Bmodp, ecc_Bmodp_shifted, ecc_redc_ppm1, + + ecc_pp1h, ecc_256_modp, USE_REDC ? ecc_256_redc : ecc_256_modp, + ecc_mod_inv, }, { 256, @@ -248,8 +251,11 @@ const struct ecc_curve nettle_secp_256r1 = ecc_Bmodq, ecc_Bmodq_shifted, NULL, + ecc_qp1h, + ecc_256_modq, ecc_256_modq, + ecc_mod_inv, }, USE_REDC, @@ -269,8 +275,6 @@ const struct ecc_curve nettle_secp_256r1 = ecc_b, ecc_g, NULL, - ecc_pp1h, ecc_unit, - ecc_qp1h, ecc_table }; @@ -158,8 +158,11 @@ const struct ecc_curve nettle_secp_384r1 = ecc_Bmodp, ecc_Bmodp_shifted, ecc_redc_ppm1, + ecc_pp1h, + ecc_384_modp, ecc_384_modp, + ecc_mod_inv, }, { 384, @@ -170,8 +173,11 @@ const struct ecc_curve nettle_secp_384r1 = ecc_Bmodq, ecc_Bmodq_shifted, NULL, + ecc_qp1h, + ecc_mod, ecc_mod, + ecc_mod_inv, }, USE_REDC, @@ -191,8 +197,6 @@ const struct ecc_curve nettle_secp_384r1 = ecc_b, ecc_g, NULL, - ecc_pp1h, ecc_unit, - ecc_qp1h, ecc_table }; @@ -86,8 +86,11 @@ const struct ecc_curve nettle_secp_521r1 = ecc_Bmodp, ecc_Bmodp_shifted, ecc_redc_ppm1, + ecc_pp1h, + ecc_521_modp, ecc_521_modp, + ecc_mod_inv, }, { 521, @@ -98,8 +101,11 @@ const struct ecc_curve nettle_secp_521r1 = ecc_Bmodq, ecc_Bmodq_shifted, NULL, + ecc_qp1h, + ecc_mod, ecc_mod, + ecc_mod_inv, }, USE_REDC, @@ -119,9 +125,7 @@ const struct ecc_curve nettle_secp_521r1 = ecc_b, ecc_g, NULL, - ecc_pp1h, ecc_unit, - ecc_qp1h, ecc_table }; diff --git a/ecc-ecdsa-sign.c b/ecc-ecdsa-sign.c index 61a75e54..de17ac4c 100644 --- a/ecc-ecdsa-sign.c +++ b/ecc-ecdsa-sign.c @@ -84,7 +84,7 @@ ecc_ecdsa_sign (const struct ecc_curve *ecc, /* Invert k, uses 5 * ecc->p.size including scratch */ mpn_copyi (hp, kp, ecc->p.size); - ecc_modq_inv (ecc, kinv, hp, tp); + ecc->q.invert (&ecc->q, kinv, hp, tp); /* Process hash digest */ ecc_hash (ecc, hp, length, digest); diff --git a/ecc-ecdsa-verify.c b/ecc-ecdsa-verify.c index 5f4229b3..a259962e 100644 --- a/ecc-ecdsa-verify.c +++ b/ecc-ecdsa-verify.c @@ -108,7 +108,7 @@ ecc_ecdsa_verify (const struct ecc_curve *ecc, /* Compute sinv, use P2 as scratch */ mpn_copyi (sinv + ecc->p.size, sp, ecc->p.size); - ecc_modq_inv (ecc, sinv, sinv + ecc->p.size, P2); + ecc->q.invert (&ecc->q, sinv, sinv + ecc->p.size, P2); /* u2 = r / s, P2 = u2 * Y */ ecc_modq_mul (ecc, u2, rp, sinv); diff --git a/ecc-eh-to-a.c b/ecc-eh-to-a.c index aed176c1..a0182308 100644 --- a/ecc-eh-to-a.c +++ b/ecc-eh-to-a.c @@ -65,7 +65,7 @@ ecc_eh_to_a (const struct ecc_curve *ecc, mpn_copyi (tp, zp, ecc->p.size); /* Needs 3*size scratch */ - ecc_modp_inv (ecc, izp, tp, tp + ecc->p.size); + ecc->p.invert (&ecc->p, izp, tp, tp + ecc->p.size); ecc_modp_mul (ecc, tp, xp, izp); cy = mpn_sub_n (r, tp, ecc->p.m, ecc->p.size); diff --git a/ecc-internal.h b/ecc-internal.h index f8be2647..263b8216 100644 --- a/ecc-internal.h +++ b/ecc-internal.h @@ -49,12 +49,11 @@ #define ecc_modp_submul_1 _nettle_ecc_modp_submul_1 #define ecc_modp_mul _nettle_ecc_modp_mul #define ecc_modp_sqr _nettle_ecc_modp_sqr -#define ecc_modp_inv _nettle_ecc_modp_inv #define ecc_modq_mul _nettle_ecc_modq_mul #define ecc_modq_add _nettle_ecc_modq_add -#define ecc_modq_inv _nettle_ecc_modq_inv #define ecc_modq_random _nettle_ecc_modq_random #define ecc_mod _nettle_ecc_mod +#define ecc_mod_inv _nettle_ecc_mod_inv #define ecc_hash _nettle_ecc_hash #define cnd_copy _nettle_cnd_copy #define sec_add_1 _nettle_sec_add_1 @@ -82,6 +81,10 @@ struct ecc_modulo; modp_mul and modp_sqr. */ typedef void ecc_mod_func (const struct ecc_modulo *m, mp_limb_t *rp); +typedef void ecc_mod_inv_func (const struct ecc_modulo *m, + mp_limb_t *vp, mp_limb_t *ap, + mp_limb_t *scratch); + typedef void ecc_add_func (const struct ecc_curve *ecc, mp_limb_t *r, const mp_limb_t *p, const mp_limb_t *q, @@ -115,9 +118,12 @@ struct ecc_modulo const mp_limb_t *B_shifted; /* m +/- 1, for redc, excluding redc_size low limbs. */ const mp_limb_t *redc_mpm1; + /* (m+1)/2 */ + const mp_limb_t *mp1h; ecc_mod_func *mod; ecc_mod_func *reduce; + ecc_mod_inv_func *invert; }; /* Represents an elliptic curve of the form @@ -156,14 +162,9 @@ struct ecc_curve equivalent Edwards curve. */ const mp_limb_t *edwards_root; - /* (p+1)/2 */ - const mp_limb_t *pp1h; /* For redc, same as Bmodp, otherwise 1. */ const mp_limb_t *unit; - /* (q+1)/2 */ - const mp_limb_t *qp1h; - /* Tables for multiplying by the generator, size determined by k and c. The first 2^c entries are defined by @@ -182,6 +183,8 @@ ecc_mod_func ecc_mod; ecc_mod_func ecc_pp1_redc; ecc_mod_func ecc_pm1_redc; +ecc_mod_inv_func ecc_mod_inv; + void ecc_modp_add (const struct ecc_curve *ecc, mp_limb_t *rp, const mp_limb_t *ap, const mp_limb_t *bp); @@ -209,10 +212,6 @@ void ecc_modp_sqr (const struct ecc_curve *ecc, mp_limb_t *rp, const mp_limb_t *ap); -void -ecc_modp_inv (const struct ecc_curve *ecc, mp_limb_t *rp, mp_limb_t *ap, - mp_limb_t *scratch); - /* mod q operations. */ void ecc_modq_mul (const struct ecc_curve *ecc, mp_limb_t *rp, @@ -222,10 +221,6 @@ ecc_modq_add (const struct ecc_curve *ecc, mp_limb_t *rp, const mp_limb_t *ap, const mp_limb_t *bp); void -ecc_modq_inv (const struct ecc_curve *ecc, mp_limb_t *rp, mp_limb_t *ap, - mp_limb_t *scratch); - -void ecc_modq_random (const struct ecc_curve *ecc, mp_limb_t *xp, void *ctx, nettle_random_func *random, mp_limb_t *scratch); @@ -248,10 +243,6 @@ sec_tabselect (mp_limb_t *rp, mp_size_t rn, const mp_limb_t *table, unsigned tn, unsigned k); -void -sec_modinv (mp_limb_t *vp, mp_limb_t *ap, mp_size_t n, - const mp_limb_t *mp, const mp_limb_t *mp1h, mp_size_t bit_size, - mp_limb_t *scratch); int ecc_25519_sqrt(mp_limb_t *rp, const mp_limb_t *ap); diff --git a/ecc-j-to-a.c b/ecc-j-to-a.c index 91b97e70..8c52eb36 100644 --- a/ecc-j-to-a.c +++ b/ecc-j-to-a.c @@ -77,7 +77,7 @@ ecc_j_to_a (const struct ecc_curve *ecc, mpn_zero (up + ecc->p.size, ecc->p.size); ecc->p.reduce (&ecc->p, up); - ecc_modp_inv (ecc, izp, up, up + ecc->p.size); + ecc->p.invert (&ecc->p, izp, up, up + ecc->p.size); /* Divide this common factor by B */ mpn_copyi (izBp, izp, ecc->p.size); @@ -91,7 +91,7 @@ ecc_j_to_a (const struct ecc_curve *ecc, /* Set s = p_z^{-1}, r_x = p_x s^2, r_y = p_y s^3 */ mpn_copyi (up, p+2*ecc->p.size, ecc->p.size); /* p_z */ - ecc_modp_inv (ecc, izp, up, up + ecc->p.size); + ecc->p.invert (&ecc->p, izp, up, up + ecc->p.size); ecc_modp_sqr (ecc, iz2p, izp); } diff --git a/sec-modinv.c b/ecc-mod-inv.c index 7f80ba85..22e533f2 100644 --- a/sec-modinv.c +++ b/ecc-mod-inv.c @@ -1,6 +1,6 @@ -/* sec-modinv.c +/* ecc-mod-inv.c - Copyright (C) 2013 Niels Möller + Copyright (C) 2013, 2014 Niels Möller This file is part of GNU Nettle. @@ -57,15 +57,19 @@ cnd_neg (int cnd, mp_limb_t *rp, const mp_limb_t *ap, mp_size_t n) /* Compute a^{-1} mod m, with running time depending only on the size. Returns zero if a == 0 (mod m), to be consistent with a^{phi(m)-1}. Also needs (m+1)/2, and m must be odd. */ + +/* FIXME: Could use mpn_sec_invert (in GMP-6), but with a bit more + scratch need since it doesn't precompute (m+1)/2. */ void -sec_modinv (mp_limb_t *vp, mp_limb_t *ap, mp_size_t n, - const mp_limb_t *mp, const mp_limb_t *mp1h, mp_size_t bit_size, - mp_limb_t *scratch) +ecc_mod_inv (const struct ecc_modulo *m, + mp_limb_t *vp, mp_limb_t *ap, + mp_limb_t *scratch) { #define bp scratch #define dp (scratch + n) #define up (scratch + 2*n) + mp_size_t n = m->size; /* Avoid the mp_bitcnt_t type for compatibility with older GMP versions. */ unsigned i; @@ -85,10 +89,10 @@ sec_modinv (mp_limb_t *vp, mp_limb_t *ap, mp_size_t n, up[0] = 1; mpn_zero (up+1, n - 1); - mpn_copyi (bp, mp, n); + mpn_copyi (bp, m->m, n); mpn_zero (vp, n); - for (i = bit_size + GMP_NUMB_BITS * n; i-- > 0; ) + for (i = m->bit_size + GMP_NUMB_BITS * n; i-- > 0; ) { mp_limb_t odd, swap, cy; @@ -146,17 +150,17 @@ sec_modinv (mp_limb_t *vp, mp_limb_t *ap, mp_size_t n, #if 1 cnd_swap (swap, up, vp, n); cy = cnd_sub_n (odd, up, vp, n); - cy -= cnd_add_n (cy, up, mp, n); + cy -= cnd_add_n (cy, up, m->m, n); #else cy = cnd_sub_n (odd, up, vp, n); cnd_add_n (swap, vp, up, n); cnd_neg (swap, up, up, n); - cnd_add_n (cy ^ swap, up, mp, n); + cnd_add_n (cy ^ swap, up, m->p, n); #endif cy = mpn_rshift (ap, ap, n, 1); assert (cy == 0); cy = mpn_rshift (up, up, n, 1); - cy = cnd_add_n (cy, up, mp1h, n); + cy = cnd_add_n (cy, up, m->mp1h, n); assert (cy == 0); } assert ( (ap[0] | ap[n-1]) == 0); @@ -125,11 +125,3 @@ ecc_modp_sqr (const struct ecc_curve *ecc, mp_limb_t *rp, mpn_sqr (rp, ap, ecc->p.size); ecc->p.reduce (&ecc->p, rp); } - -void -ecc_modp_inv (const struct ecc_curve *ecc, mp_limb_t *rp, mp_limb_t *ap, - mp_limb_t *scratch) -{ - sec_modinv (rp, ap, ecc->p.size, ecc->p.m, ecc->pp1h, ecc->p.bit_size, scratch); -} - @@ -59,10 +59,3 @@ ecc_modq_mul (const struct ecc_curve *ecc, mp_limb_t *rp, mpn_mul_n (rp, ap, bp, ecc->q.size); ecc->q.mod (&ecc->q, rp); } - -void -ecc_modq_inv (const struct ecc_curve *ecc, mp_limb_t *rp, mp_limb_t *ap, - mp_limb_t *scratch) -{ - sec_modinv (rp, ap, ecc->q.size, ecc->q.m, ecc->qp1h, ecc->q.bit_size, scratch); -} diff --git a/examples/ecc-benchmark.c b/examples/ecc-benchmark.c index c4bb7f51..0ecf3658 100644 --- a/examples/ecc-benchmark.c +++ b/examples/ecc-benchmark.c @@ -174,7 +174,7 @@ bench_modinv (void *p) { struct ecc_ctx *ctx = (struct ecc_ctx *) p; mpn_copyi (ctx->rp + ctx->ecc->p.size, ctx->ap, ctx->ecc->p.size); - ecc_modp_inv (ctx->ecc, ctx->rp, ctx->rp + ctx->ecc->p.size, ctx->tp); + ctx->ecc->p.invert (&ctx->ecc->p, ctx->rp, ctx->rp + ctx->ecc->p.size, ctx->tp); } #if !NETTLE_USE_MINI_GMP diff --git a/testsuite/ecc-modinv-test.c b/testsuite/ecc-modinv-test.c index 734700c6..8c78c700 100644 --- a/testsuite/ecc-modinv-test.c +++ b/testsuite/ecc-modinv-test.c @@ -58,10 +58,10 @@ test_main (void) /* Check behaviour for zero input */ mpn_zero (a, ecc->p.size); memset (ai, 17, ecc->p.size * sizeof(*ai)); - ecc_modp_inv (ecc, ai, a, scratch); + ecc->p.invert (&ecc->p, ai, a, scratch); if (!mpn_zero_p (ai, ecc->p.size)) { - fprintf (stderr, "ecc_modp_inv failed for zero input (bit size %u):\n", + fprintf (stderr, "ecc->p.invert failed for zero input (bit size %u):\n", ecc->p.bit_size); gmp_fprintf (stderr, "p = %Nx\n" "t = %Nx (bad)\n", @@ -73,10 +73,10 @@ test_main (void) /* Check behaviour for a = p */ mpn_copyi (a, ecc->p.m, ecc->p.size); memset (ai, 17, ecc->p.size * sizeof(*ai)); - ecc_modp_inv (ecc, ai, a, scratch); + ecc->p.invert (&ecc->p, ai, a, scratch); if (!mpn_zero_p (ai, ecc->p.size)) { - fprintf (stderr, "ecc_modp_inv failed for a = p input (bit size %u):\n", + fprintf (stderr, "ecc->p.invert failed for a = p input (bit size %u):\n", ecc->p.bit_size); gmp_fprintf (stderr, "p = %Nx\n" "t = %Nx (bad)\n", @@ -101,10 +101,10 @@ test_main (void) j, ecc->p.bit_size); continue; } - ecc_modp_inv (ecc, ai, a, scratch); + ecc->p.invert (&ecc->p, ai, a, scratch); if (mpn_cmp (ref, ai, ecc->p.size)) { - fprintf (stderr, "ecc_modp_inv failed (test %u, bit size %u):\n", + fprintf (stderr, "ecc->p.invert failed (test %u, bit size %u):\n", j, ecc->p.bit_size); gmp_fprintf (stderr, "a = %Zx\n" "p = %Nx\n" @@ -124,10 +124,10 @@ test_main (void) j, ecc->q.bit_size); continue; } - ecc_modq_inv (ecc, ai, a, scratch); + ecc->q.invert (&ecc->q, ai, a, scratch); if (mpn_cmp (ref, ai, ecc->p.size)) { - fprintf (stderr, "ecc_modq_inv failed (test %u, bit size %u):\n", + fprintf (stderr, "ecc->q.invert failed (test %u, bit size %u):\n", j, ecc->q.bit_size); gmp_fprintf (stderr, "a = %Zx\n" "p = %Nx\n" |