From abfaf8be2fa06786da94fa6e3b90773d6f178739 Mon Sep 17 00:00:00 2001 From: Dmitry Eremin-Solenikov Date: Tue, 7 Jan 2020 01:16:43 +0300 Subject: ecc: rename source files with curves data In preparation to adding GOST curves support, rename source files and use curve name as eccdata parameter. Signed-off-by: Dmitry Eremin-Solenikov --- ecc-curve448.c | 334 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 334 insertions(+) create mode 100644 ecc-curve448.c (limited to 'ecc-curve448.c') diff --git a/ecc-curve448.c b/ecc-curve448.c new file mode 100644 index 00000000..7020e3e8 --- /dev/null +++ b/ecc-curve448.c @@ -0,0 +1,334 @@ +/* ecc-curve448.c + + Arithmetic and tables for curve448, + + Copyright (C) 2017 Daiki Ueno + Copyright (C) 2017 Red Hat, Inc. + + This file is part of GNU Nettle. + + GNU Nettle is free software: you can redistribute it and/or + modify it under the terms of either: + + * the GNU Lesser General Public License as published by the Free + Software Foundation; either version 3 of the License, or (at your + option) any later version. + + or + + * the GNU General Public License as published by the Free + Software Foundation; either version 2 of the License, or (at your + option) any later version. + + or both in parallel, as here. + + GNU Nettle 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 + General Public License for more details. + + You should have received copies of the GNU General Public License and + the GNU Lesser General Public License along with this program. If + not, see http://www.gnu.org/licenses/. +*/ + +#if HAVE_CONFIG_H +# include "config.h" +#endif + +#include + +#include "ecc.h" +#include "ecc-internal.h" + +#define USE_REDC 0 + +#include "ecc-curve448.h" + +#if HAVE_NATIVE_ecc_curve448_modp +#define ecc_448_modp nettle_ecc_curve448_modp +void +ecc_448_modp (const struct ecc_modulo *m, mp_limb_t *rp); +#elif GMP_NUMB_BITS == 64 +static void +ecc_448_modp(const struct ecc_modulo *m, mp_limb_t *rp) +{ + /* Let B = 2^64, b = 2^32 = sqrt(B). + p = B^7 - b B^3 - 1 ==> B^7 = b B^3 + 1 + + We use this to reduce + + {r_{13}, ..., r_0} = + {r_6,...,r_0} + + {r_{10},...,r_7} + + 2 {r_{13},r_{12}, r_{11}} B^4 + + b {r_{10},...,r_7,r_{13},r_{12},r_{11} (mod p) + + or + + +----+----+----+----+----+----+----+ + |r_6 |r_5 |r_4 |r_3 |r_2 |r_1 |r_0 | + +----+----+----+----+----+----+----+ + |r_10|r_9 |r_8 |r_7 | + +----+----+----+----+----+----+----+ + 2 * |r_13|r_12|r_11| + +----+----+----+----+----+----+----+ + + b * |r_10|r_9 |r_8 |r_7 |r_13|r_12|r_11| + -------+----+----+----+----+----+----+----+ + c_7 |r_6 |r_5 |r_4 |r_3 |r_2 |r_1 |r_0 | + +----+----+----+----+----+----+----+ + */ + mp_limb_t c3, c4, c7; + mp_limb_t *tp = rp + 7; + + c4 = mpn_add_n (rp, rp, rp + 7, 4); + c7 = mpn_addmul_1 (rp + 4, rp + 11, 3, 2); + c3 = mpn_addmul_1 (rp, rp + 11, 3, (mp_limb_t) 1 << 32); + c7 += mpn_addmul_1 (rp + 3, rp + 7, 4, (mp_limb_t) 1 << 32); + tp[0] = c7; + tp[1] = tp[2] = 0; + tp[3] = c3 + (c7 << 32); + tp[4] = c4 + (c7 >> 32) + (tp[3] < c3); + tp[5] = tp[6] = 0; + c7 = mpn_add_n (rp, rp, tp, 7); + c7 = cnd_add_n (c7, rp, m->B, 7); + assert (c7 == 0); +} +#else +#define ecc_448_modp ecc_mod +#endif + +/* Needs 2*ecc->size limbs at rp, and 2*ecc->size additional limbs of + scratch space. No overlap allowed. */ +static void +ecc_mod_pow_2k (const struct ecc_modulo *m, + mp_limb_t *rp, const mp_limb_t *xp, + unsigned k, mp_limb_t *tp) +{ + if (k & 1) + { + ecc_mod_sqr (m, rp, xp); + k--; + } + else + { + ecc_mod_sqr (m, tp, xp); + ecc_mod_sqr (m, rp, tp); + k -= 2; + } + while (k > 0) + { + ecc_mod_sqr (m, tp, rp); + ecc_mod_sqr (m, rp, tp); + k -= 2; + } +} + +static void +ecc_mod_pow_2kp1 (const struct ecc_modulo *m, + mp_limb_t *rp, const mp_limb_t *xp, + unsigned k, mp_limb_t *tp) +{ + ecc_mod_pow_2k (m, tp, xp, k, rp); + ecc_mod_mul (m, rp, tp, xp); +} + +/* Computes a^{(p-3)/4} = a^{2^446-2^222-1} mod m. Needs 5 * n scratch + space. */ +static void +ecc_mod_pow_446m224m1 (const struct ecc_modulo *p, + mp_limb_t *rp, const mp_limb_t *ap, + mp_limb_t *scratch) +{ +/* Note overlap: operations writing to t0 clobber t1. */ +#define t0 scratch +#define t1 (scratch + 1*ECC_LIMB_SIZE) +#define t2 (scratch + 3*ECC_LIMB_SIZE) + + ecc_mod_sqr (p, rp, ap); /* a^2 */ + ecc_mod_mul (p, t0, ap, rp); /* a^3 */ + ecc_mod_sqr (p, rp, t0); /* a^6 */ + ecc_mod_mul (p, t0, ap, rp); /* a^{2^3-1} */ + + ecc_mod_pow_2kp1 (p, t1, t0, 3, rp); /* a^{2^6-1} */ + ecc_mod_pow_2k (p, rp, t1, 3, t2); /* a^{2^9-2^3} */ + ecc_mod_mul (p, t2, t0, rp); /* a^{2^9-1} */ + ecc_mod_pow_2kp1 (p, t0, t2, 9, rp); /* a^{2^18-1} */ + + ecc_mod_sqr (p, t1, t0); /* a^{2^19-2} */ + ecc_mod_mul (p, rp, ap, t1); /* a^{2^19-1} */ + ecc_mod_pow_2k (p, t1, rp, 18, t2); /* a^{2^37-2^18} */ + ecc_mod_mul (p, rp, t0, t1); /* a^{2^37-1} */ + mpn_copyi (t0, rp, p->size); + + ecc_mod_pow_2kp1 (p, rp, t0, 37, t2); /* a^{2^74-1} */ + ecc_mod_pow_2k (p, t1, rp, 37, t2); /* a^{2^111-2^37} */ + ecc_mod_mul (p, rp, t0, t1); /* a^{2^111-1} */ + ecc_mod_pow_2kp1 (p, t0, rp, 111, t2);/* a^{2^222-1} */ + + ecc_mod_sqr (p, t1, t0); /* a^{2^223-2} */ + ecc_mod_mul (p, rp, ap, t1); /* a^{2^223-1} */ + ecc_mod_pow_2k (p, t1, rp, 223, t2); /* a^{2^446-2^223} */ + ecc_mod_mul (p, rp, t0, t1); /* a^{2^446-2^222-1} */ +#undef t0 +#undef t1 +#undef t2 +} + +#define ECC_448_INV_ITCH (5*ECC_LIMB_SIZE) + +static void ecc_448_inv (const struct ecc_modulo *p, + mp_limb_t *rp, const mp_limb_t *ap, + mp_limb_t *scratch) +{ +#define t0 scratch + + ecc_mod_pow_446m224m1 (p, rp, ap, scratch); /* a^{2^446-2^222-1} */ + ecc_mod_sqr (p, t0, rp); /* a^{2^447-2^223-2} */ + ecc_mod_sqr (p, rp, t0); /* a^{2^448-2^224-4} */ + ecc_mod_mul (p, t0, ap, rp); /* a^{2^448-2^224-3} */ + + mpn_copyi (rp, t0, ECC_LIMB_SIZE); /* FIXME: Eliminate copy? */ +#undef t0 +} + +/* First, do a canonical reduction, then check if zero */ +static int +ecc_448_zero_p (const struct ecc_modulo *p, mp_limb_t *xp) +{ + mp_limb_t cy; + mp_limb_t w; + mp_size_t i; + cy = mpn_sub_n (xp, xp, p->m, ECC_LIMB_SIZE); + cnd_add_n (cy, xp, p->m, ECC_LIMB_SIZE); + + for (i = 0, w = 0; i < ECC_LIMB_SIZE; i++) + w |= xp[i]; + return w == 0; +} + +/* Compute x such that x^2 = u/v (mod p). Returns one on success, zero + on failure. + + To avoid a separate inversion, we use a trick of djb's, to + compute the candidate root as + + x = (u/v)^{(p+1)/4} = u^3 v (u^5 v^3)^{(p-3)/4}. +*/ + +/* Needs 4*n space + scratch for ecc_mod_pow_446m224m1. */ +#define ECC_448_SQRT_ITCH (9*ECC_LIMB_SIZE) + +static int +ecc_448_sqrt(const struct ecc_modulo *p, mp_limb_t *rp, + const mp_limb_t *up, const mp_limb_t *vp, + mp_limb_t *scratch) +{ +#define u3v scratch +#define u5v3 (scratch + ECC_LIMB_SIZE) +#define u5v3p (scratch + 2*ECC_LIMB_SIZE) +#define u2 (scratch + 2*ECC_LIMB_SIZE) +#define u3 (scratch + 3*ECC_LIMB_SIZE) +#define uv (scratch + 2*ECC_LIMB_SIZE) +#define u2v2 (scratch + 3*ECC_LIMB_SIZE) + +#define scratch_out (scratch + 4 * ECC_LIMB_SIZE) + +#define x2 scratch +#define vx2 (scratch + ECC_LIMB_SIZE) +#define t0 (scratch + 2*ECC_LIMB_SIZE) + + /* Live values */ + ecc_mod_sqr (p, u2, up); /* u2 */ + ecc_mod_mul (p, u3, u2, up); /* u3 */ + ecc_mod_mul (p, u3v, u3, vp); /* u3v */ + ecc_mod_mul (p, uv, up, vp); /* u3v, uv */ + ecc_mod_sqr (p, u2v2, uv); /* u3v, u2v2 */ + ecc_mod_mul (p, u5v3, u3v, u2v2); /* u3v, u5v3 */ + ecc_mod_pow_446m224m1 (p, u5v3p, u5v3, scratch_out); /* u3v, u5v3p */ + ecc_mod_mul (p, rp, u5v3p, u3v); /* none */ + + /* If square root exists, have v x^2 = u */ + ecc_mod_sqr (p, x2, rp); + ecc_mod_mul (p, vx2, x2, vp); + ecc_mod_sub (p, t0, vx2, up); + + return ecc_448_zero_p (p, t0); + +#undef u3v +#undef u5v3 +#undef u5v3p +#undef u2 +#undef u3 +#undef uv +#undef u2v2 +#undef scratch_out +#undef x2 +#undef vx2 +#undef t0 +} + +const struct ecc_curve _nettle_curve448 = +{ + { + 448, + ECC_LIMB_SIZE, + ECC_BMODP_SIZE, + 0, + ECC_448_INV_ITCH, + ECC_448_SQRT_ITCH, + + ecc_p, + ecc_Bmodp, + ecc_Bmodp_shifted, + NULL, + ecc_pp1h, + + ecc_448_modp, + ecc_448_modp, + ecc_448_inv, + ecc_448_sqrt, + }, + { + 446, + ECC_LIMB_SIZE, + ECC_BMODQ_SIZE, + 0, + ECC_MOD_INV_ITCH (ECC_LIMB_SIZE), + 0, + + ecc_q, + ecc_Bmodq, + ecc_Bmodq_shifted, + NULL, + ecc_qp1h, + + ecc_mod, /* FIXME: Implement optimized mod function */ + ecc_mod, /* FIXME: Implement optimized reduce function */ + ecc_mod_inv, + NULL, + }, + + 0, /* No redc */ + ECC_PIPPENGER_K, + ECC_PIPPENGER_C, + + ECC_ADD_EH_ITCH (ECC_LIMB_SIZE), + ECC_ADD_EHH_ITCH (ECC_LIMB_SIZE), + ECC_DUP_EH_ITCH (ECC_LIMB_SIZE), + ECC_MUL_A_EH_ITCH (ECC_LIMB_SIZE), + ECC_MUL_G_EH_ITCH (ECC_LIMB_SIZE), + ECC_EH_TO_A_ITCH (ECC_LIMB_SIZE, ECC_448_INV_ITCH), + + ecc_add_eh, + ecc_add_ehh, + ecc_dup_eh, + ecc_mul_a_eh, + ecc_mul_g_eh, + ecc_eh_to_a, + + ecc_b, + ecc_g, + ecc_unit, + ecc_table +}; -- cgit v1.2.1