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

--- 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