Tweak parameters for ecc tables.ecc-params-tweak

2 files changed, 58 insertions, 37 deletions

diff --git a/ChangeLog b/ChangeLog
index 180633e1..f2fd0904 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -6,6 +6,23 @@
 	* eccparams.c (main): New program, to list parameter alternatives
 	for Pippenger's algorithm.
 
+	* Makefile.in: Tweak parameters for ecc tables.
+	(ecc-192.h): Change parameters from k = 7, c = 6 to k = 8, c = 6.
+	Reduces table size from 15 KB to 12 KB. Modest speedup, appr. 3%
+	for ecdsa signatures.
+	(ecc-224.h): Change parameters from k = 12, c = 6 to k = 16, c =
+	7. Table size unchanged (14 KB in 32-bit platforms, 18 KB on
+	64-bit platforms. Minor speedup, appr. 1% for ecdsa signatures.
+	(ecc-256.h): Change parameters from k = 14, c = 6 to k = 11, c =
+	6. Table size unchanged, 16 KB. 14% speedup for ecdsa signatures.
+	(ecc-384.h): Changed parameters from k = 41, c = 6 to k = 32, c =
+	6. Table size unchanged. 12% speedup for ecdsa signatures.
+	(ecc-521.h): Changed parameters from k = 56, c = 6 to k 44, c = 6.
+	Table size unchanged (17 KB on 32-bit platforms, 18 KB on 64-bit
+	platforms). 15% speedup for ecdsa signatures.
+	(ecc-255.h): Change parameters from k = 14, c = 6 to k = 11, c =
+	6. Table size unchanged, 16 KB. 24% speedup for eddsa signatures.
+
 2018-02-20  Niels Möller  <nisse@lysator.liu.se>
 
 	* testsuite/cmac-test.c (test_cmac_hash): Deallocate ctx properly.
diff --git a/Makefile.in b/Makefile.in
index 56992cfe..52ac0482 100644
--- a/Makefile.in
+++ b/Makefile.in
@@ -326,50 +326,54 @@ desdata.stamp: desdata.c
 
 des.$(OBJEXT): des.c des.h $(des_headers)
 
-# Generate ECC files.
-# Some possible choices for 192:
-#	k = 15, c = 4,  64 entries,  ~3 KB
-#	k = 20, c = 6, 128 entries,  ~6 KB
-#	k = 10, c = 6, 256 entries, ~12 KB
-#	k =  7, c = 6, 320 entries, ~15 KB
-#	k =  9, c = 7, 512 entries, ~24 KB
+# Generate ECC files, with roughly 16 KB of tables per curve.
+
+# Some reasonable choices for 192:
+# k =  8, c =  6, S = 256, T =  40 ( 32 A +  8 D) 12 KB
+# k = 14, c =  7, S = 256, T =  42 ( 28 A + 14 D) 12 KB
+# k = 11, c =  6, S = 192, T =  44 ( 33 A + 11 D)  9 KB
+# k = 16, c =  6, S = 128, T =  48 ( 32 A + 16 D)  6 KB
 ecc-192.h: eccdata.stamp
-	./eccdata$(EXEEXT_FOR_BUILD) 192 7 6 $(NUMB_BITS) > $@T && mv $@T $@
-# Some possible choices for 224:
-#	k = 18, c = 4,  64 entries,  ~4 KB
-#	k = 24, c = 6, 128 entries,  ~8 KB
-#	k = 12, c = 6, 256 entries, ~16 KB
-#	k =  8, c = 6, 320 entries, ~20 KB
-#	k = 10, c = 7, 512 entries, ~32 KB
+	./eccdata$(EXEEXT_FOR_BUILD) 192 8 6 $(NUMB_BITS) > $@T && mv $@T $@
+
+# Some reasonable choices for 224:
+# k = 16, c =  7, S = 256, T =  48 ( 32 A + 16 D) ~16 KB
+# k = 10, c =  6, S = 256, T =  50 ( 40 A + 10 D) ~16 KB
+# k = 13, c =  6, S = 192, T =  52 ( 39 A + 13 D) ~12 KB
+# k =  9, c =  5, S = 160, T =  54 ( 45 A +  9 D) ~10 KB
 ecc-224.h: eccdata.stamp
-	./eccdata$(EXEEXT_FOR_BUILD) 224 12 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
+	./eccdata$(EXEEXT_FOR_BUILD) 224 16 7 $(NUMB_BITS) > $@T && mv $@T $@
+
+# Some reasonable choices for 256:
+# k =  9, c =  6, S = 320, T =  54 ( 45 A +  9 D) 20 KB
+# k = 11, c =  6, S = 256, T =  55 ( 44 A + 11 D) 16 KB
+# k = 19, c =  7, S = 256, T =  57 ( 38 A + 19 D) 16 KB
+# k = 15, c =  6, S = 192, T =  60 ( 45 A + 15 D) 12 KB
 ecc-256.h: eccdata.stamp
-	./eccdata$(EXEEXT_FOR_BUILD) 256 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
-#	k = 20, c = 6, 256 entries, ~24 KB
-#	k = 14, c = 6, 320 entries, ~30 KB
-#	k = 18, c = 7, 512 entries, ~48 KB
+	./eccdata$(EXEEXT_FOR_BUILD) 256 11 6 $(NUMB_BITS) > $@T && mv $@T $@
+
+# Some reasonable choices for 384:
+# k = 16, c =  6, S = 256, T =  80 ( 64 A + 16 D) 24 KB
+# k = 28, c =  7, S = 256, T =  84 ( 56 A + 28 D) 24 KB
+# k = 11, c =  5, S = 224, T =  88 ( 77 A + 11 D) 21 KB
+# k = 22, c =  6, S = 192, T =  88 ( 66 A + 22 D) 18 KB
+# k = 13, c =  5, S = 192, T =  91 ( 78 A + 13 D) 18 KB
+# k = 16, c =  5, S = 160, T =  96 ( 80 A + 16 D) 15 KB
+# k = 32, c =  6, S = 128, T =  96 ( 64 A + 32 D) 12 KB
 ecc-384.h: eccdata.stamp
-	./eccdata$(EXEEXT_FOR_BUILD) 384 41 6 $(NUMB_BITS) > $@T && mv $@T $@
-# Some possible choices for 521:
-#	k = 42, c = 4,  64 entries,  ~9 KB
-#	k = 56, c = 6, 128 entries, ~18 KB
-#	k = 28, c = 6, 256 entries, ~35 KB
-#	k = 19, c = 6, 320 entries, ~44 KB
-#	k = 24, c = 7, 512 entries, ~70 KB
+	./eccdata$(EXEEXT_FOR_BUILD) 384 32 6 $(NUMB_BITS) > $@T && mv $@T $@
+
+# Some reasonable choices for 521:
+# k = 29, c =  6, S = 192, T = 116 ( 87 A + 29 D) ~27 KB
+# k = 21, c =  5, S = 160, T = 126 (105 A + 21 D) ~23 KB
+# k = 44, c =  6, S = 128, T = 132 ( 88 A + 44 D) ~18 KB
+# k = 35, c =  5, S =  96, T = 140 (105 A + 35 D) ~14 KB
 ecc-521.h: eccdata.stamp
-	./eccdata$(EXEEXT_FOR_BUILD) 521 56 6 $(NUMB_BITS) > $@T && mv $@T $@
+	./eccdata$(EXEEXT_FOR_BUILD) 521 44 6 $(NUMB_BITS) > $@T && mv $@T $@
 
+# Parameter choices mostly the same as for ecc-256.h.
 ecc-25519.h: eccdata.stamp
-	./eccdata$(EXEEXT_FOR_BUILD) 255 14 6 $(NUMB_BITS) > $@T && mv $@T $@
+	./eccdata$(EXEEXT_FOR_BUILD) 255 11 6 $(NUMB_BITS) > $@T && mv $@T $@
 
 eccdata.stamp: eccdata.c
 	$(MAKE) eccdata$(EXEEXT_FOR_BUILD)