6:08 a.m.
IWD had its own implementation for ECC and math operations. Eventually
TLS will indirectly require this (via ECDH) so it made sense to move
everything into ell. Some changes had to be made to the original file
to accomidate the ell style.
The original file (ecc.c) required some changes. The ecc_point type
is now exposed as l_ecc_point. Several vli_ functions were prefixed
with "_" so they could be exposed privately. All ecc functions
that needed to be exposed as library API's were prefixed with l_ecc,
and changed to take a l_ecc_curve object, explained below.
A new type was also added, l_ecc_curve, which holds all the information
for a given curve. Users will call l_curve_get(int group) to get a
supported curve object. This curve object can then be passed to all
l_ecc API's which avoids the need for the user to know any of the
curve parameters (prime, g, n, b, etc.) or vli lengths. Some of these
parameters may still need to be obtained, so several getters were added
as well.
When using any of the l_ecc API's, any vli integers should be
created as a uint64_t array of size L_ECC_MAX_DIGITS. This ensures
that the integer will support all supported curves. L_ECC_MAX_DIGITS
should also be updated if any larger bit size curves are added.
---
Makefile.am | 8 +-
ell/ecc-private.h | 50 ++
ell/ecc.c | 1288 +++++++++++++++++++++++++++++++++++++++++++++
ell/ecc.h | 84 +++
ell/ell.h | 1 +
5 files changed, 1429 insertions(+), 2 deletions(-)
create mode 100644 ell/ecc-private.h
create mode 100644 ell/ecc.c
create mode 100644 ell/ecc.h
diff --git a/Makefile.am b/Makefile.am
index d115360..4e5f01b 100644
--- a/Makefile.am
+++ b/Makefile.am
@@ -49,7 +49,8 @@ pkginclude_HEADERS = ell/ell.h \
ell/dir.h \
ell/net.h \
ell/dhcp.h \
- ell/cert.h
+ ell/cert.h \
+ ell/ecc.h
lib_LTLIBRARIES = ell/libell.la
@@ -112,7 +113,10 @@ ell_libell_la_SOURCES = $(linux_headers) \
ell/dhcp-transport.c \
ell/dhcp-lease.c \
ell/cert.c \
- ell/cert-private.h
+ ell/cert-private.h \
+ ell/ecc-private.h \
+ ell/ecc.h \
+ ell/ecc.c
ell_libell_la_LDFLAGS = -no-undefined \
-Wl,--version-script=$(top_srcdir)/ell/ell.sym \
diff --git a/ell/ecc-private.h b/ell/ecc-private.h
new file mode 100644
index 0000000..7e0c7f8
--- /dev/null
+++ b/ell/ecc-private.h
@@ -0,0 +1,50 @@
+/*
+ *
+ * Embedded Linux library
+ *
+ * Copyright (C) 2018 Intel Corporation. All rights reserved.
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2.1 of the License, or (at your option) any later version.
+ *
+ * This library is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this library; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
+ *
+ */
+
+#include <stdbool.h>
+#include <stdint.h>
+
+struct l_ecc_curve;
+
+void _vli_mod_inv(uint64_t *result, const uint64_t *input, const uint64_t *mod,
+ unsigned int ndigits);
+
+void _vli_mod_sub(uint64_t *result, const uint64_t *left, const uint64_t *right,
+ const uint64_t *curve_prime, unsigned int ndigits);
+
+void _vli_mod_add(uint64_t *result, const uint64_t *left, const uint64_t *right,
+ const uint64_t *curve_prime, unsigned int ndigits);
+
+void _vli_rshift1(uint64_t *vli, unsigned int ndigits);
+
+void _vli_mod_mult_fast(uint64_t *result, const uint64_t *left,
+ const uint64_t *right, const uint64_t *curve_prime,
+ unsigned int ndigits);
+
+void _vli_mod_exp(uint64_t *result, uint64_t *base, uint64_t *exp,
+ const uint64_t *mod, unsigned int ndigits);
+
+int _vli_cmp(const uint64_t *left, const uint64_t *right, unsigned int ndigits);
+
+int _vli_legendre(uint64_t *val, const uint64_t *p, unsigned int ndigits);
+
+bool _ecc_compute_y(struct l_ecc_curve *curve, uint64_t *y, uint64_t *x);
diff --git a/ell/ecc.c b/ell/ecc.c
new file mode 100644
index 0000000..b3ddf30
--- /dev/null
+++ b/ell/ecc.c
@@ -0,0 +1,1288 @@
+/*
+ * Copyright (c) 2013, Kenneth MacKay
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions are
+ * met:
+ * * Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ * * Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+ * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+ * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+ * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
+ * HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+ * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
+ * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+ * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+ * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#ifdef HAVE_CONFIG_H
+#include <config.h>
+#endif
+
+#include <linux/types.h>
+#include <stdint.h>
+#include <stdbool.h>
+
+#include "private.h"
+#include "ecc.h"
+#include "ecc-private.h"
+#include "random.h"
+
+typedef struct {
+ uint64_t m_low;
+ uint64_t m_high;
+} uint128_t;
+
+static void vli_clear(uint64_t *vli, unsigned int ndigits)
+{
+ unsigned int i;
+
+ for (i = 0; i < ndigits; i++)
+ vli[i] = 0;
+}
+
+/* Returns true if vli == 0, false otherwise. */
+static bool vli_is_zero(const uint64_t *vli, unsigned int ndigits)
+{
+ unsigned int i;
+
+ for (i = 0; i < ndigits; i++) {
+ if (vli[i])
+ return false;
+ }
+
+ return true;
+}
+
+/* Returns nonzero if bit bit of vli is set. */
+static uint64_t vli_test_bit(const uint64_t *vli, unsigned int bit)
+{
+ return (vli[bit / 64] & ((uint64_t) 1 << (bit % 64)));
+}
+
+/* Counts the number of 64-bit "digits" in vli. */
+static unsigned int vli_num_digits(const uint64_t *vli, unsigned int ndigits)
+{
+ int i;
+
+ /* Search from the end until we find a non-zero digit.
+ * We do it in reverse because we expect that most digits will
+ * be nonzero.
+ */
+ for (i = ndigits - 1; i >= 0 && vli[i] == 0; i--);
+
+ return (i + 1);
+}
+
+/* Counts the number of bits required for vli. */
+static unsigned int vli_num_bits(const uint64_t *vli, unsigned int ndigits)
+{
+ unsigned int i, num_digits;
+ uint64_t digit;
+
+ num_digits = vli_num_digits(vli, ndigits);
+ if (num_digits == 0)
+ return 0;
+
+ digit = vli[num_digits - 1];
+ for (i = 0; digit; i++)
+ digit >>= 1;
+
+ return ((num_digits - 1) * 64 + i);
+}
+
+/* Sets dest = src. */
+static void vli_set(uint64_t *dest, const uint64_t *src, unsigned int ndigits)
+{
+ unsigned int i;
+
+ for (i = 0; i < ndigits; i++)
+ dest[i] = src[i];
+}
+
+/* Returns sign of left - right. */
+int _vli_cmp(const uint64_t *left, const uint64_t *right, unsigned int ndigits)
+{
+ int i;
+
+ for (i = ndigits - 1; i >= 0; i--) {
+ if (left[i] > right[i])
+ return 1;
+ else if (left[i] < right[i])
+ return -1;
+ }
+
+ return 0;
+}
+
+/* Computes result = in << c, returning carry. Can modify in place
+ * (if result == in). 0 < shift < 64.
+ */
+static uint64_t vli_lshift(uint64_t *result, const uint64_t *in,
+ unsigned int shift,
+ unsigned int ndigits)
+{
+ uint64_t carry = 0;
+ unsigned int i;
+
+ for (i = 0; i < ndigits; i++) {
+ uint64_t temp = in[i];
+
+ result[i] = (temp << shift) | carry;
+ carry = temp >> (64 - shift);
+ }
+
+ return carry;
+}
+
+/* Computes vli = vli >> 1. */
+void _vli_rshift1(uint64_t *vli, unsigned int ndigits)
+{
+ uint64_t *end = vli;
+ uint64_t carry = 0;
+
+ vli += ndigits;
+
+ while (vli-- > end) {
+ uint64_t temp = *vli;
+ *vli = (temp >> 1) | carry;
+ carry = temp << 63;
+ }
+}
+
+/* Computes result = left + right, returning carry. Can modify in place. */
+static uint64_t vli_add(uint64_t *result, const uint64_t *left,
+ const uint64_t *right,
+ unsigned int ndigits)
+{
+ uint64_t carry = 0;
+ unsigned int i;
+
+ for (i = 0; i < ndigits; i++) {
+ uint64_t sum;
+
+ sum = left[i] + right[i] + carry;
+ if (sum != left[i])
+ carry = (sum < left[i]);
+
+ result[i] = sum;
+ }
+
+ return carry;
+}
+
+/* Computes result = left - right, returning borrow. Can modify in place. */
+static uint64_t vli_sub(uint64_t *result, const uint64_t *left,
+ const uint64_t *right,
+ unsigned int ndigits)
+{
+ uint64_t borrow = 0;
+ unsigned int i;
+
+ for (i = 0; i < ndigits; i++) {
+ uint64_t diff;
+
+ diff = left[i] - right[i] - borrow;
+ if (diff != left[i])
+ borrow = (diff > left[i]);
+
+ result[i] = diff;
+ }
+
+ return borrow;
+}
+
+static uint128_t mul_64_64(uint64_t left, uint64_t right)
+{
+ uint64_t a0 = left & 0xffffffffull;
+ uint64_t a1 = left >> 32;
+ uint64_t b0 = right & 0xffffffffull;
+ uint64_t b1 = right >> 32;
+ uint64_t m0 = a0 * b0;
+ uint64_t m1 = a0 * b1;
+ uint64_t m2 = a1 * b0;
+ uint64_t m3 = a1 * b1;
+ uint128_t result;
+
+ m2 += (m0 >> 32);
+ m2 += m1;
+
+ /* Overflow */
+ if (m2 < m1)
+ m3 += 0x100000000ull;
+
+ result.m_low = (m0 & 0xffffffffull) | (m2 << 32);
+ result.m_high = m3 + (m2 >> 32);
+
+ return result;
+}
+
+static uint128_t add_128_128(uint128_t a, uint128_t b)
+{
+ uint128_t result;
+
+ result.m_low = a.m_low + b.m_low;
+ result.m_high = a.m_high + b.m_high + (result.m_low < a.m_low);
+
+ return result;
+}
+
+static void vli_mult(uint64_t *result, const uint64_t *left,
+ const uint64_t *right,
+ unsigned int ndigits)
+{
+ uint128_t r01 = { 0, 0 };
+ uint64_t r2 = 0;
+ unsigned int i, k;
+
+ /* Compute each digit of result in sequence, maintaining the
+ * carries.
+ */
+ for (k = 0; k < ndigits * 2 - 1; k++) {
+ unsigned int min;
+
+ if (k < ndigits)
+ min = 0;
+ else
+ min = (k + 1) - ndigits;
+
+ for (i = min; i <= k && i < ndigits; i++) {
+ uint128_t product;
+
+ product = mul_64_64(left[i], right[k - i]);
+
+ r01 = add_128_128(r01, product);
+ r2 += (r01.m_high < product.m_high);
+ }
+
+ result[k] = r01.m_low;
+ r01.m_low = r01.m_high;
+ r01.m_high = r2;
+ r2 = 0;
+ }
+
+ result[ndigits * 2 - 1] = r01.m_low;
+}
+
+static void vli_square(uint64_t *result, const uint64_t *left,
+ unsigned int ndigits)
+{
+ uint128_t r01 = { 0, 0 };
+ uint64_t r2 = 0;
+ unsigned int i, k;
+
+ for (k = 0; k < ndigits * 2 - 1; k++) {
+ unsigned int min;
+
+ if (k < ndigits)
+ min = 0;
+ else
+ min = (k + 1) - ndigits;
+
+ for (i = min; i <= k && i <= k - i; i++) {
+ uint128_t product;
+
+ product = mul_64_64(left[i], left[k - i]);
+
+ if (i < k - i) {
+ r2 += product.m_high >> 63;
+ product.m_high = (product.m_high << 1) |
+ (product.m_low >> 63);
+ product.m_low <<= 1;
+ }
+
+ r01 = add_128_128(r01, product);
+ r2 += (r01.m_high < product.m_high);
+ }
+
+ result[k] = r01.m_low;
+ r01.m_low = r01.m_high;
+ r01.m_high = r2;
+ r2 = 0;
+ }
+
+ result[ndigits * 2 - 1] = r01.m_low;
+}
+
+/* Computes result = (left + right) % mod.
+ * Assumes that left < mod and right < mod, result != mod.
+ */
+void _vli_mod_add(uint64_t *result, const uint64_t *left,
+ const uint64_t *right, const uint64_t *mod,
+ unsigned int ndigits)
+{
+ uint64_t carry;
+
+ carry = vli_add(result, left, right, ndigits);
+
+ /* result > mod (result = mod + remainder), so subtract mod to
+ * get remainder.
+ */
+ if (carry || _vli_cmp(result, mod, ndigits) >= 0)
+ vli_sub(result, result, mod, ndigits);
+}
+
+/* Computes result = (left - right) % mod.
+ * Assumes that left < mod and right < mod, result != mod.
+ */
+void _vli_mod_sub(uint64_t *result, const uint64_t *left,
+ const uint64_t *right, const uint64_t *mod,
+ unsigned int ndigits)
+{
+ uint64_t borrow = vli_sub(result, left, right, ndigits);
+
+ /* In this case, p_result == -diff == (max int) - diff.
+ * Since -x % d == d - x, we can get the correct result from
+ * result + mod (with overflow).
+ */
+ if (borrow)
+ vli_add(result, result, mod, ndigits);
+}
+
+/* Computes p_result = p_product % curve_p.
+ * See algorithm 5 and 6 from
+ * http://www.isys.uni-klu.ac.at/PDF/2001-0126-MT.pdf
+ */
+static void vli_mmod_fast_192(uint64_t *result, const uint64_t *product,
+ const uint64_t *curve_prime, uint64_t *tmp)
+{
+ const unsigned int ndigits = 3;
+ int carry;
+
+ vli_set(result, product, ndigits);
+
+ vli_set(tmp, &product[3], ndigits);
+ carry = vli_add(result, result, tmp, ndigits);
+
+ tmp[0] = 0;
+ tmp[1] = product[3];
+ tmp[2] = product[4];
+ carry += vli_add(result, result, tmp, ndigits);
+
+ tmp[0] = tmp[1] = product[5];
+ tmp[2] = 0;
+ carry += vli_add(result, result, tmp, ndigits);
+
+ 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
+ */
+static void vli_mmod_fast_256(uint64_t *result, const uint64_t *product,
+ const uint64_t *curve_prime, uint64_t *tmp)
+{
+ int carry;
+ const unsigned int ndigits = 4;
+
+ /* t */
+ vli_set(result, product, ndigits);
+
+ /* s1 */
+ tmp[0] = 0;
+ tmp[1] = product[5] & 0xffffffff00000000ull;
+ tmp[2] = product[6];
+ tmp[3] = product[7];
+ carry = vli_lshift(tmp, tmp, 1, ndigits);
+ carry += vli_add(result, result, tmp, ndigits);
+
+ /* s2 */
+ tmp[1] = product[6] << 32;
+ tmp[2] = (product[6] >> 32) | (product[7] << 32);
+ tmp[3] = product[7] >> 32;
+ carry += vli_lshift(tmp, tmp, 1, ndigits);
+ carry += vli_add(result, result, tmp, ndigits);
+
+ /* s3 */
+ tmp[0] = product[4];
+ tmp[1] = product[5] & 0xffffffff;
+ tmp[2] = 0;
+ tmp[3] = product[7];
+ carry += vli_add(result, result, tmp, ndigits);
+
+ /* s4 */
+ tmp[0] = (product[4] >> 32) | (product[5] << 32);
+ tmp[1] = (product[5] >> 32) | (product[6] & 0xffffffff00000000ull);
+ tmp[2] = product[7];
+ tmp[3] = (product[6] >> 32) | (product[4] << 32);
+ carry += vli_add(result, result, tmp, ndigits);
+
+ /* d1 */
+ tmp[0] = (product[5] >> 32) | (product[6] << 32);
+ tmp[1] = (product[6] >> 32);
+ tmp[2] = 0;
+ tmp[3] = (product[4] & 0xffffffff) | (product[5] << 32);
+ carry -= vli_sub(result, result, tmp, ndigits);
+
+ /* d2 */
+ tmp[0] = product[6];
+ tmp[1] = product[7];
+ tmp[2] = 0;
+ tmp[3] = (product[4] >> 32) | (product[5] & 0xffffffff00000000ull);
+ carry -= vli_sub(result, result, tmp, ndigits);
+
+ /* d3 */
+ tmp[0] = (product[6] >> 32) | (product[7] << 32);
+ tmp[1] = (product[7] >> 32) | (product[4] << 32);
+ tmp[2] = (product[4] >> 32) | (product[5] << 32);
+ tmp[3] = (product[6] << 32);
+ carry -= vli_sub(result, result, tmp, ndigits);
+
+ /* d4 */
+ tmp[0] = product[7];
+ tmp[1] = product[4] & 0xffffffff00000000ull;
+ tmp[2] = product[5];
+ tmp[3] = product[6] & 0xffffffff00000000ull;
+ 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
+*/
+static bool vli_mmod_fast(uint64_t *result, uint64_t *product,
+ const uint64_t *curve_prime,
+ unsigned int ndigits)
+{
+ uint64_t tmp[2 * L_ECC_MAX_DIGITS];
+
+ switch (ndigits) {
+ case 3:
+ vli_mmod_fast_192(result, product, curve_prime, tmp);
+ break;
+ case 4:
+ vli_mmod_fast_256(result, product, curve_prime, tmp);
+ break;
+ default:
+ return false;
+ }
+
+ return true;
+}
+
+/* Computes result = (left * right) % curve_p. */
+void _vli_mod_mult_fast(uint64_t *result, const uint64_t *left,
+ const uint64_t *right, const uint64_t *curve_prime,
+ unsigned int ndigits)
+{
+ uint64_t product[2 * L_ECC_MAX_DIGITS];
+
+ vli_mult(product, left, right, ndigits);
+ vli_mmod_fast(result, product, curve_prime, ndigits);
+}
+
+/* Computes result = left^2 % curve_p. */
+static void vli_mod_square_fast(uint64_t *result, const uint64_t *left,
+ const uint64_t *curve_prime,
+ unsigned int ndigits)
+{
+ uint64_t product[2 * L_ECC_MAX_DIGITS];
+
+ vli_square(product, left, ndigits);
+ vli_mmod_fast(result, product, curve_prime, ndigits);
+}
+
+#define EVEN(vli) (!(vli[0] & 1))
+/* Computes result = (1 / p_input) % mod. All VLIs are the same size.
+ * See "From Euclid's GCD to Montgomery Multiplication to the Great
Divide"
+ * https://labs.oracle.com/techrep/2001/smli_tr-2001-95.pdf
+ */
+void _vli_mod_inv(uint64_t *result, const uint64_t *input,
+ const uint64_t *mod,
+ unsigned int ndigits)
+{
+ uint64_t a[L_ECC_MAX_DIGITS], b[L_ECC_MAX_DIGITS];
+ uint64_t u[L_ECC_MAX_DIGITS], v[L_ECC_MAX_DIGITS];
+ uint64_t carry;
+ int cmp_result;
+
+ if (vli_is_zero(input, ndigits)) {
+ vli_clear(result, ndigits);
+ return;
+ }
+
+ vli_set(a, input, ndigits);
+ vli_set(b, mod, ndigits);
+ vli_clear(u, ndigits);
+ u[0] = 1;
+ vli_clear(v, ndigits);
+
+ while ((cmp_result = _vli_cmp(a, b, ndigits)) != 0) {
+ carry = 0;
+
+ if (EVEN(a)) {
+ _vli_rshift1(a, ndigits);
+
+ if (!EVEN(u))
+ carry = vli_add(u, u, mod, ndigits);
+
+ _vli_rshift1(u, ndigits);
+ if (carry)
+ u[ndigits - 1] |= 0x8000000000000000ull;
+ } else if (EVEN(b)) {
+ _vli_rshift1(b, ndigits);
+
+ if (!EVEN(v))
+ carry = vli_add(v, v, mod, ndigits);
+
+ _vli_rshift1(v, ndigits);
+ if (carry)
+ v[ndigits - 1] |= 0x8000000000000000ull;
+ } else if (cmp_result > 0) {
+ vli_sub(a, a, b, ndigits);
+ _vli_rshift1(a, ndigits);
+
+ if (_vli_cmp(u, v, ndigits) < 0)
+ vli_add(u, u, mod, ndigits);
+
+ vli_sub(u, u, v, ndigits);
+ if (!EVEN(u))
+ carry = vli_add(u, u, mod, ndigits);
+
+ _vli_rshift1(u, ndigits);
+ if (carry)
+ u[ndigits - 1] |= 0x8000000000000000ull;
+ } else {
+ vli_sub(b, b, a, ndigits);
+ _vli_rshift1(b, ndigits);
+
+ if (_vli_cmp(v, u, ndigits) < 0)
+ vli_add(v, v, mod, ndigits);
+
+ vli_sub(v, v, u, ndigits);
+ if (!EVEN(v))
+ carry = vli_add(v, v, mod, ndigits);
+
+ _vli_rshift1(v, ndigits);
+ if (carry)
+ v[ndigits - 1] |= 0x8000000000000000ull;
+ }
+ }
+
+ vli_set(result, u, ndigits);
+}
+
+/* ------ Point operations ------ */
+
+/* Point multiplication algorithm using Montgomery's ladder with co-Z
+ * coordinates. From http://eprint.iacr.org/2011/338.pdf
+ */
+
+/* Double in place */
+static void ecc_point_double_jacobian(uint64_t *x1, uint64_t *y1, uint64_t *z1,
+ const uint64_t *curve_prime,
+ unsigned int ndigits)
+{
+ /* t1 = x, t2 = y, t3 = z */
+ uint64_t t4[L_ECC_MAX_DIGITS];
+ uint64_t t5[L_ECC_MAX_DIGITS];
+
+ if (vli_is_zero(z1, ndigits))
+ return;
+
+ /* t4 = y1^2 */
+ vli_mod_square_fast(t4, y1, curve_prime, ndigits);
+ /* t5 = x1*y1^2 = A */
+ _vli_mod_mult_fast(t5, x1, t4, curve_prime, ndigits);
+ /* t4 = y1^4 */
+ vli_mod_square_fast(t4, t4, curve_prime, ndigits);
+ /* t2 = y1*z1 = z3 */
+ _vli_mod_mult_fast(y1, y1, z1, curve_prime, ndigits);
+ /* t3 = z1^2 */
+ vli_mod_square_fast(z1, z1, curve_prime, ndigits);
+
+ /* t1 = x1 + z1^2 */
+ _vli_mod_add(x1, x1, z1, curve_prime, ndigits);
+ /* t3 = 2*z1^2 */
+ _vli_mod_add(z1, z1, z1, curve_prime, ndigits);
+ /* t3 = x1 - z1^2 */
+ _vli_mod_sub(z1, x1, z1, curve_prime, ndigits);
+ /* t1 = x1^2 - z1^4 */
+ _vli_mod_mult_fast(x1, x1, z1, curve_prime, ndigits);
+
+ /* t3 = 2*(x1^2 - z1^4) */
+ _vli_mod_add(z1, x1, x1, curve_prime, ndigits);
+ /* t1 = 3*(x1^2 - z1^4) */
+ _vli_mod_add(x1, x1, z1, curve_prime, ndigits);
+ if (vli_test_bit(x1, 0)) {
+ uint64_t carry = vli_add(x1, x1, curve_prime, ndigits);
+ _vli_rshift1(x1, ndigits);
+ x1[ndigits - 1] |= carry << 63;
+ } else {
+ _vli_rshift1(x1, ndigits);
+ }
+ /* t1 = 3/2*(x1^2 - z1^4) = B */
+
+ /* t3 = B^2 */
+ vli_mod_square_fast(z1, x1, curve_prime, ndigits);
+ /* t3 = B^2 - A */
+ _vli_mod_sub(z1, z1, t5, curve_prime, ndigits);
+ /* t3 = B^2 - 2A = x3 */
+ _vli_mod_sub(z1, z1, t5, curve_prime, ndigits);
+ /* t5 = A - x3 */
+ _vli_mod_sub(t5, t5, z1, curve_prime, ndigits);
+ /* t1 = B * (A - x3) */
+ _vli_mod_mult_fast(x1, x1, t5, curve_prime, ndigits);
+ /* t4 = B * (A - x3) - y1^4 = y3 */
+ _vli_mod_sub(t4, x1, t4, curve_prime, ndigits);
+
+ vli_set(x1, z1, ndigits);
+ vli_set(z1, y1, ndigits);
+ vli_set(y1, t4, ndigits);
+}
+
+/* Modify (x1, y1) => (x1 * z^2, y1 * z^3) */
+static void apply_z(uint64_t *x1, uint64_t *y1, uint64_t *z,
+ const uint64_t *curve_prime, unsigned int ndigits)
+{
+ uint64_t t1[L_ECC_MAX_DIGITS];
+
+ vli_mod_square_fast(t1, z, curve_prime, ndigits); /* z^2 */
+ _vli_mod_mult_fast(x1, x1, t1, curve_prime, ndigits); /* x1 * z^2 */
+ _vli_mod_mult_fast(t1, t1, z, curve_prime, ndigits); /* z^3 */
+ _vli_mod_mult_fast(y1, y1, t1, curve_prime, ndigits); /* y1 * z^3 */
+}
+
+/* P = (x1, y1) => 2P, (x2, y2) => P' */
+static void xycz_initial_double(uint64_t *x1, uint64_t *y1, uint64_t *x2,
+ uint64_t *y2, uint64_t *p_initial_z,
+ const uint64_t *curve_prime,
+ unsigned int ndigits)
+{
+ uint64_t z[L_ECC_MAX_DIGITS];
+
+ vli_set(x2, x1, ndigits);
+ vli_set(y2, y1, ndigits);
+
+ vli_clear(z, ndigits);
+ z[0] = 1;
+
+ if (p_initial_z)
+ vli_set(z, p_initial_z, ndigits);
+
+ apply_z(x1, y1, z, curve_prime, ndigits);
+
+ ecc_point_double_jacobian(x1, y1, z, curve_prime, ndigits);
+
+ apply_z(x2, y2, z, curve_prime, ndigits);
+}
+
+/* Input P = (x1, y1, Z), Q = (x2, y2, Z)
+ * Output P' = (x1', y1', Z3), P + Q = (x3, y3, Z3)
+ * or P => P', Q => P + Q
+ */
+static void xycz_add(uint64_t *x1, uint64_t *y1, uint64_t *x2, uint64_t *y2,
+ const uint64_t *curve_prime, unsigned int ndigits)
+{
+ /* t1 = X1, t2 = Y1, t3 = X2, t4 = Y2 */
+ uint64_t t5[L_ECC_MAX_DIGITS];
+
+ /* t5 = x2 - x1 */
+ _vli_mod_sub(t5, x2, x1, curve_prime, ndigits);
+ /* t5 = (x2 - x1)^2 = A */
+ vli_mod_square_fast(t5, t5, curve_prime, ndigits);
+ /* t1 = x1*A = B */
+ _vli_mod_mult_fast(x1, x1, t5, curve_prime, ndigits);
+ /* t3 = x2*A = C */
+ _vli_mod_mult_fast(x2, x2, t5, curve_prime, ndigits);
+ /* t4 = y2 - y1 */
+ _vli_mod_sub(y2, y2, y1, curve_prime, ndigits);
+ /* t5 = (y2 - y1)^2 = D */
+ vli_mod_square_fast(t5, y2, curve_prime, ndigits);
+
+ /* t5 = D - B */
+ _vli_mod_sub(t5, t5, x1, curve_prime, ndigits);
+ /* t5 = D - B - C = x3 */
+ _vli_mod_sub(t5, t5, x2, curve_prime, ndigits);
+ /* t3 = C - B */
+ _vli_mod_sub(x2, x2, x1, curve_prime, ndigits);
+ /* t2 = y1*(C - B) */
+ _vli_mod_mult_fast(y1, y1, x2, curve_prime, ndigits);
+ /* t3 = B - x3 */
+ _vli_mod_sub(x2, x1, t5, curve_prime, ndigits);
+ /* t4 = (y2 - y1)*(B - x3) */
+ _vli_mod_mult_fast(y2, y2, x2, curve_prime, ndigits);
+ /* t4 = y3 */
+ _vli_mod_sub(y2, y2, y1, curve_prime, ndigits);
+
+ vli_set(x2, t5, ndigits);
+}
+
+/* Input P = (x1, y1, Z), Q = (x2, y2, Z)
+ * Output P + Q = (x3, y3, Z3), P - Q = (x3', y3', Z3)
+ * or P => P - Q, Q => P + Q
+ */
+static void xycz_add_c(uint64_t *x1, uint64_t *y1, uint64_t *x2, uint64_t *y2,
+ const uint64_t *curve_prime, unsigned int ndigits)
+{
+ /* t1 = X1, t2 = Y1, t3 = X2, t4 = Y2 */
+ uint64_t t5[L_ECC_MAX_DIGITS];
+ uint64_t t6[L_ECC_MAX_DIGITS];
+ uint64_t t7[L_ECC_MAX_DIGITS];
+
+ /* t5 = x2 - x1 */
+ _vli_mod_sub(t5, x2, x1, curve_prime, ndigits);
+ /* t5 = (x2 - x1)^2 = A */
+ vli_mod_square_fast(t5, t5, curve_prime, ndigits);
+ /* t1 = x1*A = B */
+ _vli_mod_mult_fast(x1, x1, t5, curve_prime, ndigits);
+ /* t3 = x2*A = C */
+ _vli_mod_mult_fast(x2, x2, t5, curve_prime, ndigits);
+ /* t4 = y2 + y1 */
+ _vli_mod_add(t5, y2, y1, curve_prime, ndigits);
+ /* t4 = y2 - y1 */
+ _vli_mod_sub(y2, y2, y1, curve_prime, ndigits);
+
+ /* t6 = C - B */
+ _vli_mod_sub(t6, x2, x1, curve_prime, ndigits);
+ /* t2 = y1 * (C - B) */
+ _vli_mod_mult_fast(y1, y1, t6, curve_prime, ndigits);
+ /* t6 = B + C */
+ _vli_mod_add(t6, x1, x2, curve_prime, ndigits);
+ /* t3 = (y2 - y1)^2 */
+ vli_mod_square_fast(x2, y2, curve_prime, ndigits);
+ /* t3 = x3 */
+ _vli_mod_sub(x2, x2, t6, curve_prime, ndigits);
+
+ /* t7 = B - x3 */
+ _vli_mod_sub(t7, x1, x2, curve_prime, ndigits);
+ /* t4 = (y2 - y1)*(B - x3) */
+ _vli_mod_mult_fast(y2, y2, t7, curve_prime, ndigits);
+ /* t4 = y3 */
+ _vli_mod_sub(y2, y2, y1, curve_prime, ndigits);
+
+ /* t7 = (y2 + y1)^2 = F */
+ vli_mod_square_fast(t7, t5, curve_prime, ndigits);
+ /* t7 = x3' */
+ _vli_mod_sub(t7, t7, t6, curve_prime, ndigits);
+ /* t6 = x3' - B */
+ _vli_mod_sub(t6, t7, x1, curve_prime, ndigits);
+ /* t6 = (y2 + y1)*(x3' - B) */
+ _vli_mod_mult_fast(t6, t6, t5, curve_prime, ndigits);
+ /* t2 = y3' */
+ _vli_mod_sub(y1, t6, y1, curve_prime, ndigits);
+
+ vli_set(x1, t7, ndigits);
+}
+
+static void ecc_point_mult(struct l_ecc_point *result,
+ const struct l_ecc_point *point, const uint64_t *scalar,
+ uint64_t *initial_z, const uint64_t *curve_prime)
+{
+ /* R0 and R1 */
+ uint64_t rx[2][L_ECC_MAX_DIGITS];
+ uint64_t ry[2][L_ECC_MAX_DIGITS];
+ uint64_t z[L_ECC_MAX_DIGITS];
+ int i, nb;
+ unsigned int ndigits = point->ndigits;
+ int num_bits = vli_num_bits(scalar, ndigits);
+
+ vli_set(rx[1], point->x, ndigits);
+ vli_set(ry[1], point->y, ndigits);
+
+ xycz_initial_double(rx[1], ry[1], rx[0], ry[0], initial_z, curve_prime,
+ ndigits);
+
+ for (i = num_bits - 2; i > 0; i--) {
+ nb = !vli_test_bit(scalar, i);
+ xycz_add_c(rx[1 - nb], ry[1 - nb], rx[nb], ry[nb], curve_prime,
+ ndigits);
+ xycz_add(rx[nb], ry[nb], rx[1 - nb], ry[1 - nb], curve_prime,
+ ndigits);
+ }
+
+ nb = !vli_test_bit(scalar, 0);
+ xycz_add_c(rx[1 - nb], ry[1 - nb], rx[nb], ry[nb], curve_prime,
+ ndigits);
+
+ /* Find final 1/Z value. */
+ /* X1 - X0 */
+ _vli_mod_sub(z, rx[1], rx[0], curve_prime, ndigits);
+ /* Yb * (X1 - X0) */
+ _vli_mod_mult_fast(z, z, ry[1 - nb], curve_prime, ndigits);
+ /* xP * Yb * (X1 - X0) */
+ _vli_mod_mult_fast(z, z, point->x, curve_prime, ndigits);
+
+ /* 1 / (xP * Yb * (X1 - X0)) */
+ _vli_mod_inv(z, z, curve_prime, point->ndigits);
+
+ /* yP / (xP * Yb * (X1 - X0)) */
+ _vli_mod_mult_fast(z, z, point->y, curve_prime, ndigits);
+ /* Xb * yP / (xP * Yb * (X1 - X0)) */
+ _vli_mod_mult_fast(z, z, rx[1 - nb], curve_prime, ndigits);
+ /* End 1/Z calculation */
+
+ xycz_add(rx[nb], ry[nb], rx[1 - nb], ry[1 - nb], curve_prime, ndigits);
+
+ apply_z(rx[0], ry[0], z, curve_prime, ndigits);
+
+ vli_set(result->x, rx[0], ndigits);
+ vli_set(result->y, ry[0], ndigits);
+}
+
+/*
+ * The code below was not in the original file and was added to support
+ * additional ECC operations. The above ECC implementation did not include
+ * functionality for point addition or the ability to solve for Y value given
+ * some X.
+ */
+
+struct l_ecc_curve {
+ unsigned int ndigits;
+ unsigned int group;
+ struct l_ecc_point g;
+ uint64_t p[L_ECC_MAX_DIGITS];
+ uint64_t n[L_ECC_MAX_DIGITS];
+ uint64_t b[L_ECC_MAX_DIGITS];
+};
+
+#define P256_CURVE_P { 0xFFFFFFFFFFFFFFFFull, 0x00000000FFFFFFFFull, \
+ 0x0000000000000000ull, 0xFFFFFFFF00000001ull }
+#define P256_CURVE_GX { 0xF4A13945D898C296ull, 0x77037D812DEB33A0ull, \
+ 0xF8BCE6E563A440F2ull, 0x6B17D1F2E12C4247ull }
+#define P256_CURVE_GY { 0xCBB6406837BF51F5ull, 0x2BCE33576B315ECEull, \
+ 0x8EE7EB4A7C0F9E16ull, 0x4FE342E2FE1A7F9Bull }
+#define P256_CURVE_N { 0xF3B9CAC2FC632551ull, 0xBCE6FAADA7179E84ull, \
+ 0xFFFFFFFFFFFFFFFFull, 0xFFFFFFFF00000000ull }
+#define P256_CURVE_B { 0x3BCE3C3E27D2604Bull, 0x651D06B0CC53B0F6ull, \
+ 0xB3EBBD55769886BCull, 0x5AC635D8AA3A93E7ull }
+
+static struct l_ecc_curve p256 = {
+ .group = 19,
+ .ndigits = 4,
+ .g = {
+ .x = P256_CURVE_GX,
+ .y = P256_CURVE_GY,
+ .ndigits = 4
+ },
+ .p = P256_CURVE_P,
+ .n = P256_CURVE_N,
+ .b = P256_CURVE_B,
+};
+
+static struct l_ecc_curve *curves[] = {
+ &p256,
+};
+
+LIB_EXPORT struct l_ecc_curve *l_ecc_curve_get(unsigned int group)
+{
+ int i;
+
+ for (i = 0; curves[i]; i++) {
+ if (curves[i]->group == group)
+ return curves[i];
+ }
+
+ return NULL;
+}
+
+LIB_EXPORT unsigned int l_ecc_curve_get_ndigits(struct l_ecc_curve *curve)
+{
+ return curve->ndigits;
+}
+
+LIB_EXPORT const uint64_t *l_ecc_curve_get_prime(struct l_ecc_curve *curve)
+{
+ return curve->p;
+}
+
+LIB_EXPORT const uint64_t *l_ecc_curve_get_b(struct l_ecc_curve *curve)
+{
+ return curve->b;
+}
+
+LIB_EXPORT struct l_ecc_point *l_ecc_curve_get_generator(
+ struct l_ecc_curve *curve)
+{
+ return &curve->g;
+}
+
+/* (rx, ry) = (px, py) + (qx, qy) */
+static void ecc_point_add(struct l_ecc_point *ret, struct l_ecc_point *p,
+ struct l_ecc_point *q, const uint64_t *curve_prime)
+{
+ /*
+ * s = (py - qy)/(px - qx)
+ *
+ * rx = s^2 - px - qx
+ * ry = s(px - rx) - py
+ */
+ uint64_t s[L_ECC_MAX_DIGITS];
+ uint64_t kp1[L_ECC_MAX_DIGITS];
+ uint64_t kp2[L_ECC_MAX_DIGITS];
+ uint64_t resx[L_ECC_MAX_DIGITS];
+ uint64_t resy[L_ECC_MAX_DIGITS];
+ unsigned int ndigits = p->ndigits;
+
+ vli_clear(s, ndigits);
+
+ /* kp1 = py - qy */
+ _vli_mod_sub(kp1, q->y, p->y, curve_prime, ndigits);
+ /* kp2 = px - qx */
+ _vli_mod_sub(kp2, q->x, p->x, curve_prime, ndigits);
+ /* s = kp1/kp2 */
+ _vli_mod_inv(kp2, kp2, curve_prime, ndigits);
+ _vli_mod_mult_fast(s, kp1, kp2, curve_prime, ndigits);
+ /* rx = s^2 - px - qx */
+ _vli_mod_mult_fast(kp1, s, s, curve_prime, ndigits);
+ _vli_mod_sub(kp1, kp1, p->x, curve_prime, ndigits);
+ _vli_mod_sub(resx, kp1, q->x, curve_prime, ndigits);
+ /* ry = s(px - rx) - py */
+ _vli_mod_sub(kp1, p->x, resx, curve_prime, ndigits);
+ _vli_mod_mult_fast(kp1, s, kp1, curve_prime, ndigits);
+ _vli_mod_sub(resy, kp1, p->y, curve_prime, ndigits);
+
+ vli_set(ret->x, resx, ndigits);
+ vli_set(ret->y, resy, ndigits);
+}
+
+/* result = (base ^ exp) % p */
+void _vli_mod_exp(uint64_t *result, uint64_t *base, uint64_t *exp,
+ const uint64_t *mod, unsigned int ndigits)
+{
+ unsigned int i;
+ int bit;
+ uint64_t n[L_ECC_MAX_DIGITS];
+ uint64_t r[L_ECC_MAX_DIGITS] = { 1 };
+
+ vli_set(n, base, ndigits);
+
+ for (i = 0; i < ndigits; i++) {
+ for (bit = 0; bit < 64; bit++) {
+ uint64_t tmp[L_ECC_MAX_DIGITS];
+
+ if (exp[i] & (1ull << bit)) {
+ _vli_mod_mult_fast(tmp, r, n, mod, ndigits);
+ vli_set(r, tmp, ndigits);
+ }
+
+ _vli_mod_mult_fast(tmp, n, n, mod, ndigits);
+ vli_set(n, tmp, ndigits);
+ }
+ }
+
+ vli_set(result, r, ndigits);
+}
+
+int _vli_legendre(uint64_t *val, const uint64_t *p, unsigned int ndigits)
+{
+ uint64_t tmp[L_ECC_MAX_DIGITS];
+ uint64_t exp[L_ECC_MAX_DIGITS];
+ uint64_t _1[L_ECC_MAX_DIGITS] = { 1ull };
+ uint64_t _0[L_ECC_MAX_DIGITS] = { 0 };
+
+ /* check that val ^ ((p - 1) / 2) == [1, 0 or -1] */
+
+ vli_sub(exp, p, _1, ndigits);
+ _vli_rshift1(exp, ndigits);
+ _vli_mod_exp(tmp, val, exp, p, ndigits);
+
+ if (_vli_cmp(tmp, _1, ndigits) == 0)
+ return 1;
+ else if (_vli_cmp(tmp, _0, ndigits) == 0)
+ return 0;
+ else
+ return -1;
+}
+
+LIB_EXPORT bool l_ecc_point_multiply(struct l_ecc_curve *curve,
+ struct l_ecc_point *ret,
+ struct l_ecc_point *p, uint64_t *scalar,
+ uint64_t *initial_z)
+{
+ ecc_point_mult(ret, p, scalar, initial_z, curve->p);
+
+ ret->ndigits = curve->ndigits;
+
+ return true;
+}
+
+LIB_EXPORT bool l_ecc_point_add(struct l_ecc_curve *curve,
+ struct l_ecc_point *ret,
+ struct l_ecc_point *p, struct l_ecc_point *q)
+{
+ ecc_point_add(ret, p, q, curve->p);
+
+ ret->ndigits = curve->ndigits;
+
+ return true;
+}
+
+/* Returns true if p_point is the point at infinity, false otherwise. */
+static bool ecc_point_is_zero(const struct l_ecc_point *point)
+{
+ return (vli_is_zero(point->x, point->ndigits) &&
+ vli_is_zero(point->y, point->ndigits));
+}
+
+LIB_EXPORT bool l_ecc_valid_point(struct l_ecc_curve *curve,
+ struct l_ecc_point *point)
+{
+ uint64_t tmp1[L_ECC_MAX_DIGITS];
+ uint64_t tmp2[L_ECC_MAX_DIGITS];
+ uint64_t _3[L_ECC_MAX_DIGITS] = { 3 }; /* -a = 3 */
+ const uint64_t *curve_prime = curve->p;
+ const uint64_t *curve_b = curve->b;
+
+ /* The point at infinity is invalid. */
+ if (ecc_point_is_zero(point))
+ return false;
+
+ /* x and y must be smaller than p. */
+ if (_vli_cmp(curve_prime, point->x, point->ndigits) != 1 ||
+ _vli_cmp(curve_prime, point->y, point->ndigits) != 1)
+ return false;
+
+ /* Computes result = y^2. */
+ vli_mod_square_fast(tmp1, point->y, curve_prime, point->ndigits);
+
+ /* Computes result = x^3 + ax + b. result must not overlap x. */
+ /* r = x^2 */
+ vli_mod_square_fast(tmp2, point->x, curve_prime, point->ndigits);
+ /* r = x^2 - 3 */
+ _vli_mod_sub(tmp2, tmp2, _3, curve_prime, point->ndigits);
+ /* r = x^3 - 3x */
+ _vli_mod_mult_fast(tmp2, tmp2, point->x, curve_prime, point->ndigits);
+ /* r = x^3 - 3x + b */
+ _vli_mod_add(tmp2, tmp2, curve_b, curve_prime, point->ndigits);
+ /* Make sure that y^2 == x^3 + ax + b */
+ return (_vli_cmp(tmp1, tmp2, point->ndigits) == 0);
+}
+
+LIB_EXPORT void l_ecc_be2native(struct l_ecc_curve *curve, uint64_t *dest,
+ uint64_t *bytes)
+{
+ unsigned int i;
+ uint64_t tmp[L_ECC_MAX_DIGITS];
+
+ for (i = 0; i < curve->ndigits; i++)
+ tmp[curve->ndigits - 1 - i] = l_get_be64(&bytes[i]);
+
+ vli_set(dest, tmp, curve->ndigits);
+}
+
+LIB_EXPORT void l_ecc_native2be(struct l_ecc_curve *curve, uint64_t *dest,
+ uint64_t *native)
+{
+ unsigned int i;
+ uint64_t tmp[L_ECC_MAX_DIGITS];
+
+ for (i = 0; i < curve->ndigits; i++)
+ l_put_be64(native[curve->ndigits - 1 - i], &tmp[i]);
+
+ vli_set(dest, tmp, curve->ndigits);
+}
+
+LIB_EXPORT void l_ecc_compute_y_sqr(struct l_ecc_curve *curve, uint64_t *y_sqr,
+ uint64_t *x)
+{
+ uint64_t sum[L_ECC_MAX_DIGITS] = { 0 };
+ uint64_t tmp[L_ECC_MAX_DIGITS] = { 0 };
+ uint64_t _3[L_ECC_MAX_DIGITS] = { 3ull }; /* -a = 3 */
+
+ /* x^3 */
+ vli_mod_square_fast(sum, x, curve->p, curve->ndigits);
+ _vli_mod_mult_fast(sum, sum, x, curve->p, curve->ndigits);
+ /* x^3 - ax */
+ _vli_mod_mult_fast(tmp, _3, x, curve->p, curve->ndigits);
+ _vli_mod_sub(sum, sum, tmp, curve->p, curve->ndigits);
+ /* x^3 - ax + b */
+ _vli_mod_add(sum, sum, curve->b, curve->p, curve->ndigits);
+
+ vli_set(y_sqr, sum, curve->ndigits);
+}
+
+bool _ecc_compute_y(struct l_ecc_curve *curve, uint64_t *y, uint64_t *x)
+{
+ /*
+ * y = sqrt(x^3 + ax + b) (mod p)
+ *
+ * Since our prime p satisfies p = 3 (mod 4), we can say:
+ *
+ * y = (x^3 - 3x + b)^((p + 1) / 4)
+ *
+ * This avoids the need for a square root function.
+ */
+
+ uint64_t sum[L_ECC_MAX_DIGITS] = { 0 };
+ uint64_t expo[L_ECC_MAX_DIGITS] = { 0 };
+ uint64_t one[L_ECC_MAX_DIGITS] = { 1ull };
+ uint64_t check[L_ECC_MAX_DIGITS] = { 0 };
+
+ vli_set(expo, curve->p, curve->ndigits);
+
+ /* x^3 - 3x + b */
+ l_ecc_compute_y_sqr(curve, sum, x);
+
+ /* (p + 1) / 4 == (p >> 2) + 1 */
+ _vli_rshift1(expo, curve->ndigits);
+ _vli_rshift1(expo, curve->ndigits);
+ _vli_mod_add(expo, expo, one, curve->p, curve->ndigits);
+ /* sum ^ ((p + 1) / 4) */
+ _vli_mod_exp(y, sum, expo, curve->p, curve->ndigits);
+
+ /* square y to ensure we have a correct value */
+ _vli_mod_mult_fast(check, y, y, curve->p, curve->ndigits);
+
+ if (_vli_cmp(check, sum, curve->ndigits) != 0)
+ return false;
+
+ return true;
+}
+
+LIB_EXPORT bool l_ecc_compute_y(struct l_ecc_curve *curve, uint64_t *y,
+ uint64_t *x, uint8_t y_bit)
+{
+ if (!_ecc_compute_y(curve, y, x))
+ return false;
+
+ if ((y[0] & 1) != y_bit)
+ _vli_mod_sub(y, curve->p, y, curve->p, curve->ndigits);
+
+ return true;
+}
+
+/*
+ * Several ECC use cases (SAE/PWD) share a similar set of operations. They
+ * require computing 3 integer values: rand, mask, and scalar where:
+ *
+ * 1 < rand < n
+ * 1 < mask < n
+ *
+ * scalar = (rand + mask) mod n
+ *
+ * (where n is curve order)
+ */
+LIB_EXPORT bool l_ecc_compute_scalar(struct l_ecc_curve *curve,
+ uint64_t *scalar, uint64_t *rand,
+ uint64_t *mask)
+{
+ unsigned int nbytes = curve->ndigits * 8;
+ uint64_t one[L_ECC_MAX_DIGITS] = { 1 };
+
+ if (unlikely(!curve) || unlikely(!scalar) ||
+ unlikely(!rand) || unlikely(!mask))
+ return false;
+
+ l_getrandom(rand, nbytes);
+
+ /* ensure 1 < p_rand < r */
+ while (!((_vli_cmp(rand, one, curve->ndigits) > 0) &&
+ (_vli_cmp(rand, curve->n, curve->ndigits) < 0)))
+ l_getrandom(rand, nbytes);
+
+ l_getrandom(mask, nbytes);
+
+ /* ensure 1 < p_mask < r */
+ while (!((_vli_cmp(mask, one, curve->ndigits) > 0) &&
+ (_vli_cmp(mask, curve->n, curve->ndigits) < 0)))
+ l_getrandom(mask, nbytes);
+
+ _vli_mod_add(scalar, rand, mask, curve->n, curve->ndigits);
+
+ return true;
+}
+
+LIB_EXPORT bool l_ecc_point_inverse(struct l_ecc_curve *curve,
+ struct l_ecc_point *point)
+{
+ if (unlikely(!curve) || unlikely(!point))
+ return false;
+
+ vli_sub(point->y, curve->p, point->y, curve->ndigits);
+
+ return true;
+}
+
+LIB_EXPORT bool l_ecc_compute_residue(struct l_ecc_curve *curve,
+ uint64_t *qr_or_qnr, bool residue)
+{
+ int check = (residue) ? -1 : 1;
+
+ l_getrandom(qr_or_qnr, curve->ndigits * 8);
+
+ while (_vli_legendre(qr_or_qnr, curve->p, curve->ndigits) != check)
+ l_getrandom(qr_or_qnr, curve->ndigits * 8);
+
+ return true;
+}
+
+LIB_EXPORT bool l_ecc_is_quadradic_residue(struct l_ecc_curve *curve,
+ uint64_t *value, uint64_t *qr,
+ uint64_t *qnr)
+{
+ unsigned int nbytes = l_ecc_curve_get_ndigits(curve) * 8;
+ uint64_t y_sqr[L_ECC_MAX_DIGITS];
+ uint64_t r[L_ECC_MAX_DIGITS];
+ uint64_t num[L_ECC_MAX_DIGITS];
+
+ if (_vli_cmp(value, curve->p, curve->ndigits) >= 0)
+ return false;
+
+ l_ecc_compute_y_sqr(curve, y_sqr, value);
+
+ l_getrandom(r, nbytes);
+
+ while (_vli_cmp(r, curve->p, curve->ndigits) >= 0)
+ l_getrandom(r, nbytes);
+
+ _vli_mod_mult_fast(num, y_sqr, r, curve->p, curve->ndigits);
+ _vli_mod_mult_fast(num, num, r, curve->p, curve->ndigits);
+
+ if (r[0] & 1) {
+ _vli_mod_mult_fast(num, num, qr, curve->p, curve->ndigits);
+
+ if (_vli_legendre(num, curve->p, curve->ndigits) == -1)
+ return true;
+ } else {
+ _vli_mod_mult_fast(num, num, qnr, curve->p, curve->ndigits);
+
+ if (_vli_legendre(num, curve->p, curve->ndigits) == 1)
+ return true;
+ }
+
+ return false;
+}
+
+LIB_EXPORT bool l_ecc_integer_add(struct l_ecc_curve *curve, uint64_t *ret,
+ uint64_t *a, uint64_t *b)
+{
+ _vli_mod_add(ret, a, b, curve->n, curve->ndigits);
+
+ return true;
+}
+
+/*
+ * This should be used when manually creating a l_ecc_point (have x[,y] and
+ * need to copy into p.x/y). Using this ensures that ndigits gets set. If a
+ * point is being initialized via l_ecc_point_add/l_ecc_point_multiply this
+ * does not need to be used since both set ndigits already.
+ */
+LIB_EXPORT void l_ecc_point_set(struct l_ecc_curve *curve,
+ struct l_ecc_point *p, void *x, void *y)
+{
+ vli_set(p->x, x, curve->ndigits);
+
+ if (y)
+ vli_set(p->y, y, curve->ndigits);
+
+ p->ndigits = curve->ndigits;
+}
diff --git a/ell/ecc.h b/ell/ecc.h
new file mode 100644
index 0000000..0601780
--- /dev/null
+++ b/ell/ecc.h
@@ -0,0 +1,84 @@
+/*
+ *
+ * Embedded Linux library
+ *
+ * Copyright (C) 2018 Intel Corporation. All rights reserved.
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2.1 of the License, or (at your option) any later version.
+ *
+ * This library is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this library; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
+ *
+ */
+
+#ifndef __ELL_ECC_H
+#define __ELL_ECC_H
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+#define L_ECC_MAX_DIGITS 4
+
+struct l_ecc_curve;
+
+struct l_ecc_point {
+ uint64_t x[L_ECC_MAX_DIGITS];
+ uint64_t y[L_ECC_MAX_DIGITS];
+ unsigned int ndigits;
+};
+
+struct l_ecc_curve *l_ecc_curve_get(unsigned int group);
+
+unsigned int l_ecc_curve_get_ndigits(struct l_ecc_curve *curve);
+
+const uint64_t *l_ecc_curve_get_prime(struct l_ecc_curve *curve);
+
+const uint64_t *l_ecc_curve_get_b(struct l_ecc_curve *curve);
+struct l_ecc_point *l_ecc_curve_get_generator(struct l_ecc_curve *curve);
+void l_ecc_point_set(struct l_ecc_curve *curve, struct l_ecc_point *p,
+ void *x, void *y);
+bool l_ecc_point_multiply(struct l_ecc_curve *curve, struct l_ecc_point *ret,
+ struct l_ecc_point *p, uint64_t *scalar,
+ uint64_t *initial_z);
+bool l_ecc_point_add(struct l_ecc_curve *curve, struct l_ecc_point *ret,
+ struct l_ecc_point *p, struct l_ecc_point *q);
+bool l_ecc_valid_point(struct l_ecc_curve *curve, struct l_ecc_point *point);
+void l_ecc_be2native(struct l_ecc_curve *curve, uint64_t *dest,
+ uint64_t *bytes);
+
+void l_ecc_native2be(struct l_ecc_curve *curve, uint64_t *dest,
+ uint64_t *native);
+void l_ecc_compute_y_sqr(struct l_ecc_curve *curve, uint64_t *y_sqr,
+ uint64_t *x);
+bool l_ecc_compute_y(struct l_ecc_curve *curve, uint64_t *y, uint64_t *x,
+ uint8_t y_bit);
+
+bool l_ecc_compute_scalar(struct l_ecc_curve *curve, uint64_t *scalar,
+ uint64_t *rand, uint64_t *mask);
+
+bool l_ecc_point_inverse(struct l_ecc_curve *curve, struct l_ecc_point *point);
+
+bool l_ecc_compute_residue(struct l_ecc_curve *curve,
+ uint64_t *qr_or_qnr, bool residue);
+
+bool l_ecc_is_quadradic_residue(struct l_ecc_curve *curve,
+ uint64_t *value, uint64_t *qr,
+ uint64_t *qnr);
+bool l_ecc_integer_add(struct l_ecc_curve *curve, uint64_t *ret, uint64_t *a,
+ uint64_t *b);
+
+#ifdef __cplusplus
+}
+#endif
+
+#endif /* __ELL_ECC_H */
diff --git a/ell/ell.h b/ell/ell.h
index 4b0eac4..7bc26bc 100644
--- a/ell/ell.h
+++ b/ell/ell.h
@@ -57,3 +57,4 @@
#include <ell/dbus-client.h>
#include <ell/dhcp.h>
#include <ell/cert.h>
+#include <ell/ecc.h>
--
2.17.1
6:08 a.m.
New subject: [PATCH 2/9] unit: moved ECC unit tests from IWD
The test was just modified to use the new l_ecc API's
---
Makefile.am | 5 +-
unit/test-ecc.c | 345 ++++++++++++++++++++++++++++++++++++++++++++++++
2 files changed, 349 insertions(+), 1 deletion(-)
create mode 100644 unit/test-ecc.c
diff --git a/Makefile.am b/Makefile.am
index 4e5f01b..f33f992 100644
--- a/Makefile.am
+++ b/Makefile.am
@@ -161,7 +161,8 @@ unit_tests = unit/test-unit \
unit/test-uuid \
unit/test-pbkdf2 \
unit/test-dhcp \
- unit/test-dir-watch
+ unit/test-dir-watch \
+ unit/test-ecc
dbus_tests = unit/test-hwdb \
unit/test-dbus \
@@ -280,6 +281,8 @@ unit_test_dhcp_LDADD = ell/libell-private.la
unit_test_dir_watch_LDADD = ell/libell-private.la
+unit_test_ecc_LDADD = ell/libell-private.la
+
if MAINTAINER_MODE
noinst_LTLIBRARIES += unit/example-plugin.la
endif
diff --git a/unit/test-ecc.c b/unit/test-ecc.c
new file mode 100644
index 0000000..2aac10a
--- /dev/null
+++ b/unit/test-ecc.c
@@ -0,0 +1,345 @@
+/*
+ *
+ * Embedded Linux library
+ *
+ * Copyright (C) 2018 Intel Corporation. All rights reserved.
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2.1 of the License, or (at your option) any later version.
+ *
+ * This library is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this library; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
+ *
+ */
+
+#ifdef HAVE_CONFIG_H
+#include <config.h>
+#endif
+
+#include <string.h>
+#include <assert.h>
+
+#include <ell/ell.h>
+#include "ell/ecc.h"
+#include "ell/ecc-private.h"
+
+#define HEX2BUF(s, buf) { \
+ unsigned char *tmp = l_util_from_hexstring(s, NULL); \
+ memcpy(buf, tmp, l_ecc_curve_get_ndigits(curve) * 8); \
+ l_free(tmp); \
+}
+
+#define CURVE_P_32_STR "ffffffffffffffffffffffff00000000"\
+ "000000000000000001000000ffffffff"
+
+enum ecc_test_type {
+ TEST_ADD = 0,
+ TEST_SUB,
+ TEST_MULT,
+ TEST_INV,
+ TEST_EXP,
+ TEST_POINT_ADD,
+ TEST_SCALAR_MULT,
+ TEST_LEGENDRE,
+};
+
+struct ecc_test_data {
+ enum ecc_test_type type;
+ /* basic math arguments/result */
+ char *a;
+ char *b;
+ char *qr;
+ char *qnr;
+ char *r;
+ bool is_residue;
+ char *mod;
+ char *result;
+ int lres;
+ /* point operations */
+ char *scalar;
+ char *ax, *ay;
+ char *bx, *by;
+ char *rx, *ry;
+};
+
+/* (a + b) mod c */
+struct ecc_test_data add_test = {
+ .type = TEST_ADD,
+ .a = "cae1d5624344984073fd955a72d4ebacedc084679333e4beebff94869e9f6ca8",
+ .b = "93a02ae89d15e38a33bf3fea4c99937825b279fa8fa81dded1ccb687cec88461",
+ .mod = CURVE_P_32_STR,
+ .result = "5e82004ae05a7bcaa7bcd545bf6e7f25"
+ "1372fe6222dc029dbccc4b0d6d67f10a"
+};
+
+/* (a - b) mod c */
+struct ecc_test_data sub_test = {
+ .type = TEST_SUB,
+ .a = "cae1d5624344984073fd955a72d4ebacedc084679333e4beebff94869e9f6ca8",
+ .b = "93a02ae89d15e38a33bf3fea4c99937825b279fa8fa81dded1ccb687cec88461",
+ .mod = CURVE_P_32_STR,
+ .result = "3741aa79a62eb4b6403e5570263b5834"
+ "c80e0a6d038bc6e01a32ddfecfd6e847"
+};
+
+/* (a * b) mod c */
+struct ecc_test_data mult_test = {
+ .type = TEST_MULT,
+ .a = "cae1d5624344984073fd955a72d4ebacedc084679333e4beebff94869e9f6ca8",
+ .b = "93a02ae89d15e38a33bf3fea4c99937825b279fa8fa81dded1ccb687cec88461",
+ .mod = CURVE_P_32_STR,
+ .result = "a31ff5c7d65d8bd806b0407f27d1f1bc"
+ "2c072e28c19720f6a654a75efc2faab5"
+
+};
+
+/* (a^-1) mod c */
+struct ecc_test_data inv_test = {
+ .type = TEST_INV,
+ .a = "cae1d5624344984073fd955a72d4ebacedc084679333e4beebff94869e9f6ca8",
+ .mod = CURVE_P_32_STR,
+ .result = "48faaac115571047ead565911fc334fd"
+ "633c986755e87ab10fd79a4453a60bc5"
+
+};
+
+/* (a^-1) mod c */
+struct ecc_test_data inv_test2 = {
+ .type = TEST_INV,
+ .a = "698e5c10b63a9c79a9720b3f7f4d2f5c9fbb31daf93ac0f8fa8ca5cde8234418",
+ .mod = CURVE_P_32_STR,
+ .result = "5fd113c3b6053c38e54e5917826c8520"
+ "c5a0708a8a47345edbb7fc1d67d9b42b"
+
+};
+
+/* (a ^ b) mod c */
+struct ecc_test_data exp_test = {
+ .type = TEST_EXP,
+ .a = "cae1d5624344984073fd955a72d4ebacedc084679333e4beebff94869e9f6ca8",
+ .b = "93a02ae89d15e38a33bf3fea4c99937825b279fa8fa81dded1ccb687cec88461",
+ .mod = CURVE_P_32_STR,
+ .result = "e7488e3a4d56938bbddc2a615c768d48"
+ "9e5634aced9ceee37249fae1caa36fec"
+
+};
+
+struct ecc_test_data legendre_test1 = {
+ .type = TEST_LEGENDRE,
+ .a = "b59c0c366aa89ba229f857190497261d5a0a7a0a774caa72aef041ff00092447",
+ .mod = "ffffffff00000001000000000000000000000000ffffffffffffffffffffffff",
+ .lres = -1
+};
+
+struct ecc_test_data legendre_test2 = {
+ .type = TEST_LEGENDRE,
+ .a = "1214f9607d348c998b3fba332d884d65945561fd007ff56d8bf603148d74d2e4",
+ .mod = "ffffffff000000010000000000000000"
+ "00000000ffffffffffffffffffffffff",
+ .lres = 1
+};
+
+struct ecc_test_data legendre_test3 = {
+ .type = TEST_LEGENDRE,
+ .a = "282d751c898bfc593b1d21b6812df48e3ec811f40349b30b7294575c47b871d8",
+ .mod = "ffffffff000000010000000000000000"
+ "00000000ffffffffffffffffffffffff",
+ .lres = 1
+};
+
+struct ecc_test_data legendre_test4 = {
+ .type = TEST_LEGENDRE,
+ .a = "0694ccde1db3d02faa26856678bd9358ecc0d82791405eb3892a8b4f07f1e5d6",
+ .mod = "ffffffff000000010000000000000000"
+ "00000000ffffffffffffffffffffffff",
+ .lres = -1
+};
+
+struct ecc_test_data legendre_test5 = {
+ .type = TEST_LEGENDRE,
+ .a = "92247f96df65a6d04af0c57318e999fd493c42864d156f7e5bba75c964f3c6b0",
+ .mod = "ffffffff000000010000000000000000"
+ "00000000ffffffffffffffffffffffff",
+ .lres = 1
+};
+
+struct ecc_test_data legendre_test6 = {
+ .type = TEST_LEGENDRE,
+ .a = "084f7eb6ed8021d095787fd401b0f19b13937dc23f7c84dfe69bb9a204bb3768",
+ .mod = "ffffffff000000010000000000000000"
+ "00000000ffffffffffffffffffffffff",
+ .lres = -1
+};
+
+struct ecc_test_data point_add_test = {
+ .type = TEST_POINT_ADD,
+ .ax = "d36b6768a3279fbe23a5bf5cc19b13354"
+ "fa2c6d6fd9de467d62db007c39452df",
+ .ay = "4d601e7be3efd7f357452de7584274c54"
+ "c18ddb0ef2f0f4cf43375152a9780c4",
+ .bx = "c833c5d3ab916ed37f16597ace5dcf41f"
+ "080891c0c41b6ce561705bd736a29e0",
+ .by = "9d266e5ba8ba3e8d9679238f44a376b05"
+ "133df0510a7b8e6e7dd3a654d40a04a",
+ .rx = "24c4ede340dbdd144ccaaea67e5b1fca"
+ "87b3aa26dc11114fcd12186318533101",
+ .ry = "1d96391fb2942bf286e9251c257b960e"
+ "7d23d4caff4b6fc898aff87e1f6f5514"
+
+};
+
+struct ecc_test_data point_mult_test = {
+ .type = TEST_SCALAR_MULT,
+ .ax = "768bc2f17fbf4e49282fbd4068994562b"
+ "fc7145306762c26a90be1e9c346ac67",
+ .ay = "93a02ae89d15e38a33bf3fea4c9993782"
+ "5b279fa8fa81dded1ccb687cec88461",
+ .scalar = "7521d940aa073c1675114ed27b866561"
+ "9c826cac8eaa341f70d61b43ad32058b",
+ .rx = "d4c80de349966df5542c984e80885d36"
+ "a965ceb74ffe6a0fdc8343184dedfe66",
+ .ry = "6d3a1ac3d1d392413286a0e00e94b01e"
+ "ae8423c7f53b9d39cc7fc9c3a5880f3b"
+
+};
+
+static void run_test(const void *arg)
+{
+ const struct ecc_test_data *data = arg;
+ uint64_t a[L_ECC_MAX_DIGITS], b[L_ECC_MAX_DIGITS], mod[L_ECC_MAX_DIGITS],
+ scalar[L_ECC_MAX_DIGITS], result[L_ECC_MAX_DIGITS],
+ check[L_ECC_MAX_DIGITS];
+ struct l_ecc_point point1, point2, point_ret;
+ struct l_ecc_curve *curve = l_ecc_curve_get(19);
+ unsigned int ndigits = l_ecc_curve_get_ndigits(curve);
+
+ memset(result, 0, sizeof(result));
+
+ if (data->a) {
+ HEX2BUF(data->a, a);
+ l_ecc_be2native(curve, a, a);
+ }
+
+ if (data->b) {
+ HEX2BUF(data->b, b);
+ l_ecc_be2native(curve, b, b);
+ }
+
+ if (data->mod) {
+ HEX2BUF(data->mod, mod);
+ l_ecc_be2native(curve, mod, mod);
+ }
+
+ if (data->ax) {
+ HEX2BUF(data->ax, point1.x);
+ l_ecc_be2native(curve, point1.x, point1.x);
+ point1.ndigits = ndigits;
+ }
+
+ if (data->ay) {
+ HEX2BUF(data->ay, point1.y);
+ l_ecc_be2native(curve, point1.y, point1.y);
+ }
+
+ if (data->bx) {
+ HEX2BUF(data->bx, point2.x);
+ l_ecc_be2native(curve, point2.x, point2.x);
+ point2.ndigits = ndigits;
+ }
+
+ if (data->by) {
+ HEX2BUF(data->by, point2.y);
+ l_ecc_be2native(curve, point2.y, point2.y);
+ }
+
+ if (data->scalar) {
+ HEX2BUF(data->scalar, scalar);
+ l_ecc_be2native(curve, scalar, scalar);
+ }
+
+ switch (data->type) {
+ case TEST_ADD:
+ _vli_mod_add(result, a, b, mod, ndigits);
+ break;
+ case TEST_SUB:
+ _vli_mod_sub(result, a, b, mod, ndigits);
+ break;
+ case TEST_MULT:
+ _vli_mod_mult_fast(result, a, b, mod, ndigits);
+ break;
+ case TEST_INV:
+ _vli_mod_inv(result, a, mod, ndigits);
+ break;
+ case TEST_EXP:
+ _vli_mod_exp(result, a, b, mod, ndigits);
+ break;
+ case TEST_LEGENDRE:
+ {
+ int lres = _vli_legendre(a, mod, ndigits);
+ assert(data->lres == lres);
+ break;
+ }
+ case TEST_POINT_ADD:
+ assert(l_ecc_valid_point(curve, &point1) == true);
+ assert(l_ecc_valid_point(curve, &point2) == true);
+
+ l_ecc_point_add(curve, &point_ret, &point1, &point2);
+
+ break;
+ case TEST_SCALAR_MULT:
+ assert(l_ecc_valid_point(curve, &point1) == true);
+
+ l_ecc_point_multiply(curve, &point_ret, &point1, scalar, NULL);
+
+ break;
+ }
+
+ if (data->type <= TEST_EXP) {
+ HEX2BUF(data->result, check);
+ l_ecc_native2be(curve, check, check);
+
+ assert(memcmp(result, check, 32) == 0);
+ } else if (data->type <= TEST_SCALAR_MULT) {
+ uint64_t checkx[L_ECC_MAX_DIGITS];
+ uint64_t checky[L_ECC_MAX_DIGITS];
+
+ HEX2BUF(data->rx, checkx);
+ l_ecc_native2be(curve, checkx, checkx);
+ HEX2BUF(data->ry, checky);
+ l_ecc_native2be(curve, checky, checky);
+
+ assert(memcmp(checkx, point_ret.x, 32) == 0);
+ assert(memcmp(checky, point_ret.y, 32) == 0);
+ assert(l_ecc_valid_point(curve, &point_ret) == true);
+ }
+}
+
+int main(int argc, char *argv[])
+{
+ l_test_init(&argc, &argv);
+
+ l_test_add("ECC add test", run_test, &add_test);
+ l_test_add("ECC sub test", run_test, &sub_test);
+ l_test_add("ECC mult test", run_test, &mult_test);
+ l_test_add("ECC inv test", run_test, &inv_test);
+ l_test_add("ECC inv test", run_test, &inv_test2);
+ l_test_add("ECC exp test", run_test, &exp_test);
+ l_test_add("ECC point add test", run_test, &point_add_test);
+ l_test_add("ECC point mult test", run_test, &point_mult_test);
+ l_test_add("ECC legendre", run_test, &legendre_test1);
+ l_test_add("ECC legendre", run_test, &legendre_test2);
+ l_test_add("ECC legendre", run_test, &legendre_test3);
+ l_test_add("ECC legendre", run_test, &legendre_test4);
+ l_test_add("ECC legendre", run_test, &legendre_test5);
+ l_test_add("ECC legendre", run_test, &legendre_test6);
+
+ return l_test_run();
+}
--
2.17.1
6:08 a.m.
New subject: [PATCH 3/9] ecdh: moved ECDH from IWD
Moved the ECDH implementation from IWD. Minor API changes were made,
e.g. to take an l_ecc_curve object. Some sanity checks were also
added to ensure random keys were within the allowable range.
---
Makefile.am | 7 +-
ell/ecdh.c | 200 ++++++++++++++++++++++++++++++++++++++++++++++++++++
ell/ecdh.h | 51 ++++++++++++++
ell/ell.h | 1 +
4 files changed, 257 insertions(+), 2 deletions(-)
create mode 100644 ell/ecdh.c
create mode 100644 ell/ecdh.h
diff --git a/Makefile.am b/Makefile.am
index f33f992..69c3cea 100644
--- a/Makefile.am
+++ b/Makefile.am
@@ -50,7 +50,8 @@ pkginclude_HEADERS = ell/ell.h \
ell/net.h \
ell/dhcp.h \
ell/cert.h \
- ell/ecc.h
+ ell/ecc.h \
+ ell/ecdh.h
lib_LTLIBRARIES = ell/libell.la
@@ -116,7 +117,9 @@ ell_libell_la_SOURCES = $(linux_headers) \
ell/cert-private.h \
ell/ecc-private.h \
ell/ecc.h \
- ell/ecc.c
+ ell/ecc.c \
+ ell/ecdh.h \
+ ell/ecdh.c
ell_libell_la_LDFLAGS = -no-undefined \
-Wl,--version-script=$(top_srcdir)/ell/ell.sym \
diff --git a/ell/ecdh.c b/ell/ecdh.c
new file mode 100644
index 0000000..be6603c
--- /dev/null
+++ b/ell/ecdh.c
@@ -0,0 +1,200 @@
+/*
+ *
+ * Embedded Linux library
+ *
+ * Copyright (C) 2018 Intel Corporation. All rights reserved.
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2.1 of the License, or (at your option) any later version.
+ *
+ * This library is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this library; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
+ *
+ */
+
+#include <stdint.h>
+
+#include "private.h"
+#include "ecc-private.h"
+#include "ecc.h"
+#include "ecdh.h"
+#include "random.h"
+
+/*
+ * Some sane maximum for calculating the public key. This *shouldn't* ever be
+ * reached in normal conditions.
+ */
+#define ECDH_MAX_ITERATIONS 20
+
+/*
+ * IETF - Compact representation of an elliptic curve point:
+ * https://tools.ietf.org/id/draft-jivsov-ecc-compact-00.xml
+ *
+ * "min(y,p-y) can be calculated with the help of the pre-calculated value
+ * p2=(p-1)/2. min(y,p-y) is y if y<p2 and p-y otherwise."
+ */
+static void calculate_p2(struct l_ecc_curve *curve, uint64_t *p2)
+{
+ const uint64_t *prime = l_ecc_curve_get_prime(curve);
+ unsigned int ndigits = l_ecc_curve_get_ndigits(curve);
+ uint64_t one[L_ECC_MAX_DIGITS] = { 1 };
+
+ _vli_mod_sub(p2, prime, one, prime, ndigits);
+ _vli_rshift1(p2, ndigits);
+}
+
+/* Checks that 0 < private < prime */
+static bool private_is_valid(struct l_ecc_curve *curve, void *private)
+{
+ const uint64_t *prime = l_ecc_curve_get_prime(curve);
+ unsigned int ndigits = l_ecc_curve_get_ndigits(curve);
+ uint64_t zero[L_ECC_MAX_DIGITS] = { 0 };
+
+ if (_vli_cmp((uint64_t *)private, prime, ndigits) > 0 ||
+ _vli_cmp((uint64_t *)private, zero, ndigits) == 0)
+ return false;
+
+ return true;
+}
+
+/*
+ * IETF draft-jivsov-ecc-compact-00 Section 4.2.1
+ *
+ * The following algorithm calculates a key pair {k, Q=k*G=(x,y)}, where k is
+ * the private key and Q=(x,y) is the public key.
+ *
+ * Black box generation:
+ * 1. Generate a key pair {k, Q=k*G=(x,y)} with KG
+ * 2. if( y != min(y,p-y) ) goto step 1
+ * 3. output {k, Q=(x,y)} as a key pair
+ */
+LIB_EXPORT bool l_ecdh_generate_key_pair(struct l_ecc_curve *curve, void *private,
+ size_t priv_len, void *public,
+ size_t pub_len)
+{
+ struct l_ecc_point pub;
+ bool compliant = false;
+ int iter = 0;
+ uint8_t *ptr = public;
+ struct l_ecc_point *g = l_ecc_curve_get_generator(curve);
+ unsigned int ndigits = l_ecc_curve_get_ndigits(curve);
+ unsigned int nbytes = ndigits * sizeof(uint64_t);
+ uint64_t p2[L_ECC_MAX_DIGITS];
+
+ calculate_p2(curve, p2);
+
+ /* the caller should only be expecting len(p) or len(p) * 2 */
+ if (pub_len != (nbytes * 2) && pub_len != nbytes)
+ return false;
+
+ while (!compliant && iter++ < ECDH_MAX_ITERATIONS) {
+ if (!l_getrandom(private, priv_len))
+ return false;
+
+ if (!private_is_valid(curve, private))
+ continue;
+
+ /* private * G(x,y) = public key */
+ l_ecc_point_multiply(curve, &pub, g, (uint64_t *)private, NULL);
+
+ /* ensure public key is compliant */
+ if (_vli_cmp(pub.y, p2, ndigits) >= 0) {
+ compliant = true;
+ break;
+ }
+ }
+
+ if (!compliant)
+ return false;
+
+ memcpy(ptr, pub.x, nbytes);
+ pub_len -= nbytes;
+ ptr += nbytes;
+
+ if (pub_len)
+ memcpy(ptr, pub.y, nbytes);
+
+ return true;
+}
+
+/*
+ * IETF draft-jivsov-ecc-compact-00 Section 4.1
+ * Encoding and decoding of an elliptic curve point
+ * ...
+ * Decoding:
+ * Given the compact representation of Q, return canonical representation
+ * of Q=(x,y) as follows:
+ * 1. y' = sqrt( x^3 + a*x + b ), where y'>0
+ * 2. y = min(y',p-y')
+ * 3. Q=(x,y) is the canonical representation of the point
+ */
+static bool decode_point(struct l_ecc_curve *curve, const uint64_t *x,
+ struct l_ecc_point *point)
+{
+ uint64_t y_min[L_ECC_MAX_DIGITS];
+ uint64_t p2[L_ECC_MAX_DIGITS];
+ unsigned int ndigits = l_ecc_curve_get_ndigits(curve);
+ const uint64_t *prime = l_ecc_curve_get_prime(curve);
+
+ if (!_ecc_compute_y(curve, y_min, (uint64_t *)x))
+ return false;
+
+ calculate_p2(curve, p2);
+
+ if (_vli_cmp(y_min, p2, ndigits) >= 0)
+ _vli_mod_sub(point->y, prime, y_min, prime, ndigits);
+ else
+ memcpy(point->y, y_min, ndigits * 8);
+
+ memcpy(point->x, x, ndigits * 8);
+
+ point->ndigits = ndigits;
+
+ return true;
+}
+
+LIB_EXPORT bool l_ecdh_generate_shared_secret(struct l_ecc_curve *curve,
+ const void *private,
+ const void *other_public,
+ size_t pub_len, void *secret,
+ size_t secret_len)
+{
+ struct l_ecc_point product;
+ struct l_ecc_point public;
+ uint64_t z[L_ECC_MAX_DIGITS];
+ unsigned int ndigits = l_ecc_curve_get_ndigits(curve);
+ unsigned int nbytes = ndigits * sizeof(uint64_t);
+
+ if (secret_len > nbytes)
+ return false;
+
+ if (pub_len == nbytes) {
+ /*
+ * Only half the public key was given, the remainder (Y) must
+ * be decoded.
+ */
+ if (!decode_point(curve, other_public, &public))
+ return false;
+ } else if (pub_len == nbytes * 2)
+ l_ecc_point_set(curve, &public, (void *)other_public,
+ (void *)other_public + nbytes);
+ else
+ return false;
+
+ if (!l_getrandom(z, nbytes))
+ return false;
+
+ l_ecc_point_multiply(curve, &product, &public, (uint64_t *)private, z);
+
+ memcpy(secret, product.x, secret_len);
+
+ return true;
+}
diff --git a/ell/ecdh.h b/ell/ecdh.h
new file mode 100644
index 0000000..0d41891
--- /dev/null
+++ b/ell/ecdh.h
@@ -0,0 +1,51 @@
+/*
+ *
+ * Embedded Linux library
+ *
+ * Copyright (C) 2018 Intel Corporation. All rights reserved.
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2.1 of the License, or (at your option) any later version.
+ *
+ * This library is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this library; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
+ *
+ */
+#ifndef __ELL_ECDH_H
+#define __ELL_ECDH_H
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+#include "ecc.h"
+
+/*
+ * Generate a private/public key pair. All inputs are expected in little-endian.
+ */
+bool l_ecdh_generate_key_pair(struct l_ecc_curve *curve, void *private,
+ size_t priv_len, void *public,
+ size_t pub_len);
+/*
+ * Generate a shared secret from a private/public key. All inputs are expected
+ * in little-endian.
+ */
+bool l_ecdh_generate_shared_secret(struct l_ecc_curve *curve,
+ const void *private,
+ const void *other_public,
+ size_t pub_len, void *secret,
+ size_t secret_len);
+
+#ifdef __cplusplus
+}
+#endif
+
+#endif /* __ELL_ECDH_H */
diff --git a/ell/ell.h b/ell/ell.h
index 7bc26bc..aab6417 100644
--- a/ell/ell.h
+++ b/ell/ell.h
@@ -58,3 +58,4 @@
#include <ell/dhcp.h>
#include <ell/cert.h>
#include <ell/ecc.h>
+#include <ell/ecdh.h>
--
2.17.1
6:08 a.m.
New subject: [PATCH 4/9] unit: added ECDH unit tests
This test was moved from IWD, with required changes to the API
---
Makefile.am | 6 +-
unit/test-ecdh.c | 166 +++++++++++++++++++++++++++++++++++++++++++++++
2 files changed, 171 insertions(+), 1 deletion(-)
create mode 100644 unit/test-ecdh.c
diff --git a/Makefile.am b/Makefile.am
index 69c3cea..dc16a2c 100644
--- a/Makefile.am
+++ b/Makefile.am
@@ -165,7 +165,8 @@ unit_tests = unit/test-unit \
unit/test-pbkdf2 \
unit/test-dhcp \
unit/test-dir-watch \
- unit/test-ecc
+ unit/test-ecc \
+ unit/test-ecdh
dbus_tests = unit/test-hwdb \
unit/test-dbus \
@@ -286,6 +287,9 @@ unit_test_dir_watch_LDADD = ell/libell-private.la
unit_test_ecc_LDADD = ell/libell-private.la
+unit_test_ecdh_LDADD = ell/libell-private.la
+unit_test_ecdh_LDFLAGS = -Wl,-wrap,l_getrandom
+
if MAINTAINER_MODE
noinst_LTLIBRARIES += unit/example-plugin.la
endif
diff --git a/unit/test-ecdh.c b/unit/test-ecdh.c
new file mode 100644
index 0000000..efc47de
--- /dev/null
+++ b/unit/test-ecdh.c
@@ -0,0 +1,166 @@
+/*
+ *
+ * Embedded Linux library
+ *
+ * Copyright (C) 2018 Intel Corporation. All rights reserved.
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2.1 of the License, or (at your option) any later version.
+ *
+ * This library is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this library; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
+ *
+ */
+
+#ifdef HAVE_CONFIG_H
+#include <config.h>
+#endif
+
+#include <string.h>
+#include <assert.h>
+#include <ell/ell.h>
+
+static bool use_real_getrandom = true;
+
+bool __wrap_l_getrandom(void *buf, size_t len);
+bool __real_l_getrandom(void *buf, size_t len);
+
+bool __wrap_l_getrandom(void *buf, size_t len)
+{
+ static const uint8_t random_buf[] = { 0x75, 0xc5, 0xfe, 0x3e, 0x53,
+ 0xcc, 0x33, 0x33, 0x64, 0xea,
+ 0xdd, 0xa1, 0xe6, 0x62, 0x7a,
+ 0xb1, 0x98, 0xa7, 0xa0, 0x1e,
+ 0xac, 0x4b, 0x1d, 0xb8, 0x71,
+ 0x5b, 0x1d, 0x00, 0x36, 0xd0,
+ 0x0f, 0xde };
+
+ if (use_real_getrandom)
+ return __real_l_getrandom(buf, len);
+
+ memcpy(buf, random_buf, len);
+
+ return true;
+}
+
+/*
+ * Tests the most basic case. Generate two full public keys and use to create
+ * two identical shared secrets.
+ */
+static void test_basic(const void *data)
+{
+ struct l_ecc_curve *curve = l_ecc_curve_get(19);
+ uint8_t private1[32];
+ uint8_t private2[32];
+
+ uint8_t public1[64];
+ uint8_t public2[64];
+
+ uint8_t secret1[32];
+ uint8_t secret2[32];
+
+ assert(l_ecdh_generate_key_pair(curve, private1, 32, public1, 64));
+ assert(l_ecdh_generate_key_pair(curve, private2, 32, public2, 64));
+
+ assert(l_ecdh_generate_shared_secret(curve, private1, public2, 64,
+ secret1, 32));
+ assert(l_ecdh_generate_shared_secret(curve, private2, public1, 64,
+ secret2, 32));
+
+ assert(!memcmp(secret1, secret2, 32));
+}
+
+/*
+ * Tests public key compliance. When generating the public keys, only specify
+ * half their length (32). This requires ECDH to compute the remainder of the
+ * public key when generating the shared secret.
+ */
+static void test_compliant_key(const void *data)
+{
+ struct l_ecc_curve *curve = l_ecc_curve_get(19);
+
+ uint8_t private1[32];
+ uint8_t private2[32];
+
+ uint8_t public1[32];
+ uint8_t public2[32];
+
+ uint8_t secret1[32];
+ uint8_t secret2[32];
+
+ assert(l_ecdh_generate_key_pair(curve, private1, 32, public1, 32));
+ assert(l_ecdh_generate_key_pair(curve, private2, 32, public2, 32));
+
+ assert(l_ecdh_generate_shared_secret(curve, private1, public2, 32,
+ secret1, 32));
+ assert(l_ecdh_generate_shared_secret(curve, private2, public1, 32,
+ secret2, 32));
+
+ assert(!memcmp(secret1, secret2, 32));
+}
+
+/*
+ * Test vector from RFC 5114 - 256-bit Random ECP Group
+ */
+static void test_vectors(const void *data)
+{
+ struct l_ecc_curve *curve = l_ecc_curve_get(19);
+
+ uint64_t a_secret[4] = { 0x867B7291D507A3AFull, 0x3FAF432A5ABCE59Eull,
+ 0xE96A8E337A128499ull, 0x814264145F2F56F2ull };
+ uint64_t a_public[8] = { 0x5E8D3B4BA83AEB15ull, 0x7165BE50BC42AE4Aull,
+ 0xC9B5A8D4160D09E9ull, 0x2AF502F3BE8952F2ull,
+ 0xC0F5015ECE5EFD85ull, 0x6795BD4BFF6E6DE3ull,
+ 0x8681A0F9872D79D5ull, 0xEB0FAF4CA986C4D3ull };
+
+ uint64_t b_secret[4] = { 0xEE1B593761CF7F41ull, 0x19CE6BCCAD562B8Eull,
+ 0xDB95A200CC0AB26Aull, 0x2CE1788EC197E096ull };
+ uint64_t b_public[8] = { 0xB3AB0715F6CE51B0ull, 0xAE06AAEA279FA775ull,
+ 0x5346E8DE6C2C8646ull, 0xB120DE4AA3649279ull,
+ 0x85C34DDE5708B2B6ull, 0x3727027092A84113ull,
+ 0xD8EC685FA3F071D8ull, 0x9F1B7EECE20D7B5Eull };
+
+ uint64_t shared_secret[4] = { 0x7F80D21C820C2788ull,
+ 0xF5811E9DC8EC8EEAull,
+ 0x93310412D19A08F1ull,
+ 0xDD0F5396219D1EA3ull };
+
+ uint64_t a_shared[4];
+ uint64_t b_shared[4];
+
+ use_real_getrandom = false;
+
+ assert(l_ecdh_generate_shared_secret(curve, a_secret,
+ (const void *) b_public,
+ 64, a_shared, 32));
+ assert(l_ecdh_generate_shared_secret(curve, b_secret,
+ (const void *) a_public,
+ 64, b_shared, 32));
+
+ assert(!memcmp(a_shared, shared_secret, 32));
+ assert(!memcmp(b_shared, shared_secret, 32));
+
+ use_real_getrandom = true;
+}
+
+int main(int argc, char *argv[])
+{
+ l_test_init(&argc, &argv);
+
+ if (l_getrandom_is_supported()) {
+ l_test_add("ECDH Basic", test_basic, NULL);
+ l_test_add("ECDH Compliant key", test_compliant_key, NULL);
+ }
+
+ l_test_add("ECDH test vector", test_vectors, NULL);
+
+ return l_test_run();
+}
--
2.17.1
6:08 a.m.
New subject: [PATCH 5/9] ecc: implement P384 fast modulus
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.c | 129 ++++++++++++++++++++++++++++++++++++++++++++++++++++++
1 file changed, 129 insertions(+)
diff --git a/ell/ecc.c b/ell/ecc.c
index b3ddf30..5d5e948 100644
--- a/ell/ecc.c
+++ b/ell/ecc.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
6:08 a.m.
New subject: [PATCH 6/9] ecc: added P384 curve definition
---
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 5d5e948..03a9610 100644
--- a/ell/ecc.c
+++ b/ell/ecc.c
@@ -1007,8 +1007,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,
+ .ndigits = 6
+ },
+ .p = P384_CURVE_P,
+ .n = P384_CURVE_N,
+ .b = P384_CURVE_B
+};
+
static struct l_ecc_curve *curves[] = {
&p256,
+ &p384,
};
LIB_EXPORT struct l_ecc_curve *l_ecc_curve_get(unsigned int group)
diff --git a/ell/ecc.h b/ell/ecc.h
index 0601780..e1c137f 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
struct l_ecc_curve;
--
2.17.1
6:08 a.m.
New subject: [PATCH 7/9] unit: update test-ecdh with more random bytes
With the addition of P384, our wrapped l_getrandom needs enough random
bytes to fill a P384 integer, 48 bytes.
---
unit/test-ecdh.c | 24 +++++++++++++++++-------
1 file changed, 17 insertions(+), 7 deletions(-)
diff --git a/unit/test-ecdh.c b/unit/test-ecdh.c
index efc47de..e44c4b6 100644
--- a/unit/test-ecdh.c
+++ b/unit/test-ecdh.c
@@ -35,13 +35,23 @@ bool __real_l_getrandom(void *buf, size_t len);
bool __wrap_l_getrandom(void *buf, size_t len)
{
- static const uint8_t random_buf[] = { 0x75, 0xc5, 0xfe, 0x3e, 0x53,
- 0xcc, 0x33, 0x33, 0x64, 0xea,
- 0xdd, 0xa1, 0xe6, 0x62, 0x7a,
- 0xb1, 0x98, 0xa7, 0xa0, 0x1e,
- 0xac, 0x4b, 0x1d, 0xb8, 0x71,
- 0x5b, 0x1d, 0x00, 0x36, 0xd0,
- 0x0f, 0xde };
+ /*
+ * Note: we at least need enough bytes for the largest curve group,
+ * currently P384
+ */
+ static const uint8_t random_buf[] = { 0x0b, 0x34, 0x0f, 0x16, 0x02,
+ 0x31, 0x88, 0xe1, 0x0e, 0x08,
+ 0xb2, 0x5f, 0x03, 0x4c, 0x3c,
+ 0xe8, 0x3d, 0xf4, 0xaa, 0xc5,
+ 0x8d, 0x2b, 0x1f, 0x43, 0xb8,
+ 0x0e, 0xf3, 0xed, 0x73, 0xd0,
+ 0xd7, 0x8d, 0x77, 0x62, 0xaf,
+ 0xa7, 0x37, 0xca, 0x20, 0x3f,
+ 0xd8, 0xf5, 0x32, 0x64, 0x7e,
+ 0xf6, 0x45, 0x46 };
+
+ if (len > sizeof(random_buf))
+ return false;
if (use_real_getrandom)
return __real_l_getrandom(buf, len);
--
2.17.1
6:08 a.m.
New subject: [PATCH 8/9] unit: added P384 unit tests
(also renamed 'test_vectors' to 'test_vector_p256' for consistency)
---
unit/test-ecdh.c | 49 ++++++++++++++++++++++++++++++++++++++++++++++--
1 file changed, 47 insertions(+), 2 deletions(-)
diff --git a/unit/test-ecdh.c b/unit/test-ecdh.c
index e44c4b6..10cb47a 100644
--- a/unit/test-ecdh.c
+++ b/unit/test-ecdh.c
@@ -120,7 +120,7 @@ static void test_compliant_key(const void *data)
/*
* Test vector from RFC 5114 - 256-bit Random ECP Group
*/
-static void test_vectors(const void *data)
+static void test_vector_p256(const void *data)
{
struct l_ecc_curve *curve = l_ecc_curve_get(19);
@@ -161,6 +161,50 @@ static void test_vectors(const void *data)
use_real_getrandom = true;
}
+static void test_vector_p384(const void *data)
+{
+ struct l_ecc_curve *curve = l_ecc_curve_get(20);
+
+ uint64_t a_secret[6] = { 0x86F05FEADB9376F1ull, 0xD706A90CBCB5DF29ull,
+ 0xD709EE7A7962A156ull, 0x5DFD8A7965571C48ull,
+ 0x44DD14E9FD126071ull, 0xD27335EA71664AF2ull };
+ uint64_t a_public[12] = { 0x7D016FE27A8B8C66ull, 0x7E6A8EA9D1FD7742ull,
+ 0x0EE6B0403D627954ull, 0xE057AB62F82054D1ull,
+ 0xDA4C6D9074417D05ull, 0x793148F1787634D5ull,
+ 0xBACED214A1A1D128ull, 0x8F7A685923DE3B67ull,
+ 0x6B8F398BB29E4236ull, 0xC947392E94F4C3F0ull,
+ 0xF480F4FB4CD40504ull, 0xC6C41294331D23E6ull };
+ uint64_t b_secret[6] = { 0x2C4A6C768BCD94D2ull, 0x9BE52E00C194A413ull,
+ 0x1F80231121CCE3D3ull, 0x3B6125262C36A7DFull,
+ 0x9C0F00D456C2F702ull, 0x52D1791FDB4B70F8ull };
+ uint64_t b_public[12] = { 0x223F12B5A1ABC120ull, 0x789D72A84865AE2Full,
+ 0x4ABC17647B6B9999ull, 0x5B36DB65915359B4ull,
+ 0xF74B8D4EFB708B3Dull, 0x5CD42AB9C41B5347ull,
+ 0xE035B0EDF36755DEull, 0x40BDE8723415A8ECull,
+ 0x0CECA16356CA9332ull, 0x8F6D5B348C0FA4D8ull,
+ 0xA3A8BFAC46B404BDull, 0xE171458FEAA939AAull };
+ uint64_t shared_secret[6] = {
+ 0xDE159A58028ABC0Eull, 0x27AA8A4540884C37ull,
+ 0x59D926EB1B8456E4ull, 0xCAE53160137D904Cull,
+ 0x55981B110575E0A8ull, 0x5EA1FC4AF7256D20ull };
+ uint64_t a_shared[6];
+ uint64_t b_shared[6];
+
+ use_real_getrandom = false;
+
+ assert(l_ecdh_generate_shared_secret(curve, a_secret,
+ (const void *) b_public,
+ 96, a_shared, 48));
+ assert(l_ecdh_generate_shared_secret(curve, b_secret,
+ (const void *) a_public,
+ 96, b_shared, 48));
+
+ assert(!memcmp(a_shared, shared_secret, 48));
+ assert(!memcmp(b_shared, shared_secret, 48));
+
+ use_real_getrandom = true;
+}
+
int main(int argc, char *argv[])
{
l_test_init(&argc, &argv);
@@ -170,7 +214,8 @@ int main(int argc, char *argv[])
l_test_add("ECDH Compliant key", test_compliant_key, NULL);
}
- l_test_add("ECDH test vector", test_vectors, 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
6:08 a.m.
New subject: [PATCH 9/9] gitignore: added test-ecc/test-ecdh
---
.gitignore | 2 ++
1 file changed, 2 insertions(+)
diff --git a/.gitignore b/.gitignore
index 16725f5..75ab7b2 100644
--- a/.gitignore
+++ b/.gitignore
@@ -56,6 +56,8 @@ unit/test-key
unit/test-pbkdf2
unit/test-dhcp
unit/test-dir-watch
+unit/test-ecc
+unit/test-ecdh
unit/cert-*.pem
unit/cert-*.csr
unit/cert-*.srl
--
2.17.1
11:20 a.m.
Hi James,
On 11/29/2018 04:08 PM, James Prestwood wrote:
IWD had its own implementation for ECC and math operations.
Eventually
TLS will indirectly require this (via ECDH) so it made sense to move
everything into ell. Some changes had to be made to the original file
to accomidate the ell style.
The original file (ecc.c) required some changes. The ecc_point type
is now exposed as l_ecc_point. Several vli_ functions were prefixed
with "_" so they could be exposed privately. All ecc functions
that needed to be exposed as library API's were prefixed with l_ecc,
and changed to take a l_ecc_curve object, explained below.
A new type was also added, l_ecc_curve, which holds all the information
for a given curve. Users will call l_curve_get(int group) to get a
supported curve object. This curve object can then be passed to all
l_ecc API's which avoids the need for the user to know any of the
curve parameters (prime, g, n, b, etc.) or vli lengths. Some of these
parameters may still need to be obtained, so several getters were added
as well.
When using any of the l_ecc API's, any vli integers should be
created as a uint64_t array of size L_ECC_MAX_DIGITS. This ensures
that the integer will support all supported curves. L_ECC_MAX_DIGITS
should also be updated if any larger bit size curves are added.
---
Makefile.am | 8 +-
ell/ecc-private.h | 50 ++
ell/ecc.c | 1288 +++++++++++++++++++++++++++++++++++++++++++++
ell/ecc.h | 84 +++
ell/ell.h | 1 +
5 files changed, 1429 insertions(+), 2 deletions(-)
create mode 100644 ell/ecc-private.h
create mode 100644 ell/ecc.c
create mode 100644 ell/ecc.h
So just commenting on the high-level API for now. Overall my impression
is that it is still exposing too much low-level details. Can we get
away with exposing less?
diff --git a/ell/ecc.h b/ell/ecc.h
new file mode 100644
index 0000000..0601780
--- /dev/null
+++ b/ell/ecc.h
@@ -0,0 +1,84 @@
+/*
+ *
+ * Embedded Linux library
+ *
+ * Copyright (C) 2018 Intel Corporation. All rights reserved.
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2.1 of the License, or (at your option) any later version.
+ *
+ * This library is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this library; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
+ *
+ */
+
+#ifndef __ELL_ECC_H
+#define __ELL_ECC_H
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+#define L_ECC_MAX_DIGITS 4
+
+struct l_ecc_curve;
+
+struct l_ecc_point {
+ uint64_t x[L_ECC_MAX_DIGITS];
+ uint64_t y[L_ECC_MAX_DIGITS];
+ unsigned int ndigits;
You might want to just store the pointer to the ecc_curve here and make
your life easier in the rest of the API.
+};
Do you really want to expose this?
+
+struct l_ecc_curve *l_ecc_curve_get(unsigned int group);
const struct l_ecc_curve *?
+
+unsigned int l_ecc_curve_get_ndigits(struct l_ecc_curve *curve);
const struct?
Is this one really needed, or can it be kept private?
+
+const uint64_t *l_ecc_curve_get_prime(struct l_ecc_curve *curve);
+
As above
+const uint64_t *l_ecc_curve_get_b(struct l_ecc_curve *curve);
And here
+struct l_ecc_point *l_ecc_curve_get_generator(struct l_ecc_curve
*curve);
And here?
+void l_ecc_point_set(struct l_ecc_curve *curve, struct l_ecc_point
*p,
+ void *x, void *y);
Should this be something like:
struct l_ecc_point *l_ecc_point_new(const struct l_ecc_curve *curve,
const void *data, size_t len);
Where I would assume data is in big endian or whatever canonical
exchange format.
+bool l_ecc_point_multiply(struct l_ecc_curve *curve, struct
l_ecc_point *ret,
+ struct l_ecc_point *p, uint64_t *scalar,
+ uint64_t *initial_z);
+bool l_ecc_point_add(struct l_ecc_curve *curve, struct l_ecc_point *ret,
+ struct l_ecc_point *p, struct l_ecc_point *q);
+bool l_ecc_valid_point(struct l_ecc_curve *curve, struct l_ecc_point *point);
+void l_ecc_be2native(struct l_ecc_curve *curve, uint64_t *dest,
+ uint64_t *bytes);
+
+void l_ecc_native2be(struct l_ecc_curve *curve, uint64_t *dest,
+ uint64_t *native);
So this may be just size_t l_ecc_point_to_be(struct l_ecc_point *point,
void *dest, size_t dest_len);
+void l_ecc_compute_y_sqr(struct l_ecc_curve *curve, uint64_t
*y_sqr,
+ uint64_t *x);
+bool l_ecc_compute_y(struct l_ecc_curve *curve, uint64_t *y, uint64_t *x,
+ uint8_t y_bit);
+
+bool l_ecc_compute_scalar(struct l_ecc_curve *curve, uint64_t *scalar,
+ uint64_t *rand, uint64_t *mask);
+
+bool l_ecc_point_inverse(struct l_ecc_curve *curve, struct l_ecc_point *point);
+
+bool l_ecc_compute_residue(struct l_ecc_curve *curve,
+ uint64_t *qr_or_qnr, bool residue);
+
+bool l_ecc_is_quadradic_residue(struct l_ecc_curve *curve,
+ uint64_t *value, uint64_t *qr,
+ uint64_t *qnr);
+bool l_ecc_integer_add(struct l_ecc_curve *curve, uint64_t *ret, uint64_t *a,
+ uint64_t *b);
+
All these uint64_t * things scare me. Can we not expose these
operations and expose something a bit more higher level?
Regards,
-Denis
11:38 a.m.
New subject: [PATCH 3/9] ecdh: moved ECDH from IWD
Hi James,
+ * Generate a private/public key pair. All inputs are expected in
little-endian.
+ */
+bool l_ecdh_generate_key_pair(struct l_ecc_curve *curve, void *private,
+ size_t priv_len, void *public,
+ size_t pub_len);
Public is just a point on the curve right? So should this be something like:
bool l_ecdh_generate_key_pair(const struct l_ecc_curve *curve,
struct l_ecc_point *out_public,
struct l_ecc_constant *out_private);
?
+/*
+ * Generate a shared secret from a private/public key. All inputs are expected
+ * in little-endian.
+ */
+bool l_ecdh_generate_shared_secret(struct l_ecc_curve *curve,
+ const void *private,
+ const void *other_public,
+ size_t pub_len, void *secret,
+ size_t secret_len);
Similarly here maybe:
struct l_ecc_point *other_public = l_ecc_point_new(curve, data, len);
bool l_ecdh_generate_shared_secret(struct l_ecc_constant *private,
struct l_ecc_point *other_public,
void *out_secret,
size_t out_secret_len);
?
Regards,
-Denis
2:31 a.m.
New subject: [PATCH 3/9] ecdh: moved ECDH from IWD
On Thu, 2018-11-29 at 21:38 -0600, Denis Kenzior wrote:
Hi James,
> + * Generate a private/public key pair. All inputs are expected in
> little-endian.
> + */
> +bool l_ecdh_generate_key_pair(struct l_ecc_curve *curve, void
> *private,
> + size_t priv_len, void *public,
> + size_t pub_len);
Public is just a point on the curve right? So should this be
something like:
bool l_ecdh_generate_key_pair(const struct l_ecc_curve *curve,
struct l_ecc_point *out_public,
struct l_ecc_constant *out_private);
?
Yes it is just a point on the curve, but I don't think that most users
of this API need or care to know to that level of detail. Also,
generating the shared secret supports compressed coordinates where only
the X coordinate is given. In this case the half public key is coming
from the network, so its much more convenient just feeding it that raw
data that converting it to a point.
> +/*
> + * Generate a shared secret from a private/public key. All inputs
> are expected
> + * in little-endian.
> + */
> +bool l_ecdh_generate_shared_secret(struct l_ecc_curve *curve,
> + const void *private,
> + const void
> *other_public,
> + size_t pub_len, void
> *secret,
> + size_t secret_len);
Similarly here maybe:
struct l_ecc_point *other_public = l_ecc_point_new(curve, data, len);
bool l_ecdh_generate_shared_secret(struct l_ecc_constant *private,
struct l_ecc_point *other_public,
void *out_secret,
size_t out_secret_len);
?
Regards,
-Denis
2:41 a.m.
New subject: [PATCH 3/9] ecdh: moved ECDH from IWD
Hi James,
> bool l_ecdh_generate_key_pair(const struct l_ecc_curve *curve,
> struct l_ecc_point *out_public,
> struct l_ecc_constant *out_private);
> ?
Yes it is just a point on the curve, but I don't think that most users
of this API need or care to know to that level of detail. Also,
But if we pass in void * and a length, don't they have to care even to a
greater degree? I mean they need to know how many bytes they should
pass in for example. And then they must somehow *know* that they want a
compressed point or uncompressed and pass in the appropriate number of
bytes. And then do the conversion to network order.
You could just make ecc_point take care of all these details.
generating the shared secret supports compressed coordinates where
only
the X coordinate is given. In this case the half public key is coming
from the network, so its much more convenient just feeding it that raw
data that converting it to a point.
You still need to validate what is coming over the network and convert
it from network byte order. The constructor for ecc_point could do this
for you.
Regards,
-Denis
870
days inactive
874
days old
12 comments
2 participants
participants (2)
-
Denis Kenzior -
James Prestwood