/* * Copyright (c) 2013, 2014 Kenneth MacKay. All rights reserved. * Copyright (c) 2019 Vitaly Chikunov <[email protected]> * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions are * met: * * Redistributions of source code must retain the above copyright * notice, this list of conditions and the following disclaimer. * * Redistributions in binary form must reproduce the above copyright * notice, this list of conditions and the following disclaimer in the * documentation and/or other materials provided with the distribution. * * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT * HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. */ #include <crypto/ecc_curve.h> #include <linux/module.h> #include <linux/random.h> #include <linux/slab.h> #include <linux/swab.h> #include <linux/fips.h> #include <crypto/ecdh.h> #include <crypto/rng.h> #include <crypto/internal/ecc.h> #include <asm/unaligned.h> #include <linux/ratelimit.h> #include "ecc_curve_defs.h" uint128_t; /* Returns curv25519 curve param */ const struct ecc_curve *ecc_get_curve25519(void) { … } EXPORT_SYMBOL(…); const struct ecc_curve *ecc_get_curve(unsigned int curve_id) { … } EXPORT_SYMBOL(…); void ecc_digits_from_bytes(const u8 *in, unsigned int nbytes, u64 *out, unsigned int ndigits) { … } EXPORT_SYMBOL(…); static u64 *ecc_alloc_digits_space(unsigned int ndigits) { … } static void ecc_free_digits_space(u64 *space) { … } struct ecc_point *ecc_alloc_point(unsigned int ndigits) { … } EXPORT_SYMBOL(…); void ecc_free_point(struct ecc_point *p) { … } EXPORT_SYMBOL(…); static void vli_clear(u64 *vli, unsigned int ndigits) { … } /* Returns true if vli == 0, false otherwise. */ bool vli_is_zero(const u64 *vli, unsigned int ndigits) { … } EXPORT_SYMBOL(…); /* Returns nonzero if bit of vli is set. */ static u64 vli_test_bit(const u64 *vli, unsigned int bit) { … } static bool vli_is_negative(const u64 *vli, unsigned int ndigits) { … } /* Counts the number of 64-bit "digits" in vli. */ static unsigned int vli_num_digits(const u64 *vli, unsigned int ndigits) { … } /* Counts the number of bits required for vli. */ unsigned int vli_num_bits(const u64 *vli, unsigned int ndigits) { … } EXPORT_SYMBOL(…); /* Set dest from unaligned bit string src. */ void vli_from_be64(u64 *dest, const void *src, unsigned int ndigits) { … } EXPORT_SYMBOL(…); void vli_from_le64(u64 *dest, const void *src, unsigned int ndigits) { … } EXPORT_SYMBOL(…); /* Sets dest = src. */ static void vli_set(u64 *dest, const u64 *src, unsigned int ndigits) { … } /* Returns sign of left - right. */ int vli_cmp(const u64 *left, const u64 *right, unsigned int ndigits) { … } EXPORT_SYMBOL(…); /* Computes result = in << c, returning carry. Can modify in place * (if result == in). 0 < shift < 64. */ static u64 vli_lshift(u64 *result, const u64 *in, unsigned int shift, unsigned int ndigits) { … } /* Computes vli = vli >> 1. */ static void vli_rshift1(u64 *vli, unsigned int ndigits) { … } /* Computes result = left + right, returning carry. Can modify in place. */ static u64 vli_add(u64 *result, const u64 *left, const u64 *right, unsigned int ndigits) { … } /* Computes result = left + right, returning carry. Can modify in place. */ static u64 vli_uadd(u64 *result, const u64 *left, u64 right, unsigned int ndigits) { … } /* Computes result = left - right, returning borrow. Can modify in place. */ u64 vli_sub(u64 *result, const u64 *left, const u64 *right, unsigned int ndigits) { … } EXPORT_SYMBOL(…); /* Computes result = left - right, returning borrow. Can modify in place. */ static u64 vli_usub(u64 *result, const u64 *left, u64 right, unsigned int ndigits) { … } static uint128_t mul_64_64(u64 left, u64 right) { … } static uint128_t add_128_128(uint128_t a, uint128_t b) { … } static void vli_mult(u64 *result, const u64 *left, const u64 *right, unsigned int ndigits) { … } /* Compute product = left * right, for a small right value. */ static void vli_umult(u64 *result, const u64 *left, u32 right, unsigned int ndigits) { … } static void vli_square(u64 *result, const u64 *left, unsigned int ndigits) { … } /* Computes result = (left + right) % mod. * Assumes that left < mod and right < mod, result != mod. */ static void vli_mod_add(u64 *result, const u64 *left, const u64 *right, const u64 *mod, unsigned int ndigits) { … } /* Computes result = (left - right) % mod. * Assumes that left < mod and right < mod, result != mod. */ static void vli_mod_sub(u64 *result, const u64 *left, const u64 *right, const u64 *mod, unsigned int ndigits) { … } /* * Computes result = product % mod * for special form moduli: p = 2^k-c, for small c (note the minus sign) * * References: * R. Crandall, C. Pomerance. Prime Numbers: A Computational Perspective. * 9 Fast Algorithms for Large-Integer Arithmetic. 9.2.3 Moduli of special form * Algorithm 9.2.13 (Fast mod operation for special-form moduli). */ static void vli_mmod_special(u64 *result, const u64 *product, const u64 *mod, unsigned int ndigits) { … } /* * Computes result = product % mod * for special form moduli: p = 2^{k-1}+c, for small c (note the plus sign) * where k-1 does not fit into qword boundary by -1 bit (such as 255). * References (loosely based on): * A. Menezes, P. van Oorschot, S. Vanstone. Handbook of Applied Cryptography. * 14.3.4 Reduction methods for moduli of special form. Algorithm 14.47. * URL: http://cacr.uwaterloo.ca/hac/about/chap14.pdf * * H. Cohen, G. Frey, R. Avanzi, C. Doche, T. Lange, K. Nguyen, F. Vercauteren. * Handbook of Elliptic and Hyperelliptic Curve Cryptography. * Algorithm 10.25 Fast reduction for special form moduli */ static void vli_mmod_special2(u64 *result, const u64 *product, const u64 *mod, unsigned int ndigits) { … } /* * Computes result = product % mod, where product is 2N words long. * Reference: Ken MacKay's micro-ecc. * Currently only designed to work for curve_p or curve_n. */ static void vli_mmod_slow(u64 *result, u64 *product, const u64 *mod, unsigned int ndigits) { … } /* Computes result = product % mod using Barrett's reduction with precomputed * value mu appended to the mod after ndigits, mu = (2^{2w} / mod) and have * length ndigits + 1, where mu * (2^w - 1) should not overflow ndigits * boundary. * * Reference: * R. Brent, P. Zimmermann. Modern Computer Arithmetic. 2010. * 2.4.1 Barrett's algorithm. Algorithm 2.5. */ static void vli_mmod_barrett(u64 *result, u64 *product, const u64 *mod, unsigned int ndigits) { … } /* Computes p_result = p_product % curve_p. * See algorithm 5 and 6 from * http://www.isys.uni-klu.ac.at/PDF/2001-0126-MT.pdf */ static void vli_mmod_fast_192(u64 *result, const u64 *product, const u64 *curve_prime, u64 *tmp) { … } /* Computes result = product % curve_prime * from http://www.nsa.gov/ia/_files/nist-routines.pdf */ static void vli_mmod_fast_256(u64 *result, const u64 *product, const u64 *curve_prime, u64 *tmp) { … } #define SL32OR32 … #define AND64H … #define AND64L … /* Computes result = product % curve_prime * from "Mathematical routines for the NIST prime elliptic curves" */ static void vli_mmod_fast_384(u64 *result, const u64 *product, const u64 *curve_prime, u64 *tmp) { … } #undef SL32OR32 #undef AND64H #undef AND64L /* * Computes result = product % curve_prime * from "Recommendations for Discrete Logarithm-Based Cryptography: * Elliptic Curve Domain Parameters" section G.1.4 */ static void vli_mmod_fast_521(u64 *result, const u64 *product, const u64 *curve_prime, u64 *tmp) { … } /* Computes result = product % curve_prime for different curve_primes. * * Note that curve_primes are distinguished just by heuristic check and * not by complete conformance check. */ static bool vli_mmod_fast(u64 *result, u64 *product, const struct ecc_curve *curve) { … } /* Computes result = (left * right) % mod. * Assumes that mod is big enough curve order. */ void vli_mod_mult_slow(u64 *result, const u64 *left, const u64 *right, const u64 *mod, unsigned int ndigits) { … } EXPORT_SYMBOL(…); /* Computes result = (left * right) % curve_prime. */ static void vli_mod_mult_fast(u64 *result, const u64 *left, const u64 *right, const struct ecc_curve *curve) { … } /* Computes result = left^2 % curve_prime. */ static void vli_mod_square_fast(u64 *result, const u64 *left, const struct ecc_curve *curve) { … } #define EVEN(vli) … /* Computes result = (1 / p_input) % mod. All VLIs are the same size. * See "From Euclid's GCD to Montgomery Multiplication to the Great Divide" * https://labs.oracle.com/techrep/2001/smli_tr-2001-95.pdf */ void vli_mod_inv(u64 *result, const u64 *input, const u64 *mod, unsigned int ndigits) { … } EXPORT_SYMBOL(…); /* ------ Point operations ------ */ /* Returns true if p_point is the point at infinity, false otherwise. */ bool ecc_point_is_zero(const struct ecc_point *point) { … } EXPORT_SYMBOL(…); /* Point multiplication algorithm using Montgomery's ladder with co-Z * coordinates. From https://eprint.iacr.org/2011/338.pdf */ /* Double in place */ static void ecc_point_double_jacobian(u64 *x1, u64 *y1, u64 *z1, const struct ecc_curve *curve) { … } /* Modify (x1, y1) => (x1 * z^2, y1 * z^3) */ static void apply_z(u64 *x1, u64 *y1, u64 *z, const struct ecc_curve *curve) { … } /* P = (x1, y1) => 2P, (x2, y2) => P' */ static void xycz_initial_double(u64 *x1, u64 *y1, u64 *x2, u64 *y2, u64 *p_initial_z, const struct ecc_curve *curve) { … } /* Input P = (x1, y1, Z), Q = (x2, y2, Z) * Output P' = (x1', y1', Z3), P + Q = (x3, y3, Z3) * or P => P', Q => P + Q */ static void xycz_add(u64 *x1, u64 *y1, u64 *x2, u64 *y2, const struct ecc_curve *curve) { … } /* Input P = (x1, y1, Z), Q = (x2, y2, Z) * Output P + Q = (x3, y3, Z3), P - Q = (x3', y3', Z3) * or P => P - Q, Q => P + Q */ static void xycz_add_c(u64 *x1, u64 *y1, u64 *x2, u64 *y2, const struct ecc_curve *curve) { … } static void ecc_point_mult(struct ecc_point *result, const struct ecc_point *point, const u64 *scalar, u64 *initial_z, const struct ecc_curve *curve, unsigned int ndigits) { … } /* Computes R = P + Q mod p */ static void ecc_point_add(const struct ecc_point *result, const struct ecc_point *p, const struct ecc_point *q, const struct ecc_curve *curve) { … } /* Computes R = u1P + u2Q mod p using Shamir's trick. * Based on: Kenneth MacKay's micro-ecc (2014). */ void ecc_point_mult_shamir(const struct ecc_point *result, const u64 *u1, const struct ecc_point *p, const u64 *u2, const struct ecc_point *q, const struct ecc_curve *curve) { … } EXPORT_SYMBOL(…); /* * This function performs checks equivalent to Appendix A.4.2 of FIPS 186-5. * Whereas A.4.2 results in an integer in the interval [1, n-1], this function * ensures that the integer is in the range of [2, n-3]. We are slightly * stricter because of the currently used scalar multiplication algorithm. */ static int __ecc_is_key_valid(const struct ecc_curve *curve, const u64 *private_key, unsigned int ndigits) { … } int ecc_is_key_valid(unsigned int curve_id, unsigned int ndigits, const u64 *private_key, unsigned int private_key_len) { … } EXPORT_SYMBOL(…); /* * ECC private keys are generated using the method of rejection sampling, * equivalent to that described in FIPS 186-5, Appendix A.2.2. * * This method generates a private key uniformly distributed in the range * [2, n-3]. */ int ecc_gen_privkey(unsigned int curve_id, unsigned int ndigits, u64 *private_key) { … } EXPORT_SYMBOL(…); int ecc_make_pub_key(unsigned int curve_id, unsigned int ndigits, const u64 *private_key, u64 *public_key) { … } EXPORT_SYMBOL(…); /* SP800-56A section 5.6.2.3.4 partial verification: ephemeral keys only */ int ecc_is_pubkey_valid_partial(const struct ecc_curve *curve, struct ecc_point *pk) { … } EXPORT_SYMBOL(…); /* SP800-56A section 5.6.2.3.3 full verification */ int ecc_is_pubkey_valid_full(const struct ecc_curve *curve, struct ecc_point *pk) { … } EXPORT_SYMBOL(…); int crypto_ecdh_shared_secret(unsigned int curve_id, unsigned int ndigits, const u64 *private_key, const u64 *public_key, u64 *secret) { … } EXPORT_SYMBOL(…); MODULE_DESCRIPTION(…) …; MODULE_LICENSE(…) …;
Codebase Browser
linux