[openssl-dev] [openssl.org #3667] [PATCH] Faster GLV elliptic curves
Billy Brumley
bbrumley at gmail.com
Wed Mar 2 09:44:56 UTC 2016
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 <rt at openssl.org> 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
>
More information about the openssl-dev
mailing list