diff options
-rw-r--r-- | ChangeLog | 15 | ||||
-rw-r--r-- | Makefile.in | 7 | ||||
-rw-r--r-- | ecc-ecdsa-sign.c | 97 | ||||
-rw-r--r-- | ecc-ecdsa-verify.c | 150 | ||||
-rw-r--r-- | ecc-hash.c | 55 | ||||
-rw-r--r-- | ecc-internal.h | 22 | ||||
-rw-r--r-- | ecc-point.c | 90 | ||||
-rw-r--r-- | ecc-random.c | 90 | ||||
-rw-r--r-- | ecc-scalar.c | 62 | ||||
-rw-r--r-- | ecc.h | 68 | ||||
-rw-r--r-- | ecdsa-sign.c | 63 | ||||
-rw-r--r-- | ecdsa-verify.c | 68 | ||||
-rw-r--r-- | ecdsa.h | 94 |
13 files changed, 874 insertions, 7 deletions
@@ -1,5 +1,20 @@ 2013-02-18 Niels Möller <nisse@lysator.liu.se> + * ecc-point.c: New file, struct ecc_point abstraction. + * ecc-scalar.c: New file, struct ecc_scalar abstraction. + * ecc-random.c (ecc_modq_random, ecc_scalar_random): New file, new + functions. + * ecc-hash.c (ecc_hash): New file and function. + * ecc-ecdsa-sign.c: New file, low-level signing interface. + * ecc-ecdsa-verify.c: New file, low-level ecdsa verify. + * ecdsa-sign.c: (ecdsa_sign): New file and function. + * ecdsa-verify.c (ecdsa_verify): New file and function. + * ecdsa.h: New header file. + * ecc.h: Declare ecc_point and ecc_scalar functions. + * ecc-internal.h: Added declarations. + * Makefile.in (hogweed_SOURCES): Added new source files. + (HEADERS): Added ecdsa.h. + * gmp-glue.c (_mpz_set_mpn): New convenience function. (_mpn_set_base256): New function. (_gmp_alloc_limbs): New function. diff --git a/Makefile.in b/Makefile.in index c9fe3f12..958278df 100644 --- a/Makefile.in +++ b/Makefile.in @@ -130,12 +130,15 @@ hogweed_SOURCES = sexp.c sexp-format.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-a-to-j.c \ ecc-dup-jj.c ecc-add-jja.c ecc-add-jjj.c \ - ecc-mul-g.c ecc-mul-a.c + ecc-mul-g.c ecc-mul-a.c ecc-hash.c ecc-random.c \ + ecc-point.c ecc-scalar.c \ + ecc-ecdsa-sign.c ecdsa-sign.c \ + ecc-ecdsa-verify.c ecdsa-verify.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 ecc.h \ + des.h des-compat.h dsa.h ecc-curve.h ecc.h ecdsa.h \ gcm.h gosthash94.h hmac.h \ knuth-lfib.h \ macros.h \ diff --git a/ecc-ecdsa-sign.c b/ecc-ecdsa-sign.c new file mode 100644 index 00000000..e85c325c --- /dev/null +++ b/ecc-ecdsa-sign.c @@ -0,0 +1,97 @@ +/* ecc-ecdsa-sign.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 <stdlib.h> + +#include "ecdsa.h" +#include "ecc-internal.h" + +/* Low-level ECDSA signing */ + +mp_size_t +ecc_ecdsa_sign_itch (const struct ecc_curve *ecc) +{ + /* Needs 3*ecc->size + scratch for ecc_mul_g. */ + return ECC_ECDSA_SIGN_ITCH (ecc->size); +} + +/* NOTE: Caller should check if r or s is zero. */ +void +ecc_ecdsa_sign (const struct ecc_curve *ecc, + const mp_limb_t *zp, + /* Random nonce, must be invertible mod ecc group + order. */ + const mp_limb_t *kp, + unsigned length, const uint8_t *digest, + mp_limb_t *rp, mp_limb_t *sp, + mp_limb_t *scratch) +{ + mp_limb_t cy; +#define P scratch +#define kinv scratch /* Needs 5*ecc->size for computation */ +#define hp (scratch + ecc->size) /* NOTE: ecc->size + 1 limbs! */ +#define tp (scratch + 2*ecc->size) + /* Procedure, according to RFC 6090, "KT-I". q denotes the group + order. + + 1. k <-- uniformly random, 0 < k < q + + 2. R <-- (r_x, r_y) = k g + + 3. s1 <-- r_x mod q + + 4. s2 <-- (h + z*s1)/k mod q. + */ + + 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); + + /* Invert k, uses 5 * ecc->size including scratch */ + mpn_copyi (hp, kp, ecc->size); + ecc_modq_inv (ecc, kinv, hp, tp); + + /* Process hash digest */ + ecc_hash (ecc, hp, length, digest); + + ecc_modq_mul (ecc, tp, zp, rp); + ecc_modq_add (ecc, hp, hp, tp); + ecc_modq_mul (ecc, tp, hp, kinv); + + mpn_copyi (sp, tp, ecc->size); +#undef P +#undef hp +#undef kinv +#undef tp +} diff --git a/ecc-ecdsa-verify.c b/ecc-ecdsa-verify.c new file mode 100644 index 00000000..57bbb9b3 --- /dev/null +++ b/ecc-ecdsa-verify.c @@ -0,0 +1,150 @@ +/* ecc-ecdsa-verify.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 <stdlib.h> + +#include "ecdsa.h" +#include "ecc-internal.h" + +/* Low-level ECDSA verify */ + +static int +zero_p (const mp_limb_t *xp, mp_size_t n) +{ + while (n > 0) + if (xp[--n] > 0) + return 0; + return 1; +} + +static int +ecdsa_in_range (const struct ecc_curve *ecc, const mp_limb_t *xp) +{ + return !zero_p (xp, ecc->size) + && mpn_cmp (xp, ecc->q, ecc->size) < 0; +} + +mp_size_t +ecc_ecdsa_verify_itch (const struct ecc_curve *ecc) +{ + /* Largest storage need is for the ecc_mul_a call, 6 * ecc->size + + ECC_MUL_A_ITCH (size) */ + return ECC_ECDSA_VERIFY_ITCH (ecc->size); +} + +/* FIXME: Use faster primitives, not requiring side-channel silence. */ +int +ecc_ecdsa_verify (const struct ecc_curve *ecc, + const mp_limb_t *pp, /* Public key */ + unsigned length, const uint8_t *digest, + const mp_limb_t *rp, const mp_limb_t *sp, + mp_limb_t *scratch) +{ + /* Procedure, according to RFC 6090, "KT-I". q denotes the group + order. + + 1. Check 0 < r, s < q. + + 2. s' <-- s^{-1} (mod q) + + 3. u1 <-- h * s' (mod q) + + 4. u2 <-- r * s' (mod q) + + 5. R = u1 G + u2 Y + + 6. Signature is valid if R_x = r (mod q). + */ + +#define P2 scratch +#define P1 (scratch + 3*ecc->size) +#define sinv (scratch + 3*ecc->size) +#define u2 (scratch + 4*ecc->size) +#define hp (scratch + 4*ecc->size) +#define u1 (scratch + 6*ecc->size) + + if (! (ecdsa_in_range (ecc, rp) + && ecdsa_in_range (ecc, sp))) + return 0; + + /* FIXME: Micro optimizations: Either simultaneous multiplication. + Or convert to projective coordinates (can be done without + division, I think), and write an ecc_add_ppp. */ + + /* Compute sinv, use P2 as scratch */ + mpn_copyi (sinv + ecc->size, sp, ecc->size); + ecc_modq_inv (ecc, sinv, sinv + ecc->size, P2); + + /* u2 = r / s, P2 = u2 * Y */ + ecc_modq_mul (ecc, u2, rp, sinv); + + /* Total storage: 5*ecc->size + ECC_MUL_A_ITCH (ecc->size) */ + ecc_mul_a (ecc, 1, P2, u2, pp, u2 + ecc->size); + + /* u1 = h / s, P1 = u1 * G */ + ecc_hash (ecc, hp, length, digest); + ecc_modq_mul (ecc, u1, hp, sinv); + + /* u = 0 can happen only if h = 0 or h = q, which is extremely + unlikely. */ + if (!zero_p (u1, ecc->size)) + { + /* Total storage: 6*ecc->size + ECC_MUL_G_ITCH (ecc->size) */ + ecc_mul_g (ecc, P1, u1, u1 + ecc->size); + + /* NOTE: ecc_add_jjj and/or ecc_j_to_a will produce garbage in + case u1 G = +/- u2 V. However, anyone who gets his or her + hands on a signature where this happens during verification, + can also get the private key as z = +/- u1 / u_2 (mod q). And + then it doesn't matter very much if verification of + signatures with that key succeeds or fails. + + u1 G = - u2 V can never happen for a correctly generated + signature, since it implies k = 0. + + u1 G = u2 V is possible, if we are unlucky enough to get h / + s_1 = z. Hitting that is about as unlikely as finding the + private key by guessing. + */ + /* 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); + + return (mpn_cmp (rp, P2, ecc->size) == 0); +#undef P2 +#undef P1 +#undef sinv +#undef u2 +#undef hp +#undef u1 +} diff --git a/ecc-hash.c b/ecc-hash.c new file mode 100644 index 00000000..0de3c187 --- /dev/null +++ b/ecc-hash.c @@ -0,0 +1,55 @@ +/* ecdsa-hash.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-internal.h" +#include "gmp-glue.h" + +/* Convert hash value to an integer. If the digest is larger than + the ecc bit size, then we must truncate it and use the leftmost + bits. */ + +/* NOTE: We don't considered the hash value to be secret, so it's ok + if the running time of this conversion depends on h. + + Requires ecc->size + 1 limbs, the extra limb may be needed for + unusual limb sizes. +*/ +void +ecc_hash (const struct ecc_curve *ecc, + mp_limb_t *hp, + unsigned length, const uint8_t *digest) +{ + if (length > ((unsigned) ecc->bit_size + 7) / 8) + length = (ecc->bit_size + 7) / 8; + + _mpn_set_base256 (hp, ecc->size + 1, digest, length); + + if (8 * length > ecc->bit_size) + /* We got a few extra bits, at the low end. Discard them. */ + mpn_rshift (hp, hp, ecc->size + 1, 8*length - ecc->bit_size); +} diff --git a/ecc-internal.h b/ecc-internal.h index a6b3fae4..0df8c9e1 100644 --- a/ecc-internal.h +++ b/ecc-internal.h @@ -27,6 +27,7 @@ #include <gmp.h> +#include "nettle-types.h" #include "ecc-curve.h" /* Name mangling */ @@ -45,13 +46,17 @@ #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_mod _nettle_ecc_mod +#define ecc_modq_random _nettle_ecc_modq_random +#define ecc_mod _nettle_ecc_mod +#define ecc_hash _nettle_ecc_hash #define cnd_copy _nettle_cnd_copy #define sec_add_1 _nettle_sec_add_1 #define sec_sub_1 _nettle_sec_sub_1 #define sec_tabselect _nettle_sec_tabselect #define sec_modinv _nettle_sec_modinv +#define ECC_MAX_SIZE ((521 + GMP_NUMB_BITS - 1) / GMP_NUMB_BITS) + /* Window size for ecc_mul_a. Using 4 bits seems like a good choice, for both Intel x86_64 and ARM Cortex A9. For the larger curves, of 384 and 521 bits, we could improve seepd by a few percent if we go @@ -185,10 +190,19 @@ 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); + +void ecc_mod (mp_limb_t *rp, mp_size_t rn, mp_size_t mn, const mp_limb_t *bp, mp_size_t bn, const mp_limb_t *b_shifted, unsigned shift); +void +ecc_hash (const struct ecc_curve *ecc, + mp_limb_t *hp, + unsigned length, const uint8_t *digest); + #define cnd_add_n(cnd, rp, ap, n) \ mpn_addmul_1 ((rp), (ap), (n), (cnd) != 0) @@ -228,8 +242,10 @@ sec_modinv (mp_limb_t *vp, mp_limb_t *ap, mp_size_t n, #define ECC_MUL_A_ITCH(size) \ (((3 << ECC_MUL_A_WBITS) + 11) * (size)) #endif -#define _ECDSA_SIGN_ITCH(size) (12*(size)) -#define _ECDSA_VERIFY_ITCH(size) \ +#define ECC_ECDSA_SIGN_ITCH(size) (12*(size)) +#define ECC_ECDSA_VERIFY_ITCH(size) \ (6*(size) + ECC_MUL_A_ITCH ((size))) +#define ECC_MODQ_RANDOM_ITCH(size) (size) +#define ECC_HASH_ITCH(size) (1+(size)) #endif /* NETTLE_ECC_INTERNAL_H_INCLUDED */ diff --git a/ecc-point.c b/ecc-point.c new file mode 100644 index 00000000..b26c192e --- /dev/null +++ b/ecc-point.c @@ -0,0 +1,90 @@ +/* ecc-point.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" +#include "gmp-glue.h" + +void +ecc_point_init (struct ecc_point *p, const struct ecc_curve *ecc) +{ + p->ecc = ecc; + p->p = _gmp_alloc_limbs (2*ecc->size); +} + +void +ecc_point_clear (struct ecc_point *p) +{ + _gmp_free_limbs (p->p, 2*p->ecc->size); +} + +int +ecc_point_set (struct ecc_point *p, const mpz_t x, const mpz_t y) +{ + mp_size_t size; + mpz_t lhs, rhs; + mpz_t t; + int res; + + size = p->ecc->size; + + if (mpz_sgn (x) < 0 || _mpz_cmp_limbs (x, p->ecc->p, size) >= 0 + || mpz_sgn (y) < 0 || _mpz_cmp_limbs (y, p->ecc->p, size) >= 0) + return 0; + + mpz_init (lhs); + mpz_init (rhs); + + /* Check that y^2 = x^3 - 3*x + b (mod p) */ + mpz_mul (lhs, y, y); + mpz_mul (rhs, x, x); + mpz_sub_ui (rhs, rhs, 3); + mpz_mul (rhs, rhs, x); + mpz_add (rhs, rhs, _mpz_init_mpn (t, p->ecc->b, size)); + + res = mpz_congruent_p (lhs, rhs, _mpz_init_mpn (t, p->ecc->p, size)); + + mpz_clear (lhs); + mpz_clear (rhs); + + if (!res) + return 0; + + _mpz_copy_limbs (p->p, x, size); + _mpz_copy_limbs (p->p + size, y, size); + + return 1; +} + +void +ecc_point_get (const struct ecc_point *p, mpz_t x, mpz_t y) +{ + mp_size_t size = p->ecc->size; + _mpz_set_mpn (x, p->p, size); + _mpz_set_mpn (y, p->p + size, size); +} diff --git a/ecc-random.c b/ecc-random.c new file mode 100644 index 00000000..acffb573 --- /dev/null +++ b/ecc-random.c @@ -0,0 +1,90 @@ +/* ecc-random.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" +#include "gmp-glue.h" +#include "nettle-internal.h" + +static int +zero_p (const struct ecc_curve *ecc, + const mp_limb_t *xp) +{ + mp_limb_t t; + mp_size_t i; + + for (i = t = 0; i < ecc->size; i++) + t |= xp[i]; + + return t == 0; +} + +static int +ecdsa_in_range (const struct ecc_curve *ecc, + const mp_limb_t *xp, mp_limb_t *scratch) +{ + /* Check if 0 < x < q, with data independent timing. */ + return !zero_p (ecc, xp) + & (mpn_sub_n (scratch, xp, ecc->q, ecc->size) != 0); +} + +void +ecc_modq_random (const struct ecc_curve *ecc, mp_limb_t *xp, + void *ctx, nettle_random_func *random, mp_limb_t *scratch) +{ + uint8_t *buf = (uint8_t *) scratch; + unsigned nbytes = (ecc->bit_size + 7)/8; + + /* The bytes ought to fit in the scratch area, unless we have very + unusual limb and byte sizes. */ + assert (nbytes <= ecc->size * sizeof (mp_limb_t)); + + do + { + /* q and p are of the same bitsize. */ + random (ctx, nbytes, buf); + buf[0] &= 0xff >> (nbytes * 8 - ecc->bit_size); + + _mpn_set_base256 (xp, ecc->size, buf, nbytes); + } + while (!ecdsa_in_range (ecc, xp, scratch)); +} + +void +ecc_scalar_random (struct ecc_scalar *x, + void *random_ctx, nettle_random_func *random) +{ + TMP_DECL (scratch, mp_limb_t, ECC_MODQ_RANDOM_ITCH (ECC_MAX_SIZE)); + TMP_ALLOC (scratch, ECC_MODQ_RANDOM_ITCH (x->ecc->size)); + + ecc_modq_random (x->ecc, x->p, random_ctx, random, scratch); +} + + diff --git a/ecc-scalar.c b/ecc-scalar.c new file mode 100644 index 00000000..b4c98fde --- /dev/null +++ b/ecc-scalar.c @@ -0,0 +1,62 @@ +/* ecc-scalar.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" +#include "gmp-glue.h" + +void +ecc_scalar_init (struct ecc_scalar *s, const struct ecc_curve *ecc) +{ + s->ecc = ecc; + s->p = _gmp_alloc_limbs (ecc->size); +} + +void +ecc_scalar_clear (struct ecc_scalar *s) +{ + _gmp_free_limbs (s->p, s->ecc->size); +} + +int +ecc_scalar_set (struct ecc_scalar *s, const mpz_t z) +{ + mp_size_t size = s->ecc->size; + + if (mpz_sgn (z) <= 0 || _mpz_cmp_limbs (z, s->ecc->q, size) >= 0) + return 0; + + _mpz_copy_limbs (s->p, z, size); + return 1; +} + +void +ecc_scalar_get (const struct ecc_scalar *s, mpz_t z) +{ + _mpz_set_mpn (z, s->p, s->ecc->size); +} @@ -25,15 +25,25 @@ #ifndef NETTLE_ECC_H_INCLUDED #define NETTLE_ECC_H_INCLUDED -#include <stdint.h> - #include <gmp.h> +#include "nettle-types.h" + #ifdef __cplusplus extern "C" { #endif /* Name mangling */ +#define ecc_point_init nettle_ecc_point_init +#define ecc_point_clear nettle_ecc_point_clear +#define ecc_point_set nettle_ecc_point_set +#define ecc_point_get nettle_ecc_point_get +#define ecc_scalar_init nettle_ecc_scalar_init +#define ecc_scalar_clear nettle_ecc_scalar_clear +#define ecc_scalar_set nettle_ecc_scalar_set +#define ecc_scalar_get nettle_ecc_scalar_get +#define ecc_scalar_random nettle_ecc_scalar_random +#define ecc_point_mul nettle_ecc_point_mul #define ecc_size nettle_ecc_size #define ecc_size_a nettle_ecc_size_a #define ecc_size_j nettle_ecc_size_j @@ -57,6 +67,60 @@ extern "C" { struct ecc_curve; +/* High level interface, for ECDSA, DH, etc */ + +/* Represents a point on the ECC curve */ +struct ecc_point +{ + const struct ecc_curve *ecc; + /* Allocated using the same allocation function as GMP. */ + mp_limb_t *p; +}; + +/* Represents a non-zero scalar, an element of Z_q^*, where q is the + group order of the curve. */ +struct ecc_scalar +{ + const struct ecc_curve *ecc; + /* Allocated using the same allocation function as GMP. */ + mp_limb_t *p; +}; + +void +ecc_point_init (struct ecc_point *p, const struct ecc_curve *ecc); +void +ecc_point_clear (struct ecc_point *p); + +/* Fails and returns zero if the point is not on the curve. */ +int +ecc_point_set (struct ecc_point *p, const mpz_t x, const mpz_t y); +void +ecc_point_get (const struct ecc_point *p, mpz_t x, mpz_t y); + +void +ecc_scalar_init (struct ecc_scalar *s, const struct ecc_curve *ecc); +void +ecc_scalar_clear (struct ecc_scalar *s); + +/* Fails and returns zero if the scalar is not in the proper range. */ +int +ecc_scalar_set (struct ecc_scalar *s, const mpz_t z); +void +ecc_scalar_get (const struct ecc_scalar *s, mpz_t z); +/* Generates a random scalar, suitable as an ECDSA private key or a + ECDH exponent. */ +void +ecc_scalar_random (struct ecc_scalar *s, + void *random_ctx, nettle_random_func *random); + +/* Computes r = n p */ +void +ecc_point_mul (struct ecc_point *r, const struct ecc_scalar *n, + const struct ecc_point *p); + + +/* 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, diff --git a/ecdsa-sign.c b/ecdsa-sign.c new file mode 100644 index 00000000..725c39a2 --- /dev/null +++ b/ecdsa-sign.c @@ -0,0 +1,63 @@ +/* ecdsa-sign.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 <stdlib.h> + +#include "ecdsa.h" +#include "ecc-internal.h" +#include "gmp-glue.h" +#include "nettle-internal.h" + +void +ecdsa_sign (const struct ecc_scalar *key, + void *random_ctx, nettle_random_func *random, + unsigned digest_length, + const uint8_t *digest, + struct dsa_signature *signature) +{ + /* At most 936 bytes. */ + TMP_DECL(k, mp_limb_t, ECC_MAX_SIZE + ECC_ECDSA_SIGN_ITCH (ECC_MAX_SIZE)); + mp_limb_t size = key->ecc->size; + mp_limb_t *rp = _mpz_write_limbs (signature->r, size); + mp_limb_t *sp = _mpz_write_limbs (signature->s, size); + + TMP_ALLOC (k, size + ECC_ECDSA_SIGN_ITCH (size)); + + /* Timing reveals the number of rounds through this loop, but the + timing is still independent of the secret k finally used. */ + do + { + ecc_modq_random (key->ecc, k, random_ctx, random, k + size); + ecc_ecdsa_sign (key->ecc, key->p, k, digest_length, digest, + rp, sp, k + size); + _mpz_done_limbs (signature->r, size); + _mpz_done_limbs (signature->s, size); + } + while (mpz_sgn (signature->r) == 0 || mpz_sgn (signature->s) == 0); +} diff --git a/ecdsa-verify.c b/ecdsa-verify.c new file mode 100644 index 00000000..0fdbe027 --- /dev/null +++ b/ecdsa-verify.c @@ -0,0 +1,68 @@ +/* ecc-ecdsa-verify.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 <stdlib.h> + +#include "ecdsa.h" +#include "ecc-internal.h" +#include "gmp-glue.h" + +int +ecdsa_verify (const struct ecc_point *pub, + unsigned length, const uint8_t *digest, + const struct dsa_signature *signature) +{ + mp_limb_t size = pub->ecc->size; + mp_size_t itch = 2*size + ECC_ECDSA_VERIFY_ITCH (size); + /* For ECC_MUL_A_WBITS == 0, at most 1512 bytes. With + ECC_MUL_A_WBITS == 4, currently needs 67 * ecc->size, at most + 4824 bytes. Don't use stack allocation for this. */ + mp_limb_t *scratch = _gmp_alloc_limbs (itch); + int res; + +#define rp scratch +#define sp (scratch + size) +#define scratch_out (scratch + 2*size) + + if (mpz_sgn (signature->r) <= 0 || mpz_size (signature->r) > size + || mpz_sgn (signature->s) <= 0 || mpz_size (signature->s) > size) + return 0; + + _mpz_copy_limbs (rp, signature->r, size); + _mpz_copy_limbs (sp, signature->s, size); + + res = ecc_ecdsa_verify (pub->ecc, pub->p, length, digest, rp, sp, scratch_out); + + _gmp_free_limbs (scratch, itch); + + return res; +#undef rp +#undef sp +#undef scratch_out +} diff --git a/ecdsa.h b/ecdsa.h new file mode 100644 index 00000000..961102e5 --- /dev/null +++ b/ecdsa.h @@ -0,0 +1,94 @@ +/* ecdsa.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_ECDSA_H_INCLUDED +#define NETTLE_ECDSA_H_INCLUDED + +#include "ecc.h" +#include "dsa.h" + +#ifdef __cplusplus +extern "C" { +#endif + +/* Name mangling */ +#define ecdsa_sign nettle_ecdsa_sign +#define ecdsa_verify nettle_ecdsa_verify +#define ecdsa_generate_keypair nettle_ecdsa_generate_keypair +#define ecc_ecdsa_sign nettle_ecc_ecdsa_sign +#define ecc_ecdsa_sign_itch nettle_ecc_ecdsa_sign_itch +#define ecc_ecdsa_verify nettle_ecc_ecdsa_verify +#define ecc_ecdsa_verify_itch nettle_ecc_ecdsa_verify_itch + +/* High level ECDSA functions. + * + * A public key is represented as a struct ecc_point, and a private + * key as a struct ecc_scalar. FIXME: Introduce some aliases? */ +void +ecdsa_sign (const struct ecc_scalar *key, + void *random_ctx, nettle_random_func *random, + unsigned digest_length, + const uint8_t *digest, + struct dsa_signature *signature); + +int +ecdsa_verify (const struct ecc_point *pub, + unsigned length, const uint8_t *digest, + const struct dsa_signature *signature); + +void +ecdsa_generate_keypair (struct ecc_point *pub, + struct ecc_scalar *key, + void *random_ctx, nettle_random_func *random); + +/* Low-level ECDSA functions. */ +mp_size_t +ecc_ecdsa_sign_itch (const struct ecc_curve *ecc); + +void +ecc_ecdsa_sign (const struct ecc_curve *ecc, + const mp_limb_t *zp, + /* Random nonce, must be invertible mod ecc group + order. */ + const mp_limb_t *kp, + unsigned length, const uint8_t *digest, + mp_limb_t *rp, mp_limb_t *sp, + mp_limb_t *scratch); + +mp_size_t +ecc_ecdsa_verify_itch (const struct ecc_curve *ecc); + +int +ecc_ecdsa_verify (const struct ecc_curve *ecc, + const mp_limb_t *pp, /* Public key */ + unsigned length, const uint8_t *digest, + const mp_limb_t *rp, const mp_limb_t *sp, + mp_limb_t *scratch); + + +#ifdef __cplusplus +} +#endif + +#endif /* NETTLE_ECDSA_H_INCLUDED */ |