[PATCH 0/3] Implement P384 curve

[PATCH 0/3] Implement P384 curve

[James Prestwood]

[-- Attachment #1: Type: text/plain, Size: 528 bytes --]

Now that ECC has been merged into ELL we can add the P384 curve definition.
TLS will eventually use this for some ECDSA cipher suites.

James Prestwood (3):
  ecc: implement P384 fast modulus
  ecc: added P384 curve definition
  unit: added P384 unit tests

 ell/ecc-external.c | 129 +++++++++++++++++++++++++++++++++++++++++++++
 ell/ecc.c          |  30 +++++++++++
 ell/ecc.h          |   2 +-
 unit/test-ecdh.c   |  66 +++++++++++++++++++++++
 4 files changed, 226 insertions(+), 1 deletion(-)

-- 
2.17.1

[PATCH 1/3] ecc: implement P384 fast modulus

[James Prestwood]

[-- Attachment #1: Type: text/plain, Size: 4835 bytes --]

This algorithm is defined in an IEICE paper:

"Simple Power Analysis on Fast Modular Reduction with Generalized Mersenne
 Prime for Elliptic Curve Cryptosystems"

Unlike the existing P192/P256 algorithms, a macro was written to deal with
converting from 32 bit chunks into 64 bits. This also makes the algorithm
much easier to read since the C values are used directly.
---
 ell/ecc-external.c | 129 +++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 129 insertions(+)

diff --git a/ell/ecc-external.c b/ell/ecc-external.c
index 7ddf865..9165bd6 100644
--- a/ell/ecc-external.c
+++ b/ell/ecc-external.c
@@ -455,6 +455,132 @@ static void vli_mmod_fast_256(uint64_t *result, const uint64_t *product,
 	}
 }
 
+/*
+ * The NIST algorithms define S values, which are comprised of 32 bit C values
+ * of the original product we are trying to reduce. Since we are working with
+ * 64 bit 'digits', we need to convert these C values into 64 bit chunks. This
+ * macro mainly makes code readability easier since we can directly pass the
+ * two C indexes (h and l). Some of these C values are zero, which is also a
+ * value C index. In this case -1 should be passed to indicate zero.
+ */
+#define ECC_SET_S(prod, h, l) ({ 				\
+	uint64_t r = 0;						\
+	if (h == -1) {						\
+		/* zero, don't do anything */			\
+	} else if (h & 1)					\
+		r |= (prod[h / 2] & 0xffffffff00000000ull);	\
+	else							\
+		r |= (prod[h / 2] << 32);			\
+	if (l == -1) {						\
+		/* zero, don't do anything */			\
+	} else if (l & 1)					\
+		r |= (prod[l / 2] >> 32);			\
+	else							\
+		r |= (prod[l / 2] & 0xffffffff);		\
+	r;							\
+})
+
+static void vli_mmod_fast_384(uint64_t *result, const uint64_t *product,
+				const uint64_t *curve_prime, uint64_t *tmp)
+{
+	int carry;
+	const unsigned int ndigits = 6;
+
+	/* t */
+	vli_set(result, product, ndigits);
+
+	/* s1 */
+	tmp[0] = 0;
+	tmp[1] = 0;
+	tmp[2] = ECC_SET_S(product, 22, 21);
+	tmp[3] = ECC_SET_S(product, -1, 23);
+	tmp[4] = 0;
+	tmp[5] = 0;
+	carry = vli_lshift(tmp, tmp, 1, ndigits);
+	carry += vli_add(result, result, tmp, ndigits);
+
+	/* s2 */
+	tmp[0] = product[6];
+	tmp[1] = product[7];
+	tmp[2] = product[8];
+	tmp[3] = product[9];
+	tmp[4] = product[10];
+	tmp[5] = product[11];
+	carry += vli_add(result, result, tmp, ndigits);
+
+	/* s3 */
+	tmp[0] = ECC_SET_S(product, 22, 21);
+	tmp[1] = ECC_SET_S(product, 12, 23);
+	tmp[2] = ECC_SET_S(product, 14, 13);
+	tmp[3] = ECC_SET_S(product, 16, 15);
+	tmp[4] = ECC_SET_S(product, 18, 17);
+	tmp[5] = ECC_SET_S(product, 20, 19);
+	carry += vli_add(result, result, tmp, ndigits);
+
+	/* s4 */
+	tmp[0] = ECC_SET_S(product, 23, -1);
+	tmp[1] = ECC_SET_S(product, 20, -1);
+	tmp[2] = ECC_SET_S(product, 13, 12);
+	tmp[3] = ECC_SET_S(product, 15, 14);
+	tmp[4] = ECC_SET_S(product, 17, 16);
+	tmp[5] = ECC_SET_S(product, 19, 18);
+	carry += vli_add(result, result, tmp, ndigits);
+
+	/* s5 */
+	tmp[0] = 0;
+	tmp[1] = 0;
+	tmp[2] = ECC_SET_S(product, 21, 20);
+	tmp[3] = ECC_SET_S(product, 23, 22);
+	tmp[4] = 0;
+	tmp[5] = 0;
+	carry += vli_add(result, result, tmp, ndigits);
+
+	/* s6 */
+	tmp[0] = ECC_SET_S(product, -1, 20);
+	tmp[1] = ECC_SET_S(product, 21, -1);
+	tmp[2] = ECC_SET_S(product, 23, 22);
+	tmp[3] = 0;
+	tmp[4] = 0;
+	tmp[5] = 0;
+	carry += vli_add(result, result, tmp, ndigits);
+
+	/* s7 */
+	tmp[0] = ECC_SET_S(product, 12, 23);
+	tmp[1] = ECC_SET_S(product, 14, 13);
+	tmp[2] = ECC_SET_S(product, 16, 15);
+	tmp[3] = ECC_SET_S(product, 18, 17);
+	tmp[4] = ECC_SET_S(product, 20, 19);
+	tmp[5] = ECC_SET_S(product, 22, 21);
+	carry -= vli_sub(result, result, tmp, ndigits);
+
+	/* s8 */
+	tmp[0] = ECC_SET_S(product, 20, -1);
+	tmp[1] = ECC_SET_S(product, 22, 21);
+	tmp[2] = ECC_SET_S(product, -1, 23);
+	tmp[3] = 0;
+	tmp[4] = 0;
+	tmp[5] = 0;
+	carry -= vli_sub(result, result, tmp, ndigits);
+
+	/* s9 */
+	tmp[0] = 0;
+	tmp[1] = ECC_SET_S(product, 23, -1);
+	tmp[2] = ECC_SET_S(product, -1, 23);
+	tmp[3] = 0;
+	tmp[4] = 0;
+	tmp[5] = 0;
+	carry -= vli_sub(result, result, tmp, ndigits);
+
+	if (carry < 0) {
+		do {
+			carry += vli_add(result, result, curve_prime, ndigits);
+		} while (carry < 0);
+	} else {
+		while (carry || _vli_cmp(curve_prime, result, ndigits) != 1)
+			carry -= vli_sub(result, result, curve_prime, ndigits);
+	}
+}
+
 /* Computes result = product % curve_prime
  *  from http://www.nsa.gov/ia/_files/nist-routines.pdf
 */
@@ -471,6 +597,9 @@ static bool vli_mmod_fast(uint64_t *result, uint64_t *product,
 	case 4:
 		vli_mmod_fast_256(result, product, curve_prime, tmp);
 		break;
+	case 6:
+		vli_mmod_fast_384(result, product, curve_prime, tmp);
+		break;
 	default:
 		return false;
 	}
-- 
2.17.1

[PATCH 2/3] ecc: added P384 curve definition

[James Prestwood]

[-- Attachment #1: Type: text/plain, Size: 1916 bytes --]

---
 ell/ecc.c | 30 ++++++++++++++++++++++++++++++
 ell/ecc.h |  2 +-
 2 files changed, 31 insertions(+), 1 deletion(-)

diff --git a/ell/ecc.c b/ell/ecc.c
index 05e2098..9421cd7 100644
--- a/ell/ecc.c
+++ b/ell/ecc.c
@@ -36,8 +36,38 @@ static struct l_ecc_curve p256 = {
 	.b = P256_CURVE_B,
 };
 
+#define P384_CURVE_P {	0x00000000FFFFFFFFull, 0xFFFFFFFF00000000ull, \
+			0xFFFFFFFFFFFFFFFEull, 0xFFFFFFFFFFFFFFFFull, \
+			0xFFFFFFFFFFFFFFFFull, 0xFFFFFFFFFFFFFFFFull }
+#define P384_CURVE_GX {	0x3A545E3872760AB7ull, 0x5502F25DBF55296Cull, \
+			0x59F741E082542A38ull, 0x6E1D3B628BA79B98ull, \
+			0x8EB1C71EF320AD74ull, 0xAA87CA22BE8B0537ull }
+#define P384_CURVE_GY {	0x7A431D7C90EA0E5Full, 0x0A60B1CE1D7E819Dull, \
+			0xE9DA3113B5F0B8C0ull, 0xF8F41DBD289A147Cull, \
+			0x5D9E98BF9292DC29ull, 0x3617DE4A96262C6Full }
+#define P384_CURVE_N {	0xECEC196ACCC52973ull, 0x581A0DB248B0A77Aull, \
+			0xC7634D81F4372DDFull, 0xFFFFFFFFFFFFFFFFull, \
+			0xFFFFFFFFFFFFFFFFull, 0xFFFFFFFFFFFFFFFFull }
+#define P384_CURVE_B {	0x2A85C8EDD3EC2AEFull, 0xC656398D8A2ED19Dull, \
+			0x0314088F5013875Aull, 0x181D9C6EFE814112ull, \
+			0x988E056BE3F82D19ull, 0xB3312FA7E23EE7E4ull }
+
+static struct l_ecc_curve p384 = {
+	.group = 20,
+	.ndigits = 6,
+	.g = {
+		.x = P384_CURVE_GX,
+		.y = P384_CURVE_GY,
+		.curve = &p384
+	},
+	.p = P384_CURVE_P,
+	.n = P384_CURVE_N,
+	.b = P384_CURVE_B
+};
+
 static struct l_ecc_curve *curves[] = {
 	&p256,
+	&p384,
 };
 
 LIB_EXPORT const struct l_ecc_curve *l_ecc_curve_get(unsigned int group)
diff --git a/ell/ecc.h b/ell/ecc.h
index 2d207af..40c7d47 100644
--- a/ell/ecc.h
+++ b/ell/ecc.h
@@ -27,7 +27,7 @@
 extern "C" {
 #endif
 
-#define L_ECC_MAX_DIGITS 4
+#define L_ECC_MAX_DIGITS 6
 #define L_ECC_SCALAR_MAX_BYTES		L_ECC_MAX_DIGITS * 8
 #define L_ECC_POINT_MAX_BYTES		L_ECC_SCALAR_MAX_BYTES * 2
 
-- 
2.17.1

[PATCH 3/3] unit: added P384 unit tests

[James Prestwood]

[-- Attachment #1: Type: text/plain, Size: 3201 bytes --]

---
 unit/test-ecdh.c | 66 ++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 66 insertions(+)

diff --git a/unit/test-ecdh.c b/unit/test-ecdh.c
index 3f9e949..cc0f3a8 100644
--- a/unit/test-ecdh.c
+++ b/unit/test-ecdh.c
@@ -148,6 +148,71 @@ static void test_vector_p256(const void *data)
 	l_ecc_scalar_free(b_shared);
 }
 
+/*
+ * Test vector from RFC 5114 - 384-bit Random ECP Group
+ */
+static void test_vector_p384(const void *data)
+{
+	const struct l_ecc_curve *curve = l_ecc_curve_get(20);
+
+	uint64_t a_sec_buf[6] = { 0x86F05FEADB9376F1ull, 0xD706A90CBCB5DF29ull,
+				0xD709EE7A7962A156ull, 0x5DFD8A7965571C48ull,
+				0x44DD14E9FD126071ull, 0xD27335EA71664AF2ull };
+	uint64_t a_pub_buf[12] = { 0x7D016FE27A8B8C66ull, 0x7E6A8EA9D1FD7742ull,
+				0x0EE6B0403D627954ull, 0xE057AB62F82054D1ull,
+				0xDA4C6D9074417D05ull, 0x793148F1787634D5ull,
+				0xBACED214A1A1D128ull, 0x8F7A685923DE3B67ull,
+				0x6B8F398BB29E4236ull, 0xC947392E94F4C3F0ull,
+				0xF480F4FB4CD40504ull, 0xC6C41294331D23E6ull };
+	uint64_t b_sec_buf[6] = { 0x2C4A6C768BCD94D2ull, 0x9BE52E00C194A413ull,
+				0x1F80231121CCE3D3ull, 0x3B6125262C36A7DFull,
+				0x9C0F00D456C2F702ull, 0x52D1791FDB4B70F8ull };
+	uint64_t b_pub_buf[12] = { 0x223F12B5A1ABC120ull, 0x789D72A84865AE2Full,
+				0x4ABC17647B6B9999ull, 0x5B36DB65915359B4ull,
+				0xF74B8D4EFB708B3Dull, 0x5CD42AB9C41B5347ull,
+				0xE035B0EDF36755DEull, 0x40BDE8723415A8ECull,
+				0x0CECA16356CA9332ull, 0x8F6D5B348C0FA4D8ull,
+				0xA3A8BFAC46B404BDull, 0xE171458FEAA939AAull };
+	uint64_t ss_buf[6] = {
+				0xDE159A58028ABC0Eull, 0x27AA8A4540884C37ull,
+				0x59D926EB1B8456E4ull, 0xCAE53160137D904Cull,
+				0x55981B110575E0A8ull, 0x5EA1FC4AF7256D20ull };
+	struct l_ecc_scalar *a_shared;
+	struct l_ecc_scalar *b_shared;
+
+	struct l_ecc_scalar *a_secret = _ecc_constant_new(curve, a_sec_buf,
+							sizeof(a_sec_buf));
+	struct l_ecc_point *a_public = l_ecc_point_new(curve);
+
+	struct l_ecc_scalar *b_secret = _ecc_constant_new(curve, b_sec_buf,
+							sizeof(b_sec_buf));
+	struct l_ecc_point *b_public = l_ecc_point_new(curve);
+
+	memcpy(a_public->x, a_pub_buf, 48);
+	memcpy(a_public->y, a_pub_buf + 6, 48);
+	memcpy(b_public->x, b_pub_buf, 48);
+	memcpy(b_public->y, b_pub_buf + 6, 48);
+
+	use_real_getrandom = false;
+
+	assert(l_ecdh_generate_shared_secret(curve, a_secret, b_public,
+						&a_shared));
+	assert(l_ecdh_generate_shared_secret(curve, b_secret, a_public,
+						&b_shared));
+
+	assert(!memcmp(a_shared->c, ss_buf, 48));
+	assert(!memcmp(b_shared->c, ss_buf, 48));
+
+	use_real_getrandom = true;
+
+	l_ecc_scalar_free(a_secret);
+	l_ecc_scalar_free(b_secret);
+	l_ecc_point_free(a_public);
+	l_ecc_point_free(b_public);
+	l_ecc_scalar_free(a_shared);
+	l_ecc_scalar_free(b_shared);
+}
+
 int main(int argc, char *argv[])
 {
 	l_test_init(&argc, &argv);
@@ -156,6 +221,7 @@ int main(int argc, char *argv[])
 		l_test_add("ECDH Basic", test_basic, NULL);
 
 	l_test_add("ECDH test vector P256", test_vector_p256, NULL);
+	l_test_add("ECDH test vector P384", test_vector_p384, NULL);
 
 	return l_test_run();
 }
-- 
2.17.1

Re: [PATCH 0/3] Implement P384 curve

[Denis Kenzior]

[-- Attachment #1: Type: text/plain, Size: 392 bytes --]

Hi James,

On 12/11/2018 06:28 PM, James Prestwood wrote:
> Now that ECC has been merged into ELL we can add the P384 curve definition.
> TLS will eventually use this for some ECDSA cipher suites.
> 
> James Prestwood (3):
>    ecc: implement P384 fast modulus
>    ecc: added P384 curve definition
>    unit: added P384 unit tests
> 

All applied, thanks.

Regards,
-Denis