[openssl-dev] [openssl.org #3667] [PATCH] Faster GLV elliptic curves

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
3 messages Options
Reply | Threaded
Open this post in threaded view
|

[openssl-dev] [openssl.org #3667] [PATCH] Faster GLV elliptic curves

Rich Salz via RT
This patch gives about 50% speed improvement for existing GLV elliptic
curves in OpenSSL. Read about it here:

http://eprint.iacr.org/2015/036

It could use a review. Perhaps the best known use case for secp256k1
right now is Bitcoin.

BBB

Before:
                              op      op/s
 160 bit ecdh (secp160r1)   0.0001s   6730.6
 192 bit ecdh (nistp192)   0.0002s   5714.8
 224 bit ecdh (nistp224)   0.0002s   4153.6
 256 bit ecdh (nistp256)   0.0003s   3573.1
 160 bit ecdh (secp160k1)   0.0002s   6198.2
 192 bit ecdh (secp192k1)   0.0002s   5191.9
 224 bit ecdh (secp224k1)   0.0003s   3789.3
 256 bit ecdh (secp256k1)   0.0003s   3281.2

                              sign    verify    sign/s verify/s
 160 bit ecdsa (secp160r1)   0.0001s   0.0002s  19289.6   5581.5
 192 bit ecdsa (nistp192)   0.0001s   0.0002s  16011.7   4650.7
 224 bit ecdsa (nistp224)   0.0001s   0.0003s  12987.1   3378.2
 256 bit ecdsa (nistp256)   0.0001s   0.0003s  11061.8   2913.0
 160 bit ecdsa (secp160k1)   0.0001s   0.0002s  18946.5   5290.5
 192 bit ecdsa (secp192k1)   0.0001s   0.0002s  15605.9   4289.9
 224 bit ecdsa (secp224k1)   0.0001s   0.0003s  12752.6   3145.9
 256 bit ecdsa (secp256k1)   0.0001s   0.0004s  10803.0   2733.2



After:
                              op      op/s
 160 bit ecdh (secp160r1)   0.0001s   6798.4
 192 bit ecdh (nistp192)   0.0002s   5667.2
 224 bit ecdh (nistp224)   0.0002s   4081.5
 256 bit ecdh (nistp256)   0.0003s   3578.9
 160 bit ecdh (secp160k1)   0.0001s   9102.5
 192 bit ecdh (secp192k1)   0.0001s   7784.3
 224 bit ecdh (secp224k1)   0.0002s   5554.4
 256 bit ecdh (secp256k1)   0.0002s   4890.4

                              sign    verify    sign/s verify/s
 160 bit ecdsa (secp160r1)   0.0001s   0.0002s  19264.6   5416.7
 192 bit ecdsa (nistp192)   0.0001s   0.0002s  15956.0   4723.1
 224 bit ecdsa (nistp224)   0.0001s   0.0003s  12855.8   3379.9
 256 bit ecdsa (nistp256)   0.0001s   0.0003s  11017.8   2911.7
 160 bit ecdsa (secp160k1)   0.0001s   0.0001s  18959.9   6705.4
 192 bit ecdsa (secp192k1)   0.0001s   0.0002s  15624.0   5681.4
 224 bit ecdsa (secp224k1)   0.0001s   0.0002s  12513.0   4189.3
 256 bit ecdsa (secp256k1)   0.0001s   0.0003s  10621.2   3569.8



$ cat /proc/cpuinfo
processor    : 0
vendor_id    : GenuineIntel
cpu family    : 6
model        : 60
model name    : Intel(R) Core(TM) i5-4570 CPU @ 3.20GHz
stepping    : 3
microcode    : 26
cpu MHz        : 800.000
cache size    : 6144 KB
physical id    : 0
siblings    : 4
core id        : 0
cpu cores    : 4
apicid        : 0
initial apicid    : 0
fpu        : yes
fpu_exception    : yes
cpuid level    : 13
wp        : yes
flags        : fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge
mca cmov pat pse36 clflush dts acpi mmx fxsr sse sse2 ss ht tm pbe
syscall nx pdpe1gb rdtscp lm constant_tsc arch_perfmon pebs bts
rep_good xtopology nonstop_tsc aperfmperf pni pclmulqdq dtes64 monitor
ds_cpl vmx smx est tm2 ssse3 fma cx16 xtpr pdcm pcid sse4_1 sse4_2
x2apic movbe popcnt tsc_deadline_timer aes xsave avx f16c rdrand
lahf_lm abm ida arat epb xsaveopt pln pts dts tpr_shadow vnmi
flexpriority ept vpid fsgsbase bmi1 hle avx2 smep bmi2 erms invpcid
rtm
bogomips    : 6384.88
clflush size    : 64
cache_alignment    : 64
address sizes    : 39 bits physical, 48 bits virtual
power management: SNIP


diff -ru --new-file openssl-1.0.1l-orig/apps/speed.c openssl-1.0.1l/apps/speed.c
--- openssl-1.0.1l-orig/apps/speed.c 2015-01-15 16:43:49.000000000 +0200
+++ openssl-1.0.1l/apps/speed.c 2015-01-19 13:44:38.232456333 +0200
@@ -244,7 +244,7 @@
 #define RSA_NUM 4
 #define DSA_NUM 3
 
-#define EC_NUM       16
+#define EC_NUM       8
 #define MAX_ECDH_SIZE 256
 
 static const char *names[ALGOR_NUM]={
@@ -512,18 +512,10 @@
 #define R_EC_P192    1
 #define R_EC_P224    2
 #define R_EC_P256    3
-#define R_EC_P384    4
-#define R_EC_P521    5
-#define R_EC_K163    6
-#define R_EC_K233    7
-#define R_EC_K283    8
-#define R_EC_K409    9
-#define R_EC_K571    10
-#define R_EC_B163    11
-#define R_EC_B233    12
-#define R_EC_B283    13
-#define R_EC_B409    14
-#define R_EC_B571    15
+#define R_EC_K160    4
+#define R_EC_K192    5
+#define R_EC_K224    6
+#define R_EC_K256    7
 
 #ifndef OPENSSL_NO_RSA
  RSA *rsa_key[RSA_NUM];
@@ -553,19 +545,10 @@
  NID_X9_62_prime192v1,
  NID_secp224r1,
  NID_X9_62_prime256v1,
- NID_secp384r1,
- NID_secp521r1,
- /* Binary Curves */
- NID_sect163k1,
- NID_sect233k1,
- NID_sect283k1,
- NID_sect409k1,
- NID_sect571k1,
- NID_sect163r2,
- NID_sect233r1,
- NID_sect283r1,
- NID_sect409r1,
- NID_sect571r1
+ NID_secp160k1,
+ NID_secp192k1,
+ NID_secp224k1,
+ NID_secp256k1
  };
  static const char * test_curves_names[EC_NUM] =
  {
@@ -574,25 +557,15 @@
  "nistp192",
  "nistp224",
  "nistp256",
- "nistp384",
- "nistp521",
- /* Binary Curves */
- "nistk163",
- "nistk233",
- "nistk283",
- "nistk409",
- "nistk571",
- "nistb163",
- "nistb233",
- "nistb283",
- "nistb409",
- "nistb571"
+ "secp160k1",
+ "secp192k1",
+ "secp224k1",
+ "secp256k1"
  };
  static int test_curves_bits[EC_NUM] =
         {
-        160, 192, 224, 256, 384, 521,
-        163, 233, 283, 409, 571,
-        163, 233, 283, 409, 571
+        160, 192, 224, 256,
+        160, 192, 224, 256
         };
 
 #endif
@@ -962,18 +935,10 @@
  else if (strcmp(*argv,"ecdsap192") == 0) ecdsa_doit[R_EC_P192]=2;
  else if (strcmp(*argv,"ecdsap224") == 0) ecdsa_doit[R_EC_P224]=2;
  else if (strcmp(*argv,"ecdsap256") == 0) ecdsa_doit[R_EC_P256]=2;
- else if (strcmp(*argv,"ecdsap384") == 0) ecdsa_doit[R_EC_P384]=2;
- else if (strcmp(*argv,"ecdsap521") == 0) ecdsa_doit[R_EC_P521]=2;
- else if (strcmp(*argv,"ecdsak163") == 0) ecdsa_doit[R_EC_K163]=2;
- else if (strcmp(*argv,"ecdsak233") == 0) ecdsa_doit[R_EC_K233]=2;
- else if (strcmp(*argv,"ecdsak283") == 0) ecdsa_doit[R_EC_K283]=2;
- else if (strcmp(*argv,"ecdsak409") == 0) ecdsa_doit[R_EC_K409]=2;
- else if (strcmp(*argv,"ecdsak571") == 0) ecdsa_doit[R_EC_K571]=2;
- else if (strcmp(*argv,"ecdsab163") == 0) ecdsa_doit[R_EC_B163]=2;
- else if (strcmp(*argv,"ecdsab233") == 0) ecdsa_doit[R_EC_B233]=2;
- else if (strcmp(*argv,"ecdsab283") == 0) ecdsa_doit[R_EC_B283]=2;
- else if (strcmp(*argv,"ecdsab409") == 0) ecdsa_doit[R_EC_B409]=2;
- else if (strcmp(*argv,"ecdsab571") == 0) ecdsa_doit[R_EC_B571]=2;
+ else if (strcmp(*argv,"ecdsak160") == 0) ecdsa_doit[R_EC_K160]=2;
+ else if (strcmp(*argv,"ecdsak192") == 0) ecdsa_doit[R_EC_K192]=2;
+ else if (strcmp(*argv,"ecdsak224") == 0) ecdsa_doit[R_EC_K224]=2;
+ else if (strcmp(*argv,"ecdsak256") == 0) ecdsa_doit[R_EC_K256]=2;
  else if (strcmp(*argv,"ecdsa") == 0)
  {
  for (i=0; i < EC_NUM; i++)
@@ -986,18 +951,10 @@
  else if (strcmp(*argv,"ecdhp192") == 0) ecdh_doit[R_EC_P192]=2;
  else if (strcmp(*argv,"ecdhp224") == 0) ecdh_doit[R_EC_P224]=2;
  else if (strcmp(*argv,"ecdhp256") == 0) ecdh_doit[R_EC_P256]=2;
- else if (strcmp(*argv,"ecdhp384") == 0) ecdh_doit[R_EC_P384]=2;
- else if (strcmp(*argv,"ecdhp521") == 0) ecdh_doit[R_EC_P521]=2;
- else if (strcmp(*argv,"ecdhk163") == 0) ecdh_doit[R_EC_K163]=2;
- else if (strcmp(*argv,"ecdhk233") == 0) ecdh_doit[R_EC_K233]=2;
- else if (strcmp(*argv,"ecdhk283") == 0) ecdh_doit[R_EC_K283]=2;
- else if (strcmp(*argv,"ecdhk409") == 0) ecdh_doit[R_EC_K409]=2;
- else if (strcmp(*argv,"ecdhk571") == 0) ecdh_doit[R_EC_K571]=2;
- else if (strcmp(*argv,"ecdhb163") == 0) ecdh_doit[R_EC_B163]=2;
- else if (strcmp(*argv,"ecdhb233") == 0) ecdh_doit[R_EC_B233]=2;
- else if (strcmp(*argv,"ecdhb283") == 0) ecdh_doit[R_EC_B283]=2;
- else if (strcmp(*argv,"ecdhb409") == 0) ecdh_doit[R_EC_B409]=2;
- else if (strcmp(*argv,"ecdhb571") == 0) ecdh_doit[R_EC_B571]=2;
+ else if (strcmp(*argv,"ecdhk160") == 0) ecdh_doit[R_EC_K160]=2;
+ else if (strcmp(*argv,"ecdhk192") == 0) ecdh_doit[R_EC_K192]=2;
+ else if (strcmp(*argv,"ecdhk224") == 0) ecdh_doit[R_EC_K224]=2;
+ else if (strcmp(*argv,"ecdhk256") == 0) ecdh_doit[R_EC_K256]=2;
  else if (strcmp(*argv,"ecdh") == 0)
  {
  for (i=0; i < EC_NUM; i++)
diff -ru --new-file openssl-1.0.1l-orig/crypto/ec/ec_curve.c openssl-1.0.1l/crypto/ec/ec_curve.c
--- openssl-1.0.1l-orig/crypto/ec/ec_curve.c 2015-01-15 16:43:49.000000000 +0200
+++ openssl-1.0.1l/crypto/ec/ec_curve.c 2015-01-19 13:43:51.375897173 +0200
@@ -1836,18 +1836,18 @@
  { NID_secp112r2, &_EC_SECG_PRIME_112R2.h, 0, "SECG curve over a 112 bit prime field" },
  { NID_secp128r1, &_EC_SECG_PRIME_128R1.h, 0, "SECG curve over a 128 bit prime field" },
  { NID_secp128r2, &_EC_SECG_PRIME_128R2.h, 0, "SECG curve over a 128 bit prime field" },
- { NID_secp160k1, &_EC_SECG_PRIME_160K1.h, 0, "SECG curve over a 160 bit prime field" },
+ { NID_secp160k1, &_EC_SECG_PRIME_160K1.h, EC_GFp_glv_method, "SECG curve over a 160 bit prime field" },
  { NID_secp160r1, &_EC_SECG_PRIME_160R1.h, 0, "SECG curve over a 160 bit prime field" },
  { NID_secp160r2, &_EC_SECG_PRIME_160R2.h, 0, "SECG/WTLS curve over a 160 bit prime field" },
  /* SECG secp192r1 is the same as X9.62 prime192v1 and hence omitted */
- { NID_secp192k1, &_EC_SECG_PRIME_192K1.h, 0, "SECG curve over a 192 bit prime field" },
- { NID_secp224k1, &_EC_SECG_PRIME_224K1.h, 0, "SECG curve over a 224 bit prime field" },
+ { NID_secp192k1, &_EC_SECG_PRIME_192K1.h, EC_GFp_glv_method, "SECG curve over a 192 bit prime field" },
+ { NID_secp224k1, &_EC_SECG_PRIME_224K1.h, EC_GFp_glv_method, "SECG curve over a 224 bit prime field" },
 #ifndef OPENSSL_NO_EC_NISTP_64_GCC_128
  { NID_secp224r1, &_EC_NIST_PRIME_224.h, EC_GFp_nistp224_method, "NIST/SECG curve over a 224 bit prime field" },
 #else
  { NID_secp224r1, &_EC_NIST_PRIME_224.h, 0, "NIST/SECG curve over a 224 bit prime field" },
 #endif
- { NID_secp256k1, &_EC_SECG_PRIME_256K1.h, 0, "SECG curve over a 256 bit prime field" },
+ { NID_secp256k1, &_EC_SECG_PRIME_256K1.h, EC_GFp_glv_method, "SECG curve over a 256 bit prime field" },
  /* SECG secp256r1 is the same as X9.62 prime256v1 and hence omitted */
  { NID_secp384r1, &_EC_NIST_PRIME_384.h, 0, "NIST/SECG curve over a 384 bit prime field" },
 #ifndef OPENSSL_NO_EC_NISTP_64_GCC_128
diff -ru --new-file openssl-1.0.1l-orig/crypto/ec/ec.h openssl-1.0.1l/crypto/ec/ec.h
--- openssl-1.0.1l-orig/crypto/ec/ec.h 2015-01-15 16:43:49.000000000 +0200
+++ openssl-1.0.1l/crypto/ec/ec.h 2015-01-19 13:43:50.864153182 +0200
@@ -146,6 +146,11 @@
  */
 const EC_METHOD *EC_GFp_mont_method(void);
 
+/** Returns GFp methods using optimized methods for GLV curves
+ *  \return  EC_METHOD object
+ */
+const EC_METHOD *EC_GFp_glv_method(void);
+
 /** Returns GFp methods using optimized methods for NIST recommended curves
  *  \return  EC_METHOD object
  */
diff -ru --new-file openssl-1.0.1l-orig/crypto/ec/ec_lcl.h openssl-1.0.1l/crypto/ec/ec_lcl.h
--- openssl-1.0.1l-orig/crypto/ec/ec_lcl.h 2015-01-15 16:43:49.000000000 +0200
+++ openssl-1.0.1l/crypto/ec/ec_lcl.h 2015-01-19 13:43:51.080045178 +0200
@@ -348,6 +348,13 @@
 int ec_GFp_mont_field_set_to_one(const EC_GROUP *, BIGNUM *r, BN_CTX *);
 
 
+/* method functions in ecp_glv.c */
+int ec_GFp_glv_mul(const EC_GROUP *group, EC_POINT *r, const BIGNUM *scalar,
+ size_t num, const EC_POINT *points[], const BIGNUM *scalars[], BN_CTX *ctx);
+int ec_GFp_glv_precompute_mult(EC_GROUP *group, BN_CTX *ctx);
+int ec_GFp_glv_have_precompute_mult(const EC_GROUP *group);
+
+
 /* method functions in ecp_nist.c */
 int ec_GFp_nist_group_copy(EC_GROUP *dest, const EC_GROUP *src);
 int ec_GFp_nist_group_set_curve(EC_GROUP *, const BIGNUM *p, const BIGNUM *a, const BIGNUM *b, BN_CTX *);
diff -ru --new-file openssl-1.0.1l-orig/crypto/ec/ecp_glv.c openssl-1.0.1l/crypto/ec/ecp_glv.c
--- openssl-1.0.1l-orig/crypto/ec/ecp_glv.c 1970-01-01 02:00:00.000000000 +0200
+++ openssl-1.0.1l/crypto/ec/ecp_glv.c 2015-01-20 11:30:44.442723943 +0200
@@ -0,0 +1,336 @@
+#include <openssl/err.h>
+
+#ifdef OPENSSL_FIPS
+#include <openssl/fips.h>
+#endif
+
+#include "ec_lcl.h"
+
+/**
+ * Faster scalar multiplication for GLV curves:
+ * http://eprint.iacr.org/2015/036
+ *
+ * @author Billy Brumley <billy.brumley AT tut DOT fi>
+ */
+
+const EC_METHOD *EC_GFp_glv_method(void)
+ {
+ static const EC_METHOD ret = {
+ EC_FLAGS_DEFAULT_OCT,
+ NID_X9_62_prime_field,
+ ec_GFp_mont_group_init,
+ ec_GFp_mont_group_finish,
+ ec_GFp_mont_group_clear_finish,
+ ec_GFp_mont_group_copy,
+ ec_GFp_mont_group_set_curve,
+ ec_GFp_simple_group_get_curve,
+ ec_GFp_simple_group_get_degree,
+ ec_GFp_simple_group_check_discriminant,
+ ec_GFp_simple_point_init,
+ ec_GFp_simple_point_finish,
+ ec_GFp_simple_point_clear_finish,
+ ec_GFp_simple_point_copy,
+ ec_GFp_simple_point_set_to_infinity,
+ ec_GFp_simple_set_Jprojective_coordinates_GFp,
+ ec_GFp_simple_get_Jprojective_coordinates_GFp,
+ ec_GFp_simple_point_set_affine_coordinates,
+ ec_GFp_simple_point_get_affine_coordinates,
+ 0,0,0,
+ ec_GFp_simple_add,
+ ec_GFp_simple_dbl,
+ ec_GFp_simple_invert,
+ ec_GFp_simple_is_at_infinity,
+ ec_GFp_simple_is_on_curve,
+ ec_GFp_simple_cmp,
+ ec_GFp_simple_make_affine,
+ ec_GFp_simple_points_make_affine,
+ ec_GFp_glv_mul,
+ ec_GFp_glv_precompute_mult,
+ ec_GFp_glv_have_precompute_mult,
+ ec_GFp_mont_field_mul,
+ ec_GFp_mont_field_sqr,
+ 0 /* field_div */,
+ ec_GFp_mont_field_encode,
+ ec_GFp_mont_field_decode,
+ ec_GFp_mont_field_set_to_one };
+
+#ifdef OPENSSL_FIPS
+ if (FIPS_mode())
+ return fips_ec_gfp_glv_method();
+#endif
+
+ return &ret;
+ }
+
+/* GLV-related per-curve constants */
+static const unsigned char glv_constants_secp160k1[] = {
+ /* beta */
+ 0x9b,0xa4,0x8c,0xba,0x5e,0xbc,0xb9,0xb6,
+ 0xbd,0x33,0xb9,0x28,0x30,0xb2,0xa2,0xe0,
+ 0xe1,0x92,0xf1,0x0a,
+ /* a1 */
+ 0x91,0x62,0xfb,0xe7,0x39,0x84,0x47,0x2a,
+ 0x0a,0x9e,
+ /* b1 */
+ 0x96,0x34,0x1f,0x11,0x38,0x93,0x3b,0xc2,
+ 0xf5,0x05,
+ /* a2 */
+ 0x01,0x27,0x97,0x1a,0xf8,0x72,0x17,0x82,
+ 0xec,0xff,0xa3,
+ /* b2 */
+ 0x91,0x62,0xfb,0xe7,0x39,0x84,0x47,0x2a,
+ 0x0a,0x9e
+};
+
+static const unsigned char glv_constants_secp192k1[] = {
+ /* beta */
+ 0xbb,0x85,0x69,0x19,0x39,0xb8,0x69,0xc1,
+ 0xd0,0x87,0xf6,0x01,0x55,0x4b,0x96,0xb8,
+ 0x0c,0xb4,0xf5,0x5b,0x35,0xf4,0x33,0xc2,
+ /* a1 */
+ 0x71,0x16,0x9b,0xe7,0x33,0x0b,0x30,0x38,
+ 0xed,0xb0,0x25,0xf1,
+ /* b1 */
+ 0xb3,0xfb,0x34,0x00,0xde,0xc5,0xc4,0xad,
+ 0xce,0xb8,0x65,0x5c,
+ /* a2 */
+ 0x01,0x25,0x11,0xcf,0xe8,0x11,0xd0,0xf4,
+ 0xe6,0xbc,0x68,0x8b,0x4d,
+ /* b2 */
+ 0x71,0x16,0x9b,0xe7,0x33,0x0b,0x30,0x38,
+ 0xed,0xb0,0x25,0xf1
+};
+
+static const unsigned char glv_constants_secp224k1[] = {
+ /* beta */
+ 0x01,0xf1,0x78,0xff,0xa4,0xb1,0x7c,0x89,
+ 0xe6,0xf7,0x3a,0xec,0xe2,0xaa,0xd5,0x7a,
+ 0xf4,0xc0,0xa7,0x48,0xb6,0x3c,0x83,0x09,
+ 0x47,0xb2,0x7e,0x04,
+ /* a1 */
+ 0xb8,0xad,0xf1,0x37,0x8a,0x6e,0xb7,0x34,
+ 0x09,0xfa,0x6c,0x9c,0x63,0x7d,
+ /* b1 */
+ 0x6b,0x8c,0xf0,0x7d,0x4c,0xa7,0x5c,0x88,
+ 0x95,0x7d,0x9d,0x67,0x05,0x91,
+ /* a2 */
+ 0x6b,0x8c,0xf0,0x7d,0x4c,0xa7,0x5c,0x88,
+ 0x95,0x7d,0x9d,0x67,0x05,0x91,
+ /* b2 */
+ 0x01,0x24,0x3a,0xe1,0xb4,0xd7,0x16,0x13,
+ 0xbc,0x9f,0x78,0x0a,0x03,0x69,0x0e
+};
+
+static const unsigned char glv_constants_secp256k1[] = {
+ /* beta */
+ 0x85,0x16,0x95,0xd4,0x9a,0x83,0xf8,0xef,
+ 0x91,0x9b,0xb8,0x61,0x53,0xcb,0xcb,0x16,
+ 0x63,0x0f,0xb6,0x8a,0xed,0x0a,0x76,0x6a,
+ 0x3e,0xc6,0x93,0xd6,0x8e,0x6a,0xfa,0x40,
+ /* a1 */
+ 0xe4,0x43,0x7e,0xd6,0x01,0x0e,0x88,0x28,
+ 0x6f,0x54,0x7f,0xa9,0x0a,0xbf,0xe4,0xc3,
+ /* b1 */
+ 0x30,0x86,0xd2,0x21,0xa7,0xd4,0x6b,0xcd,
+ 0xe8,0x6c,0x90,0xe4,0x92,0x84,0xeb,0x15,
+ /* a2 */
+ 0x30,0x86,0xd2,0x21,0xa7,0xd4,0x6b,0xcd,
+ 0xe8,0x6c,0x90,0xe4,0x92,0x84,0xeb,0x15,
+ /* b2 */
+ 0x01,0x14,0xca,0x50,0xf7,0xa8,0xe2,0xf3,
+ 0xf6,0x57,0xc1,0x10,0x8d,0x9d,0x44,0xcf,
+ 0xd8
+};
+
+/**
+ * Integer decomposition.
+ * See 3.5 in "Guide to Elliptic Curve Cryptography"
+ *
+ * The alg is slightly re-arranged to keep all constants positive
+ *
+ * n  = constants[0]
+ * a1 = constants[2]
+ * b1 = constants[3]
+ * a2 = constants[4]
+ * b2 = constants[5]
+ */
+int ec_GFp_glv_decompose(BIGNUM *k1, BIGNUM *k2, const BIGNUM *scalar, const BIGNUM **constants, BN_CTX *ctx) {
+
+ int ret = 0;
+
+ BIGNUM *twok, *c1, *c2;
+
+ BN_CTX_start(ctx);
+
+ do {
+ twok = BN_CTX_get(ctx);
+ c1   = BN_CTX_get(ctx);
+ if ((c2 = BN_CTX_get(ctx)) == NULL) break;
+
+ if (!BN_lshift1(twok, scalar)) break;
+
+ /* weird computation is for closest int rounding */
+ /* c1 = (2*b2*k+r[0])/(2*r[0]) */
+ /* c2 = (2*b1*k+r[0])/(2*r[0]) */
+ if (!BN_mul(c1, twok, constants[5], ctx)) break;
+ if (!BN_add(c1, c1, constants[0])) break;
+ if (!BN_div(c1, NULL, c1, constants[0], ctx)) break;
+ if (!BN_rshift1(c1, c1)) break;
+ if (!BN_mul(c2, twok, constants[3], ctx)) break;
+ if (!BN_add(c2, c2, constants[0])) break;
+ if (!BN_div(c2, NULL, c2, constants[0], ctx)) break;
+ if (!BN_rshift1(c2, c2)) break;
+
+ /* k1 = k - (c1*a1 + c2*a2) */
+ /* k2 = c1*b1 - c2*b2 */
+ if (!BN_mul(k1, constants[2], c1, ctx)) break;
+ if (!BN_mul(k2, constants[4], c2, ctx)) break;
+ if (!BN_add(k1, k1, k2)) break;
+ if (!BN_sub(k1, scalar, k1)) break;
+ if (!BN_mul(c1, constants[3], c1, ctx)) break;
+ if (!BN_mul(c2, constants[5], c2, ctx)) break;
+ if (!BN_sub(k2, c1, c2)) break;
+
+ ret = 1;
+ } while(0);
+
+ BN_CTX_end(ctx);
+
+ return ret;
+
+}
+
+/**
+ * Computes the sum
+ * scalar*group->generator + scalars[0]*points[0] + ... + scalars[num-1]*points[num-1]
+ */
+int ec_GFp_glv_mul(const EC_GROUP *group, EC_POINT *r, const BIGNUM *scalar,
+ size_t num, const EC_POINT *points[], const BIGNUM *scalars[], BN_CTX *ctx)
+ {
+
+ /* use default stuff if we have precomp and it can help */
+ if(num == 0 && EC_GROUP_have_precompute_mult(group))
+ return ec_wNAF_mul(group, r, scalar, num, points, scalars, ctx);
+
+ int i, ret = 0;
+
+ BIGNUM *tscalar = NULL;
+ EC_POINT **tpoints = NULL;
+ BIGNUM **tscalars = NULL;
+ BIGNUM **constants = NULL;
+
+ if ((constants = OPENSSL_malloc(6*sizeof(BIGNUM *))) == NULL) return 0;
+
+ BN_CTX_start(ctx);
+
+ /* fill in the constants */
+ for(i=0; i<6; i++) {
+ constants[i] = BN_CTX_get(ctx);
+ }
+
+ if(constants[5] == NULL) goto err;
+
+ if (!EC_GROUP_get_order(group, constants[0], ctx)) goto err;
+
+ switch(EC_GROUP_get_curve_name(group)) {
+ case NID_secp160k1:
+ BN_bin2bn(glv_constants_secp160k1 +  0, 20, constants[1]);
+ BN_bin2bn(glv_constants_secp160k1 + 20, 10, constants[2]);
+ BN_bin2bn(glv_constants_secp160k1 + 30, 10, constants[3]);
+ BN_bin2bn(glv_constants_secp160k1 + 40, 11, constants[4]);
+ BN_bin2bn(glv_constants_secp160k1 + 51, 10, constants[5]);
+ break;
+ case NID_secp192k1:
+ BN_bin2bn(glv_constants_secp192k1 +  0, 24, constants[1]);
+ BN_bin2bn(glv_constants_secp192k1 + 24, 12, constants[2]);
+ BN_bin2bn(glv_constants_secp192k1 + 36, 12, constants[3]);
+ BN_bin2bn(glv_constants_secp192k1 + 48, 13, constants[4]);
+ BN_bin2bn(glv_constants_secp192k1 + 61, 12, constants[5]);
+ break;
+ case NID_secp224k1:
+ BN_bin2bn(glv_constants_secp224k1 +  0, 28, constants[1]);
+ BN_bin2bn(glv_constants_secp224k1 + 28, 14, constants[2]);
+ BN_bin2bn(glv_constants_secp224k1 + 42, 14, constants[3]);
+ BN_bin2bn(glv_constants_secp224k1 + 56, 14, constants[4]);
+ BN_bin2bn(glv_constants_secp224k1 + 70, 15, constants[5]);
+ break;
+ case NID_secp256k1:
+ BN_bin2bn(glv_constants_secp256k1 +  0, 32, constants[1]);
+ BN_bin2bn(glv_constants_secp256k1 + 32, 16, constants[2]);
+ BN_bin2bn(glv_constants_secp256k1 + 48, 16, constants[3]);
+ BN_bin2bn(glv_constants_secp256k1 + 64, 16, constants[4]);
+ BN_bin2bn(glv_constants_secp256k1 + 80, 17, constants[5]);
+ break;
+ default:
+ goto err;
+ }
+
+ /* encode beta parameter to curve's finite field */
+ if (!group->meth->field_encode(group, constants[1], constants[1], ctx)) goto err;
+
+ /* setup some arrays and decompose scalar if it's present and apply endomorphism */
+ if(scalar == NULL) {
+ if ((tpoints = OPENSSL_malloc(2 * num * sizeof(EC_POINT *))) == NULL) goto err;
+ if ((tscalars = OPENSSL_malloc(2 * num * sizeof(BIGNUM *))) == NULL) goto err;
+ }
+ else {
+ if ((tpoints = OPENSSL_malloc((2 * num + 1) * sizeof(EC_POINT *))) == NULL) goto err;
+ if ((tscalars = OPENSSL_malloc((2 * num + 1) * sizeof(BIGNUM *))) == NULL) goto err;
+ tscalar = BN_CTX_get(ctx);
+ if ((tscalars[2*num] = BN_CTX_get(ctx)) == NULL) goto err;
+ if ((tpoints[2*num] = EC_POINT_new(group)) == NULL) goto err;
+ if (!EC_POINT_copy(tpoints[2*num], EC_GROUP_get0_generator(group))) goto err;
+ if (!group->meth->field_mul(group, &tpoints[2*num]->X, &tpoints[2*num]->X, constants[1], ctx)) goto err;
+ if (!ec_GFp_glv_decompose(tscalar, tscalars[2*num], scalar, (const BIGNUM **)constants, ctx)) goto err;
+ }
+
+ /* decompose all the other scalars and apply the endomorphism */
+ for(i=0; i < num; i++) {
+ tpoints[2*i  ] = *((EC_POINT **)points + 2*i);
+ if ((tpoints[2*i+1] = EC_POINT_new(group)) == NULL) goto err;
+ if (!EC_POINT_copy(tpoints[2*i+1], tpoints[2*i])) goto err;
+ if (!group->meth->field_mul(group, &tpoints[2*i+1]->X, &tpoints[2*i+1]->X, constants[1], ctx)) goto err;
+ tscalars[2*i  ] = BN_CTX_get(ctx);
+ if ((tscalars[2*i+1] = BN_CTX_get(ctx)) == NULL) goto err;
+ if (!ec_GFp_glv_decompose(tscalars[2*i], tscalars[2*i+1], scalars[i], (const BIGNUM **)constants, ctx)) goto err;
+ }
+
+ /* call into the multi scalar mult routine with new parameters */
+ if(scalar == NULL) {
+ ret = ec_wNAF_mul(group, r, scalar, 2*num, (const EC_POINT **)tpoints, (const BIGNUM **)tscalars, ctx);
+ }
+ else {
+ ret = ec_wNAF_mul(group, r, tscalar, 2*num+1, (const EC_POINT **)tpoints, (const BIGNUM **)tscalars, ctx);
+ }
+
+err:
+
+ /* cleanup */
+ if (tpoints != NULL) {
+ for(i=0; i < num; i++) {
+ EC_POINT_free(tpoints[2*i+1]);
+ }
+ if (scalar != NULL) {
+ EC_POINT_free(tpoints[2*num]);
+ }
+ }
+
+ BN_CTX_end(ctx);
+
+ OPENSSL_free(tpoints);
+ OPENSSL_free(tscalars);
+ OPENSSL_free(constants);
+
+ return ret;
+ }
+
+int ec_GFp_glv_precompute_mult(EC_GROUP *group, BN_CTX *ctx)
+ {
+ return ec_wNAF_precompute_mult(group, ctx);
+ }
+
+int ec_GFp_glv_have_precompute_mult(const EC_GROUP *group)
+ {
+ return ec_wNAF_have_precompute_mult(group);
+ }
+
diff -ru --new-file openssl-1.0.1l-orig/crypto/ec/Makefile openssl-1.0.1l/crypto/ec/Makefile
--- openssl-1.0.1l-orig/crypto/ec/Makefile 2015-01-15 16:45:04.000000000 +0200
+++ openssl-1.0.1l/crypto/ec/Makefile 2015-01-19 13:43:51.239965175 +0200
@@ -17,13 +17,13 @@
 APPS=
 
 LIB=$(TOP)/libcrypto.a
-LIBSRC= ec_lib.c ecp_smpl.c ecp_mont.c ecp_nist.c ec_cvt.c ec_mult.c\
+LIBSRC= ec_lib.c ecp_smpl.c ecp_mont.c ecp_glv.c ecp_nist.c ec_cvt.c ec_mult.c\
  ec_err.c ec_curve.c ec_check.c ec_print.c ec_asn1.c ec_key.c\
  ec2_smpl.c ec2_mult.c ec_ameth.c ec_pmeth.c eck_prn.c \
  ecp_nistp224.c ecp_nistp256.c ecp_nistp521.c ecp_nistputil.c \
  ecp_oct.c ec2_oct.c ec_oct.c
 
-LIBOBJ= ec_lib.o ecp_smpl.o ecp_mont.o ecp_nist.o ec_cvt.o ec_mult.o\
+LIBOBJ= ec_lib.o ecp_smpl.o ecp_mont.o ecp_glv.o ecp_nist.o ec_cvt.o ec_mult.o\
  ec_err.o ec_curve.o ec_check.o ec_print.o ec_asn1.o ec_key.o\
  ec2_smpl.o ec2_mult.o ec_ameth.o ec_pmeth.o eck_prn.o \
  ecp_nistp224.o ecp_nistp256.o ecp_nistp521.o ecp_nistputil.o \
@@ -233,6 +233,14 @@
 ecp_mont.o: ../../include/openssl/opensslv.h ../../include/openssl/ossl_typ.h
 ecp_mont.o: ../../include/openssl/safestack.h ../../include/openssl/stack.h
 ecp_mont.o: ../../include/openssl/symhacks.h ec_lcl.h ecp_mont.c
+ecp_glv.o: ../../include/openssl/asn1.h ../../include/openssl/bio.h
+ecp_glv.o: ../../include/openssl/bn.h ../../include/openssl/crypto.h
+ecp_glv.o: ../../include/openssl/e_os2.h ../../include/openssl/ec.h
+ecp_glv.o: ../../include/openssl/err.h ../../include/openssl/lhash.h
+ecp_glv.o: ../../include/openssl/obj_mac.h ../../include/openssl/opensslconf.h
+ecp_glv.o: ../../include/openssl/opensslv.h ../../include/openssl/ossl_typ.h
+ecp_glv.o: ../../include/openssl/safestack.h ../../include/openssl/stack.h
+ecp_glv.o: ../../include/openssl/symhacks.h ec_lcl.h ecp_glv.c
 ecp_nist.o: ../../include/openssl/asn1.h ../../include/openssl/bio.h
 ecp_nist.o: ../../include/openssl/bn.h ../../include/openssl/crypto.h
 ecp_nist.o: ../../include/openssl/e_os2.h ../../include/openssl/ec.h

_______________________________________________
openssl-dev mailing list
To unsubscribe: https://mta.openssl.org/mailman/listinfo/openssl-dev
Reply | Threaded
Open this post in threaded view
|

Re: [openssl.org #3667] [PATCH] Faster GLV elliptic curves

Billy Brumley
Ported from 1.0 to 1.1 -- PR:

https://github.com/openssl/openssl/pull/776

On Tue, Jan 20, 2015 at 4:02 PM, Billy Brumley via RT <[hidden email]> wrote:

> This patch gives about 50% speed improvement for existing GLV elliptic
> curves in OpenSSL. Read about it here:
>
> http://eprint.iacr.org/2015/036
>
> It could use a review. Perhaps the best known use case for secp256k1
> right now is Bitcoin.
>
> BBB
>
> Before:
>                               op      op/s
>  160 bit ecdh (secp160r1)   0.0001s   6730.6
>  192 bit ecdh (nistp192)   0.0002s   5714.8
>  224 bit ecdh (nistp224)   0.0002s   4153.6
>  256 bit ecdh (nistp256)   0.0003s   3573.1
>  160 bit ecdh (secp160k1)   0.0002s   6198.2
>  192 bit ecdh (secp192k1)   0.0002s   5191.9
>  224 bit ecdh (secp224k1)   0.0003s   3789.3
>  256 bit ecdh (secp256k1)   0.0003s   3281.2
>
>                               sign    verify    sign/s verify/s
>  160 bit ecdsa (secp160r1)   0.0001s   0.0002s  19289.6   5581.5
>  192 bit ecdsa (nistp192)   0.0001s   0.0002s  16011.7   4650.7
>  224 bit ecdsa (nistp224)   0.0001s   0.0003s  12987.1   3378.2
>  256 bit ecdsa (nistp256)   0.0001s   0.0003s  11061.8   2913.0
>  160 bit ecdsa (secp160k1)   0.0001s   0.0002s  18946.5   5290.5
>  192 bit ecdsa (secp192k1)   0.0001s   0.0002s  15605.9   4289.9
>  224 bit ecdsa (secp224k1)   0.0001s   0.0003s  12752.6   3145.9
>  256 bit ecdsa (secp256k1)   0.0001s   0.0004s  10803.0   2733.2
>
>
>
> After:
>                               op      op/s
>  160 bit ecdh (secp160r1)   0.0001s   6798.4
>  192 bit ecdh (nistp192)   0.0002s   5667.2
>  224 bit ecdh (nistp224)   0.0002s   4081.5
>  256 bit ecdh (nistp256)   0.0003s   3578.9
>  160 bit ecdh (secp160k1)   0.0001s   9102.5
>  192 bit ecdh (secp192k1)   0.0001s   7784.3
>  224 bit ecdh (secp224k1)   0.0002s   5554.4
>  256 bit ecdh (secp256k1)   0.0002s   4890.4
>
>                               sign    verify    sign/s verify/s
>  160 bit ecdsa (secp160r1)   0.0001s   0.0002s  19264.6   5416.7
>  192 bit ecdsa (nistp192)   0.0001s   0.0002s  15956.0   4723.1
>  224 bit ecdsa (nistp224)   0.0001s   0.0003s  12855.8   3379.9
>  256 bit ecdsa (nistp256)   0.0001s   0.0003s  11017.8   2911.7
>  160 bit ecdsa (secp160k1)   0.0001s   0.0001s  18959.9   6705.4
>  192 bit ecdsa (secp192k1)   0.0001s   0.0002s  15624.0   5681.4
>  224 bit ecdsa (secp224k1)   0.0001s   0.0002s  12513.0   4189.3
>  256 bit ecdsa (secp256k1)   0.0001s   0.0003s  10621.2   3569.8
>
>
>
> $ cat /proc/cpuinfo
> processor    : 0
> vendor_id    : GenuineIntel
> cpu family    : 6
> model        : 60
> model name    : Intel(R) Core(TM) i5-4570 CPU @ 3.20GHz
> stepping    : 3
> microcode    : 26
> cpu MHz        : 800.000
> cache size    : 6144 KB
> physical id    : 0
> siblings    : 4
> core id        : 0
> cpu cores    : 4
> apicid        : 0
> initial apicid    : 0
> fpu        : yes
> fpu_exception    : yes
> cpuid level    : 13
> wp        : yes
> flags        : fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge
> mca cmov pat pse36 clflush dts acpi mmx fxsr sse sse2 ss ht tm pbe
> syscall nx pdpe1gb rdtscp lm constant_tsc arch_perfmon pebs bts
> rep_good xtopology nonstop_tsc aperfmperf pni pclmulqdq dtes64 monitor
> ds_cpl vmx smx est tm2 ssse3 fma cx16 xtpr pdcm pcid sse4_1 sse4_2
> x2apic movbe popcnt tsc_deadline_timer aes xsave avx f16c rdrand
> lahf_lm abm ida arat epb xsaveopt pln pts dts tpr_shadow vnmi
> flexpriority ept vpid fsgsbase bmi1 hle avx2 smep bmi2 erms invpcid
> rtm
> bogomips    : 6384.88
> clflush size    : 64
> cache_alignment    : 64
> address sizes    : 39 bits physical, 48 bits virtual
> power management: SNIP
>
>
> diff -ru --new-file openssl-1.0.1l-orig/apps/speed.c openssl-1.0.1l/apps/speed.c
> --- openssl-1.0.1l-orig/apps/speed.c    2015-01-15 16:43:49.000000000 +0200
> +++ openssl-1.0.1l/apps/speed.c 2015-01-19 13:44:38.232456333 +0200
> @@ -244,7 +244,7 @@
>  #define RSA_NUM                4
>  #define DSA_NUM                3
>
> -#define EC_NUM       16
> +#define EC_NUM       8
>  #define MAX_ECDH_SIZE 256
>
>  static const char *names[ALGOR_NUM]={
> @@ -512,18 +512,10 @@
>  #define R_EC_P192    1
>  #define R_EC_P224    2
>  #define R_EC_P256    3
> -#define R_EC_P384    4
> -#define R_EC_P521    5
> -#define R_EC_K163    6
> -#define R_EC_K233    7
> -#define R_EC_K283    8
> -#define R_EC_K409    9
> -#define R_EC_K571    10
> -#define R_EC_B163    11
> -#define R_EC_B233    12
> -#define R_EC_B283    13
> -#define R_EC_B409    14
> -#define R_EC_B571    15
> +#define R_EC_K160    4
> +#define R_EC_K192    5
> +#define R_EC_K224    6
> +#define R_EC_K256    7
>
>  #ifndef OPENSSL_NO_RSA
>         RSA *rsa_key[RSA_NUM];
> @@ -553,19 +545,10 @@
>         NID_X9_62_prime192v1,
>         NID_secp224r1,
>         NID_X9_62_prime256v1,
> -       NID_secp384r1,
> -       NID_secp521r1,
> -       /* Binary Curves */
> -       NID_sect163k1,
> -       NID_sect233k1,
> -       NID_sect283k1,
> -       NID_sect409k1,
> -       NID_sect571k1,
> -       NID_sect163r2,
> -       NID_sect233r1,
> -       NID_sect283r1,
> -       NID_sect409r1,
> -       NID_sect571r1
> +       NID_secp160k1,
> +       NID_secp192k1,
> +       NID_secp224k1,
> +       NID_secp256k1
>         };
>         static const char * test_curves_names[EC_NUM] =
>         {
> @@ -574,25 +557,15 @@
>         "nistp192",
>         "nistp224",
>         "nistp256",
> -       "nistp384",
> -       "nistp521",
> -       /* Binary Curves */
> -       "nistk163",
> -       "nistk233",
> -       "nistk283",
> -       "nistk409",
> -       "nistk571",
> -       "nistb163",
> -       "nistb233",
> -       "nistb283",
> -       "nistb409",
> -       "nistb571"
> +       "secp160k1",
> +       "secp192k1",
> +       "secp224k1",
> +       "secp256k1"
>         };
>         static int test_curves_bits[EC_NUM] =
>          {
> -        160, 192, 224, 256, 384, 521,
> -        163, 233, 283, 409, 571,
> -        163, 233, 283, 409, 571
> +        160, 192, 224, 256,
> +        160, 192, 224, 256
>          };
>
>  #endif
> @@ -962,18 +935,10 @@
>                 else if (strcmp(*argv,"ecdsap192") == 0) ecdsa_doit[R_EC_P192]=2;
>                 else if (strcmp(*argv,"ecdsap224") == 0) ecdsa_doit[R_EC_P224]=2;
>                 else if (strcmp(*argv,"ecdsap256") == 0) ecdsa_doit[R_EC_P256]=2;
> -               else if (strcmp(*argv,"ecdsap384") == 0) ecdsa_doit[R_EC_P384]=2;
> -               else if (strcmp(*argv,"ecdsap521") == 0) ecdsa_doit[R_EC_P521]=2;
> -               else if (strcmp(*argv,"ecdsak163") == 0) ecdsa_doit[R_EC_K163]=2;
> -               else if (strcmp(*argv,"ecdsak233") == 0) ecdsa_doit[R_EC_K233]=2;
> -               else if (strcmp(*argv,"ecdsak283") == 0) ecdsa_doit[R_EC_K283]=2;
> -               else if (strcmp(*argv,"ecdsak409") == 0) ecdsa_doit[R_EC_K409]=2;
> -               else if (strcmp(*argv,"ecdsak571") == 0) ecdsa_doit[R_EC_K571]=2;
> -               else if (strcmp(*argv,"ecdsab163") == 0) ecdsa_doit[R_EC_B163]=2;
> -               else if (strcmp(*argv,"ecdsab233") == 0) ecdsa_doit[R_EC_B233]=2;
> -               else if (strcmp(*argv,"ecdsab283") == 0) ecdsa_doit[R_EC_B283]=2;
> -               else if (strcmp(*argv,"ecdsab409") == 0) ecdsa_doit[R_EC_B409]=2;
> -               else if (strcmp(*argv,"ecdsab571") == 0) ecdsa_doit[R_EC_B571]=2;
> +               else if (strcmp(*argv,"ecdsak160") == 0) ecdsa_doit[R_EC_K160]=2;
> +               else if (strcmp(*argv,"ecdsak192") == 0) ecdsa_doit[R_EC_K192]=2;
> +               else if (strcmp(*argv,"ecdsak224") == 0) ecdsa_doit[R_EC_K224]=2;
> +               else if (strcmp(*argv,"ecdsak256") == 0) ecdsa_doit[R_EC_K256]=2;
>                 else if (strcmp(*argv,"ecdsa") == 0)
>                         {
>                         for (i=0; i < EC_NUM; i++)
> @@ -986,18 +951,10 @@
>                 else if (strcmp(*argv,"ecdhp192") == 0) ecdh_doit[R_EC_P192]=2;
>                 else if (strcmp(*argv,"ecdhp224") == 0) ecdh_doit[R_EC_P224]=2;
>                 else if (strcmp(*argv,"ecdhp256") == 0) ecdh_doit[R_EC_P256]=2;
> -               else if (strcmp(*argv,"ecdhp384") == 0) ecdh_doit[R_EC_P384]=2;
> -               else if (strcmp(*argv,"ecdhp521") == 0) ecdh_doit[R_EC_P521]=2;
> -               else if (strcmp(*argv,"ecdhk163") == 0) ecdh_doit[R_EC_K163]=2;
> -               else if (strcmp(*argv,"ecdhk233") == 0) ecdh_doit[R_EC_K233]=2;
> -               else if (strcmp(*argv,"ecdhk283") == 0) ecdh_doit[R_EC_K283]=2;
> -               else if (strcmp(*argv,"ecdhk409") == 0) ecdh_doit[R_EC_K409]=2;
> -               else if (strcmp(*argv,"ecdhk571") == 0) ecdh_doit[R_EC_K571]=2;
> -               else if (strcmp(*argv,"ecdhb163") == 0) ecdh_doit[R_EC_B163]=2;
> -               else if (strcmp(*argv,"ecdhb233") == 0) ecdh_doit[R_EC_B233]=2;
> -               else if (strcmp(*argv,"ecdhb283") == 0) ecdh_doit[R_EC_B283]=2;
> -               else if (strcmp(*argv,"ecdhb409") == 0) ecdh_doit[R_EC_B409]=2;
> -               else if (strcmp(*argv,"ecdhb571") == 0) ecdh_doit[R_EC_B571]=2;
> +               else if (strcmp(*argv,"ecdhk160") == 0) ecdh_doit[R_EC_K160]=2;
> +               else if (strcmp(*argv,"ecdhk192") == 0) ecdh_doit[R_EC_K192]=2;
> +               else if (strcmp(*argv,"ecdhk224") == 0) ecdh_doit[R_EC_K224]=2;
> +               else if (strcmp(*argv,"ecdhk256") == 0) ecdh_doit[R_EC_K256]=2;
>                 else if (strcmp(*argv,"ecdh") == 0)
>                         {
>                         for (i=0; i < EC_NUM; i++)
> diff -ru --new-file openssl-1.0.1l-orig/crypto/ec/ec_curve.c openssl-1.0.1l/crypto/ec/ec_curve.c
> --- openssl-1.0.1l-orig/crypto/ec/ec_curve.c    2015-01-15 16:43:49.000000000 +0200
> +++ openssl-1.0.1l/crypto/ec/ec_curve.c 2015-01-19 13:43:51.375897173 +0200
> @@ -1836,18 +1836,18 @@
>         { NID_secp112r2, &_EC_SECG_PRIME_112R2.h, 0, "SECG curve over a 112 bit prime field" },
>         { NID_secp128r1, &_EC_SECG_PRIME_128R1.h, 0, "SECG curve over a 128 bit prime field" },
>         { NID_secp128r2, &_EC_SECG_PRIME_128R2.h, 0, "SECG curve over a 128 bit prime field" },
> -       { NID_secp160k1, &_EC_SECG_PRIME_160K1.h, 0, "SECG curve over a 160 bit prime field" },
> +       { NID_secp160k1, &_EC_SECG_PRIME_160K1.h, EC_GFp_glv_method, "SECG curve over a 160 bit prime field" },
>         { NID_secp160r1, &_EC_SECG_PRIME_160R1.h, 0, "SECG curve over a 160 bit prime field" },
>         { NID_secp160r2, &_EC_SECG_PRIME_160R2.h, 0, "SECG/WTLS curve over a 160 bit prime field" },
>         /* SECG secp192r1 is the same as X9.62 prime192v1 and hence omitted */
> -       { NID_secp192k1, &_EC_SECG_PRIME_192K1.h, 0, "SECG curve over a 192 bit prime field" },
> -       { NID_secp224k1, &_EC_SECG_PRIME_224K1.h, 0, "SECG curve over a 224 bit prime field" },
> +       { NID_secp192k1, &_EC_SECG_PRIME_192K1.h, EC_GFp_glv_method, "SECG curve over a 192 bit prime field" },
> +       { NID_secp224k1, &_EC_SECG_PRIME_224K1.h, EC_GFp_glv_method, "SECG curve over a 224 bit prime field" },
>  #ifndef OPENSSL_NO_EC_NISTP_64_GCC_128
>         { NID_secp224r1, &_EC_NIST_PRIME_224.h, EC_GFp_nistp224_method, "NIST/SECG curve over a 224 bit prime field" },
>  #else
>         { NID_secp224r1, &_EC_NIST_PRIME_224.h, 0, "NIST/SECG curve over a 224 bit prime field" },
>  #endif
> -       { NID_secp256k1, &_EC_SECG_PRIME_256K1.h, 0, "SECG curve over a 256 bit prime field" },
> +       { NID_secp256k1, &_EC_SECG_PRIME_256K1.h, EC_GFp_glv_method, "SECG curve over a 256 bit prime field" },
>         /* SECG secp256r1 is the same as X9.62 prime256v1 and hence omitted */
>         { NID_secp384r1, &_EC_NIST_PRIME_384.h, 0, "NIST/SECG curve over a 384 bit prime field" },
>  #ifndef OPENSSL_NO_EC_NISTP_64_GCC_128
> diff -ru --new-file openssl-1.0.1l-orig/crypto/ec/ec.h openssl-1.0.1l/crypto/ec/ec.h
> --- openssl-1.0.1l-orig/crypto/ec/ec.h  2015-01-15 16:43:49.000000000 +0200
> +++ openssl-1.0.1l/crypto/ec/ec.h       2015-01-19 13:43:50.864153182 +0200
> @@ -146,6 +146,11 @@
>   */
>  const EC_METHOD *EC_GFp_mont_method(void);
>
> +/** Returns GFp methods using optimized methods for GLV curves
> + *  \return  EC_METHOD object
> + */
> +const EC_METHOD *EC_GFp_glv_method(void);
> +
>  /** Returns GFp methods using optimized methods for NIST recommended curves
>   *  \return  EC_METHOD object
>   */
> diff -ru --new-file openssl-1.0.1l-orig/crypto/ec/ec_lcl.h openssl-1.0.1l/crypto/ec/ec_lcl.h
> --- openssl-1.0.1l-orig/crypto/ec/ec_lcl.h      2015-01-15 16:43:49.000000000 +0200
> +++ openssl-1.0.1l/crypto/ec/ec_lcl.h   2015-01-19 13:43:51.080045178 +0200
> @@ -348,6 +348,13 @@
>  int ec_GFp_mont_field_set_to_one(const EC_GROUP *, BIGNUM *r, BN_CTX *);
>
>
> +/* method functions in ecp_glv.c */
> +int ec_GFp_glv_mul(const EC_GROUP *group, EC_POINT *r, const BIGNUM *scalar,
> +       size_t num, const EC_POINT *points[], const BIGNUM *scalars[], BN_CTX *ctx);
> +int ec_GFp_glv_precompute_mult(EC_GROUP *group, BN_CTX *ctx);
> +int ec_GFp_glv_have_precompute_mult(const EC_GROUP *group);
> +
> +
>  /* method functions in ecp_nist.c */
>  int ec_GFp_nist_group_copy(EC_GROUP *dest, const EC_GROUP *src);
>  int ec_GFp_nist_group_set_curve(EC_GROUP *, const BIGNUM *p, const BIGNUM *a, const BIGNUM *b, BN_CTX *);
> diff -ru --new-file openssl-1.0.1l-orig/crypto/ec/ecp_glv.c openssl-1.0.1l/crypto/ec/ecp_glv.c
> --- openssl-1.0.1l-orig/crypto/ec/ecp_glv.c     1970-01-01 02:00:00.000000000 +0200
> +++ openssl-1.0.1l/crypto/ec/ecp_glv.c  2015-01-20 11:30:44.442723943 +0200
> @@ -0,0 +1,336 @@
> +#include <openssl/err.h>
> +
> +#ifdef OPENSSL_FIPS
> +#include <openssl/fips.h>
> +#endif
> +
> +#include "ec_lcl.h"
> +
> +/**
> + * Faster scalar multiplication for GLV curves:
> + * http://eprint.iacr.org/2015/036
> + *
> + * @author Billy Brumley <billy.brumley AT tut DOT fi>
> + */
> +
> +const EC_METHOD *EC_GFp_glv_method(void)
> +       {
> +       static const EC_METHOD ret = {
> +               EC_FLAGS_DEFAULT_OCT,
> +               NID_X9_62_prime_field,
> +               ec_GFp_mont_group_init,
> +               ec_GFp_mont_group_finish,
> +               ec_GFp_mont_group_clear_finish,
> +               ec_GFp_mont_group_copy,
> +               ec_GFp_mont_group_set_curve,
> +               ec_GFp_simple_group_get_curve,
> +               ec_GFp_simple_group_get_degree,
> +               ec_GFp_simple_group_check_discriminant,
> +               ec_GFp_simple_point_init,
> +               ec_GFp_simple_point_finish,
> +               ec_GFp_simple_point_clear_finish,
> +               ec_GFp_simple_point_copy,
> +               ec_GFp_simple_point_set_to_infinity,
> +               ec_GFp_simple_set_Jprojective_coordinates_GFp,
> +               ec_GFp_simple_get_Jprojective_coordinates_GFp,
> +               ec_GFp_simple_point_set_affine_coordinates,
> +               ec_GFp_simple_point_get_affine_coordinates,
> +               0,0,0,
> +               ec_GFp_simple_add,
> +               ec_GFp_simple_dbl,
> +               ec_GFp_simple_invert,
> +               ec_GFp_simple_is_at_infinity,
> +               ec_GFp_simple_is_on_curve,
> +               ec_GFp_simple_cmp,
> +               ec_GFp_simple_make_affine,
> +               ec_GFp_simple_points_make_affine,
> +               ec_GFp_glv_mul,
> +               ec_GFp_glv_precompute_mult,
> +               ec_GFp_glv_have_precompute_mult,
> +               ec_GFp_mont_field_mul,
> +               ec_GFp_mont_field_sqr,
> +               0 /* field_div */,
> +               ec_GFp_mont_field_encode,
> +               ec_GFp_mont_field_decode,
> +               ec_GFp_mont_field_set_to_one };
> +
> +#ifdef OPENSSL_FIPS
> +       if (FIPS_mode())
> +               return fips_ec_gfp_glv_method();
> +#endif
> +
> +       return &ret;
> +       }
> +
> +/* GLV-related per-curve constants */
> +static const unsigned char glv_constants_secp160k1[] = {
> +       /* beta */
> +       0x9b,0xa4,0x8c,0xba,0x5e,0xbc,0xb9,0xb6,
> +       0xbd,0x33,0xb9,0x28,0x30,0xb2,0xa2,0xe0,
> +       0xe1,0x92,0xf1,0x0a,
> +       /* a1 */
> +       0x91,0x62,0xfb,0xe7,0x39,0x84,0x47,0x2a,
> +       0x0a,0x9e,
> +       /* b1 */
> +       0x96,0x34,0x1f,0x11,0x38,0x93,0x3b,0xc2,
> +       0xf5,0x05,
> +       /* a2 */
> +       0x01,0x27,0x97,0x1a,0xf8,0x72,0x17,0x82,
> +       0xec,0xff,0xa3,
> +       /* b2 */
> +       0x91,0x62,0xfb,0xe7,0x39,0x84,0x47,0x2a,
> +       0x0a,0x9e
> +};
> +
> +static const unsigned char glv_constants_secp192k1[] = {
> +       /* beta */
> +       0xbb,0x85,0x69,0x19,0x39,0xb8,0x69,0xc1,
> +       0xd0,0x87,0xf6,0x01,0x55,0x4b,0x96,0xb8,
> +       0x0c,0xb4,0xf5,0x5b,0x35,0xf4,0x33,0xc2,
> +       /* a1 */
> +       0x71,0x16,0x9b,0xe7,0x33,0x0b,0x30,0x38,
> +       0xed,0xb0,0x25,0xf1,
> +       /* b1 */
> +       0xb3,0xfb,0x34,0x00,0xde,0xc5,0xc4,0xad,
> +       0xce,0xb8,0x65,0x5c,
> +       /* a2 */
> +       0x01,0x25,0x11,0xcf,0xe8,0x11,0xd0,0xf4,
> +       0xe6,0xbc,0x68,0x8b,0x4d,
> +       /* b2 */
> +       0x71,0x16,0x9b,0xe7,0x33,0x0b,0x30,0x38,
> +       0xed,0xb0,0x25,0xf1
> +};
> +
> +static const unsigned char glv_constants_secp224k1[] = {
> +       /* beta */
> +       0x01,0xf1,0x78,0xff,0xa4,0xb1,0x7c,0x89,
> +       0xe6,0xf7,0x3a,0xec,0xe2,0xaa,0xd5,0x7a,
> +       0xf4,0xc0,0xa7,0x48,0xb6,0x3c,0x83,0x09,
> +       0x47,0xb2,0x7e,0x04,
> +       /* a1 */
> +       0xb8,0xad,0xf1,0x37,0x8a,0x6e,0xb7,0x34,
> +       0x09,0xfa,0x6c,0x9c,0x63,0x7d,
> +       /* b1 */
> +       0x6b,0x8c,0xf0,0x7d,0x4c,0xa7,0x5c,0x88,
> +       0x95,0x7d,0x9d,0x67,0x05,0x91,
> +       /* a2 */
> +       0x6b,0x8c,0xf0,0x7d,0x4c,0xa7,0x5c,0x88,
> +       0x95,0x7d,0x9d,0x67,0x05,0x91,
> +       /* b2 */
> +       0x01,0x24,0x3a,0xe1,0xb4,0xd7,0x16,0x13,
> +       0xbc,0x9f,0x78,0x0a,0x03,0x69,0x0e
> +};
> +
> +static const unsigned char glv_constants_secp256k1[] = {
> +       /* beta */
> +       0x85,0x16,0x95,0xd4,0x9a,0x83,0xf8,0xef,
> +       0x91,0x9b,0xb8,0x61,0x53,0xcb,0xcb,0x16,
> +       0x63,0x0f,0xb6,0x8a,0xed,0x0a,0x76,0x6a,
> +       0x3e,0xc6,0x93,0xd6,0x8e,0x6a,0xfa,0x40,
> +       /* a1 */
> +       0xe4,0x43,0x7e,0xd6,0x01,0x0e,0x88,0x28,
> +       0x6f,0x54,0x7f,0xa9,0x0a,0xbf,0xe4,0xc3,
> +       /* b1 */
> +       0x30,0x86,0xd2,0x21,0xa7,0xd4,0x6b,0xcd,
> +       0xe8,0x6c,0x90,0xe4,0x92,0x84,0xeb,0x15,
> +       /* a2 */
> +       0x30,0x86,0xd2,0x21,0xa7,0xd4,0x6b,0xcd,
> +       0xe8,0x6c,0x90,0xe4,0x92,0x84,0xeb,0x15,
> +       /* b2 */
> +       0x01,0x14,0xca,0x50,0xf7,0xa8,0xe2,0xf3,
> +       0xf6,0x57,0xc1,0x10,0x8d,0x9d,0x44,0xcf,
> +       0xd8
> +};
> +
> +/**
> + * Integer decomposition.
> + * See 3.5 in "Guide to Elliptic Curve Cryptography"
> + *
> + * The alg is slightly re-arranged to keep all constants positive
> + *
> + * n  = constants[0]
> + * a1 = constants[2]
> + * b1 = constants[3]
> + * a2 = constants[4]
> + * b2 = constants[5]
> + */
> +int ec_GFp_glv_decompose(BIGNUM *k1, BIGNUM *k2, const BIGNUM *scalar, const BIGNUM **constants, BN_CTX *ctx) {
> +
> +       int ret = 0;
> +
> +       BIGNUM *twok, *c1, *c2;
> +
> +       BN_CTX_start(ctx);
> +
> +       do {
> +               twok = BN_CTX_get(ctx);
> +               c1   = BN_CTX_get(ctx);
> +               if ((c2 = BN_CTX_get(ctx)) == NULL) break;
> +
> +               if (!BN_lshift1(twok, scalar)) break;
> +
> +               /* weird computation is for closest int rounding */
> +               /* c1 = (2*b2*k+r[0])/(2*r[0]) */
> +               /* c2 = (2*b1*k+r[0])/(2*r[0]) */
> +               if (!BN_mul(c1, twok, constants[5], ctx)) break;
> +               if (!BN_add(c1, c1, constants[0])) break;
> +               if (!BN_div(c1, NULL, c1, constants[0], ctx)) break;
> +               if (!BN_rshift1(c1, c1)) break;
> +               if (!BN_mul(c2, twok, constants[3], ctx)) break;
> +               if (!BN_add(c2, c2, constants[0])) break;
> +               if (!BN_div(c2, NULL, c2, constants[0], ctx)) break;
> +               if (!BN_rshift1(c2, c2)) break;
> +
> +               /* k1 = k - (c1*a1 + c2*a2) */
> +               /* k2 = c1*b1 - c2*b2 */
> +               if (!BN_mul(k1, constants[2], c1, ctx)) break;
> +               if (!BN_mul(k2, constants[4], c2, ctx)) break;
> +               if (!BN_add(k1, k1, k2)) break;
> +               if (!BN_sub(k1, scalar, k1)) break;
> +               if (!BN_mul(c1, constants[3], c1, ctx)) break;
> +               if (!BN_mul(c2, constants[5], c2, ctx)) break;
> +               if (!BN_sub(k2, c1, c2)) break;
> +
> +               ret = 1;
> +       } while(0);
> +
> +       BN_CTX_end(ctx);
> +
> +       return ret;
> +
> +}
> +
> +/**
> + * Computes the sum
> + * scalar*group->generator + scalars[0]*points[0] + ... + scalars[num-1]*points[num-1]
> + */
> +int ec_GFp_glv_mul(const EC_GROUP *group, EC_POINT *r, const BIGNUM *scalar,
> +       size_t num, const EC_POINT *points[], const BIGNUM *scalars[], BN_CTX *ctx)
> +       {
> +
> +       /* use default stuff if we have precomp and it can help */
> +       if(num == 0 && EC_GROUP_have_precompute_mult(group))
> +               return ec_wNAF_mul(group, r, scalar, num, points, scalars, ctx);
> +
> +       int i, ret = 0;
> +
> +       BIGNUM *tscalar = NULL;
> +       EC_POINT **tpoints = NULL;
> +       BIGNUM **tscalars = NULL;
> +       BIGNUM **constants = NULL;
> +
> +       if ((constants = OPENSSL_malloc(6*sizeof(BIGNUM *))) == NULL) return 0;
> +
> +       BN_CTX_start(ctx);
> +
> +       /* fill in the constants */
> +       for(i=0; i<6; i++) {
> +               constants[i] = BN_CTX_get(ctx);
> +       }
> +
> +       if(constants[5] == NULL) goto err;
> +
> +       if (!EC_GROUP_get_order(group, constants[0], ctx)) goto err;
> +
> +       switch(EC_GROUP_get_curve_name(group)) {
> +               case NID_secp160k1:
> +                       BN_bin2bn(glv_constants_secp160k1 +  0, 20, constants[1]);
> +                       BN_bin2bn(glv_constants_secp160k1 + 20, 10, constants[2]);
> +                       BN_bin2bn(glv_constants_secp160k1 + 30, 10, constants[3]);
> +                       BN_bin2bn(glv_constants_secp160k1 + 40, 11, constants[4]);
> +                       BN_bin2bn(glv_constants_secp160k1 + 51, 10, constants[5]);
> +                       break;
> +               case NID_secp192k1:
> +                       BN_bin2bn(glv_constants_secp192k1 +  0, 24, constants[1]);
> +                       BN_bin2bn(glv_constants_secp192k1 + 24, 12, constants[2]);
> +                       BN_bin2bn(glv_constants_secp192k1 + 36, 12, constants[3]);
> +                       BN_bin2bn(glv_constants_secp192k1 + 48, 13, constants[4]);
> +                       BN_bin2bn(glv_constants_secp192k1 + 61, 12, constants[5]);
> +                       break;
> +               case NID_secp224k1:
> +                       BN_bin2bn(glv_constants_secp224k1 +  0, 28, constants[1]);
> +                       BN_bin2bn(glv_constants_secp224k1 + 28, 14, constants[2]);
> +                       BN_bin2bn(glv_constants_secp224k1 + 42, 14, constants[3]);
> +                       BN_bin2bn(glv_constants_secp224k1 + 56, 14, constants[4]);
> +                       BN_bin2bn(glv_constants_secp224k1 + 70, 15, constants[5]);
> +                       break;
> +               case NID_secp256k1:
> +                       BN_bin2bn(glv_constants_secp256k1 +  0, 32, constants[1]);
> +                       BN_bin2bn(glv_constants_secp256k1 + 32, 16, constants[2]);
> +                       BN_bin2bn(glv_constants_secp256k1 + 48, 16, constants[3]);
> +                       BN_bin2bn(glv_constants_secp256k1 + 64, 16, constants[4]);
> +                       BN_bin2bn(glv_constants_secp256k1 + 80, 17, constants[5]);
> +                       break;
> +               default:
> +                       goto err;
> +       }
> +
> +       /* encode beta parameter to curve's finite field */
> +       if (!group->meth->field_encode(group, constants[1], constants[1], ctx)) goto err;
> +
> +       /* setup some arrays and decompose scalar if it's present and apply endomorphism */
> +       if(scalar == NULL) {
> +               if ((tpoints = OPENSSL_malloc(2 * num * sizeof(EC_POINT *))) == NULL) goto err;
> +               if ((tscalars = OPENSSL_malloc(2 * num * sizeof(BIGNUM *))) == NULL) goto err;
> +       }
> +       else {
> +               if ((tpoints = OPENSSL_malloc((2 * num + 1) * sizeof(EC_POINT *))) == NULL) goto err;
> +               if ((tscalars = OPENSSL_malloc((2 * num + 1) * sizeof(BIGNUM *))) == NULL) goto err;
> +               tscalar = BN_CTX_get(ctx);
> +               if ((tscalars[2*num] = BN_CTX_get(ctx)) == NULL) goto err;
> +               if ((tpoints[2*num] = EC_POINT_new(group)) == NULL) goto err;
> +               if (!EC_POINT_copy(tpoints[2*num], EC_GROUP_get0_generator(group))) goto err;
> +               if (!group->meth->field_mul(group, &tpoints[2*num]->X, &tpoints[2*num]->X, constants[1], ctx)) goto err;
> +               if (!ec_GFp_glv_decompose(tscalar, tscalars[2*num], scalar, (const BIGNUM **)constants, ctx)) goto err;
> +       }
> +
> +       /* decompose all the other scalars and apply the endomorphism */
> +       for(i=0; i < num; i++) {
> +               tpoints[2*i  ] = *((EC_POINT **)points + 2*i);
> +               if ((tpoints[2*i+1] = EC_POINT_new(group)) == NULL) goto err;
> +               if (!EC_POINT_copy(tpoints[2*i+1], tpoints[2*i])) goto err;
> +               if (!group->meth->field_mul(group, &tpoints[2*i+1]->X, &tpoints[2*i+1]->X, constants[1], ctx)) goto err;
> +               tscalars[2*i  ] = BN_CTX_get(ctx);
> +               if ((tscalars[2*i+1] = BN_CTX_get(ctx)) == NULL) goto err;
> +               if (!ec_GFp_glv_decompose(tscalars[2*i], tscalars[2*i+1], scalars[i], (const BIGNUM **)constants, ctx)) goto err;
> +       }
> +
> +       /* call into the multi scalar mult routine with new parameters */
> +       if(scalar == NULL) {
> +               ret = ec_wNAF_mul(group, r, scalar, 2*num, (const EC_POINT **)tpoints, (const BIGNUM **)tscalars, ctx);
> +       }
> +       else {
> +               ret = ec_wNAF_mul(group, r, tscalar, 2*num+1, (const EC_POINT **)tpoints, (const BIGNUM **)tscalars, ctx);
> +       }
> +
> +err:
> +
> +       /* cleanup */
> +       if (tpoints != NULL) {
> +               for(i=0; i < num; i++) {
> +                       EC_POINT_free(tpoints[2*i+1]);
> +               }
> +               if (scalar != NULL) {
> +                       EC_POINT_free(tpoints[2*num]);
> +               }
> +       }
> +
> +       BN_CTX_end(ctx);
> +
> +       OPENSSL_free(tpoints);
> +       OPENSSL_free(tscalars);
> +       OPENSSL_free(constants);
> +
> +       return ret;
> +       }
> +
> +int ec_GFp_glv_precompute_mult(EC_GROUP *group, BN_CTX *ctx)
> +       {
> +       return ec_wNAF_precompute_mult(group, ctx);
> +       }
> +
> +int ec_GFp_glv_have_precompute_mult(const EC_GROUP *group)
> +       {
> +       return ec_wNAF_have_precompute_mult(group);
> +       }
> +
> diff -ru --new-file openssl-1.0.1l-orig/crypto/ec/Makefile openssl-1.0.1l/crypto/ec/Makefile
> --- openssl-1.0.1l-orig/crypto/ec/Makefile      2015-01-15 16:45:04.000000000 +0200
> +++ openssl-1.0.1l/crypto/ec/Makefile   2015-01-19 13:43:51.239965175 +0200
> @@ -17,13 +17,13 @@
>  APPS=
>
>  LIB=$(TOP)/libcrypto.a
> -LIBSRC=        ec_lib.c ecp_smpl.c ecp_mont.c ecp_nist.c ec_cvt.c ec_mult.c\
> +LIBSRC=        ec_lib.c ecp_smpl.c ecp_mont.c ecp_glv.c ecp_nist.c ec_cvt.c ec_mult.c\
>         ec_err.c ec_curve.c ec_check.c ec_print.c ec_asn1.c ec_key.c\
>         ec2_smpl.c ec2_mult.c ec_ameth.c ec_pmeth.c eck_prn.c \
>         ecp_nistp224.c ecp_nistp256.c ecp_nistp521.c ecp_nistputil.c \
>         ecp_oct.c ec2_oct.c ec_oct.c
>
> -LIBOBJ=        ec_lib.o ecp_smpl.o ecp_mont.o ecp_nist.o ec_cvt.o ec_mult.o\
> +LIBOBJ=        ec_lib.o ecp_smpl.o ecp_mont.o ecp_glv.o ecp_nist.o ec_cvt.o ec_mult.o\
>         ec_err.o ec_curve.o ec_check.o ec_print.o ec_asn1.o ec_key.o\
>         ec2_smpl.o ec2_mult.o ec_ameth.o ec_pmeth.o eck_prn.o \
>         ecp_nistp224.o ecp_nistp256.o ecp_nistp521.o ecp_nistputil.o \
> @@ -233,6 +233,14 @@
>  ecp_mont.o: ../../include/openssl/opensslv.h ../../include/openssl/ossl_typ.h
>  ecp_mont.o: ../../include/openssl/safestack.h ../../include/openssl/stack.h
>  ecp_mont.o: ../../include/openssl/symhacks.h ec_lcl.h ecp_mont.c
> +ecp_glv.o: ../../include/openssl/asn1.h ../../include/openssl/bio.h
> +ecp_glv.o: ../../include/openssl/bn.h ../../include/openssl/crypto.h
> +ecp_glv.o: ../../include/openssl/e_os2.h ../../include/openssl/ec.h
> +ecp_glv.o: ../../include/openssl/err.h ../../include/openssl/lhash.h
> +ecp_glv.o: ../../include/openssl/obj_mac.h ../../include/openssl/opensslconf.h
> +ecp_glv.o: ../../include/openssl/opensslv.h ../../include/openssl/ossl_typ.h
> +ecp_glv.o: ../../include/openssl/safestack.h ../../include/openssl/stack.h
> +ecp_glv.o: ../../include/openssl/symhacks.h ec_lcl.h ecp_glv.c
>  ecp_nist.o: ../../include/openssl/asn1.h ../../include/openssl/bio.h
>  ecp_nist.o: ../../include/openssl/bn.h ../../include/openssl/crypto.h
>  ecp_nist.o: ../../include/openssl/e_os2.h ../../include/openssl/ec.h
>
> _______________________________________________
> openssl-dev mailing list
> To unsubscribe: https://mta.openssl.org/mailman/listinfo/openssl-dev
>
--
openssl-dev mailing list
To unsubscribe: https://mta.openssl.org/mailman/listinfo/openssl-dev
Reply | Threaded
Open this post in threaded view
|

Re: [openssl.org #3667] [PATCH] Faster GLV elliptic curves

Rich Salz via RT
Ported from 1.0 to 1.1 -- PR:

https://github.com/openssl/openssl/pull/776

On Tue, Jan 20, 2015 at 4:02 PM, Billy Brumley via RT <[hidden email]> wrote:

> This patch gives about 50% speed improvement for existing GLV elliptic
> curves in OpenSSL. Read about it here:
>
> http://eprint.iacr.org/2015/036
>
> It could use a review. Perhaps the best known use case for secp256k1
> right now is Bitcoin.
>
> BBB
>
> Before:
>                               op      op/s
>  160 bit ecdh (secp160r1)   0.0001s   6730.6
>  192 bit ecdh (nistp192)   0.0002s   5714.8
>  224 bit ecdh (nistp224)   0.0002s   4153.6
>  256 bit ecdh (nistp256)   0.0003s   3573.1
>  160 bit ecdh (secp160k1)   0.0002s   6198.2
>  192 bit ecdh (secp192k1)   0.0002s   5191.9
>  224 bit ecdh (secp224k1)   0.0003s   3789.3
>  256 bit ecdh (secp256k1)   0.0003s   3281.2
>
>                               sign    verify    sign/s verify/s
>  160 bit ecdsa (secp160r1)   0.0001s   0.0002s  19289.6   5581.5
>  192 bit ecdsa (nistp192)   0.0001s   0.0002s  16011.7   4650.7
>  224 bit ecdsa (nistp224)   0.0001s   0.0003s  12987.1   3378.2
>  256 bit ecdsa (nistp256)   0.0001s   0.0003s  11061.8   2913.0
>  160 bit ecdsa (secp160k1)   0.0001s   0.0002s  18946.5   5290.5
>  192 bit ecdsa (secp192k1)   0.0001s   0.0002s  15605.9   4289.9
>  224 bit ecdsa (secp224k1)   0.0001s   0.0003s  12752.6   3145.9
>  256 bit ecdsa (secp256k1)   0.0001s   0.0004s  10803.0   2733.2
>
>
>
> After:
>                               op      op/s
>  160 bit ecdh (secp160r1)   0.0001s   6798.4
>  192 bit ecdh (nistp192)   0.0002s   5667.2
>  224 bit ecdh (nistp224)   0.0002s   4081.5
>  256 bit ecdh (nistp256)   0.0003s   3578.9
>  160 bit ecdh (secp160k1)   0.0001s   9102.5
>  192 bit ecdh (secp192k1)   0.0001s   7784.3
>  224 bit ecdh (secp224k1)   0.0002s   5554.4
>  256 bit ecdh (secp256k1)   0.0002s   4890.4
>
>                               sign    verify    sign/s verify/s
>  160 bit ecdsa (secp160r1)   0.0001s   0.0002s  19264.6   5416.7
>  192 bit ecdsa (nistp192)   0.0001s   0.0002s  15956.0   4723.1
>  224 bit ecdsa (nistp224)   0.0001s   0.0003s  12855.8   3379.9
>  256 bit ecdsa (nistp256)   0.0001s   0.0003s  11017.8   2911.7
>  160 bit ecdsa (secp160k1)   0.0001s   0.0001s  18959.9   6705.4
>  192 bit ecdsa (secp192k1)   0.0001s   0.0002s  15624.0   5681.4
>  224 bit ecdsa (secp224k1)   0.0001s   0.0002s  12513.0   4189.3
>  256 bit ecdsa (secp256k1)   0.0001s   0.0003s  10621.2   3569.8
>
>
>
> $ cat /proc/cpuinfo
> processor    : 0
> vendor_id    : GenuineIntel
> cpu family    : 6
> model        : 60
> model name    : Intel(R) Core(TM) i5-4570 CPU @ 3.20GHz
> stepping    : 3
> microcode    : 26
> cpu MHz        : 800.000
> cache size    : 6144 KB
> physical id    : 0
> siblings    : 4
> core id        : 0
> cpu cores    : 4
> apicid        : 0
> initial apicid    : 0
> fpu        : yes
> fpu_exception    : yes
> cpuid level    : 13
> wp        : yes
> flags        : fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge
> mca cmov pat pse36 clflush dts acpi mmx fxsr sse sse2 ss ht tm pbe
> syscall nx pdpe1gb rdtscp lm constant_tsc arch_perfmon pebs bts
> rep_good xtopology nonstop_tsc aperfmperf pni pclmulqdq dtes64 monitor
> ds_cpl vmx smx est tm2 ssse3 fma cx16 xtpr pdcm pcid sse4_1 sse4_2
> x2apic movbe popcnt tsc_deadline_timer aes xsave avx f16c rdrand
> lahf_lm abm ida arat epb xsaveopt pln pts dts tpr_shadow vnmi
> flexpriority ept vpid fsgsbase bmi1 hle avx2 smep bmi2 erms invpcid
> rtm
> bogomips    : 6384.88
> clflush size    : 64
> cache_alignment    : 64
> address sizes    : 39 bits physical, 48 bits virtual
> power management: SNIP
>
>
> diff -ru --new-file openssl-1.0.1l-orig/apps/speed.c openssl-1.0.1l/apps/speed.c
> --- openssl-1.0.1l-orig/apps/speed.c    2015-01-15 16:43:49.000000000 +0200
> +++ openssl-1.0.1l/apps/speed.c 2015-01-19 13:44:38.232456333 +0200
> @@ -244,7 +244,7 @@
>  #define RSA_NUM                4
>  #define DSA_NUM                3
>
> -#define EC_NUM       16
> +#define EC_NUM       8
>  #define MAX_ECDH_SIZE 256
>
>  static const char *names[ALGOR_NUM]={
> @@ -512,18 +512,10 @@
>  #define R_EC_P192    1
>  #define R_EC_P224    2
>  #define R_EC_P256    3
> -#define R_EC_P384    4
> -#define R_EC_P521    5
> -#define R_EC_K163    6
> -#define R_EC_K233    7
> -#define R_EC_K283    8
> -#define R_EC_K409    9
> -#define R_EC_K571    10
> -#define R_EC_B163    11
> -#define R_EC_B233    12
> -#define R_EC_B283    13
> -#define R_EC_B409    14
> -#define R_EC_B571    15
> +#define R_EC_K160    4
> +#define R_EC_K192    5
> +#define R_EC_K224    6
> +#define R_EC_K256    7
>
>  #ifndef OPENSSL_NO_RSA
>         RSA *rsa_key[RSA_NUM];
> @@ -553,19 +545,10 @@
>         NID_X9_62_prime192v1,
>         NID_secp224r1,
>         NID_X9_62_prime256v1,
> -       NID_secp384r1,
> -       NID_secp521r1,
> -       /* Binary Curves */
> -       NID_sect163k1,
> -       NID_sect233k1,
> -       NID_sect283k1,
> -       NID_sect409k1,
> -       NID_sect571k1,
> -       NID_sect163r2,
> -       NID_sect233r1,
> -       NID_sect283r1,
> -       NID_sect409r1,
> -       NID_sect571r1
> +       NID_secp160k1,
> +       NID_secp192k1,
> +       NID_secp224k1,
> +       NID_secp256k1
>         };
>         static const char * test_curves_names[EC_NUM] =
>         {
> @@ -574,25 +557,15 @@
>         "nistp192",
>         "nistp224",
>         "nistp256",
> -       "nistp384",
> -       "nistp521",
> -       /* Binary Curves */
> -       "nistk163",
> -       "nistk233",
> -       "nistk283",
> -       "nistk409",
> -       "nistk571",
> -       "nistb163",
> -       "nistb233",
> -       "nistb283",
> -       "nistb409",
> -       "nistb571"
> +       "secp160k1",
> +       "secp192k1",
> +       "secp224k1",
> +       "secp256k1"
>         };
>         static int test_curves_bits[EC_NUM] =
>          {
> -        160, 192, 224, 256, 384, 521,
> -        163, 233, 283, 409, 571,
> -        163, 233, 283, 409, 571
> +        160, 192, 224, 256,
> +        160, 192, 224, 256
>          };
>
>  #endif
> @@ -962,18 +935,10 @@
>                 else if (strcmp(*argv,"ecdsap192") == 0) ecdsa_doit[R_EC_P192]=2;
>                 else if (strcmp(*argv,"ecdsap224") == 0) ecdsa_doit[R_EC_P224]=2;
>                 else if (strcmp(*argv,"ecdsap256") == 0) ecdsa_doit[R_EC_P256]=2;
> -               else if (strcmp(*argv,"ecdsap384") == 0) ecdsa_doit[R_EC_P384]=2;
> -               else if (strcmp(*argv,"ecdsap521") == 0) ecdsa_doit[R_EC_P521]=2;
> -               else if (strcmp(*argv,"ecdsak163") == 0) ecdsa_doit[R_EC_K163]=2;
> -               else if (strcmp(*argv,"ecdsak233") == 0) ecdsa_doit[R_EC_K233]=2;
> -               else if (strcmp(*argv,"ecdsak283") == 0) ecdsa_doit[R_EC_K283]=2;
> -               else if (strcmp(*argv,"ecdsak409") == 0) ecdsa_doit[R_EC_K409]=2;
> -               else if (strcmp(*argv,"ecdsak571") == 0) ecdsa_doit[R_EC_K571]=2;
> -               else if (strcmp(*argv,"ecdsab163") == 0) ecdsa_doit[R_EC_B163]=2;
> -               else if (strcmp(*argv,"ecdsab233") == 0) ecdsa_doit[R_EC_B233]=2;
> -               else if (strcmp(*argv,"ecdsab283") == 0) ecdsa_doit[R_EC_B283]=2;
> -               else if (strcmp(*argv,"ecdsab409") == 0) ecdsa_doit[R_EC_B409]=2;
> -               else if (strcmp(*argv,"ecdsab571") == 0) ecdsa_doit[R_EC_B571]=2;
> +               else if (strcmp(*argv,"ecdsak160") == 0) ecdsa_doit[R_EC_K160]=2;
> +               else if (strcmp(*argv,"ecdsak192") == 0) ecdsa_doit[R_EC_K192]=2;
> +               else if (strcmp(*argv,"ecdsak224") == 0) ecdsa_doit[R_EC_K224]=2;
> +               else if (strcmp(*argv,"ecdsak256") == 0) ecdsa_doit[R_EC_K256]=2;
>                 else if (strcmp(*argv,"ecdsa") == 0)
>                         {
>                         for (i=0; i < EC_NUM; i++)
> @@ -986,18 +951,10 @@
>                 else if (strcmp(*argv,"ecdhp192") == 0) ecdh_doit[R_EC_P192]=2;
>                 else if (strcmp(*argv,"ecdhp224") == 0) ecdh_doit[R_EC_P224]=2;
>                 else if (strcmp(*argv,"ecdhp256") == 0) ecdh_doit[R_EC_P256]=2;
> -               else if (strcmp(*argv,"ecdhp384") == 0) ecdh_doit[R_EC_P384]=2;
> -               else if (strcmp(*argv,"ecdhp521") == 0) ecdh_doit[R_EC_P521]=2;
> -               else if (strcmp(*argv,"ecdhk163") == 0) ecdh_doit[R_EC_K163]=2;
> -               else if (strcmp(*argv,"ecdhk233") == 0) ecdh_doit[R_EC_K233]=2;
> -               else if (strcmp(*argv,"ecdhk283") == 0) ecdh_doit[R_EC_K283]=2;
> -               else if (strcmp(*argv,"ecdhk409") == 0) ecdh_doit[R_EC_K409]=2;
> -               else if (strcmp(*argv,"ecdhk571") == 0) ecdh_doit[R_EC_K571]=2;
> -               else if (strcmp(*argv,"ecdhb163") == 0) ecdh_doit[R_EC_B163]=2;
> -               else if (strcmp(*argv,"ecdhb233") == 0) ecdh_doit[R_EC_B233]=2;
> -               else if (strcmp(*argv,"ecdhb283") == 0) ecdh_doit[R_EC_B283]=2;
> -               else if (strcmp(*argv,"ecdhb409") == 0) ecdh_doit[R_EC_B409]=2;
> -               else if (strcmp(*argv,"ecdhb571") == 0) ecdh_doit[R_EC_B571]=2;
> +               else if (strcmp(*argv,"ecdhk160") == 0) ecdh_doit[R_EC_K160]=2;
> +               else if (strcmp(*argv,"ecdhk192") == 0) ecdh_doit[R_EC_K192]=2;
> +               else if (strcmp(*argv,"ecdhk224") == 0) ecdh_doit[R_EC_K224]=2;
> +               else if (strcmp(*argv,"ecdhk256") == 0) ecdh_doit[R_EC_K256]=2;
>                 else if (strcmp(*argv,"ecdh") == 0)
>                         {
>                         for (i=0; i < EC_NUM; i++)
> diff -ru --new-file openssl-1.0.1l-orig/crypto/ec/ec_curve.c openssl-1.0.1l/crypto/ec/ec_curve.c
> --- openssl-1.0.1l-orig/crypto/ec/ec_curve.c    2015-01-15 16:43:49.000000000 +0200
> +++ openssl-1.0.1l/crypto/ec/ec_curve.c 2015-01-19 13:43:51.375897173 +0200
> @@ -1836,18 +1836,18 @@
>         { NID_secp112r2, &_EC_SECG_PRIME_112R2.h, 0, "SECG curve over a 112 bit prime field" },
>         { NID_secp128r1, &_EC_SECG_PRIME_128R1.h, 0, "SECG curve over a 128 bit prime field" },
>         { NID_secp128r2, &_EC_SECG_PRIME_128R2.h, 0, "SECG curve over a 128 bit prime field" },
> -       { NID_secp160k1, &_EC_SECG_PRIME_160K1.h, 0, "SECG curve over a 160 bit prime field" },
> +       { NID_secp160k1, &_EC_SECG_PRIME_160K1.h, EC_GFp_glv_method, "SECG curve over a 160 bit prime field" },
>         { NID_secp160r1, &_EC_SECG_PRIME_160R1.h, 0, "SECG curve over a 160 bit prime field" },
>         { NID_secp160r2, &_EC_SECG_PRIME_160R2.h, 0, "SECG/WTLS curve over a 160 bit prime field" },
>         /* SECG secp192r1 is the same as X9.62 prime192v1 and hence omitted */
> -       { NID_secp192k1, &_EC_SECG_PRIME_192K1.h, 0, "SECG curve over a 192 bit prime field" },
> -       { NID_secp224k1, &_EC_SECG_PRIME_224K1.h, 0, "SECG curve over a 224 bit prime field" },
> +       { NID_secp192k1, &_EC_SECG_PRIME_192K1.h, EC_GFp_glv_method, "SECG curve over a 192 bit prime field" },
> +       { NID_secp224k1, &_EC_SECG_PRIME_224K1.h, EC_GFp_glv_method, "SECG curve over a 224 bit prime field" },
>  #ifndef OPENSSL_NO_EC_NISTP_64_GCC_128
>         { NID_secp224r1, &_EC_NIST_PRIME_224.h, EC_GFp_nistp224_method, "NIST/SECG curve over a 224 bit prime field" },
>  #else
>         { NID_secp224r1, &_EC_NIST_PRIME_224.h, 0, "NIST/SECG curve over a 224 bit prime field" },
>  #endif
> -       { NID_secp256k1, &_EC_SECG_PRIME_256K1.h, 0, "SECG curve over a 256 bit prime field" },
> +       { NID_secp256k1, &_EC_SECG_PRIME_256K1.h, EC_GFp_glv_method, "SECG curve over a 256 bit prime field" },
>         /* SECG secp256r1 is the same as X9.62 prime256v1 and hence omitted */
>         { NID_secp384r1, &_EC_NIST_PRIME_384.h, 0, "NIST/SECG curve over a 384 bit prime field" },
>  #ifndef OPENSSL_NO_EC_NISTP_64_GCC_128
> diff -ru --new-file openssl-1.0.1l-orig/crypto/ec/ec.h openssl-1.0.1l/crypto/ec/ec.h
> --- openssl-1.0.1l-orig/crypto/ec/ec.h  2015-01-15 16:43:49.000000000 +0200
> +++ openssl-1.0.1l/crypto/ec/ec.h       2015-01-19 13:43:50.864153182 +0200
> @@ -146,6 +146,11 @@
>   */
>  const EC_METHOD *EC_GFp_mont_method(void);
>
> +/** Returns GFp methods using optimized methods for GLV curves
> + *  \return  EC_METHOD object
> + */
> +const EC_METHOD *EC_GFp_glv_method(void);
> +
>  /** Returns GFp methods using optimized methods for NIST recommended curves
>   *  \return  EC_METHOD object
>   */
> diff -ru --new-file openssl-1.0.1l-orig/crypto/ec/ec_lcl.h openssl-1.0.1l/crypto/ec/ec_lcl.h
> --- openssl-1.0.1l-orig/crypto/ec/ec_lcl.h      2015-01-15 16:43:49.000000000 +0200
> +++ openssl-1.0.1l/crypto/ec/ec_lcl.h   2015-01-19 13:43:51.080045178 +0200
> @@ -348,6 +348,13 @@
>  int ec_GFp_mont_field_set_to_one(const EC_GROUP *, BIGNUM *r, BN_CTX *);
>
>
> +/* method functions in ecp_glv.c */
> +int ec_GFp_glv_mul(const EC_GROUP *group, EC_POINT *r, const BIGNUM *scalar,
> +       size_t num, const EC_POINT *points[], const BIGNUM *scalars[], BN_CTX *ctx);
> +int ec_GFp_glv_precompute_mult(EC_GROUP *group, BN_CTX *ctx);
> +int ec_GFp_glv_have_precompute_mult(const EC_GROUP *group);
> +
> +
>  /* method functions in ecp_nist.c */
>  int ec_GFp_nist_group_copy(EC_GROUP *dest, const EC_GROUP *src);
>  int ec_GFp_nist_group_set_curve(EC_GROUP *, const BIGNUM *p, const BIGNUM *a, const BIGNUM *b, BN_CTX *);
> diff -ru --new-file openssl-1.0.1l-orig/crypto/ec/ecp_glv.c openssl-1.0.1l/crypto/ec/ecp_glv.c
> --- openssl-1.0.1l-orig/crypto/ec/ecp_glv.c     1970-01-01 02:00:00.000000000 +0200
> +++ openssl-1.0.1l/crypto/ec/ecp_glv.c  2015-01-20 11:30:44.442723943 +0200
> @@ -0,0 +1,336 @@
> +#include <openssl/err.h>
> +
> +#ifdef OPENSSL_FIPS
> +#include <openssl/fips.h>
> +#endif
> +
> +#include "ec_lcl.h"
> +
> +/**
> + * Faster scalar multiplication for GLV curves:
> + * http://eprint.iacr.org/2015/036
> + *
> + * @author Billy Brumley <billy.brumley AT tut DOT fi>
> + */
> +
> +const EC_METHOD *EC_GFp_glv_method(void)
> +       {
> +       static const EC_METHOD ret = {
> +               EC_FLAGS_DEFAULT_OCT,
> +               NID_X9_62_prime_field,
> +               ec_GFp_mont_group_init,
> +               ec_GFp_mont_group_finish,
> +               ec_GFp_mont_group_clear_finish,
> +               ec_GFp_mont_group_copy,
> +               ec_GFp_mont_group_set_curve,
> +               ec_GFp_simple_group_get_curve,
> +               ec_GFp_simple_group_get_degree,
> +               ec_GFp_simple_group_check_discriminant,
> +               ec_GFp_simple_point_init,
> +               ec_GFp_simple_point_finish,
> +               ec_GFp_simple_point_clear_finish,
> +               ec_GFp_simple_point_copy,
> +               ec_GFp_simple_point_set_to_infinity,
> +               ec_GFp_simple_set_Jprojective_coordinates_GFp,
> +               ec_GFp_simple_get_Jprojective_coordinates_GFp,
> +               ec_GFp_simple_point_set_affine_coordinates,
> +               ec_GFp_simple_point_get_affine_coordinates,
> +               0,0,0,
> +               ec_GFp_simple_add,
> +               ec_GFp_simple_dbl,
> +               ec_GFp_simple_invert,
> +               ec_GFp_simple_is_at_infinity,
> +               ec_GFp_simple_is_on_curve,
> +               ec_GFp_simple_cmp,
> +               ec_GFp_simple_make_affine,
> +               ec_GFp_simple_points_make_affine,
> +               ec_GFp_glv_mul,
> +               ec_GFp_glv_precompute_mult,
> +               ec_GFp_glv_have_precompute_mult,
> +               ec_GFp_mont_field_mul,
> +               ec_GFp_mont_field_sqr,
> +               0 /* field_div */,
> +               ec_GFp_mont_field_encode,
> +               ec_GFp_mont_field_decode,
> +               ec_GFp_mont_field_set_to_one };
> +
> +#ifdef OPENSSL_FIPS
> +       if (FIPS_mode())
> +               return fips_ec_gfp_glv_method();
> +#endif
> +
> +       return &ret;
> +       }
> +
> +/* GLV-related per-curve constants */
> +static const unsigned char glv_constants_secp160k1[] = {
> +       /* beta */
> +       0x9b,0xa4,0x8c,0xba,0x5e,0xbc,0xb9,0xb6,
> +       0xbd,0x33,0xb9,0x28,0x30,0xb2,0xa2,0xe0,
> +       0xe1,0x92,0xf1,0x0a,
> +       /* a1 */
> +       0x91,0x62,0xfb,0xe7,0x39,0x84,0x47,0x2a,
> +       0x0a,0x9e,
> +       /* b1 */
> +       0x96,0x34,0x1f,0x11,0x38,0x93,0x3b,0xc2,
> +       0xf5,0x05,
> +       /* a2 */
> +       0x01,0x27,0x97,0x1a,0xf8,0x72,0x17,0x82,
> +       0xec,0xff,0xa3,
> +       /* b2 */
> +       0x91,0x62,0xfb,0xe7,0x39,0x84,0x47,0x2a,
> +       0x0a,0x9e
> +};
> +
> +static const unsigned char glv_constants_secp192k1[] = {
> +       /* beta */
> +       0xbb,0x85,0x69,0x19,0x39,0xb8,0x69,0xc1,
> +       0xd0,0x87,0xf6,0x01,0x55,0x4b,0x96,0xb8,
> +       0x0c,0xb4,0xf5,0x5b,0x35,0xf4,0x33,0xc2,
> +       /* a1 */
> +       0x71,0x16,0x9b,0xe7,0x33,0x0b,0x30,0x38,
> +       0xed,0xb0,0x25,0xf1,
> +       /* b1 */
> +       0xb3,0xfb,0x34,0x00,0xde,0xc5,0xc4,0xad,
> +       0xce,0xb8,0x65,0x5c,
> +       /* a2 */
> +       0x01,0x25,0x11,0xcf,0xe8,0x11,0xd0,0xf4,
> +       0xe6,0xbc,0x68,0x8b,0x4d,
> +       /* b2 */
> +       0x71,0x16,0x9b,0xe7,0x33,0x0b,0x30,0x38,
> +       0xed,0xb0,0x25,0xf1
> +};
> +
> +static const unsigned char glv_constants_secp224k1[] = {
> +       /* beta */
> +       0x01,0xf1,0x78,0xff,0xa4,0xb1,0x7c,0x89,
> +       0xe6,0xf7,0x3a,0xec,0xe2,0xaa,0xd5,0x7a,
> +       0xf4,0xc0,0xa7,0x48,0xb6,0x3c,0x83,0x09,
> +       0x47,0xb2,0x7e,0x04,
> +       /* a1 */
> +       0xb8,0xad,0xf1,0x37,0x8a,0x6e,0xb7,0x34,
> +       0x09,0xfa,0x6c,0x9c,0x63,0x7d,
> +       /* b1 */
> +       0x6b,0x8c,0xf0,0x7d,0x4c,0xa7,0x5c,0x88,
> +       0x95,0x7d,0x9d,0x67,0x05,0x91,
> +       /* a2 */
> +       0x6b,0x8c,0xf0,0x7d,0x4c,0xa7,0x5c,0x88,
> +       0x95,0x7d,0x9d,0x67,0x05,0x91,
> +       /* b2 */
> +       0x01,0x24,0x3a,0xe1,0xb4,0xd7,0x16,0x13,
> +       0xbc,0x9f,0x78,0x0a,0x03,0x69,0x0e
> +};
> +
> +static const unsigned char glv_constants_secp256k1[] = {
> +       /* beta */
> +       0x85,0x16,0x95,0xd4,0x9a,0x83,0xf8,0xef,
> +       0x91,0x9b,0xb8,0x61,0x53,0xcb,0xcb,0x16,
> +       0x63,0x0f,0xb6,0x8a,0xed,0x0a,0x76,0x6a,
> +       0x3e,0xc6,0x93,0xd6,0x8e,0x6a,0xfa,0x40,
> +       /* a1 */
> +       0xe4,0x43,0x7e,0xd6,0x01,0x0e,0x88,0x28,
> +       0x6f,0x54,0x7f,0xa9,0x0a,0xbf,0xe4,0xc3,
> +       /* b1 */
> +       0x30,0x86,0xd2,0x21,0xa7,0xd4,0x6b,0xcd,
> +       0xe8,0x6c,0x90,0xe4,0x92,0x84,0xeb,0x15,
> +       /* a2 */
> +       0x30,0x86,0xd2,0x21,0xa7,0xd4,0x6b,0xcd,
> +       0xe8,0x6c,0x90,0xe4,0x92,0x84,0xeb,0x15,
> +       /* b2 */
> +       0x01,0x14,0xca,0x50,0xf7,0xa8,0xe2,0xf3,
> +       0xf6,0x57,0xc1,0x10,0x8d,0x9d,0x44,0xcf,
> +       0xd8
> +};
> +
> +/**
> + * Integer decomposition.
> + * See 3.5 in "Guide to Elliptic Curve Cryptography"
> + *
> + * The alg is slightly re-arranged to keep all constants positive
> + *
> + * n  = constants[0]
> + * a1 = constants[2]
> + * b1 = constants[3]
> + * a2 = constants[4]
> + * b2 = constants[5]
> + */
> +int ec_GFp_glv_decompose(BIGNUM *k1, BIGNUM *k2, const BIGNUM *scalar, const BIGNUM **constants, BN_CTX *ctx) {
> +
> +       int ret = 0;
> +
> +       BIGNUM *twok, *c1, *c2;
> +
> +       BN_CTX_start(ctx);
> +
> +       do {
> +               twok = BN_CTX_get(ctx);
> +               c1   = BN_CTX_get(ctx);
> +               if ((c2 = BN_CTX_get(ctx)) == NULL) break;
> +
> +               if (!BN_lshift1(twok, scalar)) break;
> +
> +               /* weird computation is for closest int rounding */
> +               /* c1 = (2*b2*k+r[0])/(2*r[0]) */
> +               /* c2 = (2*b1*k+r[0])/(2*r[0]) */
> +               if (!BN_mul(c1, twok, constants[5], ctx)) break;
> +               if (!BN_add(c1, c1, constants[0])) break;
> +               if (!BN_div(c1, NULL, c1, constants[0], ctx)) break;
> +               if (!BN_rshift1(c1, c1)) break;
> +               if (!BN_mul(c2, twok, constants[3], ctx)) break;
> +               if (!BN_add(c2, c2, constants[0])) break;
> +               if (!BN_div(c2, NULL, c2, constants[0], ctx)) break;
> +               if (!BN_rshift1(c2, c2)) break;
> +
> +               /* k1 = k - (c1*a1 + c2*a2) */
> +               /* k2 = c1*b1 - c2*b2 */
> +               if (!BN_mul(k1, constants[2], c1, ctx)) break;
> +               if (!BN_mul(k2, constants[4], c2, ctx)) break;
> +               if (!BN_add(k1, k1, k2)) break;
> +               if (!BN_sub(k1, scalar, k1)) break;
> +               if (!BN_mul(c1, constants[3], c1, ctx)) break;
> +               if (!BN_mul(c2, constants[5], c2, ctx)) break;
> +               if (!BN_sub(k2, c1, c2)) break;
> +
> +               ret = 1;
> +       } while(0);
> +
> +       BN_CTX_end(ctx);
> +
> +       return ret;
> +
> +}
> +
> +/**
> + * Computes the sum
> + * scalar*group->generator + scalars[0]*points[0] + ... + scalars[num-1]*points[num-1]
> + */
> +int ec_GFp_glv_mul(const EC_GROUP *group, EC_POINT *r, const BIGNUM *scalar,
> +       size_t num, const EC_POINT *points[], const BIGNUM *scalars[], BN_CTX *ctx)
> +       {
> +
> +       /* use default stuff if we have precomp and it can help */
> +       if(num == 0 && EC_GROUP_have_precompute_mult(group))
> +               return ec_wNAF_mul(group, r, scalar, num, points, scalars, ctx);
> +
> +       int i, ret = 0;
> +
> +       BIGNUM *tscalar = NULL;
> +       EC_POINT **tpoints = NULL;
> +       BIGNUM **tscalars = NULL;
> +       BIGNUM **constants = NULL;
> +
> +       if ((constants = OPENSSL_malloc(6*sizeof(BIGNUM *))) == NULL) return 0;
> +
> +       BN_CTX_start(ctx);
> +
> +       /* fill in the constants */
> +       for(i=0; i<6; i++) {
> +               constants[i] = BN_CTX_get(ctx);
> +       }
> +
> +       if(constants[5] == NULL) goto err;
> +
> +       if (!EC_GROUP_get_order(group, constants[0], ctx)) goto err;
> +
> +       switch(EC_GROUP_get_curve_name(group)) {
> +               case NID_secp160k1:
> +                       BN_bin2bn(glv_constants_secp160k1 +  0, 20, constants[1]);
> +                       BN_bin2bn(glv_constants_secp160k1 + 20, 10, constants[2]);
> +                       BN_bin2bn(glv_constants_secp160k1 + 30, 10, constants[3]);
> +                       BN_bin2bn(glv_constants_secp160k1 + 40, 11, constants[4]);
> +                       BN_bin2bn(glv_constants_secp160k1 + 51, 10, constants[5]);
> +                       break;
> +               case NID_secp192k1:
> +                       BN_bin2bn(glv_constants_secp192k1 +  0, 24, constants[1]);
> +                       BN_bin2bn(glv_constants_secp192k1 + 24, 12, constants[2]);
> +                       BN_bin2bn(glv_constants_secp192k1 + 36, 12, constants[3]);
> +                       BN_bin2bn(glv_constants_secp192k1 + 48, 13, constants[4]);
> +                       BN_bin2bn(glv_constants_secp192k1 + 61, 12, constants[5]);
> +                       break;
> +               case NID_secp224k1:
> +                       BN_bin2bn(glv_constants_secp224k1 +  0, 28, constants[1]);
> +                       BN_bin2bn(glv_constants_secp224k1 + 28, 14, constants[2]);
> +                       BN_bin2bn(glv_constants_secp224k1 + 42, 14, constants[3]);
> +                       BN_bin2bn(glv_constants_secp224k1 + 56, 14, constants[4]);
> +                       BN_bin2bn(glv_constants_secp224k1 + 70, 15, constants[5]);
> +                       break;
> +               case NID_secp256k1:
> +                       BN_bin2bn(glv_constants_secp256k1 +  0, 32, constants[1]);
> +                       BN_bin2bn(glv_constants_secp256k1 + 32, 16, constants[2]);
> +                       BN_bin2bn(glv_constants_secp256k1 + 48, 16, constants[3]);
> +                       BN_bin2bn(glv_constants_secp256k1 + 64, 16, constants[4]);
> +                       BN_bin2bn(glv_constants_secp256k1 + 80, 17, constants[5]);
> +                       break;
> +               default:
> +                       goto err;
> +       }
> +
> +       /* encode beta parameter to curve's finite field */
> +       if (!group->meth->field_encode(group, constants[1], constants[1], ctx)) goto err;
> +
> +       /* setup some arrays and decompose scalar if it's present and apply endomorphism */
> +       if(scalar == NULL) {
> +               if ((tpoints = OPENSSL_malloc(2 * num * sizeof(EC_POINT *))) == NULL) goto err;
> +               if ((tscalars = OPENSSL_malloc(2 * num * sizeof(BIGNUM *))) == NULL) goto err;
> +       }
> +       else {
> +               if ((tpoints = OPENSSL_malloc((2 * num + 1) * sizeof(EC_POINT *))) == NULL) goto err;
> +               if ((tscalars = OPENSSL_malloc((2 * num + 1) * sizeof(BIGNUM *))) == NULL) goto err;
> +               tscalar = BN_CTX_get(ctx);
> +               if ((tscalars[2*num] = BN_CTX_get(ctx)) == NULL) goto err;
> +               if ((tpoints[2*num] = EC_POINT_new(group)) == NULL) goto err;
> +               if (!EC_POINT_copy(tpoints[2*num], EC_GROUP_get0_generator(group))) goto err;
> +               if (!group->meth->field_mul(group, &tpoints[2*num]->X, &tpoints[2*num]->X, constants[1], ctx)) goto err;
> +               if (!ec_GFp_glv_decompose(tscalar, tscalars[2*num], scalar, (const BIGNUM **)constants, ctx)) goto err;
> +       }
> +
> +       /* decompose all the other scalars and apply the endomorphism */
> +       for(i=0; i < num; i++) {
> +               tpoints[2*i  ] = *((EC_POINT **)points + 2*i);
> +               if ((tpoints[2*i+1] = EC_POINT_new(group)) == NULL) goto err;
> +               if (!EC_POINT_copy(tpoints[2*i+1], tpoints[2*i])) goto err;
> +               if (!group->meth->field_mul(group, &tpoints[2*i+1]->X, &tpoints[2*i+1]->X, constants[1], ctx)) goto err;
> +               tscalars[2*i  ] = BN_CTX_get(ctx);
> +               if ((tscalars[2*i+1] = BN_CTX_get(ctx)) == NULL) goto err;
> +               if (!ec_GFp_glv_decompose(tscalars[2*i], tscalars[2*i+1], scalars[i], (const BIGNUM **)constants, ctx)) goto err;
> +       }
> +
> +       /* call into the multi scalar mult routine with new parameters */
> +       if(scalar == NULL) {
> +               ret = ec_wNAF_mul(group, r, scalar, 2*num, (const EC_POINT **)tpoints, (const BIGNUM **)tscalars, ctx);
> +       }
> +       else {
> +               ret = ec_wNAF_mul(group, r, tscalar, 2*num+1, (const EC_POINT **)tpoints, (const BIGNUM **)tscalars, ctx);
> +       }
> +
> +err:
> +
> +       /* cleanup */
> +       if (tpoints != NULL) {
> +               for(i=0; i < num; i++) {
> +                       EC_POINT_free(tpoints[2*i+1]);
> +               }
> +               if (scalar != NULL) {
> +                       EC_POINT_free(tpoints[2*num]);
> +               }
> +       }
> +
> +       BN_CTX_end(ctx);
> +
> +       OPENSSL_free(tpoints);
> +       OPENSSL_free(tscalars);
> +       OPENSSL_free(constants);
> +
> +       return ret;
> +       }
> +
> +int ec_GFp_glv_precompute_mult(EC_GROUP *group, BN_CTX *ctx)
> +       {
> +       return ec_wNAF_precompute_mult(group, ctx);
> +       }
> +
> +int ec_GFp_glv_have_precompute_mult(const EC_GROUP *group)
> +       {
> +       return ec_wNAF_have_precompute_mult(group);
> +       }
> +
> diff -ru --new-file openssl-1.0.1l-orig/crypto/ec/Makefile openssl-1.0.1l/crypto/ec/Makefile
> --- openssl-1.0.1l-orig/crypto/ec/Makefile      2015-01-15 16:45:04.000000000 +0200
> +++ openssl-1.0.1l/crypto/ec/Makefile   2015-01-19 13:43:51.239965175 +0200
> @@ -17,13 +17,13 @@
>  APPS=
>
>  LIB=$(TOP)/libcrypto.a
> -LIBSRC=        ec_lib.c ecp_smpl.c ecp_mont.c ecp_nist.c ec_cvt.c ec_mult.c\
> +LIBSRC=        ec_lib.c ecp_smpl.c ecp_mont.c ecp_glv.c ecp_nist.c ec_cvt.c ec_mult.c\
>         ec_err.c ec_curve.c ec_check.c ec_print.c ec_asn1.c ec_key.c\
>         ec2_smpl.c ec2_mult.c ec_ameth.c ec_pmeth.c eck_prn.c \
>         ecp_nistp224.c ecp_nistp256.c ecp_nistp521.c ecp_nistputil.c \
>         ecp_oct.c ec2_oct.c ec_oct.c
>
> -LIBOBJ=        ec_lib.o ecp_smpl.o ecp_mont.o ecp_nist.o ec_cvt.o ec_mult.o\
> +LIBOBJ=        ec_lib.o ecp_smpl.o ecp_mont.o ecp_glv.o ecp_nist.o ec_cvt.o ec_mult.o\
>         ec_err.o ec_curve.o ec_check.o ec_print.o ec_asn1.o ec_key.o\
>         ec2_smpl.o ec2_mult.o ec_ameth.o ec_pmeth.o eck_prn.o \
>         ecp_nistp224.o ecp_nistp256.o ecp_nistp521.o ecp_nistputil.o \
> @@ -233,6 +233,14 @@
>  ecp_mont.o: ../../include/openssl/opensslv.h ../../include/openssl/ossl_typ.h
>  ecp_mont.o: ../../include/openssl/safestack.h ../../include/openssl/stack.h
>  ecp_mont.o: ../../include/openssl/symhacks.h ec_lcl.h ecp_mont.c
> +ecp_glv.o: ../../include/openssl/asn1.h ../../include/openssl/bio.h
> +ecp_glv.o: ../../include/openssl/bn.h ../../include/openssl/crypto.h
> +ecp_glv.o: ../../include/openssl/e_os2.h ../../include/openssl/ec.h
> +ecp_glv.o: ../../include/openssl/err.h ../../include/openssl/lhash.h
> +ecp_glv.o: ../../include/openssl/obj_mac.h ../../include/openssl/opensslconf.h
> +ecp_glv.o: ../../include/openssl/opensslv.h ../../include/openssl/ossl_typ.h
> +ecp_glv.o: ../../include/openssl/safestack.h ../../include/openssl/stack.h
> +ecp_glv.o: ../../include/openssl/symhacks.h ec_lcl.h ecp_glv.c
>  ecp_nist.o: ../../include/openssl/asn1.h ../../include/openssl/bio.h
>  ecp_nist.o: ../../include/openssl/bn.h ../../include/openssl/crypto.h
>  ecp_nist.o: ../../include/openssl/e_os2.h ../../include/openssl/ec.h
>
> _______________________________________________
> openssl-dev mailing list
> To unsubscribe: https://mta.openssl.org/mailman/listinfo/openssl-dev
>


--
Ticket here: http://rt.openssl.org/Ticket/Display.html?id=3667
Please log in as guest with password guest if prompted

--
openssl-dev mailing list
To unsubscribe: https://mta.openssl.org/mailman/listinfo/openssl-dev