/* * Copyright (c) 2013, 2014 Kenneth MacKay. All rights reserved. * Copyright (c) 2019 Vitaly Chikunov <vt@altlinux.org> * * 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. */ #include <crypto/ecc_curve.h>#include <linux/module.h>#include <linux/random.h>#include <linux/slab.h>#include <linux/swab.h>#include <linux/fips.h>#include <crypto/ecdh.h>#include <crypto/rng.h>#include <crypto/internal/ecc.h>#include <linux/unaligned.h>#include <linux/ratelimit.h> #include "ecc_curve_defs.h" typedef struct { u64 m_low; u64 m_high;} uint128_t; /* Returns curv25519 curve param */const struct ecc_curve *ecc_get_curve25519(void){ return &ecc_25519;}EXPORT_SYMBOL(ecc_get_curve25519); const struct ecc_curve *ecc_get_curve(unsigned int curve_id){ switch (curve_id) { /* In FIPS mode only allow P256 and higher */ case ECC_CURVE_NIST_P192: return fips_enabled ? NULL : &nist_p192; case ECC_CURVE_NIST_P256: return &nist_p256; case ECC_CURVE_NIST_P384: return &nist_p384; case ECC_CURVE_NIST_P521: return &nist_p521; default: return NULL; }}EXPORT_SYMBOL(ecc_get_curve); void ecc_digits_from_bytes(const u8 *in, unsigned int nbytes, u64 *out, unsigned int ndigits){ int diff = ndigits - DIV_ROUND_UP_POW2(nbytes, sizeof(u64)); unsigned int o = nbytes & 7; __be64 msd = 0; /* diff > 0: not enough input bytes: set most significant digits to 0 */ if (diff > 0) { ndigits -= diff; memset(&out[ndigits], 0, diff * sizeof(u64)); } if (o) { memcpy((u8 *)&msd + sizeof(msd) - o, in, o); out[--ndigits] = be64_to_cpu(msd); in += o; } ecc_swap_digits(in, out, ndigits);}EXPORT_SYMBOL(ecc_digits_from_bytes); struct ecc_point *ecc_alloc_point(unsigned int ndigits){ struct ecc_point *p; size_t ndigits_sz; if (!ndigits) return NULL; p = kmalloc_obj(*p); if (!p) return NULL; ndigits_sz = ndigits * sizeof(u64); p->x = kmalloc(ndigits_sz, GFP_KERNEL); if (!p->x) goto err_alloc_x; p->y = kmalloc(ndigits_sz, GFP_KERNEL); if (!p->y) goto err_alloc_y; p->ndigits = ndigits; return p; err_alloc_y: kfree(p->x);err_alloc_x: kfree(p); return NULL;}EXPORT_SYMBOL(ecc_alloc_point); void ecc_free_point(struct ecc_point *p){ if (!p) return; kfree_sensitive(p->x); kfree_sensitive(p->y); kfree_sensitive(p);}EXPORT_SYMBOL(ecc_free_point); static void vli_clear(u64 *vli, unsigned int ndigits){ int i; for (i = 0; i < ndigits; i++) vli[i] = 0;} /* Returns true if vli == 0, false otherwise. */bool vli_is_zero(const u64 *vli, unsigned int ndigits){ int i; for (i = 0; i < ndigits; i++) { if (vli[i]) return false; } return true;}EXPORT_SYMBOL(vli_is_zero); /* Returns nonzero if bit of vli is set. */static u64 vli_test_bit(const u64 *vli, unsigned int bit){ return (vli[bit / 64] & ((u64)1 << (bit % 64)));} static bool vli_is_negative(const u64 *vli, unsigned int ndigits){ return vli_test_bit(vli, ndigits * 64 - 1);} /* Counts the number of 64-bit "digits" in vli. */static unsigned int vli_num_digits(const u64 *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. */unsigned int vli_num_bits(const u64 *vli, unsigned int ndigits){ unsigned int i, num_digits; u64 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);}EXPORT_SYMBOL(vli_num_bits); /* Set dest from unaligned bit string src. */void vli_from_be64(u64 *dest, const void *src, unsigned int ndigits){ int i; const u64 *from = src; for (i = 0; i < ndigits; i++) dest[i] = get_unaligned_be64(&from[ndigits - 1 - i]);}EXPORT_SYMBOL(vli_from_be64); void vli_from_le64(u64 *dest, const void *src, unsigned int ndigits){ int i; const u64 *from = src; for (i = 0; i < ndigits; i++) dest[i] = get_unaligned_le64(&from[i]);}EXPORT_SYMBOL(vli_from_le64); /* Sets dest = src. */static void vli_set(u64 *dest, const u64 *src, unsigned int ndigits){ int i; for (i = 0; i < ndigits; i++) dest[i] = src[i];} /* Returns sign of left - right. */int vli_cmp(const u64 *left, const u64 *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;}EXPORT_SYMBOL(vli_cmp); /* Computes result = in << c, returning carry. Can modify in place * (if result == in). 0 < shift < 64. */static u64 vli_lshift(u64 *result, const u64 *in, unsigned int shift, unsigned int ndigits){ u64 carry = 0; int i; for (i = 0; i < ndigits; i++) { u64 temp = in[i]; result[i] = (temp << shift) | carry; carry = temp >> (64 - shift); } return carry;} /* Computes vli = vli >> 1. */static void vli_rshift1(u64 *vli, unsigned int ndigits){ u64 *end = vli; u64 carry = 0; vli += ndigits; while (vli-- > end) { u64 temp = *vli; *vli = (temp >> 1) | carry; carry = temp << 63; }} #ifdef __has_builtin#if __has_builtin(__builtin_addcll)#define USE_BUILTIN_ADDC#endif#endif /* Computes result = left + right + carry_in and updates carry_out */static inline void add_carry(u64 left, u64 right, u64 *result, u64 carry_in, u64 *carry_out){#ifdef USE_BUILTIN_ADDC *result = __builtin_addcll(left, right, carry_in, carry_out);#else u64 sum1, sum2; u64 c1 = __builtin_uaddll_overflow(left, right, &sum1); u64 c2 = __builtin_uaddll_overflow(sum1, carry_in, &sum2); *result = sum2; *carry_out = c1 | c2;#endif} #ifdef __has_builtin#if __has_builtin(__builtin_subcll)#define USE_BUILTIN_SUBC#endif#endif /* Computes result = left - right - borrow_in and updates borrow_out */static inline void sub_borrow(u64 left, u64 right, u64 *result, u64 borrow_in, u64 *borrow_out){#ifdef USE_BUILTIN_SUBC *result = __builtin_subcll(left, right, borrow_in, borrow_out);#else u64 diff1, diff2; u64 b1 = __builtin_usubll_overflow(left, right, &diff1); u64 b2 = __builtin_usubll_overflow(diff1, borrow_in, &diff2); *result = diff2; *borrow_out = b1 | b2;#endif} /* Computes result = left + right, returning carry. Can modify in place. */static u64 vli_add(u64 *result, const u64 *left, const u64 *right, unsigned int ndigits){ u64 carry = 0; int i; for (i = 0; i < ndigits; i++) add_carry(left[i], right[i], &result[i], carry, &carry); return carry;} /* Computes result = left + right, returning carry. Can modify in place. */static u64 vli_uadd(u64 *result, const u64 *left, u64 right, unsigned int ndigits){ u64 carry; int i; if (ndigits == 0) return right; carry = __builtin_uaddll_overflow(left[0], right, &result[0]); for (i = 1; i < ndigits; i++) carry = __builtin_uaddll_overflow(left[i], carry, &result[i]); return carry;} /* Computes result = left - right, returning borrow. Can modify in place. */u64 vli_sub(u64 *result, const u64 *left, const u64 *right, unsigned int ndigits){ u64 borrow = 0; int i; for (i = 0; i < ndigits; i++) sub_borrow(left[i], right[i], &result[i], borrow, &borrow); return borrow;}EXPORT_SYMBOL(vli_sub); /* Computes result = left - right, returning borrow. Can modify in place. */static u64 vli_usub(u64 *result, const u64 *left, u64 right, unsigned int ndigits){ u64 borrow; int i; if (ndigits == 0) return right; borrow = __builtin_usubll_overflow(left[0], right, &result[0]); for (i = 1; i < ndigits; i++) borrow = __builtin_usubll_overflow(left[i], borrow, &result[i]); return borrow;} static uint128_t mul_64_64(u64 left, u64 right){ uint128_t result;#if defined(CONFIG_ARCH_SUPPORTS_INT128) unsigned __int128 m = (unsigned __int128)left * right; result.m_low = m; result.m_high = m >> 64;#else u64 a0 = left & 0xffffffffull; u64 a1 = left >> 32; u64 b0 = right & 0xffffffffull; u64 b1 = right >> 32; u64 m0 = a0 * b0; u64 m1 = a0 * b1; u64 m2 = a1 * b0; u64 m3 = a1 * b1; m2 += (m0 >> 32); m2 += m1; /* Overflow */ if (m2 < m1) m3 += 0x100000000ull; result.m_low = (m0 & 0xffffffffull) | (m2 << 32); result.m_high = m3 + (m2 >> 32);#endif return result;} /* Calculate addition with overflow checking. Returns true on wrap-around, * false otherwise. */static bool check_add_128_128_overflow(uint128_t *result, uint128_t a, uint128_t b){ bool carry; result->m_low = a.m_low + b.m_low; carry = (result->m_low < a.m_low); result->m_high = a.m_high + b.m_high + carry; /* Using constant-time bitwise arithmetic to prevent timing * side-channels. */ carry = (result->m_high < a.m_high) | ((result->m_high == a.m_high) & carry); return carry;} static void vli_mult(u64 *result, const u64 *left, const u64 *right, unsigned int ndigits){ uint128_t r01 = { 0, 0 }; u64 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]); r2 += check_add_128_128_overflow(&r01, r01, product); } result[k] = r01.m_low; r01.m_low = r01.m_high; r01.m_high = r2; r2 = 0; } result[ndigits * 2 - 1] = r01.m_low;} /* Compute product = left * right, for a small right value. */static void vli_umult(u64 *result, const u64 *left, u32 right, unsigned int ndigits){ uint128_t r01 = { 0 }; unsigned int k; for (k = 0; k < ndigits; k++) { uint128_t product; product = mul_64_64(left[k], right); check_add_128_128_overflow(&r01, r01, product); /* no carry */ result[k] = r01.m_low; r01.m_low = r01.m_high; r01.m_high = 0; } result[k] = r01.m_low; for (++k; k < ndigits * 2; k++) result[k] = 0;} static void vli_square(u64 *result, const u64 *left, unsigned int ndigits){ uint128_t r01 = { 0, 0 }; u64 r2 = 0; int i, k;Lines 1–500 of 1736. Load more
/* * Copyright (c) 2013, 2014 Kenneth MacKay. All rights reserved. * Copyright (c) 2019 Vitaly Chikunov <vt@altlinux.org> * * 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. */ #include <crypto/ecc_curve.h> #include <linux/module.h> #include <linux/random.h> #include <linux/slab.h> #include <linux/swab.h> #include <linux/fips.h> #include <crypto/ecdh.h> #include <crypto/rng.h> #include <crypto/internal/ecc.h> #include <linux/unaligned.h> #include <linux/ratelimit.h> #include "ecc_curve_defs.h" typedef struct { u64 m_low; u64 m_high; } uint128_t; /* Returns curv25519 curve param */ const struct ecc_curve *ecc_get_curve25519(void) { return &ecc_25519; } EXPORT_SYMBOL(ecc_get_curve25519); const struct ecc_curve *ecc_get_curve(unsigned int curve_id) { switch (curve_id) { /* In FIPS mode only allow P256 and higher */ case ECC_CURVE_NIST_P192: return fips_enabled ? NULL : &nist_p192; case ECC_CURVE_NIST_P256: return &nist_p256; case ECC_CURVE_NIST_P384: return &nist_p384; case ECC_CURVE_NIST_P521: return &nist_p521; default: return NULL; } } EXPORT_SYMBOL(ecc_get_curve); void ecc_digits_from_bytes(const u8 *in, unsigned int nbytes, u64 *out, unsigned int ndigits) { int diff = ndigits - DIV_ROUND_UP_POW2(nbytes, sizeof(u64)); unsigned int o = nbytes & 7; __be64 msd = 0; /* diff > 0: not enough input bytes: set most significant digits to 0 */ if (diff > 0) { ndigits -= diff; memset(&out[ndigits], 0, diff * sizeof(u64)); } if (o) { memcpy((u8 *)&msd + sizeof(msd) - o, in, o); out[--ndigits] = be64_to_cpu(msd); in += o; } ecc_swap_digits(in, out, ndigits); } EXPORT_SYMBOL(ecc_digits_from_bytes); struct ecc_point *ecc_alloc_point(unsigned int ndigits) { struct ecc_point *p; size_t ndigits_sz; if (!ndigits) return NULL; p = kmalloc_obj(*p); if (!p) return NULL; ndigits_sz = ndigits * sizeof(u64); p->x = kmalloc(ndigits_sz, GFP_KERNEL); if (!p->x) goto err_alloc_x; p->y = kmalloc(ndigits_sz, GFP_KERNEL); if (!p->y) goto err_alloc_y; p->ndigits = ndigits; return p; err_alloc_y: kfree(p->x); err_alloc_x: kfree(p); return NULL; } EXPORT_SYMBOL(ecc_alloc_point); void ecc_free_point(struct ecc_point *p) { if (!p) return; kfree_sensitive(p->x); kfree_sensitive(p->y); kfree_sensitive(p); } EXPORT_SYMBOL(ecc_free_point); static void vli_clear(u64 *vli, unsigned int ndigits) { int i; for (i = 0; i < ndigits; i++) vli[i] = 0; } /* Returns true if vli == 0, false otherwise. */ bool vli_is_zero(const u64 *vli, unsigned int ndigits) { int i; for (i = 0; i < ndigits; i++) { if (vli[i]) return false; } return true; } EXPORT_SYMBOL(vli_is_zero); /* Returns nonzero if bit of vli is set. */ static u64 vli_test_bit(const u64 *vli, unsigned int bit) { return (vli[bit / 64] & ((u64)1 << (bit % 64))); } static bool vli_is_negative(const u64 *vli, unsigned int ndigits) { return vli_test_bit(vli, ndigits * 64 - 1); } /* Counts the number of 64-bit "digits" in vli. */ static unsigned int vli_num_digits(const u64 *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. */ unsigned int vli_num_bits(const u64 *vli, unsigned int ndigits) { unsigned int i, num_digits; u64 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); } EXPORT_SYMBOL(vli_num_bits); /* Set dest from unaligned bit string src. */ void vli_from_be64(u64 *dest, const void *src, unsigned int ndigits) { int i; const u64 *from = src; for (i = 0; i < ndigits; i++) dest[i] = get_unaligned_be64(&from[ndigits - 1 - i]); } EXPORT_SYMBOL(vli_from_be64); void vli_from_le64(u64 *dest, const void *src, unsigned int ndigits) { int i; const u64 *from = src; for (i = 0; i < ndigits; i++) dest[i] = get_unaligned_le64(&from[i]); } EXPORT_SYMBOL(vli_from_le64); /* Sets dest = src. */ static void vli_set(u64 *dest, const u64 *src, unsigned int ndigits) { int i; for (i = 0; i < ndigits; i++) dest[i] = src[i]; } /* Returns sign of left - right. */ int vli_cmp(const u64 *left, const u64 *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; } EXPORT_SYMBOL(vli_cmp); /* Computes result = in << c, returning carry. Can modify in place * (if result == in). 0 < shift < 64. */ static u64 vli_lshift(u64 *result, const u64 *in, unsigned int shift, unsigned int ndigits) { u64 carry = 0; int i; for (i = 0; i < ndigits; i++) { u64 temp = in[i]; result[i] = (temp << shift) | carry; carry = temp >> (64 - shift); } return carry; } /* Computes vli = vli >> 1. */ static void vli_rshift1(u64 *vli, unsigned int ndigits) { u64 *end = vli; u64 carry = 0; vli += ndigits; while (vli-- > end) { u64 temp = *vli; *vli = (temp >> 1) | carry; carry = temp << 63; } } #ifdef __has_builtin #if __has_builtin(__builtin_addcll) #define USE_BUILTIN_ADDC #endif #endif /* Computes result = left + right + carry_in and updates carry_out */ static inline void add_carry(u64 left, u64 right, u64 *result, u64 carry_in, u64 *carry_out) { #ifdef USE_BUILTIN_ADDC *result = __builtin_addcll(left, right, carry_in, carry_out); #else u64 sum1, sum2; u64 c1 = __builtin_uaddll_overflow(left, right, &sum1); u64 c2 = __builtin_uaddll_overflow(sum1, carry_in, &sum2); *result = sum2; *carry_out = c1 | c2; #endif } #ifdef __has_builtin #if __has_builtin(__builtin_subcll) #define USE_BUILTIN_SUBC #endif #endif /* Computes result = left - right - borrow_in and updates borrow_out */ static inline void sub_borrow(u64 left, u64 right, u64 *result, u64 borrow_in, u64 *borrow_out) { #ifdef USE_BUILTIN_SUBC *result = __builtin_subcll(left, right, borrow_in, borrow_out); #else u64 diff1, diff2; u64 b1 = __builtin_usubll_overflow(left, right, &diff1); u64 b2 = __builtin_usubll_overflow(diff1, borrow_in, &diff2); *result = diff2; *borrow_out = b1 | b2; #endif } /* Computes result = left + right, returning carry. Can modify in place. */ static u64 vli_add(u64 *result, const u64 *left, const u64 *right, unsigned int ndigits) { u64 carry = 0; int i; for (i = 0; i < ndigits; i++) add_carry(left[i], right[i], &result[i], carry, &carry); return carry; } /* Computes result = left + right, returning carry. Can modify in place. */ static u64 vli_uadd(u64 *result, const u64 *left, u64 right, unsigned int ndigits) { u64 carry; int i; if (ndigits == 0) return right; carry = __builtin_uaddll_overflow(left[0], right, &result[0]); for (i = 1; i < ndigits; i++) carry = __builtin_uaddll_overflow(left[i], carry, &result[i]); return carry; } /* Computes result = left - right, returning borrow. Can modify in place. */ u64 vli_sub(u64 *result, const u64 *left, const u64 *right, unsigned int ndigits) { u64 borrow = 0; int i; for (i = 0; i < ndigits; i++) sub_borrow(left[i], right[i], &result[i], borrow, &borrow); return borrow; } EXPORT_SYMBOL(vli_sub); /* Computes result = left - right, returning borrow. Can modify in place. */ static u64 vli_usub(u64 *result, const u64 *left, u64 right, unsigned int ndigits) { u64 borrow; int i; if (ndigits == 0) return right; borrow = __builtin_usubll_overflow(left[0], right, &result[0]); for (i = 1; i < ndigits; i++) borrow = __builtin_usubll_overflow(left[i], borrow, &result[i]); return borrow; } static uint128_t mul_64_64(u64 left, u64 right) { uint128_t result; #if defined(CONFIG_ARCH_SUPPORTS_INT128) unsigned __int128 m = (unsigned __int128)left * right; result.m_low = m; result.m_high = m >> 64; #else u64 a0 = left & 0xffffffffull; u64 a1 = left >> 32; u64 b0 = right & 0xffffffffull; u64 b1 = right >> 32; u64 m0 = a0 * b0; u64 m1 = a0 * b1; u64 m2 = a1 * b0; u64 m3 = a1 * b1; m2 += (m0 >> 32); m2 += m1; /* Overflow */ if (m2 < m1) m3 += 0x100000000ull; result.m_low = (m0 & 0xffffffffull) | (m2 << 32); result.m_high = m3 + (m2 >> 32); #endif return result; } /* Calculate addition with overflow checking. Returns true on wrap-around, * false otherwise. */ static bool check_add_128_128_overflow(uint128_t *result, uint128_t a, uint128_t b) { bool carry; result->m_low = a.m_low + b.m_low; carry = (result->m_low < a.m_low); result->m_high = a.m_high + b.m_high + carry; /* Using constant-time bitwise arithmetic to prevent timing * side-channels. */ carry = (result->m_high < a.m_high) | ((result->m_high == a.m_high) & carry); return carry; } static void vli_mult(u64 *result, const u64 *left, const u64 *right, unsigned int ndigits) { uint128_t r01 = { 0, 0 }; u64 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]); r2 += check_add_128_128_overflow(&r01, r01, product); } result[k] = r01.m_low; r01.m_low = r01.m_high; r01.m_high = r2; r2 = 0; } result[ndigits * 2 - 1] = r01.m_low; } /* Compute product = left * right, for a small right value. */ static void vli_umult(u64 *result, const u64 *left, u32 right, unsigned int ndigits) { uint128_t r01 = { 0 }; unsigned int k; for (k = 0; k < ndigits; k++) { uint128_t product; product = mul_64_64(left[k], right); check_add_128_128_overflow(&r01, r01, product); /* no carry */ result[k] = r01.m_low; r01.m_low = r01.m_high; r01.m_high = 0; } result[k] = r01.m_low; for (++k; k < ndigits * 2; k++) result[k] = 0; } static void vli_square(u64 *result, const u64 *left, unsigned int ndigits) { uint128_t r01 = { 0, 0 }; u64 r2 = 0; int i, k;