diff options
| author | Rob Austein <sra@hactrn.net> | 2015-08-21 14:21:10 -0400 |
|---|---|---|
| committer | Rob Austein <sra@hactrn.net> | 2015-08-21 14:21:10 -0400 |
| commit | 511819f0f73c5f37d3f7c033f01d29ef88bfa9cb (patch) | |
| tree | ca6a7f815c745a59a1e0566a54b475acdb7512e6 | |
| parent | c8a5dd6875785a053ae6b1956ebf924b6f468ec9 (diff) | |
Updated point doubling and addition to use algorithms from the
hyperelliptic.org formula database. Compiles, still not tested.
| -rw-r--r-- | ecdsa.c | 207 |
1 files changed, 97 insertions, 110 deletions
@@ -253,10 +253,16 @@ static inline int point_equal(const ec_point_t * const P, * All of these are operations in the field underlying the specified * curve, and assume that operands are already in Montgomery form. * - * Several of these are written a bit oddly, in an attempt to make - * them run in constant time. Be warned that an optimizing compiler - * may be clever enough to defeat this. In the long run, the real - * solution is probably to perform these field operations in Verilog. + * The ff_add() and ff_sub() are written a bit oddly, in an attempt to + * make them run in constant time. An optimizing compiler may be + * clever enough to defeat this. In the long run, we probably want to + * perform these field operations in Verilog anyway. + * + * We might be able to squeeze a bit more speed out of the point + * arithmetic by making using fp_mul_2d() when multiplying by a power + * of two. Skipping for now as a premature optimization, but if we do + * need this, it'd probably be simplest to add a ff_dbl() function + * which handles overflow in the same way that ff_add() does. */ static inline void ff_add(const ecdsa_curve_t * const curve, @@ -266,9 +272,12 @@ static inline void ff_add(const ecdsa_curve_t * const curve, { fp_int t[2][1]; memset(t, 0, sizeof(t)); + fp_add(unconst_fp_int(a), unconst_fp_int(b), t[0]); fp_sub(t[0], unconst_fp_int(curve->q), t[1]); - fp_copy(t[fp_cmp(t[0], unconst_fp_int(curve->q)) != FP_LT], c); + + fp_copy(t[fp_cmp_d(t[1], 0) != FP_LT], c); + memset(t, 0, sizeof(t)); } @@ -279,21 +288,12 @@ static inline void ff_sub(const ecdsa_curve_t * const curve, { fp_int t[2][1]; memset(t, 0, sizeof(t)); + fp_sub(unconst_fp_int(a), unconst_fp_int(b), t[0]); fp_add(t[0], unconst_fp_int(curve->q), t[1]); - fp_copy(t[fp_cmp_d(c, 0) == FP_LT], c); - memset(t, 0, sizeof(t)); -} -static inline void ff_div2(const ecdsa_curve_t * const curve, - const fp_int * const a, - fp_int *b) -{ - fp_int t[2][1]; - memset(t, 0, sizeof(t)); - fp_copy(unconst_fp_int(a), t[0]); - fp_add(t[0], unconst_fp_int(curve->q), t[1]); - fp_div_2(t[fp_isodd(unconst_fp_int(a))], b); + fp_copy(t[fp_cmp_d(t[0], 0) == FP_LT], c); + memset(t, 0, sizeof(t)); } @@ -314,37 +314,14 @@ static inline void ff_sqr(const ecdsa_curve_t * const curve, fp_montgomery_reduce(b, unconst_fp_int(curve->q), curve->rho); } -#warning Change point arithmetic algorithms? -/* - * The point doubling and addition algorithms we use here are from - * libtomcrypt. The formula database at hyperelliptic.org lists - * faster algorithms satisfying the same preconditions, perhaps we - * should use those instead? - * - * Labels in the following refer to entries on the page: - * http://www.hyperelliptic.org/EFD/g1p/auto-shortw-jacobian-3.html - * - * The libtomcrypt doubling algorithm looks like a trivial variation - * on dbl-2004-hmv. We might want to use dbl-2001-b instead. - * - * The libtomcrypt addition algorithm doesn't match up exactly with - * any listed algorithm, but I suspect it's a variation on - * add-1998-cmo-2. We might want to use add-2007-bl instead. - * - * There are faster algorithms listed, but all of them appear to - * require whacking one or both points back into affine - * representation, which has its own costs, so, at least for now, it'd - * probably be best to stick with algorithms that don't require this. - */ - /** * Double an EC point. * @param P The point to double * @param R [out] The destination of the double * @param curve The curve parameters structure * - * Algorithm is a minor variation on algorithm 3.21 from Guide to - * Elliptic Curve Cryptography. + * Algorithm is dbl-2001-b from + * http://www.hyperelliptic.org/EFD/g1p/auto-shortw-jacobian-3.html */ static inline void point_double(const ec_point_t * const P, @@ -353,36 +330,41 @@ static inline void point_double(const ec_point_t * const P, { assert(P != NULL && R != NULL && curve != NULL); - fp_int t1[1]; fp_init(t1); - fp_int t2[1]; fp_init(t2); - - if (P != R) - *R = *P; - - ff_sqr (curve, R->z, t1); /* t1 = Pz ** 2 */ - ff_sub (curve, R->x, t1, t2); /* t2 = Px - Pz ** 2 */ - ff_add (curve, R->x, t1, t1); /* t1 = Px + Pz ** 2 */ - ff_mul (curve, t1, t2, t2); /* t2 = 1 * (Px - Pz ** 2) * (Px + Pz ** 2) */ - ff_add (curve, t2, t2, t1); /* t1 = 2 * (Px - Pz ** 2) * (Px + Pz ** 2) */ - ff_add (curve, t1, t *.[ao]
*.pyc
*~
Makefile
TAGS
cryptech_rpcd
tests/test-aes-key-wrap
tests/test-bus
tests/test-ecdsa
tests/test-ecdsa-*.der
tests/test-hash
tests/test-mkmif
tests/test-pbkdf2
tests/test-rpc_bighash
tests/test-rpc_get_random
tests/test-rpc_get_version
tests/test-rpc_hash
tests/test-rpc_login
tests/test-rpc_pkey
tests/test-rpc_server
tests/test-rsa
tests/test-rsa-*.der
tests/test-trng
utils/cores
utils/eim_peek_poke
|