From 3e33071e4a7070aae5a6017cc9b37dada064a531 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Niels=20M=C3=B6ller?= Date: Fri, 15 Feb 2013 11:01:13 +0100 Subject: Integrate ecc_mul_g. --- ChangeLog | 20 +++++ Makefile.in | 6 +- ecc-add-jja.c | 122 +++++++++++++++++++++++++++++ ecc-dup-jj.c | 107 +++++++++++++++++++++++++ ecc-j-to-a.c | 115 +++++++++++++++++++++++++++ ecc-mul-g.c | 103 ++++++++++++++++++++++++ ecc-size.c | 48 ++++++++++++ ecc.h | 191 +++++++++++++++++++++++++++++++++++++++++++++ sec-tabselect.c | 53 +++++++++++++ testsuite/.test-rules.make | 3 + testsuite/Makefile.in | 3 +- testsuite/ecc-mul-g-test.c | 58 ++++++++++++++ testsuite/testutils.c | 126 ++++++++++++++++++++++++++++++ testsuite/testutils.h | 10 +++ 14 files changed, 962 insertions(+), 3 deletions(-) create mode 100644 ecc-add-jja.c create mode 100644 ecc-dup-jj.c create mode 100644 ecc-j-to-a.c create mode 100644 ecc-mul-g.c create mode 100644 ecc-size.c create mode 100644 ecc.h create mode 100644 sec-tabselect.c create mode 100644 testsuite/ecc-mul-g-test.c diff --git a/ChangeLog b/ChangeLog index fc0a9395..79305a9a 100644 --- a/ChangeLog +++ b/ChangeLog @@ -1,5 +1,25 @@ 2013-02-15 Niels Möller + Integrate ecc_mul_g. + * ecc.h: New file. + * ecc-j-to-a.c: New file. + * ecc-size.c: New file. + * ecc-add-jja.c: New file. + * ecc-dup-jj.c: New file. + * ecc-mul-g.c: New file. + * sec-tabselect.c: New file. + * Makefile.in (hogweed_SOURCES): Added new files. + (HEADERS): Added ecc.h + * testsuite/ecc-mul-g-test.c: New file. + * testsuite/Makefile.in (TS_HOGWEED_SOURCES): Added + ecc-mul-g-test.c. + * testsuite/testutils.c (xalloc_limbs): New function. + (test_mpn): New function. + (test_ecc_point): New function. + (test_ecc_mul_a): New function. + (test_ecc_mul_j): New function. + * testsuite/testutils.h: Corresponding declarations. + Integrate ECC internals. * ecc-curve.h: New file. * ecc-internal.h: New file. diff --git a/Makefile.in b/Makefile.in index b6c46920..0d8df181 100644 --- a/Makefile.in +++ b/Makefile.in @@ -127,12 +127,14 @@ hogweed_SOURCES = sexp.c sexp-format.c \ gmp-glue.c cnd-copy.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-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 HEADERS = aes.h arcfour.h arctwo.h asn1.h bignum.h blowfish.h \ base16.h base64.h buffer.h camellia.h cast128.h \ cbc.h ctr.h \ - des.h des-compat.h dsa.h ecc-curve.h \ + des.h des-compat.h dsa.h ecc-curve.h ecc.h \ gcm.h gosthash94.h hmac.h \ knuth-lfib.h \ macros.h \ diff --git a/ecc-add-jja.c b/ecc-add-jja.c new file mode 100644 index 00000000..f358e8ba --- /dev/null +++ b/ecc-add-jja.c @@ -0,0 +1,122 @@ +/* ecc-dup-jj.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" + +/* NOTE: Behaviour for corner cases: + + + p = 0 ==> r = 0 (invalid except if also q = 0) + + + q = 0 ==> r = invalid + + + p = -q ==> r = 0, correct! + + + p = q ==> r = 0, invalid +*/ + +mp_size_t +ecc_add_jja_itch (const struct ecc_curve *ecc) +{ + return ECC_ADD_JJA_ITCH (ecc->size); +} + +void +ecc_add_jja (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#doubling-dbl-2001-b): + + Computation Operation Live variables + + ZZ = Z_1^2 sqr ZZ + H = X_2*ZZ - X_1 mul (djb: U_2) ZZ, H + HH = H^2 sqr ZZ, H, HH + ZZZ = ZZ*Z_1 mul ZZ, H, HH, ZZZ + Z_3 = (Z_1+H)^2-ZZ-HH sqr H, HH, ZZZ + W = 2 (Y_2*ZZZ - Y_1) mul (djb: S_2) H, HH, W + I = 4*HH H, W, I + J = H*I mul W, I, J + V = X_1*I mul W, J, V + X_3 = W^2-J-2*V sqr W, J, V + Y_3 = W*(V-X_3)-2*Y_1*J mul, mul + */ +#define zz scratch +#define h (scratch + ecc->size) +#define hh (scratch + 2*ecc->size) +#define w (scratch + 3*ecc->size) +#define j (scratch + 4*ecc->size) +#define v scratch + +#define x1 p +#define y1 (p + ecc->size) +#define z1 (p + 2*ecc->size) +#define x2 q +#define y2 (q + ecc->size) + + /* zz */ + ecc_modp_sqr (ecc, zz, z1); + /* h*/ + ecc_modp_mul (ecc, h, x2, zz); + ecc_modp_sub (ecc, h, h, x1); + /* hh */ + ecc_modp_sqr (ecc, hh, h); + /* Do z^3 early, store at w. */ + ecc_modp_mul (ecc, w, zz, z1); + /* z_3, use j area for scratch */ + ecc_modp_add (ecc, r + 2*ecc->size, p + 2*ecc->size, h); + ecc_modp_sqr (ecc, j, r + 2*ecc->size); + ecc_modp_sub (ecc, j, j, zz); + ecc_modp_sub (ecc, r + 2*ecc->size, j, hh); + + /* w */ + ecc_modp_mul (ecc, j, y2, w); + ecc_modp_sub (ecc, w, j, y1); + ecc_modp_mul_1 (ecc, w, w, 2); + + /* i replaces hh, j */ + ecc_modp_mul_1 (ecc, hh, hh, 4); + ecc_modp_mul (ecc, j, hh, h); + + /* v */ + ecc_modp_mul (ecc, v, x1, hh); + + /* x_3, use (h, hh) as sqratch */ + ecc_modp_sqr (ecc, h, w); + ecc_modp_sub (ecc, r, h, j); + ecc_modp_submul_1 (ecc, r, v, 2); + + /* y_3, use (h, hh) as sqratch */ + ecc_modp_mul (ecc, h, y1, j); /* frees j */ + ecc_modp_sub (ecc, r + ecc->size, v, r); + ecc_modp_mul (ecc, j, r + ecc->size, w); + ecc_modp_submul_1 (ecc, j, h, 2); + mpn_copyi (r + ecc->size, j, ecc->size); +} diff --git a/ecc-dup-jj.c b/ecc-dup-jj.c new file mode 100644 index 00000000..3c850d70 --- /dev/null +++ b/ecc-dup-jj.c @@ -0,0 +1,107 @@ +/* ecc-dup-jj.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" + +/* NOTE: Behaviour for corner cases: + + + p = 0 ==> r = 0, correct! +*/ +mp_size_t +ecc_dup_jj_itch (const struct ecc_curve *ecc) +{ + return ECC_DUP_JJ_ITCH (ecc->size); +} + +void +ecc_dup_jj (const struct ecc_curve *ecc, + mp_limb_t *r, const mp_limb_t *p, + mp_limb_t *scratch) +{ + /* Formulas (from djb, + http://www.hyperelliptic.org/EFD/g1p/auto-shortw-jacobian-3.html#doubling-dbl-2001-b): + + Computation Operation Live variables + delta = z^2 sqr delta + gamma = y^2 sqr delta, gamma + z' = (y+z)^2-gamma-delta sqr delta, gamma + alpha = 3*(x-delta)*(x+delta) mul gamma, beta, alpha + beta = x*gamma mul gamma, beta, alpha + x' = alpha^2-8*beta sqr gamma, beta, alpha + y' = alpha*(4*beta-x')-8*gamma^2 mul, sqr + */ + +#define delta scratch +#define gamma (scratch + ecc->size) +#define beta (scratch + 2*ecc->size) +#define g2 (scratch + 3*ecc->size) +#define sum (scratch + 4*ecc->size) +#define alpha scratch /* Overlap delta */ + +#define xp p +#define yp (p + ecc->size) +#define zp (p + 2*ecc->size) + + /* delta */ + ecc_modp_sqr (ecc, delta, zp); + + /* gamma */ + ecc_modp_sqr (ecc, gamma, yp); + + /* z'. Can use beta area as scratch. */ + ecc_modp_add (ecc, r + 2*ecc->size, yp, zp); + ecc_modp_sqr (ecc, beta, r + 2*ecc->size); + ecc_modp_sub (ecc, beta, beta, gamma); + ecc_modp_sub (ecc, r + 2*ecc->size, beta, delta); + + /* alpha. Can use beta area as scratch, and overwrite delta. */ + ecc_modp_add (ecc, sum, xp, delta); + ecc_modp_sub (ecc, delta, xp, delta); + ecc_modp_mul (ecc, beta, sum, delta); + ecc_modp_mul_1 (ecc, alpha, beta, 3); + + /* beta */ + ecc_modp_mul (ecc, beta, xp, gamma); + + /* Do gamma^2 and 4*beta early, to get them out of the way. We can + then use the old area at gamma as scratch. */ + ecc_modp_sqr (ecc, g2, gamma); + ecc_modp_mul_1 (ecc, sum, beta, 4); + + /* x' */ + ecc_modp_sqr (ecc, gamma, alpha); /* Overwrites gamma and beta */ + ecc_modp_submul_1 (ecc, gamma, sum, 2); + mpn_copyi (r, gamma, ecc->size); + + /* y' */ + ecc_modp_sub (ecc, sum, sum, r); + ecc_modp_mul (ecc, gamma, sum, alpha); + ecc_modp_submul_1 (ecc, gamma, g2, 8); + mpn_copyi (r + ecc->size, gamma, ecc->size); +} diff --git a/ecc-j-to-a.c b/ecc-j-to-a.c new file mode 100644 index 00000000..ae56bbaf --- /dev/null +++ b/ecc-j-to-a.c @@ -0,0 +1,115 @@ +/* ecc-j-to-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 "ecc.h" +#include "ecc-internal.h" + +mp_size_t +ecc_j_to_a_itch (const struct ecc_curve *ecc) +{ + /* Needs 2*ecc->size + scratch for ecc_modq_inv */ + return ECC_J_TO_A_ITCH (ecc->size); +} + +void +ecc_j_to_a (const struct ecc_curve *ecc, + int flags, + mp_limb_t *r, const mp_limb_t *p, + mp_limb_t *scratch) +{ +#define izp scratch +#define up (scratch + ecc->size) +#define iz2p (scratch + ecc->size) +#define iz3p (scratch + 2*ecc->size) +#define tp scratch + + mp_limb_t cy; + + if (ecc->use_redc) + { + /* Set v = (r_z / B^2)^-1, + + r_x = p_x v^2 / B^3 = ((v/B * v)/B * p_x)/B + r_y = p_y v^3 / B^4 = (((v/B * v)/B * v)/B * p_x)/B + + Skip the first redc, if we want to stay in Montgomery + representation. + */ + + mpn_copyi (up, p + 2*ecc->size, ecc->size); + mpn_zero (up + ecc->size, ecc->size); + ecc->redc (ecc, up); + mpn_zero (up + ecc->size, ecc->size); + ecc->redc (ecc, up); + + ecc_modp_inv (ecc, izp, up, up + ecc->size); + + if (flags & 1) + { + /* Divide this common factor by B */ + mpn_copyi (iz3p, izp, ecc->size); + mpn_zero (iz3p + ecc->size, ecc->size); + ecc->redc (ecc, iz3p); + + ecc_modp_mul (ecc, iz2p, izp, iz3p); + } + else + ecc_modp_sqr (ecc, iz2p, izp); + } + else + { + /* Set s = p_z^{-1}, r_x = p_x s^2, r_y = p_y s^3 */ + + mpn_copyi (up, p+2*ecc->size, ecc->size); /* p_z */ + ecc_modp_inv (ecc, izp, up, up + ecc->size); + + ecc_modp_sqr (ecc, iz2p, izp); + } + + ecc_modp_mul (ecc, iz3p, iz2p, p); + /* ecc_modp (and ecc_modp_mul) may return a value up to 2p - 1, so + do a conditional subtraction. */ + cy = mpn_sub_n (r, iz3p, ecc->p, ecc->size); + cnd_copy (cy, r, iz3p, ecc->size); + + if (flags & 2) + /* Skip y coordinate */ + return; + + ecc_modp_mul (ecc, iz3p, iz2p, izp); + ecc_modp_mul (ecc, tp, iz3p, p + ecc->size); + /* And a similar subtraction. */ + cy = mpn_sub_n (r + ecc->size, tp, ecc->p, ecc->size); + cnd_copy (cy, r + ecc->size, tp, ecc->size); + +#undef izp +#undef up +#undef iz2p +#undef iz3p +#undef tp +} diff --git a/ecc-mul-g.c b/ecc-mul-g.c new file mode 100644 index 00000000..e202e26b --- /dev/null +++ b/ecc-mul-g.c @@ -0,0 +1,103 @@ +/* ecc-mul-g.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 + +#include "ecc.h" +#include "ecc-internal.h" + +mp_size_t +ecc_mul_g_itch (const struct ecc_curve *ecc) +{ + /* Needs 3*ecc->size + scratch for ecc_add_jja. */ + return ECC_MUL_G_ITCH (ecc->size); +} + +void +ecc_mul_g (const struct ecc_curve *ecc, mp_limb_t *r, + const mp_limb_t *np, mp_limb_t *scratch) +{ + /* Scratch need determined by the ecc_add_jja call. Current total is + 9 * ecc->size, at most 648 bytes. */ +#define tp scratch +#define scratch_out (scratch + 3*ecc->size) + + unsigned k, c; + unsigned i, j; + unsigned bit_rows; + + int is_zero; + + k = ecc->pippenger_k; + c = ecc->pippenger_c; + + bit_rows = (ecc->bit_size + k - 1) / k; + + mpn_zero (r, 3*ecc->size); + + for (i = k, is_zero = 1; i-- > 0; ) + { + ecc_dup_jj (ecc, r, r, scratch); + for (j = 0; j * c < bit_rows; j++) + { + unsigned bits; + mp_bitcnt_t bit_index; + + /* Extract c bits from n, stride k, starting at i + kcj, + ending at i + k (cj + c - 1)*/ + for (bits = 0, bit_index = i + k*(c*j+c); bit_index > i + k*c*j; ) + { + mp_size_t limb_index; + unsigned shift; + + bit_index -= k; + + limb_index = bit_index / GMP_NUMB_BITS; + if (limb_index >= ecc->size) + continue; + + shift = bit_index % GMP_NUMB_BITS; + bits = (bits << 1) | ((np[limb_index] >> shift) & 1); + } + sec_tabselect (tp, 2*ecc->size, + (ecc->pippenger_table + + (2*ecc->size * (mp_size_t) j << c)), + 1<size); + cnd_copy (is_zero, r + 2*ecc->size, ecc->unit, ecc->size); + + ecc_add_jja (ecc, tp, r, tp, 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 tp +#undef scratch_out +} diff --git a/ecc-size.c b/ecc-size.c new file mode 100644 index 00000000..c829d460 --- /dev/null +++ b/ecc-size.c @@ -0,0 +1,48 @@ +/* ecc-size.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_size (const struct ecc_curve *ecc) +{ + return ecc->size; +} + +mp_size_t +ecc_size_a (const struct ecc_curve *ecc) +{ + return 2*ecc->size; +} + +mp_size_t +ecc_size_j (const struct ecc_curve *ecc) +{ + return 3*ecc->size; +} diff --git a/ecc.h b/ecc.h new file mode 100644 index 00000000..c65a23ba --- /dev/null +++ b/ecc.h @@ -0,0 +1,191 @@ +/* ecc.h */ + +/* 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. */ + +#ifndef NETTLE_ECC_H_INCLUDED +#define NETTLE_ECC_H_INCLUDED + +#include + +#include + +#ifdef __cplusplus +extern "C" { +#endif + +/* Name mangling */ +#define ecc_size nettle_ecc_size +#define ecc_size_a nettle_ecc_size_a +#define ecc_size_j nettle_ecc_size_j +#define ecc_a_to_a_itch nettle_ecc_a_to_a_itch +#define ecc_a_to_a nettle_ecc_a_to_a +#define ecc_a_to_j nettle_ecc_a_to_j +#define ecc_j_to_a_itch nettle_ecc_j_to_a_itch +#define ecc_j_to_a nettle_ecc_j_to_a +#define ecc_dup_ja_itch nettle_ecc_dup_ja_itch +#define ecc_dup_ja nettle_ecc_dup_ja +#define ecc_dup_jj_itch nettle_ecc_dup_jj_itch +#define ecc_dup_jj nettle_ecc_dup_jj +#define ecc_add_jja_itch nettle_ecc_add_jja_itch +#define ecc_add_jja nettle_ecc_add_jja +#define ecc_add_jjj_itch nettle_ecc_add_jjj_itch +#define ecc_add_jjj nettle_ecc_add_jjj +#define ecc_mul_g_itch nettle_ecc_mul_g_itch +#define ecc_mul_g nettle_ecc_mul_g +#define ecc_mul_a_itch nettle_ecc_mul_a_itch +#define ecc_mul_a nettle_ecc_mul_a + +struct ecc_curve; + +/* 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. + + 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 + coordinates. However, note that most of the ECC functions do *not* + support infinity as an input or output. +*/ + +/* FIXME: Also provided some compile time constants? */ + +/* Returns the size of a single coordinate. */ +mp_size_t +ecc_size (const struct ecc_curve *ecc); + +/* Size of a point, using affine coordinates x, y. */ +mp_size_t +ecc_size_a (const struct ecc_curve *ecc); + +/* Size of a point, using jacobian coordinates X, Y and Z. */ +mp_size_t +ecc_size_j (const struct ecc_curve *ecc); + +/* FIXME: Rename the low-level (and side-channel silent) functions to + _ecc_*, and provide public ecc_* functions which handle the + infinity points properly? */ + +/* Converts the affine coordinates of a point into montgomery form, if + used for this curve. */ +mp_size_t +ecc_a_to_a_itch (const struct ecc_curve *ecc); +void +ecc_a_to_a (const struct ecc_curve *ecc, + mp_limb_t *r, const mp_limb_t *p, + mp_limb_t *scratch); + +/* Converts a point P in affine coordinates into a point R in jacobian + coordinates. If INITIAL is non-zero, and the curve uses montgomery + coordinates, also convert coordinates to montgomery form. */ +void +ecc_a_to_j (const struct ecc_curve *ecc, + int initial, + 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. */ +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, + mp_limb_t *r, const mp_limb_t *p, + mp_limb_t *scratch); + +/* Group operations */ + + +/* Point doubling, with jacobian output and affine input. Corner + cases: Correctly sets R = 0 (r_Z = 0) if p = 0 or 2p = 0. */ +mp_size_t +ecc_dup_ja_itch (const struct ecc_curve *ecc); +void +ecc_dup_ja (const struct ecc_curve *ecc, + mp_limb_t *r, const mp_limb_t *p, + mp_limb_t *scratch); + +/* Point doubling, with jacobian input and output. Corner cases: + Correctly sets R = 0 (r_Z = 0) if p = 0 or 2p = 0. */ +mp_size_t +ecc_dup_jj_itch (const struct ecc_curve *ecc); +void +ecc_dup_jj (const struct ecc_curve *ecc, + mp_limb_t *r, const mp_limb_t *p, + mp_limb_t *scratch); + + +/* Point addition, with jacobian output, one jacobian input and one + affine input. Corner cases: Fails for the cases + + P = Q != 0 Duplication of non-zero point + P = 0, Q != 0 or P != 0, Q = 0 One input zero + + Correctly gives R = 0 if P = Q = 0 or P = -Q. */ +mp_size_t +ecc_add_jja_itch (const struct ecc_curve *ecc); +void +ecc_add_jja (const struct ecc_curve *ecc, + mp_limb_t *r, const mp_limb_t *p, const mp_limb_t *q, + mp_limb_t *scratch); + +/* Point addition with Jacobian input and output. */ +mp_size_t +ecc_add_jjj_itch (const struct ecc_curve *ecc); +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); + + +/* Computes N * the group generator. N is an array of ecc_size() + limbs. It must be in the range 0 < N < group order, then R != 0, + and the algorithm can work without any intermediate values getting + to zero. */ +mp_size_t +ecc_mul_g_itch (const struct ecc_curve *ecc); +void +ecc_mul_g (const struct ecc_curve *ecc, mp_limb_t *r, + const mp_limb_t *np, mp_limb_t *scratch); + +/* Computes N * P. The scalar N is the same as for ecc_mul_g. P is a + non-zero point on the curve, in affine coordinates. Pass a non-zero + INITIAL if the point coordinates have not previously been converted + to Montgomery representation. Output R is a non-zero point, in + Jacobian coordinates. */ +mp_size_t +ecc_mul_a_itch (const struct ecc_curve *ecc); +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); + +#ifdef __cplusplus +} +#endif + +#endif /* NETTLE_ECC_H_INCLUDED */ diff --git a/sec-tabselect.c b/sec-tabselect.c new file mode 100644 index 00000000..f9e3c8c5 --- /dev/null +++ b/sec-tabselect.c @@ -0,0 +1,53 @@ +/* sec-tabselect.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 + +#include "ecc-internal.h" + +/* Copy the k'th element of the table out tn elements, each of size + rn. Always read complete table. Similar to gmp's mpn_tabselect. */ +/* FIXME: Should we need to volatile declare anything? */ +void +sec_tabselect (mp_limb_t *rp, mp_size_t rn, + const mp_limb_t *table, unsigned tn, + unsigned k) +{ + const mp_limb_t *end = table + tn * rn; + const mp_limb_t *p; + mp_size_t i; + + assert (k < tn); + mpn_zero (rp, rn); + for (p = table; p < end; p += rn, k--) + { + mp_limb_t mask = - (mp_limb_t) (k == 0); + for (i = 0; i < rn; i++) + rp[i] += mask & p[i]; + } +} diff --git a/testsuite/.test-rules.make b/testsuite/.test-rules.make index 0f5cb568..5d877316 100644 --- a/testsuite/.test-rules.make +++ b/testsuite/.test-rules.make @@ -169,6 +169,9 @@ ecc-modinv-test$(EXEEXT): ecc-modinv-test.$(OBJEXT) ecc-redc-test$(EXEEXT): ecc-redc-test.$(OBJEXT) $(LINK) ecc-redc-test.$(OBJEXT) $(TEST_OBJS) -o ecc-redc-test$(EXEEXT) +ecc-mul-g-test$(EXEEXT): ecc-mul-g-test.$(OBJEXT) + $(LINK) ecc-mul-g-test.$(OBJEXT) $(TEST_OBJS) -o ecc-mul-g-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 cdfa766b..32f2e9b4 100644 --- a/testsuite/Makefile.in +++ b/testsuite/Makefile.in @@ -35,7 +35,8 @@ TS_HOGWEED_SOURCES = sexp-test.c sexp-format-test.c \ pkcs1-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-mod-test.c ecc-modinv-test.c ecc-redc-test.c \ + ecc-mul-g-test.c TS_SOURCES = $(TS_NETTLE_SOURCES) $(TS_HOGWEED_SOURCES) CXX_SOURCES = cxx-test.cxx diff --git a/testsuite/ecc-mul-g-test.c b/testsuite/ecc-mul-g-test.c new file mode 100644 index 00000000..3c2e63ca --- /dev/null +++ b/testsuite/ecc-mul-g-test.c @@ -0,0 +1,58 @@ +#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_g_itch (ecc)); + + mpn_zero (n, size); + + n[0] = 1; + ecc_mul_g (ecc, p, n, scratch); + ecc_j_to_a (ecc, 1, p, p, scratch); + + if (mpn_cmp (p, ecc->g, 2*size != 0)) + { + fprintf (stderr, "ecc_mul_g with n = 1 failed.\n"); + abort (); + } + + for (n[0] = 2; n[0] <= 4; n[0]++) + { + ecc_mul_g (ecc, p, n, scratch); + test_ecc_mul_j (i, n[0], p); + } + + /* (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); + mpn_sub_n (p + size, ecc->p, p + size, size); + if (mpn_cmp (p, ecc->g, 2*size) != 0) + { + fprintf (stderr, "ecc_mul_g with n = order - 1 failed.\n"); + abort (); + } + + free (n); + free (p); + free (q); + free (scratch); + } + mpz_clear (r); + gmp_randclear (state); +} diff --git a/testsuite/testutils.c b/testsuite/testutils.c index 60614a0e..14d5df29 100644 --- a/testsuite/testutils.c +++ b/testsuite/testutils.c @@ -8,6 +8,7 @@ #include "macros.h" #include "nettle-internal.h" +#include #include #include #include @@ -628,6 +629,12 @@ mpz_togglebit (mpz_t x, unsigned long int bit) #if WITH_HOGWEED +mp_limb_t * +xalloc_limbs (mp_size_t n) +{ + return xalloc (n * sizeof (mp_limb_t)); +} + #define SIGN(key, hash, msg, signature) do { \ hash##_update(&hash, LDATA(msg)); \ ASSERT(rsa_##hash##_sign(key, &hash, signature)); \ @@ -1095,5 +1102,124 @@ const struct ecc_curve * const ecc_curves[] = { NULL }; +static int +test_mpn (const char *ref, const mp_limb_t *xp, mp_size_t n) +{ + mpz_t r; + int res; + + mpz_init_set_str (r, ref, 16); + while (n > 0 && xp[n-1] == 0) + n--; + + res = (_mpz_cmp_limbs (r, xp, n) == 0); + mpz_clear (r); + return res; +} + +struct ecc_ref_point +{ + const char *x; + const char *y; +}; + +static void +test_ecc_point (const struct ecc_curve *ecc, + const struct ecc_ref_point *ref, + const mp_limb_t *p) +{ + if (! (test_mpn (ref->x, p, ecc->size) + && test_mpn (ref->y, p + ecc->size, ecc->size) )) + { + gmp_fprintf (stderr, "Incorrect point!\n" + "got: x = %Nx\n" + " y = %Nx\n" + "ref: x = %s\n" + " y = %s\n", + p, ecc->size, p + ecc->size, ecc->size, + ref->x, ref->y); + abort(); + } +} + +void +test_ecc_mul_a (unsigned curve, unsigned n, const mp_limb_t *p) +{ + /* For each curve, the points 2 g, 3 g and 4 g */ + static const struct ecc_ref_point ref[5][3] = { + { { "dafebf5828783f2ad35534631588a3f629a70fb16982a888", + "dd6bda0d993da0fa46b27bbc141b868f59331afa5c7e93ab" }, + { "76e32a2557599e6edcd283201fb2b9aadfd0d359cbb263da", + "782c37e372ba4520aa62e0fed121d49ef3b543660cfd05fd" }, + { "35433907297cc378b0015703374729d7a4fe46647084e4ba", + "a2649984f2135c301ea3acb0776cd4f125389b311db3be32" } + }, + { { "706a46dc76dcb76798e60e6d89474788d16dc18032d268fd1a704fa6", + "1c2b76a7bc25e7702a704fa986892849fca629487acf3709d2e4e8bb" }, + { "df1b1d66a551d0d31eff822558b9d2cc75c2180279fe0d08fd896d04", + "a3f7f03cadd0be444c0aa56830130ddf77d317344e1af3591981a925" }, + { "ae99feebb5d26945b54892092a8aee02912930fa41cd114e40447301", + "482580a0ec5bc47e88bc8c378632cd196cb3fa058a7114eb03054c9" }, + }, + { { "7cf27b188d034f7e8a52380304b51ac3c08969e277f21b35a60b48fc47669978", + "7775510db8ed040293d9ac69f7430dbba7dade63ce982299e04b79d227873d1" }, + { "5ecbe4d1a6330a44c8f7ef951d4bf165e6c6b721efada985fb41661bc6e7fd6c", + "8734640c4998ff7e374b06ce1a64a2ecd82ab036384fb83d9a79b127a27d5032" }, + { "e2534a3532d08fbba02dde659ee62bd0031fe2db785596ef509302446b030852", + "e0f1575a4c633cc719dfee5fda862d764efc96c3f30ee0055c42c23f184ed8c6" }, + }, + { { "8d999057ba3d2d969260045c55b97f089025959a6f434d651d207d19fb96e9e" + "4fe0e86ebe0e64f85b96a9c75295df61", + "8e80f1fa5b1b3cedb7bfe8dffd6dba74b275d875bc6cc43e904e505f256ab425" + "5ffd43e94d39e22d61501e700a940e80" }, + { "77a41d4606ffa1464793c7e5fdc7d98cb9d3910202dcd06bea4f240d3566da6" + "b408bbae5026580d02d7e5c70500c831", + "c995f7ca0b0c42837d0bbe9602a9fc998520b41c85115aa5f7684c0edc111eac" + "c24abd6be4b5d298b65f28600a2f1df1" }, + { "138251cd52ac9298c1c8aad977321deb97e709bd0b4ca0aca55dc8ad51dcfc9d" + "1589a1597e3a5120e1efd631c63e1835", + "cacae29869a62e1631e8a28181ab56616dc45d918abc09f3ab0e63cf792aa4dc" + "ed7387be37bba569549f1c02b270ed67" }, + }, + { { "43" + "3c219024277e7e682fcb288148c282747403279b1ccc06352c6e5505d769be97" + "b3b204da6ef55507aa104a3a35c5af41cf2fa364d60fd967f43e3933ba6d783d", + "f4" + "bb8cc7f86db26700a7f3eceeeed3f0b5c6b5107c4da97740ab21a29906c42dbb" + "b3e377de9f251f6b93937fa99a3248f4eafcbe95edc0f4f71be356d661f41b02" + }, + { "1a7" + "3d352443de29195dd91d6a64b5959479b52a6e5b123d9ab9e5ad7a112d7a8dd1" + "ad3f164a3a4832051da6bd16b59fe21baeb490862c32ea05a5919d2ede37ad7d", + "13e" + "9b03b97dfa62ddd9979f86c6cab814f2f1557fa82a9d0317d2f8ab1fa355ceec" + "2e2dd4cf8dc575b02d5aced1dec3c70cf105c9bc93a590425f588ca1ee86c0e5" }, + { "35" + "b5df64ae2ac204c354b483487c9070cdc61c891c5ff39afc06c5d55541d3ceac" + "8659e24afe3d0750e8b88e9f078af066a1d5025b08e5a5e2fbc87412871902f3", + "82" + "096f84261279d2b673e0178eb0b4abb65521aef6e6e32e1b5ae63fe2f19907f2" + "79f283e54ba385405224f750a95b85eebb7faef04699d1d9e21f47fc346e4d0d" }, + } + }; + assert (curve < 5); + assert (n >= 2 && n <= 4); + test_ecc_point (ecc_curves[curve], &ref[curve][n-2], p); +} + +void +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); + + test_ecc_mul_a (curve, n, np); + + free (np); + free (scratch); +} + #endif /* WITH_HOGWEED */ diff --git a/testsuite/testutils.h b/testsuite/testutils.h index ed57b33e..14aa794d 100644 --- a/testsuite/testutils.h +++ b/testsuite/testutils.h @@ -19,6 +19,7 @@ # include "rsa.h" # include "dsa.h" # include "ecc-curve.h" +# include "ecc.h" # include "ecc-internal.h" # include "gmp-glue.h" #endif @@ -150,6 +151,9 @@ test_armor(const struct nettle_armor *armor, const uint8_t *ascii); #if WITH_HOGWEED +mp_limb_t * +xalloc_limbs (mp_size_t n); + void test_rsa_set_key_1(struct rsa_public_key *pub, struct rsa_private_key *key); @@ -195,6 +199,12 @@ test_dsa_key(struct dsa_public_key *pub, extern const struct ecc_curve * const ecc_curves[]; +void +test_ecc_mul_a (unsigned curve, unsigned n, const mp_limb_t *p); + +void +test_ecc_mul_j (unsigned curve, unsigned n, const mp_limb_t *p); + #endif /* WITH_HOGWEED */ /* LDATA needs to handle NUL characters. */ -- cgit v1.2.1