This patch speeds up binary curve ECC, particularly ECDSA sign and
verify -- up to 5x improvement. It also rolls in RT 3863.
Before patch: $ apps/openssl speed ecdh; apps/openssl speed ecdsa
op op/s
160 bit ecdh (secp160r1) 0.0002s 6071.7
192 bit ecdh (nistp192) 0.0002s 5274.3
224 bit ecdh (nistp224) 0.0003s 3765.9
256 bit ecdh (nistp256) 0.0001s 15110.3
384 bit ecdh (nistp384) 0.0006s 1623.6
521 bit ecdh (nistp521) 0.0013s 779.8
163 bit ecdh (nistk163) 0.0002s 5458.8
233 bit ecdh (nistk233) 0.0002s 4278.8
283 bit ecdh (nistk283) 0.0004s 2370.3
409 bit ecdh (nistk409) 0.0007s 1512.3
571 bit ecdh (nistk571) 0.0016s 634.6
163 bit ecdh (nistb163) 0.0002s 5226.9
233 bit ecdh (nistb233) 0.0002s 4102.0
283 bit ecdh (nistb283) 0.0005s 2214.0
409 bit ecdh (nistb409) 0.0007s 1403.5
571 bit ecdh (nistb571) 0.0017s 589.6
sign verify sign/s verify/s
160 bit ecdsa (secp160r1) 0.0001s 0.0002s 18743.2 5022.9
192 bit ecdsa (nistp192) 0.0001s 0.0002s 16058.0 4275.1
224 bit ecdsa (nistp224) 0.0001s 0.0003s 12243.6 3101.8
256 bit ecdsa (nistp256) 0.0000s 0.0001s 25672.8 10551.7
384 bit ecdsa (nistp384) 0.0002s 0.0007s 5672.3 1337.2
521 bit ecdsa (nistp521) 0.0004s 0.0015s 2739.5 656.6
163 bit ecdsa (nistk163) 0.0002s 0.0004s 5926.5 2628.6
233 bit ecdsa (nistk233) 0.0003s 0.0005s 3005.7 2040.8
283 bit ecdsa (nistk283) 0.0005s 0.0009s 1986.0 1135.5
409 bit ecdsa (nistk409) 0.0011s 0.0014s 875.8 714.8
571 bit ecdsa (nistk571) 0.0025s 0.0033s 407.2 307.5
163 bit ecdsa (nistb163) 0.0002s 0.0004s 5955.7 2496.3
233 bit ecdsa (nistb233) 0.0003s 0.0005s 3027.2 1941.5
283 bit ecdsa (nistb283) 0.0005s 0.0009s 1979.3 1069.0
409 bit ecdsa (nistb409) 0.0011s 0.0015s 873.9 680.9
571 bit ecdsa (nistb571) 0.0025s 0.0035s 407.6 285.1
After patch: $ apps/openssl speed ecdh; apps/openssl speed ecdsa
op op/s
160 bit ecdh (secp160r1) 0.0002s 6071.2
192 bit ecdh (nistp192) 0.0002s 5182.0
224 bit ecdh (nistp224) 0.0003s 3811.1
256 bit ecdh (nistp256) 0.0001s 15146.6
384 bit ecdh (nistp384) 0.0006s 1629.7
521 bit ecdh (nistp521) 0.0013s 787.5
163 bit ecdh (nistk163) 0.0002s 4953.6
233 bit ecdh (nistk233) 0.0003s 3875.9
283 bit ecdh (nistk283) 0.0005s 2163.5
409 bit ecdh (nistk409) 0.0008s 1292.3
571 bit ecdh (nistk571) 0.0017s 579.4
163 bit ecdh (nistb163) 0.0002s 4920.8
233 bit ecdh (nistb233) 0.0003s 3797.5
283 bit ecdh (nistb283) 0.0005s 2187.6
409 bit ecdh (nistb409) 0.0008s 1294.3
571 bit ecdh (nistb571) 0.0017s 573.1
sign verify sign/s verify/s
160 bit ecdsa (secp160r1) 0.0001s 0.0002s 18759.4 5074.0
192 bit ecdsa (nistp192) 0.0001s 0.0002s 16093.8 4261.2
224 bit ecdsa (nistp224) 0.0001s 0.0003s 12219.5 3194.9
256 bit ecdsa (nistp256) 0.0000s 0.0001s 25561.8 10578.7
384 bit ecdsa (nistp384) 0.0002s 0.0007s 5665.2 1352.6
521 bit ecdsa (nistp521) 0.0004s 0.0015s 2714.5 647.4
163 bit ecdsa (nistk163) 0.0001s 0.0002s 17117.7 4026.1
233 bit ecdsa (nistk233) 0.0001s 0.0003s 12921.6 3108.2
283 bit ecdsa (nistk283) 0.0001s 0.0006s 7994.1 1784.6
409 bit ecdsa (nistk409) 0.0002s 0.0009s 4943.8 1074.2
571 bit ecdsa (nistk571) 0.0004s 0.0021s 2235.5 476.0
163 bit ecdsa (nistb163) 0.0001s 0.0002s 17119.8 4002.7
233 bit ecdsa (nistb233) 0.0001s 0.0003s 13129.5 3104.2
283 bit ecdsa (nistb283) 0.0001s 0.0006s 7977.2 1765.5
409 bit ecdsa (nistb409) 0.0002s 0.0009s 4927.0 1073.8
571 bit ecdsa (nistb571) 0.0004s 0.0021s 2263.0 478.2
$ 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 : 0x17
cpu MHz : 3200.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 nopl xtopology nonstop_tsc aperfmperf eagerfpu 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 dtherm
tpr_shadow vnmi flexpriority ept vpid fsgsbase tsc_adjust 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>
>From e7d26ad981772aacfa0e5607c9c392c9786c0bff Mon Sep 17 00:00:00 2001
From: Billy Brumley <[email protected]>
Date: Thu, 20 Aug 2015 18:13:23 +0300
Subject: [PATCH] Binary ECC: lambda projective coordinates
---
crypto/ec/Makefile | 13 +-
crypto/ec/ec2_lambda.c | 438 +++++++++++++++++++++++++++++++++++++++++++++++++
crypto/ec/ec2_smpl.c | 1 +
crypto/ec/ec_cvt.c | 7 +-
crypto/ec/ec_key.c | 2 +
crypto/ec/ec_lcl.h | 15 ++
include/openssl/ec.h | 5 +
7 files changed, 478 insertions(+), 3 deletions(-)
create mode 100644 crypto/ec/ec2_lambda.c
diff --git a/crypto/ec/Makefile b/crypto/ec/Makefile
index a2c135a..242573d 100644
--- a/crypto/ec/Makefile
+++ b/crypto/ec/Makefile
@@ -19,13 +19,13 @@ GENERAL=Makefile
LIB=$(TOP)/libcrypto.a
LIBSRC= ec_lib.c ecp_smpl.c ecp_mont.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 \
+ ec2_smpl.c ec2_lambda.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\
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 \
+ ec2_smpl.o ec2_lambda.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 \
ecp_oct.o ec2_oct.o ec_oct.o $(EC_ASM)
@@ -113,6 +113,15 @@ ec2_smpl.o: ../../include/openssl/opensslv.h ../../include/openssl/ossl_typ.h
ec2_smpl.o: ../../include/openssl/safestack.h ../../include/openssl/stack.h
ec2_smpl.o: ../../include/openssl/symhacks.h ../include/internal/bn_int.h
ec2_smpl.o: ec2_smpl.c ec_lcl.h
+ec2_lambda.o: ../../include/openssl/asn1.h ../../include/openssl/bio.h
+ec2_lambda.o: ../../include/openssl/bn.h ../../include/openssl/crypto.h
+ec2_lambda.o: ../../include/openssl/e_os2.h ../../include/openssl/ec.h
+ec2_lambda.o: ../../include/openssl/err.h ../../include/openssl/lhash.h
+ec2_lambda.o: ../../include/openssl/obj_mac.h ../../include/openssl/opensslconf.h
+ec2_lambda.o: ../../include/openssl/opensslv.h ../../include/openssl/ossl_typ.h
+ec2_lambda.o: ../../include/openssl/safestack.h ../../include/openssl/stack.h
+ec2_lambda.o: ../../include/openssl/symhacks.h ../include/internal/bn_int.h
+ec2_lambda.o: ec2_lambda.c ec_lcl.h
ec_ameth.o: ../../e_os.h ../../include/openssl/asn1.h
ec_ameth.o: ../../include/openssl/asn1t.h ../../include/openssl/bio.h
ec_ameth.o: ../../include/openssl/bn.h ../../include/openssl/buffer.h
diff --git a/crypto/ec/ec2_lambda.c b/crypto/ec/ec2_lambda.c
new file mode 100644
index 0000000..36248a5
--- /dev/null
+++ b/crypto/ec/ec2_lambda.c
@@ -0,0 +1,438 @@
+/* crypto/ec/ec2_lambda.c */
+/**
+ * Binary curve arithmetic using lambda-projective coordinates.
+ * Only supports short binary curve coeffs a=0 and a=1.
+ * Essentially projective form of (x, y) -> (x, lambda)
+ * where lambda = x XOR y/x.
+ *
+ * NB: Everything internally is lambda-affine/proj, relies
+ * on set/get_affine_coordinates function pointers for the
+ * "external"-facing interface to handle the conversion
+ * to/from the standard short form.
+ *
+ * See "Faster Binary Curve Software: A Case Study",
+ * NordSec 2015, to appear.
+ *
+ * @author Billy Brumley <billy.brumley AT tut DOT fi>
+ */
+
+#include <openssl/err.h>
+
+#include "internal/bn_int.h"
+#include "ec_lcl.h"
+
+#ifndef OPENSSL_NO_EC2M
+
+const EC_METHOD *EC_GF2m_lambda_method(void)
+{
+ static const EC_METHOD ret = {
+ EC_FLAGS_DEFAULT_OCT,
+ NID_X9_62_characteristic_two_field,
+ ec_GF2m_simple_group_init,
+ ec_GF2m_simple_group_finish,
+ ec_GF2m_simple_group_clear_finish,
+ ec_GF2m_simple_group_copy,
+ ec_GF2m_simple_group_set_curve,
+ ec_GF2m_simple_group_get_curve,
+ ec_GF2m_simple_group_get_degree,
+ ec_GF2m_simple_group_check_discriminant,
+ ec_GF2m_simple_point_init,
+ ec_GF2m_simple_point_finish,
+ ec_GF2m_simple_point_clear_finish,
+ ec_GF2m_simple_point_copy,
+ ec_GF2m_simple_point_set_to_infinity,
+ 0 /* set_Jprojective_coordinates_GFp */ ,
+ 0 /* get_Jprojective_coordinates_GFp */ ,
+ ec_GF2m_lambda_point_set_affine_coordinates,
+ ec_GF2m_lambda_point_get_affine_coordinates,
+ 0, 0, 0,
+ ec_GF2m_lambda_add,
+ ec_GF2m_lambda_dbl,
+ ec_GF2m_lambda_invert,
+ ec_GF2m_simple_is_at_infinity,
+ ec_GF2m_lambda_is_on_curve,
+ ec_GF2m_simple_cmp,
+ ec_GF2m_lambda_make_affine,
+ ec_GF2m_simple_points_make_affine,
+ 0 /* mul defaults to ec_wNAF_mul */ ,
+ /* next two functions defined in ec2_mult.c */
+ ec_GF2m_precompute_mult,
+ ec_GF2m_have_precompute_mult,
+ ec_GF2m_simple_field_mul,
+ ec_GF2m_simple_field_sqr,
+ ec_GF2m_simple_field_div,
+ 0 /* field_encode */ ,
+ 0 /* field_decode */ ,
+ 0 /* field_set_to_one */
+ };
+
+ return &ret;
+}
+
+/**
+ * Computes a + a and stores the result in r.
+ * Src: EFD "dbl-2013-olar"
+ *
+ * @param a input point in lambda-affine/proj
+ * @param r output point in lambda-proj
+ */
+int ec_GF2m_lambda_dbl(const EC_GROUP *group, EC_POINT *r, const EC_POINT *a,
+ BN_CTX *ctx)
+{
+ if (EC_POINT_is_at_infinity(group, a)) {
+ return EC_POINT_set_to_infinity(group, r);
+ }
+
+ int ret = 0;
+ BN_CTX_start(ctx);
+
+ do {
+ BIGNUM *t0, *t1, *t2, *t3;
+ t0 = BN_CTX_get(ctx);
+ t1 = BN_CTX_get(ctx);
+ t2 = BN_CTX_get(ctx);
+ t3 = BN_CTX_get(ctx);
+ if (t3 == NULL) break;
+ if (!group->meth->field_sqr(group, t0, a->Y, ctx)) break;
+ if (!group->meth->field_mul(group, t3, a->Z, a->Y, ctx)) break;
+ if (!group->meth->field_sqr(group, t1, a->Z, ctx)) break;
+ if (!group->meth->field_mul(group, t2, a->X, a->Z, ctx)) break;
+ if (!BN_GF2m_add(t0, t3, t0)) break;
+ if (BN_is_one(group->a)) {
+ if (!BN_GF2m_add(t0, t0, t1)) break;
+ }
+ if (!group->meth->field_sqr(group, r->X, t0, ctx)) break;
+ if (!group->meth->field_mul(group, r->Z, t1, t0, ctx)) break;
+ if (!group->meth->field_mul(group, t0, t3, t0, ctx)) break;
+ if (!group->meth->field_sqr(group, t2, t2, ctx)) break;
+ if (!BN_GF2m_add(t0, r->Z, t0)) break;
+ if (!BN_GF2m_add(t0, t0, r->X)) break;
+ if (!BN_GF2m_add(r->Y, t0, t2)) break;
+ ret = 1;
+ } while(0);
+
+ r->Z_is_one = 0;
+ BN_CTX_end(ctx);
+ return ret;
+}
+
+/**
+ * Computes a + b and stores the result in r.
+ * NB: Call through the wrapper.
+ * Src: EFD "add-2013-olar"
+ *
+ * @param a input point in lambda-affine/proj
+ * @param b input point in lambda-affine
+ * @param r output point in lambda-proj
+ */
+int ec_GF2m_lambda_add_mixed(const EC_GROUP *group, EC_POINT *r, const EC_POINT *a,
+ const EC_POINT *b, BN_CTX *ctx)
+{
+ int ret = 0;
+ BN_CTX_start(ctx);
+
+ do {
+ BIGNUM *t0, *t1, *t2, *t3;
+ t0 = BN_CTX_get(ctx);
+ t1 = BN_CTX_get(ctx);
+ t2 = BN_CTX_get(ctx);
+ t3 = BN_CTX_get(ctx);
+ if (t3 == NULL) break;
+ if (!group->meth->field_mul(group, t1, b->Y, a->Z, ctx)) break;
+ if (!BN_GF2m_add(t2, t1, a->Y)) break;
+ if (!group->meth->field_mul(group, t1, b->X, a->Z, ctx)) break;
+ if (!BN_GF2m_add(t0, t1, a->X)) break;
+ if (BN_is_zero(t0)) {
+ if (BN_is_zero(t2)) {
+ /* a and b are the same in lambda-affine, so double */
+ ret = ec_GF2m_lambda_dbl(group, r, b, ctx);
+ }
+ else {
+ /* b = -a, so infty */
+ ret = EC_POINT_set_to_infinity(group, r);
+ }
+ break;
+ }
+ if (!group->meth->field_mul(group, t1, t1, t2, ctx)) break;
+ if (!group->meth->field_mul(group, t3, a->X, t2, ctx)) break;
+ if (!group->meth->field_sqr(group, t0, t0, ctx)) break;
+ if (!group->meth->field_mul(group, r->X, t1, t3, ctx)) break;
+ if (!BN_GF2m_add(t3, a->Z, a->Y)) break;
+ if (!group->meth->field_mul(group, t2, t0, t2, ctx)) break;
+ if (!BN_GF2m_add(t0, t0, t1)) break;
+ if (!group->meth->field_mul(group, t3, t3, t2, ctx)) break;
+ if (!group->meth->field_sqr(group, t0, t0, ctx)) break;
+ if (!group->meth->field_mul(group, r->Z, a->Z, t2, ctx)) break;
+ if (!BN_GF2m_add(r->Y, t3, t0)) break;
+ ret = 1;
+ } while(0);
+
+ BN_CTX_end(ctx);
+ return ret;
+}
+
+/**
+ * Computes a + b and stores the result in r.
+ * NB: Call through the wrapper.
+ * Src: EFD "add-2013-olar"
+ *
+ * @param a input point in lambda-affine/proj
+ * @param b input point in lambda-affine/proj
+ * @param r output point in lambda-proj
+ */
+int ec_GF2m_lambda_add_proj(const EC_GROUP *group, EC_POINT *r, const EC_POINT *a,
+ const EC_POINT *b, BN_CTX *ctx)
+{
+ int ret = 0;
+ BN_CTX_start(ctx);
+
+ do {
+ BIGNUM *t0, *t1, *t2, *t3, *t4, *t5;
+ t0 = BN_CTX_get(ctx);
+ t1 = BN_CTX_get(ctx);
+ t2 = BN_CTX_get(ctx);
+ t3 = BN_CTX_get(ctx);
+ t4 = BN_CTX_get(ctx);
+ t5 = BN_CTX_get(ctx);
+ if (t5 == NULL) break;
+ if (!group->meth->field_mul(group, t3, a->X, b->Z, ctx)) break;
+ if (!group->meth->field_mul(group, t2, b->X, a->Z, ctx)) break;
+ if (!group->meth->field_mul(group, t0, b->Y, a->Z, ctx)) break;
+ if (!group->meth->field_mul(group, t1, b->Z, a->Y, ctx)) break;
+ if (!BN_GF2m_add(t0, t0, t1)) break;
+ if (!BN_GF2m_add(t1, t2, t3)) break;
+ if (BN_is_zero(t1)) {
+ if (BN_is_zero(t0)) {
+ /* a and b are the same in lambda-affine, so double */
+ ret = ec_GF2m_lambda_dbl(group, r, a, ctx);
+ }
+ else {
+ /* b = -a, so infty */
+ ret = EC_POINT_set_to_infinity(group, r);
+ }
+ break;
+ }
+ if (!BN_GF2m_add(t4, a->Z, a->Y)) break;
+ if (!group->meth->field_mul(group, t2, t2, t0, ctx)) break;
+ if (!group->meth->field_sqr(group, t5, t1, ctx)) break;
+ if (!group->meth->field_mul(group, t3, t3, t0, ctx)) break;
+ if (!group->meth->field_mul(group, t1, t5, t0, ctx)) break;
+ if (!group->meth->field_mul(group, r->X, t2, t3, ctx)) break;
+ if (!group->meth->field_mul(group, t0, b->Z, t1, ctx)) break;
+ if (!BN_GF2m_add(t1, t5, t2)) break;
+ if (!group->meth->field_mul(group, t4, t4, t0, ctx)) break;
+ if (!group->meth->field_sqr(group, t1, t1, ctx)) break;
+ if (!group->meth->field_mul(group, r->Z, a->Z, t0, ctx)) break;
+ if (!BN_GF2m_add(r->Y, t4, t1)) break;
+ ret = 1;
+ } while(0);
+
+ BN_CTX_end(ctx);
+ return ret;
+}
+
+/**
+ * Computes a + b and stores the result in r.
+ * Wrapper function that supports lambda-affine/proj/mixed.
+ *
+ * @param a input point in lambda-affine/proj
+ * @param b input point in lambda-affine/proj
+ * @param r output point in lambda-proj
+ */
+int ec_GF2m_lambda_add(const EC_GROUP *group, EC_POINT *r, const EC_POINT *a,
+ const EC_POINT *b, BN_CTX *ctx)
+{
+
+ if (EC_POINT_is_at_infinity(group, a)) {
+ if (!EC_POINT_copy(r, b))
+ return 0;
+ return 1;
+ }
+
+ if (EC_POINT_is_at_infinity(group, b)) {
+ if (!EC_POINT_copy(r, a))
+ return 0;
+ return 1;
+ }
+
+ int ret = 0;
+
+ if (a == b) {
+ ret = ec_GF2m_lambda_dbl(group, r, a, ctx);
+ }
+ else if (b->Z_is_one) {
+ ret = ec_GF2m_lambda_add_mixed(group,r,a,b,ctx);
+ }
+ else if (a->Z_is_one) {
+ ret = ec_GF2m_lambda_add_mixed(group,r,b,a,ctx);
+ }
+ else {
+ ret = ec_GF2m_lambda_add_proj(group,r,a,b,ctx);
+ }
+
+ r->Z_is_one = 0;
+ return ret;
+}
+
+/**
+ * Inverts point wrt lambda-affine/proj coords.
+ * I.e. -(X, Y, Z) -> (X, Y XOR Z, Z)
+ *
+ * @param point input and output point
+ */
+int ec_GF2m_lambda_invert(const EC_GROUP *group, EC_POINT *point, BN_CTX *ctx)
+{
+ /* -infty -> infty */
+ if (EC_POINT_is_at_infinity(group, point))
+ return 1;
+
+ return BN_GF2m_add(point->Y, point->Y, point->Z);
+}
+
+/**
+ * Sets point to lambda-affine coord equiv of short coords (x,y)
+ * I.e. (x, y) -> (x, x XOR y/x, 1)
+ * @param point output point in lambda-affine
+ * @param x input coord in short-affine
+ * @param y input coord in short-affine
+ */
+int ec_GF2m_lambda_point_set_affine_coordinates(const EC_GROUP *group,
+ EC_POINT *point,
+ const BIGNUM *x,
+ const BIGNUM *y, BN_CTX *ctx)
+{
+ if (x == NULL || y == NULL) {
+ ECerr(EC_F_EC_GF2M_SIMPLE_POINT_SET_AFFINE_COORDINATES,
+ ERR_R_PASSED_NULL_PARAMETER);
+ return 0;
+ }
+
+ int ret = 0;
+
+ do {
+ if (!BN_copy(point->X, x)) break;
+ BN_set_negative(point->X, 0);
+ if (!group->meth->field_div(group, point->Y, y, point->X, ctx)) break;
+ if (!BN_GF2m_add(point->Y, point->Y, point->X)) break;
+ BN_set_negative(point->Y, 0);
+ if (!BN_one(point->Z)) break;
+ BN_set_negative(point->Z, 0);
+ point->Z_is_one = 1;
+ ret = 1;
+ } while(0);
+
+ return ret;
+}
+
+/**
+ * Sets x and y to short-affine equiv of lambda-affine/proj point.
+ * I.e. (X, Y, Z) -> (X/Z, Y/Z, 1) then
+ * (x, y) -> (x, (x XOR y) * x)
+ *
+ * @param point input point in lambda-affine/proj
+ * @param x output coord in short-affine. Can be NULL.
+ * @param y output coord in short-affine. Can be NULL.
+ */
+int ec_GF2m_lambda_point_get_affine_coordinates(const EC_GROUP *group,
+ const EC_POINT *point,
+ BIGNUM *x, BIGNUM *y,
+ BN_CTX *ctx)
+{
+ if (EC_POINT_is_at_infinity(group, point)) {
+ ECerr(EC_F_EC_GF2M_SIMPLE_POINT_GET_AFFINE_COORDINATES,
+ EC_R_POINT_AT_INFINITY);
+ return 0;
+ }
+
+ int ret = 0;
+ EC_POINT *r;
+
+ do {
+ if ((r = EC_POINT_new(group)) == NULL) break;
+ if (!EC_POINT_copy(r, point)) break;
+ if (!EC_POINT_make_affine(group, r, ctx)) break;
+ if (x != NULL) {
+ if (!BN_copy(x, r->X)) break;
+ BN_set_negative(x, 0);
+ }
+ if (y != NULL) {
+ if (!BN_GF2m_add(y, r->Y, r->X)) break;
+ if (!group->meth->field_mul(group, y, y, point->X, ctx)) break;
+ BN_set_negative(y, 0);
+ }
+ ret = 1;
+ } while(0);
+
+ EC_POINT_free(r);
+ return ret;
+}
+
+/**
+ * Converts lambda-affine/proj point to lambda-affine.
+ * I.e. (X, Y, Z) -> (X/Z, Y/Z, 1)
+ *
+ * @param point input/output point
+ */
+int ec_GF2m_lambda_make_affine(const EC_GROUP *group, EC_POINT *point, BN_CTX *ctx)
+{
+ /* infty -> infty */
+ if (EC_POINT_is_at_infinity(group, point))
+ return 1;
+
+ int ret = 0;
+
+ do {
+ if (!BN_GF2m_mod_inv_arr(point->Z, point->Z, group->poly, ctx)) break;
+ if (!group->meth->field_mul(group, point->X, point->X, point->Z, ctx)) break;
+ if (!group->meth->field_mul(group, point->Y, point->Y, point->Z, ctx)) break;
+ if (!BN_one(point->Z)) break;
+ point->Z_is_one = 1;
+ ret = 1;
+ } while(0);
+
+ return ret;
+}
+
+/**
+ * Check if point satisfies the lambda-projective curve equation:
+ * (L**2 + L * Z + a * Z**2) * X**2 = X**4 + b * Z**4
+ *
+ * @param point lambda-affine/proj point to test if its on the curve
+ */
+int ec_GF2m_lambda_is_on_curve(const EC_GROUP *group, const EC_POINT *point,
+ BN_CTX *ctx)
+{
+ /* infty always on curve */
+ if (EC_POINT_is_at_infinity(group, point))
+ return 1;
+
+ int ret = 0;
+ BN_CTX_start(ctx);
+
+ do {
+ BIGNUM *t1, *t2, *t3;
+ t1 = BN_CTX_get(ctx);
+ t2 = BN_CTX_get(ctx);
+ t3 = BN_CTX_get(ctx);
+ if (t3 == NULL) break;
+ if (!group->meth->field_sqr(group, t1, point->Y, ctx)) break;
+ if (!group->meth->field_mul(group, t2, point->Y, point->Z, ctx)) break;
+ if (!BN_GF2m_add(t1, t1, t2)) break;
+ if (!group->meth->field_sqr(group, t2, point->Z, ctx)) break;
+ if (BN_is_one(group->a)) {
+ if (!BN_GF2m_add(t1, t1, t2)) break;
+ }
+ if (!group->meth->field_sqr(group, t3, point->X, ctx)) break;
+ if (!BN_GF2m_add(t1, t1, t3)) break;
+ if (!group->meth->field_mul(group, t1, t1, t3, ctx)) break;
+ if (!group->meth->field_sqr(group, t2, t2, ctx)) break;
+ if (!group->meth->field_mul(group, t2, t2, group->b, ctx)) break;
+ if (!BN_GF2m_add(t1, t1, t2)) break;
+ ret = BN_is_zero(t1);
+ } while(0);
+
+ BN_CTX_end(ctx);
+ return ret;
+}
+
+#endif
diff --git a/crypto/ec/ec2_smpl.c b/crypto/ec/ec2_smpl.c
index d6a41a4..eafe4ae 100644
--- a/crypto/ec/ec2_smpl.c
+++ b/crypto/ec/ec2_smpl.c
@@ -742,6 +742,7 @@ int ec_GF2m_simple_make_affine(const EC_GROUP *group, EC_POINT *point,
goto err;
if (!BN_one(point->Z))
goto err;
+ point->Z_is_one = 1;
ret = 1;
diff --git a/crypto/ec/ec_cvt.c b/crypto/ec/ec_cvt.c
index 0720615..813ad10 100644
--- a/crypto/ec/ec_cvt.c
+++ b/crypto/ec/ec_cvt.c
@@ -127,7 +127,12 @@ EC_GROUP *EC_GROUP_new_curve_GF2m(const BIGNUM *p, const BIGNUM *a,
const EC_METHOD *meth;
EC_GROUP *ret;
- meth = EC_GF2m_simple_method();
+ if (BN_is_zero(a) || BN_is_one(a)) {
+ meth = EC_GF2m_lambda_method();
+ }
+ else {
+ meth = EC_GF2m_simple_method();
+ }
ret = EC_GROUP_new(meth);
if (ret == NULL)
diff --git a/crypto/ec/ec_key.c b/crypto/ec/ec_key.c
index a954c8e..6c10bb4 100644
--- a/crypto/ec/ec_key.c
+++ b/crypto/ec/ec_key.c
@@ -367,6 +367,8 @@ int EC_KEY_set_public_key_affine_coordinates(EC_KEY *key, BIGNUM *x,
tx = BN_CTX_get(ctx);
ty = BN_CTX_get(ctx);
+ if (ty == NULL)
+ goto err;
#ifndef OPENSSL_NO_EC2M
tmp_nid = EC_METHOD_get_field_type(EC_GROUP_method_of(key->group));
diff --git a/crypto/ec/ec_lcl.h b/crypto/ec/ec_lcl.h
index 3bf64c6..472f6fb 100644
--- a/crypto/ec/ec_lcl.h
+++ b/crypto/ec/ec_lcl.h
@@ -445,6 +445,21 @@ int ec_GF2m_simple_field_sqr(const EC_GROUP *, BIGNUM *r, const BIGNUM *a,
int ec_GF2m_simple_field_div(const EC_GROUP *, BIGNUM *r, const BIGNUM *a,
const BIGNUM *b, BN_CTX *);
+/* method functions in ec2_lambda.c */
+int ec_GF2m_lambda_point_set_affine_coordinates(const EC_GROUP *, EC_POINT *,
+ const BIGNUM *x,
+ const BIGNUM *y, BN_CTX *);
+int ec_GF2m_lambda_point_get_affine_coordinates(const EC_GROUP *,
+ const EC_POINT *, BIGNUM *x,
+ BIGNUM *y, BN_CTX *);
+int ec_GF2m_lambda_add(const EC_GROUP *, EC_POINT *r, const EC_POINT *a,
+ const EC_POINT *b, BN_CTX *);
+int ec_GF2m_lambda_dbl(const EC_GROUP *, EC_POINT *r, const EC_POINT *a,
+ BN_CTX *);
+int ec_GF2m_lambda_invert(const EC_GROUP *, EC_POINT *, BN_CTX *);
+int ec_GF2m_lambda_is_on_curve(const EC_GROUP *, const EC_POINT *, BN_CTX *);
+int ec_GF2m_lambda_make_affine(const EC_GROUP *, EC_POINT *, BN_CTX *);
+
/* method functions in ec2_mult.c */
int ec_GF2m_simple_mul(const EC_GROUP *group, EC_POINT *r,
const BIGNUM *scalar, size_t num,
diff --git a/include/openssl/ec.h b/include/openssl/ec.h
index 2d36dd5..96fee50 100644
--- a/include/openssl/ec.h
+++ b/include/openssl/ec.h
@@ -177,6 +177,11 @@ const EC_METHOD *EC_GFp_nistp521_method(void);
*/
const EC_METHOD *EC_GF2m_simple_method(void);
+/** Returns the lambda GF2m ec method
+ * \return EC_METHOD object
+ */
+const EC_METHOD *EC_GF2m_lambda_method(void);
+
# endif
/********************************************************************/
--
1.9.1
_______________________________________________
openssl-bugs-mod mailing list
[email protected]
https://mta.openssl.org/mailman/listinfo/openssl-bugs-mod
_______________________________________________
openssl-dev mailing list
To unsubscribe: https://mta.openssl.org/mailman/listinfo/openssl-dev
