diff options
| -rw-r--r-- | ChangeLog | 9 | ||||
| -rw-r--r-- | Makefile.in | 5 | ||||
| -rw-r--r-- | ecc-a-to-j.c | 51 | ||||
| -rw-r--r-- | ecc-add-jjj.c | 118 | ||||
| -rw-r--r-- | ecc-mul-a.c | 181 | ||||
| -rw-r--r-- | testsuite/.test-rules.make | 3 | ||||
| -rw-r--r-- | testsuite/Makefile.in | 2 | ||||
| -rw-r--r-- | testsuite/ecc-mul-a-test.c | 102 |
8 files changed, 468 insertions, 3 deletions
@@ -1,5 +1,14 @@ 2013-02-15 Niels Möller <nisse@lysator.liu.se> + Integrate ecc_mul_a. + * ecc-a-to-j.c: New file. + * ecc-add-jjj.c: New file. + * ecc-mul-a.c: New file. + * Makefile.in (hogweed_SOURCES): Added new files. + * testsuite/ecc-mul-a-test.c: New file. + * testsuite/Makefile.in (TS_HOGWEED_SOURCES): Added + ecc-mul-a-test.c. + * testsuite/testutils.c: Removed redundant includes. (die): New function. diff --git a/Makefile.in b/Makefile.in index 0d8df181..c9fe3f12 100644 --- a/Makefile.in +++ b/Makefile.in @@ -128,8 +128,9 @@ hogweed_SOURCES = sexp.c sexp-format.c \ ecc-mod.c ecc-generic-modp.c ecc-generic-modq.c \ ecc-modp.c ecc-modq.c ecc-generic-redc.c \ ecc-192.c ecc-224.c ecc-256.c ecc-384.c ecc-521.c \ - ecc-size.c ecc-j-to-a.c ecc-dup-jj.c ecc-add-jja.c \ - ecc-mul-g.c + ecc-size.c ecc-j-to-a.c ecc-a-to-j.c \ + ecc-dup-jj.c ecc-add-jja.c ecc-add-jjj.c \ + ecc-mul-g.c ecc-mul-a.c HEADERS = aes.h arcfour.h arctwo.h asn1.h bignum.h blowfish.h \ base16.h base64.h buffer.h camellia.h cast128.h \ diff --git a/ecc-a-to-j.c b/ecc-a-to-j.c new file mode 100644 index 00000000..5fbc0a88 --- /dev/null +++ b/ecc-a-to-j.c @@ -0,0 +1,51 @@ +/* ecc-a-to-j.c */ + +/* nettle, low-level cryptographics library + * + * Copyright (C) 2013 Niels Möller + * + * The nettle library is free software; you can redistribute it and/or modify + * it under the terms of the GNU Lesser General Public License as published by + * the Free Software Foundation; either version 2.1 of the License, or (at your + * option) any later version. + * + * The nettle library is distributed in the hope that it will be useful, but + * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY + * or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public + * License for more details. + * + * You should have received a copy of the GNU Lesser General Public License + * along with the nettle library; see the file COPYING.LIB. If not, write to + * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, + * MA 02111-1301, USA. + */ + +/* Development of Nettle's ECC support was funded by Internetfonden. */ + +#if HAVE_CONFIG_H +# include "config.h" +#endif + +#include "ecc.h" +#include "ecc-internal.h" + +void +ecc_a_to_j (const struct ecc_curve *ecc, + int initial, + mp_limb_t *r, const mp_limb_t *p) +{ + if (ecc->use_redc && initial) + { + mpn_copyd (r + ecc->size, p, 2*ecc->size); + + mpn_zero (r, ecc->size); + ecc->modp (ecc, r); + + mpn_zero (r + ecc->size, ecc->size); + ecc->modp (ecc, r + ecc->size); + } + else if (r != p) + mpn_copyi (r, p, 2*ecc->size); + + mpn_copyi (r + 2*ecc->size, ecc->unit, ecc->size); +} diff --git a/ecc-add-jjj.c b/ecc-add-jjj.c new file mode 100644 index 00000000..e0506375 --- /dev/null +++ b/ecc-add-jjj.c @@ -0,0 +1,118 @@ +/* ecc-add-jjj.c */ + +/* nettle, low-level cryptographics library + * + * Copyright (C) 2013 Niels Möller + * + * The nettle library is free software; you can redistribute it and/or modify + * it under the terms of the GNU Lesser General Public License as published by + * the Free Software Foundation; either version 2.1 of the License, or (at your + * option) any later version. + * + * The nettle library is distributed in the hope that it will be useful, but + * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY + * or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public + * License for more details. + * + * You should have received a copy of the GNU Lesser General Public License + * along with the nettle library; see the file COPYING.LIB. If not, write to + * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, + * MA 02111-1301, USA. + */ + +/* Development of Nettle's ECC support was funded by Internetfonden. */ + +#if HAVE_CONFIG_H +# include "config.h" +#endif + +#include "ecc.h" +#include "ecc-internal.h" + +mp_size_t +ecc_add_jjj_itch (const struct ecc_curve *ecc) +{ + /* Needs 8 * ecc->size */ + return ECC_ADD_JJJ_ITCH (ecc->size); +} + +void +ecc_add_jjj (const struct ecc_curve *ecc, + mp_limb_t *r, const mp_limb_t *p, const mp_limb_t *q, + mp_limb_t *scratch) +{ + /* Formulas, from djb, + http://www.hyperelliptic.org/EFD/g1p/auto-shortw-jacobian-3.html#addition-add-2007-bl: + + Computation Operation Live variables + + Z1Z1 = Z1^2 sqr Z1Z1 + Z2Z2 = Z2^2 sqr Z1Z1, Z2Z2 + U1 = X1*Z2Z2 mul Z1Z1, Z2Z2, U1 + U2 = X2*Z1Z1 mul Z1Z1, Z2Z2, U1, U2 + H = U2-U1 Z1Z1, Z2Z2, U1, H + Z3 = ((Z1+Z2)^2-Z1Z1-Z2Z2)*H sqr, mul Z1Z1, Z2Z2, U1, H + S1 = Y1*Z2*Z2Z2 mul, mul Z1Z1, U1, H, S1 + S2 = Y2*Z1*Z1Z1 mul, mul U1, H, S1, S2 + W = 2*(S2-S1) (djb: r) U1, H, S1, W + I = (2*H)^2 sqr U1, H, S1, W, I + J = H*I mul U1, S1, W, J, V + V = U1*I mul S1, W, J, V + X3 = W^2-J-2*V sqr S1, W, J, V + Y3 = W*(V-X3)-2*S1*J mul, mul + */ + mp_limb_t *z1z1 = scratch; + mp_limb_t *z2z2 = scratch + ecc->size; + mp_limb_t *u1 = scratch + 2*ecc->size; + mp_limb_t *u2 = scratch + 3*ecc->size; + mp_limb_t *s1 = scratch; /* overlap z1z1 */ + mp_limb_t *s2 = scratch + ecc->size; /* overlap z2z2 */ + mp_limb_t *i = scratch + 4*ecc->size; + mp_limb_t *j = scratch + 5*ecc->size; + mp_limb_t *v = scratch + 6*ecc->size; + + /* z1^2, z2^2, u1 = x1 x2^2, u2 = x2 z1^2 - u1 */ + ecc_modp_sqr (ecc, z1z1, p + 2*ecc->size); + ecc_modp_sqr (ecc, z2z2, q + 2*ecc->size); + ecc_modp_mul (ecc, u1, p, z2z2); + ecc_modp_mul (ecc, u2, q, z1z1); + ecc_modp_sub (ecc, u2, u2, u1); /* Store h in u2 */ + + /* z3, use i, j, v as scratch, result at i. */ + ecc_modp_add (ecc, i, p + 2*ecc->size, q + 2*ecc->size); + ecc_modp_sqr (ecc, v, i); + ecc_modp_sub (ecc, v, v, z1z1); + ecc_modp_sub (ecc, v, v, z2z2); + ecc_modp_mul (ecc, i, v, u2); + /* Delayed write, to support in-place operation. */ + + /* s1 = y1 z2^3, s2 = y2 z1^3, scratch at j and v */ + ecc_modp_mul (ecc, j, z1z1, p + 2*ecc->size); /* z1^3 */ + ecc_modp_mul (ecc, v, z2z2, q + 2*ecc->size); /* z2^3 */ + ecc_modp_mul (ecc, s1, p + ecc->size, v); + ecc_modp_mul (ecc, v, j, q + ecc->size); + ecc_modp_sub (ecc, s2, v, s1); + ecc_modp_mul_1 (ecc, s2, s2, 2); + + /* Store z3 */ + mpn_copyi (r + 2*ecc->size, i, ecc->size); + + /* i, j, v */ + ecc_modp_sqr (ecc, i, u2); + ecc_modp_mul_1 (ecc, i, i, 4); + ecc_modp_mul (ecc, j, u2, i); + ecc_modp_mul (ecc, v, u1, i); + + /* now, u1, u2 and i are free for reuse .*/ + /* x3, use u1, u2 as scratch */ + ecc_modp_sqr (ecc, u1, s2); + ecc_modp_sub (ecc, r, u1, j); + ecc_modp_submul_1 (ecc, r, v, 2); + + /* y3 */ + ecc_modp_mul (ecc, u1, s1, j); /* Frees j */ + ecc_modp_sub (ecc, u2, v, r); /* Frees v */ + ecc_modp_mul (ecc, i, s2, u2); + ecc_modp_submul_1 (ecc, i, u1, 2); + mpn_copyi (r + ecc->size, i, ecc->size); +} diff --git a/ecc-mul-a.c b/ecc-mul-a.c new file mode 100644 index 00000000..0b347162 --- /dev/null +++ b/ecc-mul-a.c @@ -0,0 +1,181 @@ +/* ecc-mul-a.c */ + +/* nettle, low-level cryptographics library + * + * Copyright (C) 2013 Niels Möller + * + * The nettle library is free software; you can redistribute it and/or modify + * it under the terms of the GNU Lesser General Public License as published by + * the Free Software Foundation; either version 2.1 of the License, or (at your + * option) any later version. + * + * The nettle library is distributed in the hope that it will be useful, but + * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY + * or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public + * License for more details. + * + * You should have received a copy of the GNU Lesser General Public License + * along with the nettle library; see the file COPYING.LIB. If not, write to + * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, + * MA 02111-1301, USA. + */ + +/* Development of Nettle's ECC support was funded by Internetfonden. */ + +#if HAVE_CONFIG_H +# include "config.h" +#endif + +#include <assert.h> + +#include "ecc.h" +#include "ecc-internal.h" + +mp_size_t +ecc_mul_a_itch (const struct ecc_curve *ecc) +{ + /* Binary algorithm needs 6*ecc->size + scratch for ecc_add_jja. + Current total is 12 ecc->size, at most 864 bytes. + + Window algorithm needs (3<<w) * ecc->size for the table, + 3*ecc->size for a temporary point, and scratch for + ecc_add_jjj. */ + return ECC_MUL_A_ITCH (ecc->size); +} + +#if ECC_MUL_A_WBITS == 0 +void +ecc_mul_a (const struct ecc_curve *ecc, + int initial, mp_limb_t *r, + const mp_limb_t *np, const mp_limb_t *p, + mp_limb_t *scratch) +{ +#define tp scratch +#define pj (scratch + 3*ecc->size) +#define scratch_out (scratch + 6*ecc->size) + + int is_zero; + + unsigned i; + + ecc_a_to_j (ecc, initial, pj, p); + mpn_zero (r, 3*ecc->size); + + for (i = ecc->size, is_zero = 1; i-- > 0; ) + { + mp_limb_t w = np[i]; + mp_limb_t bit; + + for (bit = (mp_limb_t) 1 << (GMP_NUMB_BITS - 1); + bit > 0; + bit >>= 1) + { + int digit; + + ecc_dup_jj (ecc, r, r, scratch_out); + ecc_add_jja (ecc, tp, r, pj, scratch_out); + + digit = (w & bit) > 0; + /* If is_zero is set, r is the zero point, + and ecc_add_jja produced garbage. */ + cnd_copy (is_zero, tp, pj, 3*ecc->size); + is_zero &= ~digit; + /* If we had a one-bit, use the sum. */ + cnd_copy (digit, r, tp, 3*ecc->size); + } + } +} +#else /* ECC_MUL_A_WBITS > 1 */ + +#define TABLE_SIZE (1U << ECC_MUL_A_WBITS) +#define TABLE_MASK (TABLE_SIZE - 1) + +#define TABLE(j) (table + (j) * 3*ecc->size) + +static void +table_init (const struct ecc_curve *ecc, + mp_limb_t *table, unsigned bits, + int initial, const mp_limb_t *p, + mp_limb_t *scratch) +{ + unsigned size = 1 << bits; + unsigned j; + + mpn_zero (TABLE(0), 3*ecc->size); + ecc_a_to_j (ecc, initial, TABLE(1), p); + + for (j = 2; j < size; j += 2) + { + ecc_dup_jj (ecc, TABLE(j), TABLE(j/2), scratch); + ecc_add_jja (ecc, TABLE(j+1), TABLE(j), TABLE(1), scratch); + } +} + +void +ecc_mul_a (const struct ecc_curve *ecc, + int initial, mp_limb_t *r, + const mp_limb_t *np, const mp_limb_t *p, + mp_limb_t *scratch) +{ +#define tp scratch +#define table (scratch + 3*ecc->size) + mp_limb_t *scratch_out = table + (3*ecc->size << ECC_MUL_A_WBITS); + int is_zero = 0; + + mp_bitcnt_t blocks = (ecc->bit_size + ECC_MUL_A_WBITS - 1) / ECC_MUL_A_WBITS; + mp_bitcnt_t bit_index = (blocks-1) * ECC_MUL_A_WBITS; + + mp_size_t limb_index = bit_index / GMP_NUMB_BITS; + unsigned shift = bit_index % GMP_NUMB_BITS; + mp_limb_t w, bits; + + table_init (ecc, table, ECC_MUL_A_WBITS, initial, p, scratch_out); + + w = np[limb_index]; + bits = w >> shift; + if (limb_index < ecc->size - 1) + bits |= np[limb_index + 1] << (GMP_NUMB_BITS - shift); + + assert (bits < TABLE_SIZE); + + sec_tabselect (r, 3*ecc->size, table, TABLE_SIZE, bits); + is_zero = (bits == 0); + + for (;;) + { + unsigned j; + if (shift >= ECC_MUL_A_WBITS) + { + shift -= ECC_MUL_A_WBITS; + bits = w >> shift; + } + else + { + if (limb_index == 0) + { + assert (shift == 0); + break; + } + bits = w << (ECC_MUL_A_WBITS - shift); + w = np[--limb_index]; + shift = shift + GMP_NUMB_BITS - ECC_MUL_A_WBITS; + bits |= w >> shift; + } + for (j = 0; j < ECC_MUL_A_WBITS; j++) + ecc_dup_jj (ecc, r, r, scratch_out); + + bits &= TABLE_MASK; + sec_tabselect (tp, 3*ecc->size, table, TABLE_SIZE, bits); + cnd_copy (is_zero, r, tp, 3*ecc->size); + ecc_add_jjj (ecc, tp, tp, r, scratch_out); + + /* Use the sum when valid. ecc_add_jja produced garbage if + is_zero != 0 or bits == 0, . */ + cnd_copy (bits & (is_zero - 1), r, tp, 3*ecc->size); + is_zero &= (bits == 0); + } +#undef table +#undef tp +} + +#endif /* ECC_MUL_A_WBITS > 1 */ diff --git a/testsuite/.test-rules.make b/testsuite/.test-rules.make index 5d877316..fdd2c768 100644 --- a/testsuite/.test-rules.make +++ b/testsuite/.test-rules.make @@ -172,6 +172,9 @@ ecc-redc-test$(EXEEXT): ecc-redc-test.$(OBJEXT) ecc-mul-g-test$(EXEEXT): ecc-mul-g-test.$(OBJEXT) $(LINK) ecc-mul-g-test.$(OBJEXT) $(TEST_OBJS) -o ecc-mul-g-test$(EXEEXT) +ecc-mul-a-test$(EXEEXT): ecc-mul-a-test.$(OBJEXT) + $(LINK) ecc-mul-a-test.$(OBJEXT) $(TEST_OBJS) -o ecc-mul-a-test$(EXEEXT) + sha1-huge-test$(EXEEXT): sha1-huge-test.$(OBJEXT) $(LINK) sha1-huge-test.$(OBJEXT) $(TEST_OBJS) -o sha1-huge-test$(EXEEXT) diff --git a/testsuite/Makefile.in b/testsuite/Makefile.in index 32f2e9b4..c8db7657 100644 --- a/testsuite/Makefile.in +++ b/testsuite/Makefile.in @@ -36,7 +36,7 @@ TS_HOGWEED_SOURCES = sexp-test.c sexp-format-test.c \ rsa-test.c rsa-encrypt-test.c rsa-keygen-test.c \ dsa-test.c dsa-keygen-test.c \ ecc-mod-test.c ecc-modinv-test.c ecc-redc-test.c \ - ecc-mul-g-test.c + ecc-mul-g-test.c ecc-mul-a-test.c TS_SOURCES = $(TS_NETTLE_SOURCES) $(TS_HOGWEED_SOURCES) CXX_SOURCES = cxx-test.cxx diff --git a/testsuite/ecc-mul-a-test.c b/testsuite/ecc-mul-a-test.c new file mode 100644 index 00000000..c3306b84 --- /dev/null +++ b/testsuite/ecc-mul-a-test.c @@ -0,0 +1,102 @@ +#include "testutils.h" + +void +test_main (void) +{ + gmp_randstate_t state; + mpz_t r; + unsigned i; + + gmp_randinit_default (state); + mpz_init (r); + + for (i = 0; ecc_curves[i]; i++) + { + const struct ecc_curve *ecc = ecc_curves[i]; + mp_size_t size = ecc_size (ecc); + mp_limb_t *p = xalloc_limbs (ecc_size_j (ecc)); + mp_limb_t *q = xalloc_limbs (ecc_size_j (ecc)); + mp_limb_t *n = xalloc_limbs (size); + mp_limb_t *scratch = xalloc_limbs (ecc_mul_a_itch (ecc)); + unsigned j; + + mpn_zero (n, size); + + n[0] = 1; + ecc_mul_a (ecc, 1, p, n, ecc->g, scratch); + ecc_j_to_a (ecc, 1, 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); + + if (ecc->use_redc) + { + ecc_mul_a (ecc, 0, p, n, ecc->redc_g, scratch); + ecc_j_to_a (ecc, 1, p, p, scratch); + + if (mpn_cmp (p, ecc->g, 2*size != 0)) + die ("curve %d: ecc_mul_a with n = 1 and redc failed.\n", ecc->bit_size); + } + for (n[0] = 2; n[0] <= 4; n[0]++) + { + ecc_mul_a (ecc, 1, p, n, ecc->g, scratch); + test_ecc_mul_j (i, n[0], p); + if (ecc->use_redc) + { + ecc_mul_a (ecc, 0, p, n, ecc->redc_g, scratch); + test_ecc_mul_j (i, n[0], p); + } + } + + /* (order - 1) * g = - g */ + mpn_sub_1 (n, ecc->q, size, 1); + ecc_mul_a (ecc, 1, p, n, ecc->g, scratch); + ecc_j_to_a (ecc, 1, p, p, scratch); + mpn_sub_n (p + size, ecc->p, p + size, size); + if (mpn_cmp (p, ecc->g, 2*size) != 0) + { + fprintf (stderr, "ecc_mul_a with n = order - 1 failed.\n"); + abort (); + } + + mpn_zero (n, size); + + for (j = 0; j < 100; j++) + { + if (j & 1) + mpz_rrandomb (r, state, size * GMP_NUMB_BITS); + else + mpz_urandomb (r, state, size * GMP_NUMB_BITS); + + /* Reduce so that (almost surely) n < q */ + _mpz_copy_limbs (n, r, size); + n[size - 1] %= ecc->q[size - 1]; + + ecc_mul_a (ecc, 1, p, n, ecc->g, scratch); + ecc_j_to_a (ecc, 1, p, p, scratch); + + ecc_mul_g (ecc, q, n, scratch); + ecc_j_to_a (ecc, 1, q, q, scratch); + + if (mpn_cmp (p, q, 2*size)) + { + gmp_fprintf (stderr, + "Different results from ecc_mul_a and ecc_mul_g.\n" + " bits = %u\n" + " n = %Nx\n", + ecc->bit_size, n, size); + gmp_fprintf (stderr, "p = %Nx,\n %Nx\n", + p, size, p + size, size); + gmp_fprintf (stderr, "q = %Nx,\n %Nx\n", + q, size, q + size, size); + abort (); + } + } + free (n); + free (p); + free (q); + free (scratch); + } + mpz_clear (r); + gmp_randclear (state); +} |