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 <[email protected]> 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
