| /* |
| * |
| * 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 |
| |
| #define _GNU_SOURCE |
| #include <stdio.h> |
| #include <stdint.h> |
| #include <stdbool.h> |
| #include <string.h> |
| #include <stdlib.h> |
| #include <errno.h> |
| |
| #include "ecc.h" |
| #include "ecc-private.h" |
| #include "random.h" |
| #include "useful.h" |
| #include "private.h" |
| #include "missing.h" |
| |
| /* |
| * RFC 5114 - Section 2.6 256-bit Random ECP Group |
| */ |
| #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 const struct l_ecc_curve p256 = { |
| .name = "secp256r1", |
| .ike_group = 19, |
| .tls_group = 23, |
| .ndigits = 4, |
| .g = { |
| .x = P256_CURVE_GX, |
| .y = P256_CURVE_GY, |
| .curve = &p256 |
| }, |
| .p = P256_CURVE_P, |
| .n = P256_CURVE_N, |
| .b = P256_CURVE_B, |
| .z = -10, |
| }; |
| |
| /* |
| * RFC 5114 - Section 2.7 384-bit Random ECP Group |
| */ |
| #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 const struct l_ecc_curve p384 = { |
| .name = "secp384r1", |
| .ike_group = 20, |
| .tls_group = 24, |
| .ndigits = 6, |
| .g = { |
| .x = P384_CURVE_GX, |
| .y = P384_CURVE_GY, |
| .curve = &p384 |
| }, |
| .p = P384_CURVE_P, |
| .n = P384_CURVE_N, |
| .b = P384_CURVE_B, |
| .z = -12, |
| }; |
| |
| static const struct l_ecc_curve *curves[] = { |
| &p384, |
| &p256, |
| }; |
| |
| /* Returns supported IKE groups, sorted by the highest effective key size */ |
| LIB_EXPORT const unsigned int *l_ecc_supported_ike_groups(void) |
| { |
| static unsigned int supported_ike_groups[L_ARRAY_SIZE(curves) + 1]; |
| static bool ike_first = true; |
| |
| if (ike_first) { |
| unsigned int i; |
| |
| for (i = 0; i < L_ARRAY_SIZE(curves); i++) |
| supported_ike_groups[i] = curves[i]->ike_group; |
| |
| supported_ike_groups[i] = 0; |
| ike_first = false; |
| } |
| |
| return supported_ike_groups; |
| } |
| |
| /* Returns supported TLS groups, sorted by the highest effective key size */ |
| LIB_EXPORT const unsigned int *l_ecc_supported_tls_groups(void) |
| { |
| static unsigned int supported_tls_groups[L_ARRAY_SIZE(curves) + 1]; |
| static bool tls_first = true; |
| |
| if (tls_first) { |
| unsigned int i; |
| |
| for (i = 0; i < L_ARRAY_SIZE(curves); i++) |
| supported_tls_groups[i] = curves[i]->tls_group; |
| |
| supported_tls_groups[i] = 0; |
| tls_first = false; |
| } |
| |
| return supported_tls_groups; |
| } |
| |
| LIB_EXPORT const struct l_ecc_curve *l_ecc_curve_from_name(const char *name) |
| { |
| int i; |
| |
| if (unlikely(!name)) |
| return NULL; |
| |
| for (i = 0; curves[i]; i++) { |
| if (!strcmp(curves[i]->name, name)) |
| return curves[i]; |
| } |
| |
| return NULL; |
| } |
| |
| LIB_EXPORT const struct l_ecc_curve *l_ecc_curve_from_ike_group( |
| unsigned int group) |
| { |
| unsigned int i; |
| |
| for (i = 0; i < L_ARRAY_SIZE(curves); i++) { |
| if (curves[i]->ike_group == group) |
| return curves[i]; |
| } |
| |
| return NULL; |
| } |
| |
| LIB_EXPORT const struct l_ecc_curve *l_ecc_curve_from_tls_group( |
| unsigned int group) |
| { |
| unsigned int i; |
| |
| for (i = 0; i < L_ARRAY_SIZE(curves); i++) { |
| if (curves[i]->tls_group == group) |
| return curves[i]; |
| } |
| |
| return NULL; |
| } |
| |
| LIB_EXPORT const char *l_ecc_curve_get_name(const struct l_ecc_curve *curve) |
| { |
| if (unlikely(!curve)) |
| return NULL; |
| |
| return curve->name; |
| } |
| |
| LIB_EXPORT unsigned int l_ecc_curve_get_ike_group( |
| const struct l_ecc_curve *curve) |
| { |
| if (unlikely(!curve)) |
| return 0; |
| |
| return curve->ike_group; |
| } |
| |
| LIB_EXPORT unsigned int l_ecc_curve_get_tls_group( |
| const struct l_ecc_curve *curve) |
| { |
| if (unlikely(!curve)) |
| return 0; |
| |
| return curve->tls_group; |
| } |
| |
| LIB_EXPORT struct l_ecc_scalar *l_ecc_curve_get_order( |
| const struct l_ecc_curve *curve) |
| { |
| return _ecc_constant_new(curve, curve->n, curve->ndigits * 8); |
| } |
| |
| LIB_EXPORT struct l_ecc_scalar *l_ecc_curve_get_prime( |
| const struct l_ecc_curve *curve) |
| { |
| if (unlikely(!curve)) |
| return NULL; |
| |
| return _ecc_constant_new(curve, curve->p, curve->ndigits * 8); |
| } |
| |
| LIB_EXPORT size_t l_ecc_curve_get_scalar_bytes(const struct l_ecc_curve *curve) |
| { |
| if (unlikely(!curve)) |
| return 0; |
| |
| return curve->ndigits * 8; |
| } |
| |
| static bool ecc_valid_point(struct l_ecc_point *point) |
| { |
| const struct l_ecc_curve *curve = point->curve; |
| uint64_t tmp1[L_ECC_MAX_DIGITS]; |
| uint64_t tmp2[L_ECC_MAX_DIGITS]; |
| uint64_t _3[L_ECC_MAX_DIGITS] = { 3 }; /* -a = 3 */ |
| unsigned int ndigits = curve->ndigits; |
| |
| /* 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->p, point->x, ndigits) != 1 || |
| _vli_cmp(curve->p, point->y, ndigits) != 1) |
| return false; |
| |
| /* Computes result = y^2. */ |
| _vli_mod_square_fast(tmp1, point->y, curve->p, ndigits); |
| |
| /* Computes result = x^3 + ax + b. result must not overlap x. */ |
| /* r = x^2 */ |
| _vli_mod_square_fast(tmp2, point->x, curve->p, ndigits); |
| /* r = x^2 - 3 */ |
| _vli_mod_sub(tmp2, tmp2, _3, curve->p, ndigits); |
| /* r = x^3 - 3x */ |
| _vli_mod_mult_fast(tmp2, tmp2, point->x, curve->p, ndigits); |
| /* r = x^3 - 3x + b */ |
| _vli_mod_add(tmp2, tmp2, curve->b, curve->p, ndigits); |
| /* Make sure that y^2 == x^3 + ax + b */ |
| return (_vli_cmp(tmp1, tmp2, ndigits) == 0); |
| } |
| |
| void _ecc_be2native(uint64_t *dest, const uint64_t *bytes, |
| unsigned int ndigits) |
| { |
| unsigned int i; |
| uint64_t tmp[2 * L_ECC_MAX_DIGITS]; |
| |
| for (i = 0; i < ndigits; i++) |
| tmp[ndigits - 1 - i] = l_get_be64(&bytes[i]); |
| |
| memcpy(dest, tmp, ndigits * 8); |
| } |
| |
| void _ecc_native2be(uint64_t *dest, const uint64_t *native, |
| unsigned int ndigits) |
| { |
| unsigned int i; |
| uint64_t tmp[L_ECC_MAX_DIGITS]; |
| |
| for (i = 0; i < ndigits; i++) |
| l_put_be64(native[ndigits - 1 - i], &tmp[i]); |
| |
| memcpy(dest, tmp, ndigits * 8); |
| } |
| |
| static void ecc_compute_y_sqr(const struct l_ecc_curve *curve, |
| uint64_t *y_sqr, const 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); |
| |
| memcpy(y_sqr, sum, curve->ndigits * 8); |
| } |
| |
| /* |
| * Compute sqrt(y^2) |
| * Since our prime p satisfies p = 3 (mod 4), we can say: |
| * |
| * y = (y^2)^((p + 1) / 4) |
| * |
| * This avoids the need for a square root function. |
| */ |
| static void ecc_compute_sqrt(const struct l_ecc_curve *curve, |
| uint64_t *y, const uint64_t *y_sqr) |
| { |
| uint64_t expo[L_ECC_MAX_DIGITS]; |
| uint64_t one[L_ECC_MAX_DIGITS] = { 1ull }; |
| |
| memcpy(expo, curve->p, curve->ndigits * 8); |
| |
| /* (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, y_sqr, expo, curve->p, curve->ndigits); |
| } |
| |
| bool _ecc_compute_y(const struct l_ecc_curve *curve, uint64_t *y, |
| const uint64_t *x) |
| { |
| uint64_t sum[L_ECC_MAX_DIGITS] = { 0 }; |
| uint64_t check[L_ECC_MAX_DIGITS] = { 0 }; |
| |
| /* y = sqrt(x^3 + ax + b) (mod p) */ |
| ecc_compute_y_sqr(curve, sum, x); |
| ecc_compute_sqrt(curve, y, sum); |
| |
| /* 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; |
| } |
| |
| /* |
| * 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." |
| */ |
| void _ecc_calculate_p2(const struct l_ecc_curve *curve, uint64_t *p2) |
| { |
| uint64_t one[L_ECC_MAX_DIGITS] = { 1 }; |
| |
| _vli_mod_sub(p2, curve->p, one, curve->p, curve->ndigits); |
| _vli_rshift1(p2, curve->ndigits); |
| } |
| |
| /* |
| * 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(const struct l_ecc_curve *curve, uint64_t *x, |
| struct l_ecc_point *point) |
| { |
| uint64_t y_min[L_ECC_MAX_DIGITS]; |
| uint64_t p2[L_ECC_MAX_DIGITS]; |
| |
| if (!_ecc_compute_y(curve, y_min, (uint64_t *)x)) |
| return false; |
| |
| _ecc_calculate_p2(curve, p2); |
| |
| if (_vli_cmp(y_min, p2, curve->ndigits) >= 0) |
| _vli_mod_sub(point->y, curve->p, y_min, |
| curve->p, curve->ndigits); |
| else |
| memcpy(point->y, y_min, curve->ndigits * 8); |
| |
| memcpy(point->x, x, curve->ndigits * 8); |
| |
| return true; |
| } |
| |
| /* (rx, ry) = (px, py) + (qx, qy) */ |
| void _ecc_point_add(struct l_ecc_point *ret, const struct l_ecc_point *p, |
| const 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->curve->ndigits; |
| |
| memset(s, 0, ndigits * 8); |
| |
| /* 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); |
| |
| memcpy(ret->x, resx, ndigits * 8); |
| memcpy(ret->y, resy, ndigits * 8); |
| } |
| |
| /* result = (base ^ exp) % p */ |
| void _vli_mod_exp(uint64_t *result, const uint64_t *base, const 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 }; |
| |
| memcpy(n, base, ndigits * 8); |
| |
| 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); |
| memcpy(r, tmp, ndigits * 8); |
| } |
| |
| _vli_mod_mult_fast(tmp, n, n, mod, ndigits); |
| memcpy(n, tmp, ndigits * 8); |
| } |
| } |
| |
| memcpy(result, r, ndigits * 8); |
| } |
| |
| __attribute__((noinline)) static int vli_equal(const uint64_t *a, |
| const uint64_t *b, |
| unsigned int ndigits) |
| { |
| uint64_t diff = 0; |
| unsigned int i; |
| |
| for (i = 0; i < ndigits; i++) { |
| diff |= a[i] ^ b[i]; |
| __asm__ ("" : "=r" (diff) : "0" (diff)); |
| } |
| |
| return (~diff & (diff - 1)) >> 63; |
| } |
| |
| 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; |
| if (_vli_cmp(tmp, _0, ndigits) == 0) |
| return 0; |
| return -1; |
| } |
| |
| bool _vli_is_zero_or_one(const uint64_t *vli, unsigned int ndigits) |
| { |
| uint64_t _1[L_ECC_MAX_DIGITS] = { 1ull }; |
| int ret; |
| |
| ret = secure_select(vli_equal(vli, _1, ndigits), true, false); |
| ret = secure_select(l_secure_memeq(vli, ndigits * 8, 0), true, ret); |
| |
| return ret; |
| } |
| |
| LIB_EXPORT struct l_ecc_point *l_ecc_point_new(const struct l_ecc_curve *curve) |
| { |
| struct l_ecc_point *p = l_new(struct l_ecc_point, 1); |
| |
| p->curve = curve; |
| |
| return p; |
| } |
| |
| LIB_EXPORT struct l_ecc_point *l_ecc_point_from_data( |
| const struct l_ecc_curve *curve, |
| enum l_ecc_point_type type, |
| const void *data, size_t len) |
| { |
| struct l_ecc_point *p; |
| size_t bytes = curve->ndigits * 8; |
| uint64_t tmp[L_ECC_MAX_DIGITS]; |
| bool sub; |
| |
| if (!data) |
| return NULL; |
| |
| /* Verify the data length matches a full point or X coordinate */ |
| if (type == L_ECC_POINT_TYPE_FULL) { |
| if (len != bytes * 2) |
| return NULL; |
| } else if (len != bytes) |
| return NULL; |
| |
| p = l_ecc_point_new(curve); |
| |
| _ecc_be2native(p->x, (void *) data, curve->ndigits); |
| |
| switch (type) { |
| case L_ECC_POINT_TYPE_COMPLIANT: |
| if (!decode_point(curve, p->x, p)) |
| goto failed; |
| |
| break; |
| case L_ECC_POINT_TYPE_COMPRESSED_BIT0: |
| case L_ECC_POINT_TYPE_COMPRESSED_BIT1: |
| if (!_ecc_compute_y(curve, p->y, p->x)) |
| goto failed; |
| |
| sub = secure_select(type == L_ECC_POINT_TYPE_COMPRESSED_BIT0, |
| !(p->y[0] & 1), p->y[0] & 1); |
| |
| _vli_mod_sub(tmp, curve->p, p->y, curve->p, curve->ndigits); |
| |
| l_secure_select(sub, tmp, p->y, p->y, curve->ndigits * 8); |
| |
| break; |
| case L_ECC_POINT_TYPE_FULL: |
| _ecc_be2native(p->y, (void *) data + bytes, curve->ndigits); |
| |
| if (!ecc_valid_point(p)) |
| goto failed; |
| |
| break; |
| } |
| |
| return p; |
| |
| failed: |
| l_free(p); |
| return NULL; |
| } |
| |
| LIB_EXPORT struct l_ecc_point *l_ecc_point_from_sswu( |
| const struct l_ecc_scalar *u) |
| { |
| const struct l_ecc_curve *curve = u->curve; |
| unsigned int ndigits = curve->ndigits; |
| uint64_t z[L_ECC_MAX_DIGITS] = { abs(curve->z) }; |
| uint64_t _3[L_ECC_MAX_DIGITS] = { 3ull }; /* -a = 3 */ |
| uint64_t u2z[L_ECC_MAX_DIGITS]; |
| uint64_t t1[L_ECC_MAX_DIGITS]; |
| uint64_t t2[L_ECC_MAX_DIGITS]; |
| uint64_t m[L_ECC_MAX_DIGITS]; |
| uint64_t t[L_ECC_MAX_DIGITS]; |
| uint64_t x1l[L_ECC_MAX_DIGITS]; |
| uint64_t x1r[L_ECC_MAX_DIGITS]; |
| uint64_t x1[L_ECC_MAX_DIGITS]; |
| uint64_t gx1[L_ECC_MAX_DIGITS]; |
| uint64_t x2[L_ECC_MAX_DIGITS]; |
| uint64_t gx2[L_ECC_MAX_DIGITS]; |
| /* reuse m/t/x1l,x1r, they are unused by the time x/v/y/p-y is needed */ |
| uint64_t *x = m; |
| uint64_t *v = t; |
| uint64_t *yl = x1l; |
| uint64_t *yr = x1r; |
| bool l; |
| struct l_ecc_point *P; |
| |
| /* |
| * m = (z^2 * u^4 + z * u^2) modulo p |
| * u2z = u^2 * z |
| * t2 = u2z^2 |
| * m = t2 - u2z since for all our curves z is negative |
| */ |
| _vli_mod_square_fast(u2z, u->c, curve->p, ndigits); |
| _vli_mod_mult_fast(u2z, u2z, z, curve->p, ndigits); |
| _vli_mod_square_fast(t2, u2z, curve->p, ndigits); |
| _vli_mod_sub(m, t2, u2z, curve->p, ndigits); |
| |
| /* |
| * l = CEQ(m, 0) |
| * t = inv0(m) where inv0(x) is calculated as x^(p-2) modulo p |
| */ |
| l = l_secure_memeq(m, sizeof(m), 0); |
| |
| memset(t2, 0, sizeof(t2)); |
| t2[0] = 2ull; |
| _vli_mod_sub(t1, curve->p, t2, curve->p, ndigits); |
| _vli_mod_exp(t, m, t1, curve->p, ndigits); |
| |
| /* Calculate: b / z*a, both z and a are negative */ |
| _vli_mod_mult_fast(t1, z, _3, curve->p, ndigits); |
| _vli_mod_inv(t1, t1, curve->p, ndigits); |
| _vli_mod_mult_fast(x1l, curve->b, t1, curve->p, ndigits); |
| |
| /* t = 1 + t */ |
| memset(t2, 0, sizeof(t2)); |
| t2[0] = 1ull; |
| _vli_mod_add(t, t, t2, curve->p, ndigits); |
| |
| /* t1 = 1 / a */ |
| _vli_mod_inv(t1, _3, curve->p, ndigits); |
| |
| /* x1r = b * t1 * t */ |
| _vli_mod_mult_fast(x1r, curve->b, t1, curve->p, ndigits); |
| _vli_mod_mult_fast(x1r, x1r, t, curve->p, ndigits); |
| |
| /* x1 = CSEL(l, (b / (z*a) modulo p), ((-b/a) * (1 + t)) modulo p) */ |
| l_secure_select(l, x1l, x1r, x1, ndigits * 8); |
| |
| /* gx1 = (x1^3 + a*x1 + b) modulo p */ |
| ecc_compute_y_sqr(curve, gx1, x1); |
| |
| /* x2 = (z*u^2*x1) modulo p, z is negative, hence the second op */ |
| _vli_mod_mult_fast(x2, u2z, x1, curve->p, ndigits); |
| _vli_mod_sub(x2, curve->p, x2, curve->p, ndigits); |
| |
| /* gx2 = (x2^3 + a*x2 + b) modulo p */ |
| ecc_compute_y_sqr(curve, gx2, x2); |
| |
| /* |
| * l = gx1 is a quadratic residue modulo p |
| * x is a quadratic residue if x^((p-1)/2) modulo p is zero or one |
| */ |
| _vli_mod_sub(t1, curve->p, t2, curve->p, ndigits); |
| _vli_rshift1(t1, ndigits); |
| _vli_mod_exp(t2, gx1, t1, curve->p, ndigits); |
| l = _vli_is_zero_or_one(t2, ndigits); |
| |
| /* v = CSEL(l, gx1, gx2) */ |
| l_secure_select(l, gx1, gx2, v, ndigits * 8); |
| /* x = CSEL(l, x1, x2) */ |
| l_secure_select(l, x1, x2, x, ndigits * 8); |
| /* y = sqrt(v) */ |
| ecc_compute_sqrt(curve, yl, v); |
| /* l = CEQ(LSB(u), LSB(y)) */ |
| l = !((u->c[0] & 1ull) ^ (yl[0] & 1ull)); |
| |
| /* p - y */ |
| _vli_mod_sub(yr, curve->p, yl, curve->p, ndigits); |
| |
| /* P = CSEL(l, (x,y), (x, p-y)) */ |
| P = l_ecc_point_new(curve); |
| memcpy(P->x, x, ndigits * 8); |
| l_secure_select(l, yl, yr, P->y, ndigits * 8); |
| |
| return P; |
| } |
| |
| LIB_EXPORT struct l_ecc_point *l_ecc_point_clone(const struct l_ecc_point *p) |
| { |
| if (!p) |
| return NULL; |
| |
| return l_memdup(p, sizeof(*p)); |
| } |
| |
| LIB_EXPORT const struct l_ecc_curve *l_ecc_point_get_curve( |
| const struct l_ecc_point *p) |
| { |
| if (!p) |
| return NULL; |
| |
| return p->curve; |
| } |
| |
| LIB_EXPORT ssize_t l_ecc_point_get_x(const struct l_ecc_point *p, void *x, |
| size_t xlen) |
| { |
| if (xlen < p->curve->ndigits * 8) |
| return -EMSGSIZE; |
| |
| _ecc_native2be(x, p->x, p->curve->ndigits); |
| |
| return p->curve->ndigits * 8; |
| } |
| |
| LIB_EXPORT ssize_t l_ecc_point_get_y(const struct l_ecc_point *p, void *y, |
| size_t ylen) |
| { |
| if (ylen < p->curve->ndigits * 8) |
| return -EMSGSIZE; |
| |
| _ecc_native2be(y, p->y, p->curve->ndigits); |
| |
| return p->curve->ndigits * 8; |
| } |
| |
| LIB_EXPORT bool l_ecc_point_y_isodd(const struct l_ecc_point *p) |
| { |
| return p->y[0] & 1; |
| } |
| |
| LIB_EXPORT ssize_t l_ecc_point_get_data(const struct l_ecc_point *p, void *buf, |
| size_t len) |
| { |
| if (len < (p->curve->ndigits * 8) * 2) |
| return -EMSGSIZE; |
| |
| _ecc_native2be(buf, (uint64_t *) p->x, p->curve->ndigits); |
| _ecc_native2be(buf + (p->curve->ndigits * 8), (uint64_t *) p->y, |
| p->curve->ndigits); |
| |
| return (p->curve->ndigits * 8) * 2; |
| } |
| |
| LIB_EXPORT void l_ecc_point_free(struct l_ecc_point *p) |
| { |
| if (unlikely(!p)) |
| return; |
| |
| explicit_bzero(p->x, p->curve->ndigits * 8); |
| explicit_bzero(p->y, p->curve->ndigits * 8); |
| l_free(p); |
| } |
| |
| struct l_ecc_scalar *_ecc_constant_new(const struct l_ecc_curve *curve, |
| const void *buf, size_t len) |
| { |
| struct l_ecc_scalar *c; |
| |
| if (unlikely(!curve)) |
| return NULL; |
| |
| if (buf && len != curve->ndigits * 8) |
| return NULL; |
| |
| c = l_new(struct l_ecc_scalar, 1); |
| |
| c->curve = curve; |
| |
| if (buf) |
| memcpy(c->c, buf, len); |
| |
| return c; |
| } |
| |
| LIB_EXPORT struct l_ecc_scalar *l_ecc_scalar_new( |
| const struct l_ecc_curve *curve, |
| const void *buf, size_t len) |
| { |
| struct l_ecc_scalar *c; |
| |
| c = _ecc_constant_new(curve, NULL, 0); |
| if (!c) |
| return NULL; |
| |
| if (!buf) |
| return c; |
| |
| _ecc_be2native(c->c, buf, curve->ndigits); |
| |
| if (!_vli_is_zero_or_one(c->c, curve->ndigits) && |
| secure_memcmp_64(curve->n, c->c, curve->ndigits) > 0) |
| return c; |
| |
| l_ecc_scalar_free(c); |
| |
| return NULL; |
| } |
| |
| /* |
| * Build a scalar = value modulo p where p is the prime number for a given |
| * curve. bytes can contain a numer with up to 2x number of digits as the |
| * curve. This is used in Hash to Curve calculations. |
| */ |
| LIB_EXPORT struct l_ecc_scalar *l_ecc_scalar_new_modp( |
| const struct l_ecc_curve *curve, |
| const void *bytes, size_t len) |
| { |
| struct l_ecc_scalar *c; |
| uint64_t tmp[2 * L_ECC_MAX_DIGITS]; |
| unsigned int ndigits = len / 8; |
| |
| if (!bytes) |
| return NULL; |
| |
| if (len % 8) |
| return NULL; |
| |
| if (ndigits > curve->ndigits * 2) |
| return NULL; |
| |
| c = _ecc_constant_new(curve, NULL, 0); |
| if (!c) |
| return NULL; |
| |
| memset(tmp, 0, sizeof(tmp)); |
| _ecc_be2native(tmp, bytes, ndigits); |
| |
| _vli_mmod_fast(c->c, tmp, curve->p, curve->ndigits); |
| |
| if (!_vli_is_zero_or_one(c->c, curve->ndigits) && |
| secure_memcmp_64(curve->n, c->c, curve->ndigits) > 0) |
| return c; |
| |
| l_ecc_scalar_free(c); |
| |
| return NULL; |
| } |
| |
| /* |
| * Takes a buffer of the same size as the curve and scales it to a range |
| * 1..n using value = (value mod (n - 1)) + 1. For the curves we support |
| * this can be done using a subtraction operation due to the size of n |
| */ |
| LIB_EXPORT struct l_ecc_scalar *l_ecc_scalar_new_reduced_1_to_n( |
| const struct l_ecc_curve *curve, |
| const void *buf, size_t len) |
| { |
| uint64_t _1[L_ECC_MAX_DIGITS] = { 1ull }; |
| uint64_t tmp[L_ECC_MAX_DIGITS]; |
| struct l_ecc_scalar *c; |
| |
| if (!buf) |
| return NULL; |
| |
| if (len != curve->ndigits * 8) |
| return NULL; |
| |
| c = _ecc_constant_new(curve, NULL, 0); |
| if (!c) |
| return NULL; |
| |
| _vli_sub(tmp, curve->n, _1, curve->ndigits); |
| _ecc_be2native(c->c, buf, curve->ndigits); |
| |
| if (_vli_cmp(c->c, tmp, curve->ndigits) >= 0) |
| _vli_sub(c->c, c->c, tmp, curve->ndigits); |
| |
| _vli_add(c->c, c->c, _1, curve->ndigits); |
| |
| return c; |
| } |
| |
| LIB_EXPORT struct l_ecc_scalar *l_ecc_scalar_new_random( |
| const struct l_ecc_curve *curve) |
| { |
| uint64_t r[L_ECC_MAX_DIGITS]; |
| |
| l_getrandom(r, curve->ndigits * 8); |
| |
| while (_vli_cmp(r, curve->p, curve->ndigits) > 0 || |
| _vli_cmp(r, curve->n, curve->ndigits) > 0 || |
| _vli_is_zero_or_one(r, curve->ndigits)) |
| l_getrandom(r, curve->ndigits * 8); |
| |
| return _ecc_constant_new(curve, r, curve->ndigits * 8); |
| } |
| |
| LIB_EXPORT ssize_t l_ecc_scalar_get_data(const struct l_ecc_scalar *c, |
| void *buf, size_t len) |
| { |
| if (len < c->curve->ndigits * 8) |
| return -EMSGSIZE; |
| |
| _ecc_native2be(buf, (uint64_t *) c->c, c->curve->ndigits); |
| |
| return c->curve->ndigits * 8; |
| } |
| |
| LIB_EXPORT void l_ecc_scalar_free(struct l_ecc_scalar *c) |
| { |
| if (unlikely(!c)) |
| return; |
| |
| explicit_bzero(c->c, c->curve->ndigits * 8); |
| l_free(c); |
| } |
| |
| LIB_EXPORT bool l_ecc_scalar_add(struct l_ecc_scalar *ret, |
| const struct l_ecc_scalar *a, |
| const struct l_ecc_scalar *b, |
| const struct l_ecc_scalar *mod) |
| { |
| if (unlikely(!ret || !a || !b || !mod)) |
| return false; |
| |
| _vli_mod_add(ret->c, a->c, b->c, mod->c, a->curve->ndigits); |
| |
| return true; |
| } |
| |
| LIB_EXPORT bool l_ecc_point_multiply(struct l_ecc_point *ret, |
| const struct l_ecc_scalar *scalar, |
| const struct l_ecc_point *point) |
| { |
| if (unlikely(!ret || !scalar || !point)) |
| return false; |
| |
| _ecc_point_mult(ret, point, scalar->c, NULL, scalar->curve->p); |
| |
| return true; |
| } |
| |
| LIB_EXPORT bool l_ecc_point_add(struct l_ecc_point *ret, |
| const struct l_ecc_point *a, |
| const struct l_ecc_point *b) |
| { |
| if (unlikely(!ret || !a || !b)) |
| return false; |
| |
| _ecc_point_add(ret, a, b, a->curve->p); |
| |
| return true; |
| } |
| |
| LIB_EXPORT bool l_ecc_point_inverse(struct l_ecc_point *p) |
| { |
| if (unlikely(!p)) |
| return false; |
| |
| _vli_mod_sub(p->y, p->curve->p, p->y, p->curve->p, p->curve->ndigits); |
| |
| return true; |
| } |
| |
| LIB_EXPORT bool l_ecc_scalar_multiply(struct l_ecc_scalar *ret, |
| const struct l_ecc_scalar *a, |
| const struct l_ecc_scalar *b) |
| { |
| if (unlikely(!ret || !a || !b)) |
| return false; |
| |
| _vli_mod_mult_fast(ret->c, a->c, b->c, a->curve->p, a->curve->ndigits); |
| |
| return true; |
| } |
| |
| LIB_EXPORT int l_ecc_scalar_legendre(struct l_ecc_scalar *value) |
| { |
| if (unlikely(!value)) |
| return -1; |
| |
| return _vli_legendre(value->c, value->curve->p, value->curve->ndigits); |
| } |
| |
| LIB_EXPORT bool l_ecc_scalar_sum_x(struct l_ecc_scalar *ret, |
| const struct l_ecc_scalar *x) |
| { |
| if (unlikely(!ret || !x)) |
| return false; |
| |
| ecc_compute_y_sqr(x->curve, ret->c, x->c); |
| |
| return true; |
| } |
| |
| LIB_EXPORT bool l_ecc_scalars_are_equal(const struct l_ecc_scalar *a, |
| const struct l_ecc_scalar *b) |
| { |
| if (unlikely(!a || !b)) |
| return false; |
| |
| return (memcmp(a->c, b->c, a->curve->ndigits * 8) == 0); |
| } |
| |
| LIB_EXPORT bool l_ecc_points_are_equal(const struct l_ecc_point *a, |
| const struct l_ecc_point *b) |
| { |
| if (unlikely(!a || !b)) |
| return false; |
| |
| return ((memcmp(a->x, b->x, a->curve->ndigits * 8) == 0) && |
| (memcmp(a->y, b->y, a->curve->ndigits * 8) == 0)); |
| } |