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