^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 2) * Copyright (c) 2013, 2014 Kenneth MacKay. All rights reserved.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 3) * Copyright (c) 2019 Vitaly Chikunov <vt@altlinux.org>
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 4) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 5) * Redistribution and use in source and binary forms, with or without
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 6) * modification, are permitted provided that the following conditions are
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 7) * met:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 8) * * Redistributions of source code must retain the above copyright
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 9) * notice, this list of conditions and the following disclaimer.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 10) * * Redistributions in binary form must reproduce the above copyright
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 11) * notice, this list of conditions and the following disclaimer in the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 12) * documentation and/or other materials provided with the distribution.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 13) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 14) * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 15) * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 16) * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 17) * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 18) * HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 19) * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 20) * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 21) * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 22) * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 23) * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 24) * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 25) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 26)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 27) #include <linux/module.h>
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 28) #include <linux/random.h>
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 29) #include <linux/slab.h>
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 30) #include <linux/swab.h>
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 31) #include <linux/fips.h>
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 32) #include <crypto/ecdh.h>
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 33) #include <crypto/rng.h>
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 34) #include <asm/unaligned.h>
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 35) #include <linux/ratelimit.h>
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 36)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 37) #include "ecc.h"
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 38) #include "ecc_curve_defs.h"
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 39)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 40) typedef struct {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 41) u64 m_low;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 42) u64 m_high;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 43) } uint128_t;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 44)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 45) static inline const struct ecc_curve *ecc_get_curve(unsigned int curve_id)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 46) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 47) switch (curve_id) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 48) /* In FIPS mode only allow P256 and higher */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 49) case ECC_CURVE_NIST_P192:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 50) return fips_enabled ? NULL : &nist_p192;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 51) case ECC_CURVE_NIST_P256:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 52) return &nist_p256;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 53) default:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 54) return NULL;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 55) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 56) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 57)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 58) static u64 *ecc_alloc_digits_space(unsigned int ndigits)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 59) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 60) size_t len = ndigits * sizeof(u64);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 61)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 62) if (!len)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 63) return NULL;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 64)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 65) return kmalloc(len, GFP_KERNEL);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 66) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 67)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 68) static void ecc_free_digits_space(u64 *space)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 69) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 70) kfree_sensitive(space);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 71) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 72)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 73) static struct ecc_point *ecc_alloc_point(unsigned int ndigits)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 74) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 75) struct ecc_point *p = kmalloc(sizeof(*p), GFP_KERNEL);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 76)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 77) if (!p)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 78) return NULL;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 79)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 80) p->x = ecc_alloc_digits_space(ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 81) if (!p->x)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 82) goto err_alloc_x;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 83)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 84) p->y = ecc_alloc_digits_space(ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 85) if (!p->y)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 86) goto err_alloc_y;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 87)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 88) p->ndigits = ndigits;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 89)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 90) return p;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 91)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 92) err_alloc_y:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 93) ecc_free_digits_space(p->x);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 94) err_alloc_x:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 95) kfree(p);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 96) return NULL;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 97) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 98)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 99) static void ecc_free_point(struct ecc_point *p)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 100) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 101) if (!p)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 102) return;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 103)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 104) kfree_sensitive(p->x);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 105) kfree_sensitive(p->y);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 106) kfree_sensitive(p);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 107) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 108)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 109) static void vli_clear(u64 *vli, unsigned int ndigits)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 110) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 111) int i;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 112)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 113) for (i = 0; i < ndigits; i++)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 114) vli[i] = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 115) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 116)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 117) /* Returns true if vli == 0, false otherwise. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 118) bool vli_is_zero(const u64 *vli, unsigned int ndigits)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 119) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 120) int i;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 121)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 122) for (i = 0; i < ndigits; i++) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 123) if (vli[i])
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 124) return false;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 125) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 126)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 127) return true;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 128) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 129) EXPORT_SYMBOL(vli_is_zero);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 130)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 131) /* Returns nonzero if bit bit of vli is set. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 132) static u64 vli_test_bit(const u64 *vli, unsigned int bit)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 133) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 134) return (vli[bit / 64] & ((u64)1 << (bit % 64)));
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 135) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 136)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 137) static bool vli_is_negative(const u64 *vli, unsigned int ndigits)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 138) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 139) return vli_test_bit(vli, ndigits * 64 - 1);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 140) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 141)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 142) /* Counts the number of 64-bit "digits" in vli. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 143) static unsigned int vli_num_digits(const u64 *vli, unsigned int ndigits)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 144) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 145) int i;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 146)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 147) /* Search from the end until we find a non-zero digit.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 148) * We do it in reverse because we expect that most digits will
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 149) * be nonzero.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 150) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 151) for (i = ndigits - 1; i >= 0 && vli[i] == 0; i--);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 152)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 153) return (i + 1);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 154) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 155)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 156) /* Counts the number of bits required for vli. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 157) static unsigned int vli_num_bits(const u64 *vli, unsigned int ndigits)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 158) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 159) unsigned int i, num_digits;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 160) u64 digit;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 161)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 162) num_digits = vli_num_digits(vli, ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 163) if (num_digits == 0)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 164) return 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 165)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 166) digit = vli[num_digits - 1];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 167) for (i = 0; digit; i++)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 168) digit >>= 1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 169)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 170) return ((num_digits - 1) * 64 + i);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 171) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 172)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 173) /* Set dest from unaligned bit string src. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 174) void vli_from_be64(u64 *dest, const void *src, unsigned int ndigits)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 175) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 176) int i;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 177) const u64 *from = src;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 178)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 179) for (i = 0; i < ndigits; i++)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 180) dest[i] = get_unaligned_be64(&from[ndigits - 1 - i]);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 181) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 182) EXPORT_SYMBOL(vli_from_be64);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 183)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 184) void vli_from_le64(u64 *dest, const void *src, unsigned int ndigits)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 185) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 186) int i;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 187) const u64 *from = src;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 188)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 189) for (i = 0; i < ndigits; i++)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 190) dest[i] = get_unaligned_le64(&from[i]);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 191) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 192) EXPORT_SYMBOL(vli_from_le64);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 193)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 194) /* Sets dest = src. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 195) static void vli_set(u64 *dest, const u64 *src, unsigned int ndigits)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 196) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 197) int i;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 198)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 199) for (i = 0; i < ndigits; i++)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 200) dest[i] = src[i];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 201) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 202)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 203) /* Returns sign of left - right. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 204) int vli_cmp(const u64 *left, const u64 *right, unsigned int ndigits)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 205) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 206) int i;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 207)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 208) for (i = ndigits - 1; i >= 0; i--) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 209) if (left[i] > right[i])
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 210) return 1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 211) else if (left[i] < right[i])
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 212) return -1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 213) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 214)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 215) return 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 216) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 217) EXPORT_SYMBOL(vli_cmp);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 218)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 219) /* Computes result = in << c, returning carry. Can modify in place
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 220) * (if result == in). 0 < shift < 64.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 221) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 222) static u64 vli_lshift(u64 *result, const u64 *in, unsigned int shift,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 223) unsigned int ndigits)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 224) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 225) u64 carry = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 226) int i;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 227)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 228) for (i = 0; i < ndigits; i++) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 229) u64 temp = in[i];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 230)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 231) result[i] = (temp << shift) | carry;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 232) carry = temp >> (64 - shift);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 233) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 234)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 235) return carry;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 236) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 237)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 238) /* Computes vli = vli >> 1. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 239) static void vli_rshift1(u64 *vli, unsigned int ndigits)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 240) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 241) u64 *end = vli;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 242) u64 carry = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 243)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 244) vli += ndigits;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 245)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 246) while (vli-- > end) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 247) u64 temp = *vli;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 248) *vli = (temp >> 1) | carry;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 249) carry = temp << 63;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 250) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 251) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 252)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 253) /* Computes result = left + right, returning carry. Can modify in place. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 254) static u64 vli_add(u64 *result, const u64 *left, const u64 *right,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 255) unsigned int ndigits)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 256) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 257) u64 carry = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 258) int i;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 259)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 260) for (i = 0; i < ndigits; i++) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 261) u64 sum;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 262)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 263) sum = left[i] + right[i] + carry;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 264) if (sum != left[i])
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 265) carry = (sum < left[i]);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 266)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 267) result[i] = sum;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 268) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 269)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 270) return carry;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 271) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 272)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 273) /* Computes result = left + right, returning carry. Can modify in place. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 274) static u64 vli_uadd(u64 *result, const u64 *left, u64 right,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 275) unsigned int ndigits)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 276) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 277) u64 carry = right;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 278) int i;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 279)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 280) for (i = 0; i < ndigits; i++) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 281) u64 sum;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 282)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 283) sum = left[i] + carry;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 284) if (sum != left[i])
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 285) carry = (sum < left[i]);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 286) else
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 287) carry = !!carry;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 288)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 289) result[i] = sum;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 290) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 291)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 292) return carry;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 293) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 294)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 295) /* Computes result = left - right, returning borrow. Can modify in place. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 296) u64 vli_sub(u64 *result, const u64 *left, const u64 *right,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 297) unsigned int ndigits)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 298) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 299) u64 borrow = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 300) int i;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 301)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 302) for (i = 0; i < ndigits; i++) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 303) u64 diff;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 304)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 305) diff = left[i] - right[i] - borrow;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 306) if (diff != left[i])
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 307) borrow = (diff > left[i]);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 308)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 309) result[i] = diff;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 310) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 311)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 312) return borrow;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 313) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 314) EXPORT_SYMBOL(vli_sub);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 315)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 316) /* Computes result = left - right, returning borrow. Can modify in place. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 317) static u64 vli_usub(u64 *result, const u64 *left, u64 right,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 318) unsigned int ndigits)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 319) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 320) u64 borrow = right;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 321) int i;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 322)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 323) for (i = 0; i < ndigits; i++) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 324) u64 diff;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 325)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 326) diff = left[i] - borrow;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 327) if (diff != left[i])
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 328) borrow = (diff > left[i]);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 329)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 330) result[i] = diff;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 331) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 332)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 333) return borrow;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 334) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 335)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 336) static uint128_t mul_64_64(u64 left, u64 right)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 337) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 338) uint128_t result;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 339) #if defined(CONFIG_ARCH_SUPPORTS_INT128)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 340) unsigned __int128 m = (unsigned __int128)left * right;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 341)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 342) result.m_low = m;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 343) result.m_high = m >> 64;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 344) #else
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 345) u64 a0 = left & 0xffffffffull;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 346) u64 a1 = left >> 32;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 347) u64 b0 = right & 0xffffffffull;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 348) u64 b1 = right >> 32;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 349) u64 m0 = a0 * b0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 350) u64 m1 = a0 * b1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 351) u64 m2 = a1 * b0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 352) u64 m3 = a1 * b1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 353)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 354) m2 += (m0 >> 32);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 355) m2 += m1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 356)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 357) /* Overflow */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 358) if (m2 < m1)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 359) m3 += 0x100000000ull;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 360)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 361) result.m_low = (m0 & 0xffffffffull) | (m2 << 32);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 362) result.m_high = m3 + (m2 >> 32);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 363) #endif
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 364) return result;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 365) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 366)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 367) static uint128_t add_128_128(uint128_t a, uint128_t b)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 368) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 369) uint128_t result;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 370)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 371) result.m_low = a.m_low + b.m_low;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 372) result.m_high = a.m_high + b.m_high + (result.m_low < a.m_low);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 373)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 374) return result;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 375) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 376)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 377) static void vli_mult(u64 *result, const u64 *left, const u64 *right,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 378) unsigned int ndigits)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 379) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 380) uint128_t r01 = { 0, 0 };
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 381) u64 r2 = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 382) unsigned int i, k;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 383)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 384) /* Compute each digit of result in sequence, maintaining the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 385) * carries.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 386) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 387) for (k = 0; k < ndigits * 2 - 1; k++) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 388) unsigned int min;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 389)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 390) if (k < ndigits)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 391) min = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 392) else
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 393) min = (k + 1) - ndigits;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 394)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 395) for (i = min; i <= k && i < ndigits; i++) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 396) uint128_t product;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 397)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 398) product = mul_64_64(left[i], right[k - i]);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 399)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 400) r01 = add_128_128(r01, product);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 401) r2 += (r01.m_high < product.m_high);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 402) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 403)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 404) result[k] = r01.m_low;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 405) r01.m_low = r01.m_high;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 406) r01.m_high = r2;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 407) r2 = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 408) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 409)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 410) result[ndigits * 2 - 1] = r01.m_low;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 411) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 412)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 413) /* Compute product = left * right, for a small right value. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 414) static void vli_umult(u64 *result, const u64 *left, u32 right,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 415) unsigned int ndigits)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 416) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 417) uint128_t r01 = { 0 };
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 418) unsigned int k;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 419)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 420) for (k = 0; k < ndigits; k++) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 421) uint128_t product;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 422)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 423) product = mul_64_64(left[k], right);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 424) r01 = add_128_128(r01, product);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 425) /* no carry */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 426) result[k] = r01.m_low;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 427) r01.m_low = r01.m_high;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 428) r01.m_high = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 429) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 430) result[k] = r01.m_low;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 431) for (++k; k < ndigits * 2; k++)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 432) result[k] = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 433) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 434)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 435) static void vli_square(u64 *result, const u64 *left, unsigned int ndigits)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 436) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 437) uint128_t r01 = { 0, 0 };
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 438) u64 r2 = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 439) int i, k;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 440)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 441) for (k = 0; k < ndigits * 2 - 1; k++) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 442) unsigned int min;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 443)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 444) if (k < ndigits)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 445) min = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 446) else
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 447) min = (k + 1) - ndigits;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 448)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 449) for (i = min; i <= k && i <= k - i; i++) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 450) uint128_t product;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 451)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 452) product = mul_64_64(left[i], left[k - i]);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 453)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 454) if (i < k - i) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 455) r2 += product.m_high >> 63;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 456) product.m_high = (product.m_high << 1) |
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 457) (product.m_low >> 63);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 458) product.m_low <<= 1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 459) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 460)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 461) r01 = add_128_128(r01, product);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 462) r2 += (r01.m_high < product.m_high);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 463) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 464)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 465) result[k] = r01.m_low;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 466) r01.m_low = r01.m_high;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 467) r01.m_high = r2;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 468) r2 = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 469) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 470)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 471) result[ndigits * 2 - 1] = r01.m_low;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 472) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 473)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 474) /* Computes result = (left + right) % mod.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 475) * Assumes that left < mod and right < mod, result != mod.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 476) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 477) static void vli_mod_add(u64 *result, const u64 *left, const u64 *right,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 478) const u64 *mod, unsigned int ndigits)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 479) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 480) u64 carry;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 481)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 482) carry = vli_add(result, left, right, ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 483)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 484) /* result > mod (result = mod + remainder), so subtract mod to
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 485) * get remainder.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 486) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 487) if (carry || vli_cmp(result, mod, ndigits) >= 0)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 488) vli_sub(result, result, mod, ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 489) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 490)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 491) /* Computes result = (left - right) % mod.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 492) * Assumes that left < mod and right < mod, result != mod.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 493) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 494) static void vli_mod_sub(u64 *result, const u64 *left, const u64 *right,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 495) const u64 *mod, unsigned int ndigits)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 496) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 497) u64 borrow = vli_sub(result, left, right, ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 498)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 499) /* In this case, p_result == -diff == (max int) - diff.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 500) * Since -x % d == d - x, we can get the correct result from
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 501) * result + mod (with overflow).
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 502) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 503) if (borrow)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 504) vli_add(result, result, mod, ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 505) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 506)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 507) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 508) * Computes result = product % mod
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 509) * for special form moduli: p = 2^k-c, for small c (note the minus sign)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 510) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 511) * References:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 512) * R. Crandall, C. Pomerance. Prime Numbers: A Computational Perspective.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 513) * 9 Fast Algorithms for Large-Integer Arithmetic. 9.2.3 Moduli of special form
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 514) * Algorithm 9.2.13 (Fast mod operation for special-form moduli).
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 515) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 516) static void vli_mmod_special(u64 *result, const u64 *product,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 517) const u64 *mod, unsigned int ndigits)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 518) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 519) u64 c = -mod[0];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 520) u64 t[ECC_MAX_DIGITS * 2];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 521) u64 r[ECC_MAX_DIGITS * 2];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 522)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 523) vli_set(r, product, ndigits * 2);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 524) while (!vli_is_zero(r + ndigits, ndigits)) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 525) vli_umult(t, r + ndigits, c, ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 526) vli_clear(r + ndigits, ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 527) vli_add(r, r, t, ndigits * 2);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 528) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 529) vli_set(t, mod, ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 530) vli_clear(t + ndigits, ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 531) while (vli_cmp(r, t, ndigits * 2) >= 0)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 532) vli_sub(r, r, t, ndigits * 2);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 533) vli_set(result, r, ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 534) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 535)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 536) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 537) * Computes result = product % mod
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 538) * for special form moduli: p = 2^{k-1}+c, for small c (note the plus sign)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 539) * where k-1 does not fit into qword boundary by -1 bit (such as 255).
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 540)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 541) * References (loosely based on):
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 542) * A. Menezes, P. van Oorschot, S. Vanstone. Handbook of Applied Cryptography.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 543) * 14.3.4 Reduction methods for moduli of special form. Algorithm 14.47.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 544) * URL: http://cacr.uwaterloo.ca/hac/about/chap14.pdf
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 545) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 546) * H. Cohen, G. Frey, R. Avanzi, C. Doche, T. Lange, K. Nguyen, F. Vercauteren.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 547) * Handbook of Elliptic and Hyperelliptic Curve Cryptography.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 548) * Algorithm 10.25 Fast reduction for special form moduli
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 549) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 550) static void vli_mmod_special2(u64 *result, const u64 *product,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 551) const u64 *mod, unsigned int ndigits)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 552) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 553) u64 c2 = mod[0] * 2;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 554) u64 q[ECC_MAX_DIGITS];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 555) u64 r[ECC_MAX_DIGITS * 2];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 556) u64 m[ECC_MAX_DIGITS * 2]; /* expanded mod */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 557) int carry; /* last bit that doesn't fit into q */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 558) int i;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 559)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 560) vli_set(m, mod, ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 561) vli_clear(m + ndigits, ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 562)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 563) vli_set(r, product, ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 564) /* q and carry are top bits */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 565) vli_set(q, product + ndigits, ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 566) vli_clear(r + ndigits, ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 567) carry = vli_is_negative(r, ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 568) if (carry)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 569) r[ndigits - 1] &= (1ull << 63) - 1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 570) for (i = 1; carry || !vli_is_zero(q, ndigits); i++) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 571) u64 qc[ECC_MAX_DIGITS * 2];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 572)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 573) vli_umult(qc, q, c2, ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 574) if (carry)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 575) vli_uadd(qc, qc, mod[0], ndigits * 2);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 576) vli_set(q, qc + ndigits, ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 577) vli_clear(qc + ndigits, ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 578) carry = vli_is_negative(qc, ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 579) if (carry)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 580) qc[ndigits - 1] &= (1ull << 63) - 1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 581) if (i & 1)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 582) vli_sub(r, r, qc, ndigits * 2);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 583) else
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 584) vli_add(r, r, qc, ndigits * 2);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 585) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 586) while (vli_is_negative(r, ndigits * 2))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 587) vli_add(r, r, m, ndigits * 2);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 588) while (vli_cmp(r, m, ndigits * 2) >= 0)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 589) vli_sub(r, r, m, ndigits * 2);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 590)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 591) vli_set(result, r, ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 592) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 593)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 594) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 595) * Computes result = product % mod, where product is 2N words long.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 596) * Reference: Ken MacKay's micro-ecc.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 597) * Currently only designed to work for curve_p or curve_n.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 598) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 599) static void vli_mmod_slow(u64 *result, u64 *product, const u64 *mod,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 600) unsigned int ndigits)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 601) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 602) u64 mod_m[2 * ECC_MAX_DIGITS];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 603) u64 tmp[2 * ECC_MAX_DIGITS];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 604) u64 *v[2] = { tmp, product };
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 605) u64 carry = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 606) unsigned int i;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 607) /* Shift mod so its highest set bit is at the maximum position. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 608) int shift = (ndigits * 2 * 64) - vli_num_bits(mod, ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 609) int word_shift = shift / 64;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 610) int bit_shift = shift % 64;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 611)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 612) vli_clear(mod_m, word_shift);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 613) if (bit_shift > 0) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 614) for (i = 0; i < ndigits; ++i) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 615) mod_m[word_shift + i] = (mod[i] << bit_shift) | carry;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 616) carry = mod[i] >> (64 - bit_shift);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 617) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 618) } else
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 619) vli_set(mod_m + word_shift, mod, ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 620)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 621) for (i = 1; shift >= 0; --shift) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 622) u64 borrow = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 623) unsigned int j;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 624)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 625) for (j = 0; j < ndigits * 2; ++j) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 626) u64 diff = v[i][j] - mod_m[j] - borrow;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 627)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 628) if (diff != v[i][j])
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 629) borrow = (diff > v[i][j]);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 630) v[1 - i][j] = diff;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 631) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 632) i = !(i ^ borrow); /* Swap the index if there was no borrow */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 633) vli_rshift1(mod_m, ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 634) mod_m[ndigits - 1] |= mod_m[ndigits] << (64 - 1);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 635) vli_rshift1(mod_m + ndigits, ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 636) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 637) vli_set(result, v[i], ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 638) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 639)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 640) /* Computes result = product % mod using Barrett's reduction with precomputed
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 641) * value mu appended to the mod after ndigits, mu = (2^{2w} / mod) and have
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 642) * length ndigits + 1, where mu * (2^w - 1) should not overflow ndigits
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 643) * boundary.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 644) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 645) * Reference:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 646) * R. Brent, P. Zimmermann. Modern Computer Arithmetic. 2010.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 647) * 2.4.1 Barrett's algorithm. Algorithm 2.5.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 648) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 649) static void vli_mmod_barrett(u64 *result, u64 *product, const u64 *mod,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 650) unsigned int ndigits)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 651) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 652) u64 q[ECC_MAX_DIGITS * 2];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 653) u64 r[ECC_MAX_DIGITS * 2];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 654) const u64 *mu = mod + ndigits;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 655)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 656) vli_mult(q, product + ndigits, mu, ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 657) if (mu[ndigits])
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 658) vli_add(q + ndigits, q + ndigits, product + ndigits, ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 659) vli_mult(r, mod, q + ndigits, ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 660) vli_sub(r, product, r, ndigits * 2);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 661) while (!vli_is_zero(r + ndigits, ndigits) ||
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 662) vli_cmp(r, mod, ndigits) != -1) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 663) u64 carry;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 664)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 665) carry = vli_sub(r, r, mod, ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 666) vli_usub(r + ndigits, r + ndigits, carry, ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 667) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 668) vli_set(result, r, ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 669) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 670)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 671) /* Computes p_result = p_product % curve_p.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 672) * See algorithm 5 and 6 from
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 673) * http://www.isys.uni-klu.ac.at/PDF/2001-0126-MT.pdf
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 674) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 675) static void vli_mmod_fast_192(u64 *result, const u64 *product,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 676) const u64 *curve_prime, u64 *tmp)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 677) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 678) const unsigned int ndigits = 3;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 679) int carry;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 680)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 681) vli_set(result, product, ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 682)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 683) vli_set(tmp, &product[3], ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 684) carry = vli_add(result, result, tmp, ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 685)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 686) tmp[0] = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 687) tmp[1] = product[3];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 688) tmp[2] = product[4];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 689) carry += vli_add(result, result, tmp, ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 690)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 691) tmp[0] = tmp[1] = product[5];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 692) tmp[2] = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 693) carry += vli_add(result, result, tmp, ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 694)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 695) while (carry || vli_cmp(curve_prime, result, ndigits) != 1)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 696) carry -= vli_sub(result, result, curve_prime, ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 697) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 698)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 699) /* Computes result = product % curve_prime
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 700) * from http://www.nsa.gov/ia/_files/nist-routines.pdf
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 701) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 702) static void vli_mmod_fast_256(u64 *result, const u64 *product,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 703) const u64 *curve_prime, u64 *tmp)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 704) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 705) int carry;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 706) const unsigned int ndigits = 4;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 707)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 708) /* t */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 709) vli_set(result, product, ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 710)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 711) /* s1 */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 712) tmp[0] = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 713) tmp[1] = product[5] & 0xffffffff00000000ull;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 714) tmp[2] = product[6];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 715) tmp[3] = product[7];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 716) carry = vli_lshift(tmp, tmp, 1, ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 717) carry += vli_add(result, result, tmp, ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 718)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 719) /* s2 */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 720) tmp[1] = product[6] << 32;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 721) tmp[2] = (product[6] >> 32) | (product[7] << 32);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 722) tmp[3] = product[7] >> 32;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 723) carry += vli_lshift(tmp, tmp, 1, ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 724) carry += vli_add(result, result, tmp, ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 725)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 726) /* s3 */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 727) tmp[0] = product[4];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 728) tmp[1] = product[5] & 0xffffffff;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 729) tmp[2] = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 730) tmp[3] = product[7];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 731) carry += vli_add(result, result, tmp, ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 732)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 733) /* s4 */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 734) tmp[0] = (product[4] >> 32) | (product[5] << 32);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 735) tmp[1] = (product[5] >> 32) | (product[6] & 0xffffffff00000000ull);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 736) tmp[2] = product[7];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 737) tmp[3] = (product[6] >> 32) | (product[4] << 32);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 738) carry += vli_add(result, result, tmp, ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 739)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 740) /* d1 */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 741) tmp[0] = (product[5] >> 32) | (product[6] << 32);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 742) tmp[1] = (product[6] >> 32);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 743) tmp[2] = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 744) tmp[3] = (product[4] & 0xffffffff) | (product[5] << 32);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 745) carry -= vli_sub(result, result, tmp, ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 746)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 747) /* d2 */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 748) tmp[0] = product[6];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 749) tmp[1] = product[7];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 750) tmp[2] = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 751) tmp[3] = (product[4] >> 32) | (product[5] & 0xffffffff00000000ull);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 752) carry -= vli_sub(result, result, tmp, ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 753)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 754) /* d3 */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 755) tmp[0] = (product[6] >> 32) | (product[7] << 32);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 756) tmp[1] = (product[7] >> 32) | (product[4] << 32);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 757) tmp[2] = (product[4] >> 32) | (product[5] << 32);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 758) tmp[3] = (product[6] << 32);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 759) carry -= vli_sub(result, result, tmp, ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 760)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 761) /* d4 */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 762) tmp[0] = product[7];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 763) tmp[1] = product[4] & 0xffffffff00000000ull;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 764) tmp[2] = product[5];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 765) tmp[3] = product[6] & 0xffffffff00000000ull;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 766) carry -= vli_sub(result, result, tmp, ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 767)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 768) if (carry < 0) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 769) do {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 770) carry += vli_add(result, result, curve_prime, ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 771) } while (carry < 0);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 772) } else {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 773) while (carry || vli_cmp(curve_prime, result, ndigits) != 1)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 774) carry -= vli_sub(result, result, curve_prime, ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 775) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 776) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 777)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 778) /* Computes result = product % curve_prime for different curve_primes.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 779) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 780) * Note that curve_primes are distinguished just by heuristic check and
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 781) * not by complete conformance check.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 782) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 783) static bool vli_mmod_fast(u64 *result, u64 *product,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 784) const u64 *curve_prime, unsigned int ndigits)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 785) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 786) u64 tmp[2 * ECC_MAX_DIGITS];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 787)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 788) /* Currently, both NIST primes have -1 in lowest qword. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 789) if (curve_prime[0] != -1ull) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 790) /* Try to handle Pseudo-Marsenne primes. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 791) if (curve_prime[ndigits - 1] == -1ull) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 792) vli_mmod_special(result, product, curve_prime,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 793) ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 794) return true;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 795) } else if (curve_prime[ndigits - 1] == 1ull << 63 &&
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 796) curve_prime[ndigits - 2] == 0) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 797) vli_mmod_special2(result, product, curve_prime,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 798) ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 799) return true;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 800) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 801) vli_mmod_barrett(result, product, curve_prime, ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 802) return true;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 803) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 804)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 805) switch (ndigits) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 806) case 3:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 807) vli_mmod_fast_192(result, product, curve_prime, tmp);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 808) break;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 809) case 4:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 810) vli_mmod_fast_256(result, product, curve_prime, tmp);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 811) break;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 812) default:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 813) pr_err_ratelimited("ecc: unsupported digits size!\n");
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 814) return false;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 815) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 816)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 817) return true;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 818) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 819)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 820) /* Computes result = (left * right) % mod.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 821) * Assumes that mod is big enough curve order.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 822) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 823) void vli_mod_mult_slow(u64 *result, const u64 *left, const u64 *right,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 824) const u64 *mod, unsigned int ndigits)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 825) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 826) u64 product[ECC_MAX_DIGITS * 2];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 827)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 828) vli_mult(product, left, right, ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 829) vli_mmod_slow(result, product, mod, ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 830) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 831) EXPORT_SYMBOL(vli_mod_mult_slow);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 832)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 833) /* Computes result = (left * right) % curve_prime. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 834) static void vli_mod_mult_fast(u64 *result, const u64 *left, const u64 *right,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 835) const u64 *curve_prime, unsigned int ndigits)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 836) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 837) u64 product[2 * ECC_MAX_DIGITS];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 838)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 839) vli_mult(product, left, right, ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 840) vli_mmod_fast(result, product, curve_prime, ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 841) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 842)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 843) /* Computes result = left^2 % curve_prime. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 844) static void vli_mod_square_fast(u64 *result, const u64 *left,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 845) const u64 *curve_prime, unsigned int ndigits)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 846) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 847) u64 product[2 * ECC_MAX_DIGITS];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 848)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 849) vli_square(product, left, ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 850) vli_mmod_fast(result, product, curve_prime, ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 851) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 852)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 853) #define EVEN(vli) (!(vli[0] & 1))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 854) /* Computes result = (1 / p_input) % mod. All VLIs are the same size.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 855) * See "From Euclid's GCD to Montgomery Multiplication to the Great Divide"
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 856) * https://labs.oracle.com/techrep/2001/smli_tr-2001-95.pdf
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 857) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 858) void vli_mod_inv(u64 *result, const u64 *input, const u64 *mod,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 859) unsigned int ndigits)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 860) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 861) u64 a[ECC_MAX_DIGITS], b[ECC_MAX_DIGITS];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 862) u64 u[ECC_MAX_DIGITS], v[ECC_MAX_DIGITS];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 863) u64 carry;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 864) int cmp_result;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 865)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 866) if (vli_is_zero(input, ndigits)) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 867) vli_clear(result, ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 868) return;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 869) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 870)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 871) vli_set(a, input, ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 872) vli_set(b, mod, ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 873) vli_clear(u, ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 874) u[0] = 1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 875) vli_clear(v, ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 876)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 877) while ((cmp_result = vli_cmp(a, b, ndigits)) != 0) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 878) carry = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 879)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 880) if (EVEN(a)) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 881) vli_rshift1(a, ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 882)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 883) if (!EVEN(u))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 884) carry = vli_add(u, u, mod, ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 885)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 886) vli_rshift1(u, ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 887) if (carry)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 888) u[ndigits - 1] |= 0x8000000000000000ull;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 889) } else if (EVEN(b)) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 890) vli_rshift1(b, ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 891)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 892) if (!EVEN(v))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 893) carry = vli_add(v, v, mod, ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 894)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 895) vli_rshift1(v, ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 896) if (carry)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 897) v[ndigits - 1] |= 0x8000000000000000ull;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 898) } else if (cmp_result > 0) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 899) vli_sub(a, a, b, ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 900) vli_rshift1(a, ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 901)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 902) if (vli_cmp(u, v, ndigits) < 0)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 903) vli_add(u, u, mod, ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 904)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 905) vli_sub(u, u, v, ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 906) if (!EVEN(u))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 907) carry = vli_add(u, u, mod, ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 908)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 909) vli_rshift1(u, ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 910) if (carry)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 911) u[ndigits - 1] |= 0x8000000000000000ull;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 912) } else {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 913) vli_sub(b, b, a, ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 914) vli_rshift1(b, ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 915)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 916) if (vli_cmp(v, u, ndigits) < 0)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 917) vli_add(v, v, mod, ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 918)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 919) vli_sub(v, v, u, ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 920) if (!EVEN(v))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 921) carry = vli_add(v, v, mod, ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 922)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 923) vli_rshift1(v, ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 924) if (carry)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 925) v[ndigits - 1] |= 0x8000000000000000ull;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 926) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 927) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 928)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 929) vli_set(result, u, ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 930) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 931) EXPORT_SYMBOL(vli_mod_inv);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 932)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 933) /* ------ Point operations ------ */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 934)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 935) /* Returns true if p_point is the point at infinity, false otherwise. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 936) static bool ecc_point_is_zero(const struct ecc_point *point)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 937) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 938) return (vli_is_zero(point->x, point->ndigits) &&
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 939) vli_is_zero(point->y, point->ndigits));
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 940) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 941)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 942) /* Point multiplication algorithm using Montgomery's ladder with co-Z
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 943) * coordinates. From https://eprint.iacr.org/2011/338.pdf
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 944) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 945)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 946) /* Double in place */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 947) static void ecc_point_double_jacobian(u64 *x1, u64 *y1, u64 *z1,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 948) u64 *curve_prime, unsigned int ndigits)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 949) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 950) /* t1 = x, t2 = y, t3 = z */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 951) u64 t4[ECC_MAX_DIGITS];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 952) u64 t5[ECC_MAX_DIGITS];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 953)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 954) if (vli_is_zero(z1, ndigits))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 955) return;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 956)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 957) /* t4 = y1^2 */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 958) vli_mod_square_fast(t4, y1, curve_prime, ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 959) /* t5 = x1*y1^2 = A */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 960) vli_mod_mult_fast(t5, x1, t4, curve_prime, ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 961) /* t4 = y1^4 */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 962) vli_mod_square_fast(t4, t4, curve_prime, ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 963) /* t2 = y1*z1 = z3 */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 964) vli_mod_mult_fast(y1, y1, z1, curve_prime, ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 965) /* t3 = z1^2 */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 966) vli_mod_square_fast(z1, z1, curve_prime, ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 967)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 968) /* t1 = x1 + z1^2 */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 969) vli_mod_add(x1, x1, z1, curve_prime, ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 970) /* t3 = 2*z1^2 */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 971) vli_mod_add(z1, z1, z1, curve_prime, ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 972) /* t3 = x1 - z1^2 */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 973) vli_mod_sub(z1, x1, z1, curve_prime, ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 974) /* t1 = x1^2 - z1^4 */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 975) vli_mod_mult_fast(x1, x1, z1, curve_prime, ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 976)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 977) /* t3 = 2*(x1^2 - z1^4) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 978) vli_mod_add(z1, x1, x1, curve_prime, ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 979) /* t1 = 3*(x1^2 - z1^4) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 980) vli_mod_add(x1, x1, z1, curve_prime, ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 981) if (vli_test_bit(x1, 0)) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 982) u64 carry = vli_add(x1, x1, curve_prime, ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 983)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 984) vli_rshift1(x1, ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 985) x1[ndigits - 1] |= carry << 63;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 986) } else {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 987) vli_rshift1(x1, ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 988) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 989) /* t1 = 3/2*(x1^2 - z1^4) = B */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 990)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 991) /* t3 = B^2 */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 992) vli_mod_square_fast(z1, x1, curve_prime, ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 993) /* t3 = B^2 - A */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 994) vli_mod_sub(z1, z1, t5, curve_prime, ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 995) /* t3 = B^2 - 2A = x3 */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 996) vli_mod_sub(z1, z1, t5, curve_prime, ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 997) /* t5 = A - x3 */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 998) vli_mod_sub(t5, t5, z1, curve_prime, ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 999) /* t1 = B * (A - x3) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1000) vli_mod_mult_fast(x1, x1, t5, curve_prime, ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1001) /* t4 = B * (A - x3) - y1^4 = y3 */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1002) vli_mod_sub(t4, x1, t4, curve_prime, ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1003)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1004) vli_set(x1, z1, ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1005) vli_set(z1, y1, ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1006) vli_set(y1, t4, ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1007) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1008)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1009) /* Modify (x1, y1) => (x1 * z^2, y1 * z^3) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1010) static void apply_z(u64 *x1, u64 *y1, u64 *z, u64 *curve_prime,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1011) unsigned int ndigits)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1012) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1013) u64 t1[ECC_MAX_DIGITS];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1014)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1015) vli_mod_square_fast(t1, z, curve_prime, ndigits); /* z^2 */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1016) vli_mod_mult_fast(x1, x1, t1, curve_prime, ndigits); /* x1 * z^2 */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1017) vli_mod_mult_fast(t1, t1, z, curve_prime, ndigits); /* z^3 */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1018) vli_mod_mult_fast(y1, y1, t1, curve_prime, ndigits); /* y1 * z^3 */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1019) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1020)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1021) /* P = (x1, y1) => 2P, (x2, y2) => P' */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1022) static void xycz_initial_double(u64 *x1, u64 *y1, u64 *x2, u64 *y2,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1023) u64 *p_initial_z, u64 *curve_prime,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1024) unsigned int ndigits)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1025) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1026) u64 z[ECC_MAX_DIGITS];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1027)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1028) vli_set(x2, x1, ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1029) vli_set(y2, y1, ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1030)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1031) vli_clear(z, ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1032) z[0] = 1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1033)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1034) if (p_initial_z)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1035) vli_set(z, p_initial_z, ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1036)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1037) apply_z(x1, y1, z, curve_prime, ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1038)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1039) ecc_point_double_jacobian(x1, y1, z, curve_prime, ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1040)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1041) apply_z(x2, y2, z, curve_prime, ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1042) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1043)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1044) /* Input P = (x1, y1, Z), Q = (x2, y2, Z)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1045) * Output P' = (x1', y1', Z3), P + Q = (x3, y3, Z3)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1046) * or P => P', Q => P + Q
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1047) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1048) static void xycz_add(u64 *x1, u64 *y1, u64 *x2, u64 *y2, u64 *curve_prime,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1049) unsigned int ndigits)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1050) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1051) /* t1 = X1, t2 = Y1, t3 = X2, t4 = Y2 */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1052) u64 t5[ECC_MAX_DIGITS];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1053)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1054) /* t5 = x2 - x1 */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1055) vli_mod_sub(t5, x2, x1, curve_prime, ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1056) /* t5 = (x2 - x1)^2 = A */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1057) vli_mod_square_fast(t5, t5, curve_prime, ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1058) /* t1 = x1*A = B */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1059) vli_mod_mult_fast(x1, x1, t5, curve_prime, ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1060) /* t3 = x2*A = C */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1061) vli_mod_mult_fast(x2, x2, t5, curve_prime, ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1062) /* t4 = y2 - y1 */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1063) vli_mod_sub(y2, y2, y1, curve_prime, ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1064) /* t5 = (y2 - y1)^2 = D */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1065) vli_mod_square_fast(t5, y2, curve_prime, ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1066)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1067) /* t5 = D - B */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1068) vli_mod_sub(t5, t5, x1, curve_prime, ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1069) /* t5 = D - B - C = x3 */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1070) vli_mod_sub(t5, t5, x2, curve_prime, ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1071) /* t3 = C - B */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1072) vli_mod_sub(x2, x2, x1, curve_prime, ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1073) /* t2 = y1*(C - B) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1074) vli_mod_mult_fast(y1, y1, x2, curve_prime, ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1075) /* t3 = B - x3 */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1076) vli_mod_sub(x2, x1, t5, curve_prime, ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1077) /* t4 = (y2 - y1)*(B - x3) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1078) vli_mod_mult_fast(y2, y2, x2, curve_prime, ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1079) /* t4 = y3 */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1080) vli_mod_sub(y2, y2, y1, curve_prime, ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1081)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1082) vli_set(x2, t5, ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1083) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1084)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1085) /* Input P = (x1, y1, Z), Q = (x2, y2, Z)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1086) * Output P + Q = (x3, y3, Z3), P - Q = (x3', y3', Z3)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1087) * or P => P - Q, Q => P + Q
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1088) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1089) static void xycz_add_c(u64 *x1, u64 *y1, u64 *x2, u64 *y2, u64 *curve_prime,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1090) unsigned int ndigits)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1091) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1092) /* t1 = X1, t2 = Y1, t3 = X2, t4 = Y2 */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1093) u64 t5[ECC_MAX_DIGITS];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1094) u64 t6[ECC_MAX_DIGITS];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1095) u64 t7[ECC_MAX_DIGITS];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1096)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1097) /* t5 = x2 - x1 */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1098) vli_mod_sub(t5, x2, x1, curve_prime, ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1099) /* t5 = (x2 - x1)^2 = A */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1100) vli_mod_square_fast(t5, t5, curve_prime, ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1101) /* t1 = x1*A = B */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1102) vli_mod_mult_fast(x1, x1, t5, curve_prime, ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1103) /* t3 = x2*A = C */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1104) vli_mod_mult_fast(x2, x2, t5, curve_prime, ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1105) /* t4 = y2 + y1 */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1106) vli_mod_add(t5, y2, y1, curve_prime, ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1107) /* t4 = y2 - y1 */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1108) vli_mod_sub(y2, y2, y1, curve_prime, ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1109)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1110) /* t6 = C - B */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1111) vli_mod_sub(t6, x2, x1, curve_prime, ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1112) /* t2 = y1 * (C - B) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1113) vli_mod_mult_fast(y1, y1, t6, curve_prime, ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1114) /* t6 = B + C */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1115) vli_mod_add(t6, x1, x2, curve_prime, ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1116) /* t3 = (y2 - y1)^2 */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1117) vli_mod_square_fast(x2, y2, curve_prime, ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1118) /* t3 = x3 */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1119) vli_mod_sub(x2, x2, t6, curve_prime, ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1120)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1121) /* t7 = B - x3 */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1122) vli_mod_sub(t7, x1, x2, curve_prime, ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1123) /* t4 = (y2 - y1)*(B - x3) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1124) vli_mod_mult_fast(y2, y2, t7, curve_prime, ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1125) /* t4 = y3 */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1126) vli_mod_sub(y2, y2, y1, curve_prime, ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1127)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1128) /* t7 = (y2 + y1)^2 = F */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1129) vli_mod_square_fast(t7, t5, curve_prime, ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1130) /* t7 = x3' */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1131) vli_mod_sub(t7, t7, t6, curve_prime, ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1132) /* t6 = x3' - B */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1133) vli_mod_sub(t6, t7, x1, curve_prime, ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1134) /* t6 = (y2 + y1)*(x3' - B) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1135) vli_mod_mult_fast(t6, t6, t5, curve_prime, ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1136) /* t2 = y3' */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1137) vli_mod_sub(y1, t6, y1, curve_prime, ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1138)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1139) vli_set(x1, t7, ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1140) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1141)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1142) static void ecc_point_mult(struct ecc_point *result,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1143) const struct ecc_point *point, const u64 *scalar,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1144) u64 *initial_z, const struct ecc_curve *curve,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1145) unsigned int ndigits)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1146) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1147) /* R0 and R1 */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1148) u64 rx[2][ECC_MAX_DIGITS];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1149) u64 ry[2][ECC_MAX_DIGITS];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1150) u64 z[ECC_MAX_DIGITS];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1151) u64 sk[2][ECC_MAX_DIGITS];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1152) u64 *curve_prime = curve->p;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1153) int i, nb;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1154) int num_bits;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1155) int carry;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1156)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1157) carry = vli_add(sk[0], scalar, curve->n, ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1158) vli_add(sk[1], sk[0], curve->n, ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1159) scalar = sk[!carry];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1160) num_bits = sizeof(u64) * ndigits * 8 + 1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1161)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1162) vli_set(rx[1], point->x, ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1163) vli_set(ry[1], point->y, ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1164)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1165) xycz_initial_double(rx[1], ry[1], rx[0], ry[0], initial_z, curve_prime,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1166) ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1167)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1168) for (i = num_bits - 2; i > 0; i--) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1169) nb = !vli_test_bit(scalar, i);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1170) xycz_add_c(rx[1 - nb], ry[1 - nb], rx[nb], ry[nb], curve_prime,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1171) ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1172) xycz_add(rx[nb], ry[nb], rx[1 - nb], ry[1 - nb], curve_prime,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1173) ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1174) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1175)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1176) nb = !vli_test_bit(scalar, 0);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1177) xycz_add_c(rx[1 - nb], ry[1 - nb], rx[nb], ry[nb], curve_prime,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1178) ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1179)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1180) /* Find final 1/Z value. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1181) /* X1 - X0 */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1182) vli_mod_sub(z, rx[1], rx[0], curve_prime, ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1183) /* Yb * (X1 - X0) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1184) vli_mod_mult_fast(z, z, ry[1 - nb], curve_prime, ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1185) /* xP * Yb * (X1 - X0) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1186) vli_mod_mult_fast(z, z, point->x, curve_prime, ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1187)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1188) /* 1 / (xP * Yb * (X1 - X0)) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1189) vli_mod_inv(z, z, curve_prime, point->ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1190)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1191) /* yP / (xP * Yb * (X1 - X0)) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1192) vli_mod_mult_fast(z, z, point->y, curve_prime, ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1193) /* Xb * yP / (xP * Yb * (X1 - X0)) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1194) vli_mod_mult_fast(z, z, rx[1 - nb], curve_prime, ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1195) /* End 1/Z calculation */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1196)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1197) xycz_add(rx[nb], ry[nb], rx[1 - nb], ry[1 - nb], curve_prime, ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1198)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1199) apply_z(rx[0], ry[0], z, curve_prime, ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1200)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1201) vli_set(result->x, rx[0], ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1202) vli_set(result->y, ry[0], ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1203) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1204)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1205) /* Computes R = P + Q mod p */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1206) static void ecc_point_add(const struct ecc_point *result,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1207) const struct ecc_point *p, const struct ecc_point *q,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1208) const struct ecc_curve *curve)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1209) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1210) u64 z[ECC_MAX_DIGITS];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1211) u64 px[ECC_MAX_DIGITS];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1212) u64 py[ECC_MAX_DIGITS];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1213) unsigned int ndigits = curve->g.ndigits;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1214)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1215) vli_set(result->x, q->x, ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1216) vli_set(result->y, q->y, ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1217) vli_mod_sub(z, result->x, p->x, curve->p, ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1218) vli_set(px, p->x, ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1219) vli_set(py, p->y, ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1220) xycz_add(px, py, result->x, result->y, curve->p, ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1221) vli_mod_inv(z, z, curve->p, ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1222) apply_z(result->x, result->y, z, curve->p, ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1223) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1224)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1225) /* Computes R = u1P + u2Q mod p using Shamir's trick.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1226) * Based on: Kenneth MacKay's micro-ecc (2014).
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1227) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1228) void ecc_point_mult_shamir(const struct ecc_point *result,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1229) const u64 *u1, const struct ecc_point *p,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1230) const u64 *u2, const struct ecc_point *q,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1231) const struct ecc_curve *curve)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1232) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1233) u64 z[ECC_MAX_DIGITS];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1234) u64 sump[2][ECC_MAX_DIGITS];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1235) u64 *rx = result->x;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1236) u64 *ry = result->y;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1237) unsigned int ndigits = curve->g.ndigits;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1238) unsigned int num_bits;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1239) struct ecc_point sum = ECC_POINT_INIT(sump[0], sump[1], ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1240) const struct ecc_point *points[4];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1241) const struct ecc_point *point;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1242) unsigned int idx;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1243) int i;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1244)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1245) ecc_point_add(&sum, p, q, curve);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1246) points[0] = NULL;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1247) points[1] = p;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1248) points[2] = q;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1249) points[3] = ∑
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1250)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1251) num_bits = max(vli_num_bits(u1, ndigits),
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1252) vli_num_bits(u2, ndigits));
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1253) i = num_bits - 1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1254) idx = (!!vli_test_bit(u1, i)) | ((!!vli_test_bit(u2, i)) << 1);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1255) point = points[idx];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1256)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1257) vli_set(rx, point->x, ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1258) vli_set(ry, point->y, ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1259) vli_clear(z + 1, ndigits - 1);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1260) z[0] = 1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1261)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1262) for (--i; i >= 0; i--) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1263) ecc_point_double_jacobian(rx, ry, z, curve->p, ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1264) idx = (!!vli_test_bit(u1, i)) | ((!!vli_test_bit(u2, i)) << 1);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1265) point = points[idx];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1266) if (point) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1267) u64 tx[ECC_MAX_DIGITS];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1268) u64 ty[ECC_MAX_DIGITS];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1269) u64 tz[ECC_MAX_DIGITS];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1270)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1271) vli_set(tx, point->x, ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1272) vli_set(ty, point->y, ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1273) apply_z(tx, ty, z, curve->p, ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1274) vli_mod_sub(tz, rx, tx, curve->p, ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1275) xycz_add(tx, ty, rx, ry, curve->p, ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1276) vli_mod_mult_fast(z, z, tz, curve->p, ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1277) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1278) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1279) vli_mod_inv(z, z, curve->p, ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1280) apply_z(rx, ry, z, curve->p, ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1281) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1282) EXPORT_SYMBOL(ecc_point_mult_shamir);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1283)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1284) static inline void ecc_swap_digits(const u64 *in, u64 *out,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1285) unsigned int ndigits)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1286) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1287) const __be64 *src = (__force __be64 *)in;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1288) int i;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1289)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1290) for (i = 0; i < ndigits; i++)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1291) out[i] = be64_to_cpu(src[ndigits - 1 - i]);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1292) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1293)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1294) static int __ecc_is_key_valid(const struct ecc_curve *curve,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1295) const u64 *private_key, unsigned int ndigits)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1296) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1297) u64 one[ECC_MAX_DIGITS] = { 1, };
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1298) u64 res[ECC_MAX_DIGITS];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1299)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1300) if (!private_key)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1301) return -EINVAL;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1302)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1303) if (curve->g.ndigits != ndigits)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1304) return -EINVAL;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1305)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1306) /* Make sure the private key is in the range [2, n-3]. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1307) if (vli_cmp(one, private_key, ndigits) != -1)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1308) return -EINVAL;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1309) vli_sub(res, curve->n, one, ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1310) vli_sub(res, res, one, ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1311) if (vli_cmp(res, private_key, ndigits) != 1)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1312) return -EINVAL;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1313)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1314) return 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1315) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1316)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1317) int ecc_is_key_valid(unsigned int curve_id, unsigned int ndigits,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1318) const u64 *private_key, unsigned int private_key_len)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1319) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1320) int nbytes;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1321) const struct ecc_curve *curve = ecc_get_curve(curve_id);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1322)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1323) nbytes = ndigits << ECC_DIGITS_TO_BYTES_SHIFT;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1324)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1325) if (private_key_len != nbytes)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1326) return -EINVAL;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1327)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1328) return __ecc_is_key_valid(curve, private_key, ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1329) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1330) EXPORT_SYMBOL(ecc_is_key_valid);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1331)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1332) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1333) * ECC private keys are generated using the method of extra random bits,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1334) * equivalent to that described in FIPS 186-4, Appendix B.4.1.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1335) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1336) * d = (c mod(n–1)) + 1 where c is a string of random bits, 64 bits longer
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1337) * than requested
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1338) * 0 <= c mod(n-1) <= n-2 and implies that
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1339) * 1 <= d <= n-1
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1340) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1341) * This method generates a private key uniformly distributed in the range
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1342) * [1, n-1].
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1343) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1344) int ecc_gen_privkey(unsigned int curve_id, unsigned int ndigits, u64 *privkey)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1345) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1346) const struct ecc_curve *curve = ecc_get_curve(curve_id);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1347) u64 priv[ECC_MAX_DIGITS];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1348) unsigned int nbytes = ndigits << ECC_DIGITS_TO_BYTES_SHIFT;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1349) unsigned int nbits = vli_num_bits(curve->n, ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1350) int err;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1351)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1352) /* Check that N is included in Table 1 of FIPS 186-4, section 6.1.1 */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1353) if (nbits < 160 || ndigits > ARRAY_SIZE(priv))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1354) return -EINVAL;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1355)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1356) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1357) * FIPS 186-4 recommends that the private key should be obtained from a
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1358) * RBG with a security strength equal to or greater than the security
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1359) * strength associated with N.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1360) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1361) * The maximum security strength identified by NIST SP800-57pt1r4 for
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1362) * ECC is 256 (N >= 512).
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1363) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1364) * This condition is met by the default RNG because it selects a favored
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1365) * DRBG with a security strength of 256.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1366) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1367) if (crypto_get_default_rng())
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1368) return -EFAULT;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1369)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1370) err = crypto_rng_get_bytes(crypto_default_rng, (u8 *)priv, nbytes);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1371) crypto_put_default_rng();
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1372) if (err)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1373) return err;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1374)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1375) /* Make sure the private key is in the valid range. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1376) if (__ecc_is_key_valid(curve, priv, ndigits))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1377) return -EINVAL;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1378)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1379) ecc_swap_digits(priv, privkey, ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1380)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1381) return 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1382) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1383) EXPORT_SYMBOL(ecc_gen_privkey);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1384)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1385) int ecc_make_pub_key(unsigned int curve_id, unsigned int ndigits,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1386) const u64 *private_key, u64 *public_key)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1387) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1388) int ret = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1389) struct ecc_point *pk;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1390) u64 priv[ECC_MAX_DIGITS];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1391) const struct ecc_curve *curve = ecc_get_curve(curve_id);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1392)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1393) if (!private_key || !curve || ndigits > ARRAY_SIZE(priv)) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1394) ret = -EINVAL;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1395) goto out;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1396) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1397)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1398) ecc_swap_digits(private_key, priv, ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1399)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1400) pk = ecc_alloc_point(ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1401) if (!pk) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1402) ret = -ENOMEM;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1403) goto out;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1404) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1405)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1406) ecc_point_mult(pk, &curve->g, priv, NULL, curve, ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1407)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1408) /* SP800-56A rev 3 5.6.2.1.3 key check */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1409) if (ecc_is_pubkey_valid_full(curve, pk)) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1410) ret = -EAGAIN;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1411) goto err_free_point;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1412) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1413)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1414) ecc_swap_digits(pk->x, public_key, ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1415) ecc_swap_digits(pk->y, &public_key[ndigits], ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1416)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1417) err_free_point:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1418) ecc_free_point(pk);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1419) out:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1420) return ret;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1421) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1422) EXPORT_SYMBOL(ecc_make_pub_key);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1423)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1424) /* SP800-56A section 5.6.2.3.4 partial verification: ephemeral keys only */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1425) int ecc_is_pubkey_valid_partial(const struct ecc_curve *curve,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1426) struct ecc_point *pk)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1427) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1428) u64 yy[ECC_MAX_DIGITS], xxx[ECC_MAX_DIGITS], w[ECC_MAX_DIGITS];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1429)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1430) if (WARN_ON(pk->ndigits != curve->g.ndigits))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1431) return -EINVAL;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1432)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1433) /* Check 1: Verify key is not the zero point. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1434) if (ecc_point_is_zero(pk))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1435) return -EINVAL;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1436)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1437) /* Check 2: Verify key is in the range [1, p-1]. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1438) if (vli_cmp(curve->p, pk->x, pk->ndigits) != 1)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1439) return -EINVAL;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1440) if (vli_cmp(curve->p, pk->y, pk->ndigits) != 1)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1441) return -EINVAL;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1442)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1443) /* Check 3: Verify that y^2 == (x^3 + a·x + b) mod p */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1444) vli_mod_square_fast(yy, pk->y, curve->p, pk->ndigits); /* y^2 */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1445) vli_mod_square_fast(xxx, pk->x, curve->p, pk->ndigits); /* x^2 */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1446) vli_mod_mult_fast(xxx, xxx, pk->x, curve->p, pk->ndigits); /* x^3 */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1447) vli_mod_mult_fast(w, curve->a, pk->x, curve->p, pk->ndigits); /* a·x */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1448) vli_mod_add(w, w, curve->b, curve->p, pk->ndigits); /* a·x + b */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1449) vli_mod_add(w, w, xxx, curve->p, pk->ndigits); /* x^3 + a·x + b */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1450) if (vli_cmp(yy, w, pk->ndigits) != 0) /* Equation */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1451) return -EINVAL;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1452)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1453) return 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1454) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1455) EXPORT_SYMBOL(ecc_is_pubkey_valid_partial);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1456)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1457) /* SP800-56A section 5.6.2.3.3 full verification */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1458) int ecc_is_pubkey_valid_full(const struct ecc_curve *curve,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1459) struct ecc_point *pk)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1460) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1461) struct ecc_point *nQ;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1462)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1463) /* Checks 1 through 3 */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1464) int ret = ecc_is_pubkey_valid_partial(curve, pk);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1465)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1466) if (ret)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1467) return ret;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1468)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1469) /* Check 4: Verify that nQ is the zero point. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1470) nQ = ecc_alloc_point(pk->ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1471) if (!nQ)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1472) return -ENOMEM;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1473)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1474) ecc_point_mult(nQ, pk, curve->n, NULL, curve, pk->ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1475) if (!ecc_point_is_zero(nQ))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1476) ret = -EINVAL;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1477)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1478) ecc_free_point(nQ);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1479)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1480) return ret;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1481) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1482) EXPORT_SYMBOL(ecc_is_pubkey_valid_full);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1483)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1484) int crypto_ecdh_shared_secret(unsigned int curve_id, unsigned int ndigits,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1485) const u64 *private_key, const u64 *public_key,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1486) u64 *secret)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1487) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1488) int ret = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1489) struct ecc_point *product, *pk;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1490) u64 priv[ECC_MAX_DIGITS];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1491) u64 rand_z[ECC_MAX_DIGITS];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1492) unsigned int nbytes;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1493) const struct ecc_curve *curve = ecc_get_curve(curve_id);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1494)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1495) if (!private_key || !public_key || !curve ||
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1496) ndigits > ARRAY_SIZE(priv) || ndigits > ARRAY_SIZE(rand_z)) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1497) ret = -EINVAL;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1498) goto out;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1499) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1500)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1501) nbytes = ndigits << ECC_DIGITS_TO_BYTES_SHIFT;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1502)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1503) get_random_bytes(rand_z, nbytes);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1504)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1505) pk = ecc_alloc_point(ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1506) if (!pk) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1507) ret = -ENOMEM;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1508) goto out;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1509) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1510)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1511) ecc_swap_digits(public_key, pk->x, ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1512) ecc_swap_digits(&public_key[ndigits], pk->y, ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1513) ret = ecc_is_pubkey_valid_partial(curve, pk);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1514) if (ret)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1515) goto err_alloc_product;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1516)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1517) ecc_swap_digits(private_key, priv, ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1518)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1519) product = ecc_alloc_point(ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1520) if (!product) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1521) ret = -ENOMEM;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1522) goto err_alloc_product;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1523) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1524)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1525) ecc_point_mult(product, pk, priv, rand_z, curve, ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1526)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1527) if (ecc_point_is_zero(product)) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1528) ret = -EFAULT;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1529) goto err_validity;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1530) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1531)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1532) ecc_swap_digits(product->x, secret, ndigits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1533)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1534) err_validity:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1535) memzero_explicit(priv, sizeof(priv));
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1536) memzero_explicit(rand_z, sizeof(rand_z));
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1537) ecc_free_point(product);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1538) err_alloc_product:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1539) ecc_free_point(pk);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1540) out:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1541) return ret;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1542) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1543) EXPORT_SYMBOL(crypto_ecdh_shared_secret);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1544)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1545) MODULE_LICENSE("Dual BSD/GPL");
Orange Pi5 kernel
Deprecated Linux kernel 5.10.110 for OrangePi 5/5B/5+ boards
3 Commits
0 Branches
0 Tags