Signed-off-by: Dmitry Eremin-Solenikov <[email protected]>
---
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-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^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)
{
--
2.14.2
_______________________________________________
nettle-bugs mailing list
[email protected]
http://lists.lysator.liu.se/mailman/listinfo/nettle-bugs
