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