Signed-off-by: Dmitry Eremin-Solenikov dbaryshkov@gmail.com --- Makefile.in | 14 +++++- ecc-curve.h | 1 + ecc-dup-jj-0.c | 109 +++++++++++++++++++++++++++++++++++++++++++++++ ecc-internal.h | 10 ++++- eccdata.c | 33 ++++++++++++++ testsuite/ecc-add-test.c | 2 +- testsuite/ecc-dup-test.c | 2 +- testsuite/testutils.c | 12 +++++- 8 files changed, 176 insertions(+), 7 deletions(-) create mode 100644 ecc-dup-jj-0.c
diff --git a/Makefile.in b/Makefile.in index fc93a689053d..3d054f113f87 100644 --- a/Makefile.in +++ b/Makefile.in @@ -168,9 +168,9 @@ hogweed_SOURCES = sexp.c sexp-format.c \ ecc-mod.c ecc-mod-inv.c \ ecc-mod-arith.c ecc-pp1-redc.c ecc-pm1-redc.c \ ecc-192.c ecc-224.c ecc-256.c ecc-384.c ecc-521.c \ - ecc-25519.c \ + ecc-25519.c ecc-256k1.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-dup-jj.c ecc-dup-jj-0.c ecc-add-jja.c ecc-add-jjj.c \ ecc-eh-to-a.c \ ecc-dup-eh.c ecc-add-eh.c ecc-add-ehh.c \ ecc-mul-g-eh.c ecc-mul-a-eh.c \ @@ -343,6 +343,14 @@ ecc-224.h: eccdata.stamp # k = 12, c = 7, 512 entries, ~32 KB ecc-256.h: eccdata.stamp ./eccdata$(EXEEXT_FOR_BUILD) secp256r1 14 6 $(NUMB_BITS) > $@T && mv $@T $@ +# Some possible choices for 256: +# k = 20, c = 4, 64 entries, ~4 KB +# k = 27, c = 6, 128 entries, ~8 KB +# k = 14, c = 6, 256 entries, ~16 KB +# k = 9, c = 6, 320 entries, ~20 KB +# k = 12, c = 7, 512 entries, ~32 KB +ecc-256k1.h: eccdata.stamp + ./eccdata$(EXEEXT_FOR_BUILD) secp256k1 14 6 $(NUMB_BITS) > $@T && mv $@T $@ # Some possible choices for 384: # k = 31, c = 4, 64 entries, ~6 KB # k = 41, c = 6, 128 entries, ~12 KB @@ -370,6 +378,7 @@ eccdata.stamp: eccdata.c ecc-192.$(OBJEXT): ecc-192.h ecc-224.$(OBJEXT): ecc-224.h ecc-256.$(OBJEXT): ecc-256.h +ecc-256k1.$(OBJEXT): ecc-256k1.h ecc-384.$(OBJEXT): ecc-384.h ecc-521.$(OBJEXT): ecc-521.h ecc-25519.$(OBJEXT): ecc-25519.h @@ -626,6 +635,7 @@ distcheck: dist clean-here: -rm -f $(TARGETS) *.$(OBJEXT) *.s *.so *.dll *.a \ ecc-192.h ecc-224.h ecc-256.h ecc-384.h ecc-521.h ecc-25519.h \ + ecc-256k1.h \ eccdata$(EXEEXT_FOR_BUILD) eccdata.stamp -rm -rf .lib libnettle.stamp libhogweed.stamp
diff --git a/ecc-curve.h b/ecc-curve.h index 574c9f2e00e1..7bcfcd20f2da 100644 --- a/ecc-curve.h +++ b/ecc-curve.h @@ -44,6 +44,7 @@ struct ecc_curve; extern const struct ecc_curve nettle_secp_192r1; extern const struct ecc_curve nettle_secp_224r1; extern const struct ecc_curve nettle_secp_256r1; +extern const struct ecc_curve nettle_secp_256k1; extern const struct ecc_curve nettle_secp_384r1; extern const struct ecc_curve nettle_secp_521r1;
diff --git a/ecc-dup-jj-0.c b/ecc-dup-jj-0.c new file mode 100644 index 000000000000..b62bf008ed2a --- /dev/null +++ b/ecc-dup-jj-0.c @@ -0,0 +1,109 @@ +/* ecc-dup-jj-0.c + + Copyright (C) 2017 Dmitry Eremin-Solenikov + Copyright (C) 2013 Niels Möller + + 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/. +*/ + +/* Development of Nettle's ECC support was funded by the .SE Internet Fund. */ + +#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! +*/ +void +ecc_dup_jj_0 (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-db...): + + 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^2 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->p.size) +#define beta (scratch + 2*ecc->p.size) +#define g2 (scratch + 3*ecc->p.size) +#define sum (scratch + 4*ecc->p.size) +#define alpha scratch /* Overlap delta */ + +#define xp p +#define yp (p + ecc->p.size) +#define zp (p + 2*ecc->p.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->p.size, yp, zp); + ecc_modp_sqr (ecc, beta, r + 2*ecc->p.size); + ecc_modp_sub (ecc, beta, beta, gamma); + ecc_modp_sub (ecc, r + 2*ecc->p.size, beta, delta); + + /* alpha. Can use beta area as scratch, and overwrite delta. */ + ecc_modp_sqr (ecc, beta, xp); + 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->p.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->p.size, gamma, ecc->p.size); +} diff --git a/ecc-internal.h b/ecc-internal.h index 6475e4803aca..98e8515f3b82 100644 --- a/ecc-internal.h +++ b/ecc-internal.h @@ -57,6 +57,7 @@ #define ecc_j_to_a _nettle_ecc_j_to_a #define ecc_eh_to_a _nettle_ecc_eh_to_a #define ecc_dup_jj _nettle_ecc_dup_jj +#define ecc_dup_jj_0 _nettle_ecc_dup_jj_0 #define ecc_add_jja _nettle_ecc_add_jja #define ecc_add_jjj _nettle_ecc_add_jjj #define ecc_dup_eh _nettle_ecc_dup_eh @@ -299,13 +300,20 @@ ecc_eh_to_a (const struct ecc_curve *ecc,
/* Group operations */
-/* Point doubling, with jacobian input and output. Corner cases: +/* Point doubling, with jacobian input and output for a = -3. Corner cases: Correctly sets R = 0 (r_Z = 0) if p = 0 or 2p = 0. */ void ecc_dup_jj (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 for a = 0. Corner cases: + Correctly sets R = 0 (r_Z = 0) if p = 0 or 2p = 0. */ +void +ecc_dup_jj_0 (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
diff --git a/eccdata.c b/eccdata.c index 56d779f8ca6e..ecd50723a4e7 100644 --- a/eccdata.c +++ b/eccdata.c @@ -500,6 +500,39 @@ ecc_curve_init (struct ecc_curve *ecc, const char *curve) "e2534a3532d08fbba02dde659ee62bd0031fe2db785596ef509302446b030852", "e0f1575a4c633cc719dfee5fda862d764efc96c3f30ee0055c42c23f184ed8c6");
+ } else if (!strcmp(curve, "secp256k1")) { + ecc_curve_init_str (ecc, ECC_TYPE_WEIERSTRASS, + /* p = 2^{256} - 2^{32} - 2^{9} - 2^{8} - 2^{7} - 2^{6} - 2^{4} - 1 */ + "ffffffffffffffffffffffffffffffff" + "fffffffffffffffffffffffefffffc2f", + + 0, + + "7", + + "fffffffffffffffffffffffffffffffe" + "baaedce6af48a03bbfd25e8cd0364141", + + "79be667ef9dcbbac55a06295ce870b07" + "029bfcdb2dce28d959f2815b16f81798", + + "483ada7726a3c4655da4fbfc0e1108a8" + "fd17b448a68554199c47d08ffb10d4b8", + NULL, NULL); + + ecc->ref = ecc_alloc (3); + ecc_set_str (&ecc->ref[0], /* 2 g */ + "c6047f9441ed7d6d3045406e95c07cd85c778e4b8cef3ca7abac09b95c709ee5", + "1ae168fea63dc339a3c58419466ceaeef7f632653266d0e1236431a950cfe52a"); + + ecc_set_str (&ecc->ref[1], /* 3 g */ + "f9308a019258c31049344f85f89d5229b531c845836f99b08601f113bce036f9", + "388f7b0f632de8140fe337e62a37f3566500a99934c2231b6cb9fd7584b8e672"); + + ecc_set_str (&ecc->ref[2], /* 4 g */ + "e493dbf1c10d80f3581e4904930b1404cc6c13900ee0758474fa94abe8c4cd13", + "51ed993ea0d455b75642e2098ea51448d967ae33bfbdfe40cfe97bdc47739922"); + } else if (!strcmp(curve, "secp384r1")) { ecc_curve_init_str (ecc, ECC_TYPE_WEIERSTRASS, /* p = 2^{384} - 2^{128} - 2^{96} + 2^{32} - 1 */ diff --git a/testsuite/ecc-add-test.c b/testsuite/ecc-add-test.c index ad2bd29230ee..d2df0c604ef3 100644 --- a/testsuite/ecc-add-test.c +++ b/testsuite/ecc-add-test.c @@ -54,7 +54,7 @@ test_main (void) else { ASSERT (ecc->add_hhh == ecc_add_jjj); - ASSERT (ecc->dup == ecc_dup_jj); + ASSERT (ecc->dup == ecc_dup_jj || ecc->dup == ecc_dup_jj_0); }
ecc->dup (ecc, g2, g, scratch); diff --git a/testsuite/ecc-dup-test.c b/testsuite/ecc-dup-test.c index 0ae4444a7cb0..7b280b1c0f65 100644 --- a/testsuite/ecc-dup-test.c +++ b/testsuite/ecc-dup-test.c @@ -30,7 +30,7 @@ test_main (void) free (z); } else - ASSERT (ecc->dup == ecc_dup_jj); + ASSERT (ecc->dup == ecc_dup_jj || ecc->dup == ecc_dup_jj_0);
ecc->dup (ecc, p, g, scratch); test_ecc_mul_h (i, 2, p); diff --git a/testsuite/testutils.c b/testsuite/testutils.c index 6f897617cadb..f2c884533131 100644 --- a/testsuite/testutils.c +++ b/testsuite/testutils.c @@ -1215,6 +1215,7 @@ const struct ecc_curve * const ecc_curves[] = { &nettle_secp_192r1, &nettle_secp_224r1, &nettle_secp_256r1, + &nettle_secp_256k1, &nettle_secp_384r1, &nettle_secp_521r1, &_nettle_curve25519, @@ -1269,7 +1270,7 @@ 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[6][3] = { + static const struct ecc_ref_point ref[7][3] = { { { "dafebf5828783f2ad35534631588a3f629a70fb16982a888", "dd6bda0d993da0fa46b27bbc141b868f59331afa5c7e93ab" }, { "76e32a2557599e6edcd283201fb2b9aadfd0d359cbb263da", @@ -1291,6 +1292,13 @@ test_ecc_mul_a (unsigned curve, unsigned n, const mp_limb_t *p) { "e2534a3532d08fbba02dde659ee62bd0031fe2db785596ef509302446b030852", "e0f1575a4c633cc719dfee5fda862d764efc96c3f30ee0055c42c23f184ed8c6" }, }, + { { "c6047f9441ed7d6d3045406e95c07cd85c778e4b8cef3ca7abac09b95c709ee5", + "1ae168fea63dc339a3c58419466ceaeef7f632653266d0e1236431a950cfe52a" }, + { "f9308a019258c31049344f85f89d5229b531c845836f99b08601f113bce036f9", + "388f7b0f632de8140fe337e62a37f3566500a99934c2231b6cb9fd7584b8e672" }, + { "e493dbf1c10d80f3581e4904930b1404cc6c13900ee0758474fa94abe8c4cd13", + "51ed993ea0d455b75642e2098ea51448d967ae33bfbdfe40cfe97bdc47739922" }, + }, { { "8d999057ba3d2d969260045c55b97f089025959a6f434d651d207d19fb96e9e" "4fe0e86ebe0e64f85b96a9c75295df61", "8e80f1fa5b1b3cedb7bfe8dffd6dba74b275d875bc6cc43e904e505f256ab425" @@ -1332,7 +1340,7 @@ test_ecc_mul_a (unsigned curve, unsigned n, const mp_limb_t *p) "47d0e827cb1595e1470eb88580d5716c4cf22832ea2f0ff0df38ab61ca32112f" }, } }; - assert (curve < 6); + assert (curve < 7); assert (n <= 4); if (n == 0) {