[openssl-dev] [openssl.org #3667] [PATCH] Faster GLV elliptic curves
Billy Brumley via RT
rt at openssl.org
Tue Jan 20 14:02:25 UTC 2015
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
-------------- next part --------------
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
More information about the openssl-dev
mailing list