tc_ecc.h

Go to the documentation of this file.

/* ecc.h - TinyCrypt interface to common ECC functions */

/* Copyright (c) 2014, Kenneth MacKay
 * All rights reserved.
 *
 * 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.
 */

/*
 *  Copyright (C) 2017 by Intel Corporation, All Rights Reserved.
 *
 *  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.
 *
 *    - Neither the name of Intel Corporation nor the names of its contributors
 *    may be used to endorse or promote products derived from this software
 *    without specific prior written permission.
 *
 *  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 OWNER 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.
 */

#ifndef __TC_UECC_H__
#define __TC_UECC_H__

#include <stdint.h>

#ifdef __cplusplus
extern "C" {
#endif

/* Word size (4 bytes considering 32-bits architectures) */
#define tc_uECC_WORD_SIZE 4

/* setting max number of calls to prng: */
#ifndef tc_uECC_RNG_MAX_TRIES
#define tc_uECC_RNG_MAX_TRIES 64
#endif

/* defining data types to store word and bit counts: */
typedef int8_t wordcount_t;
typedef int16_t bitcount_t;
/* defining data type for comparison result: */
typedef int8_t cmpresult_t;
/* defining data type to store ECC coordinate/point in 32bits words: */
typedef unsigned int tc_uECC_word_t;
/* defining data type to store an ECC coordinate/point in 64bits words: */
typedef uint64_t tc_uECC_dword_t;

/* defining masks useful for ecc computations: */
#define HIGH_BIT_SET 0x80000000
#define tc_uECC_WORD_BITS 32
#define tc_uECC_WORD_BITS_SHIFT 5
#define tc_uECC_WORD_BITS_MASK 0x01F

/* Number of words of 32 bits to represent an element of the the curve p-256: */
#define NUM_ECC_WORDS 8
/* Number of bytes to represent an element of the the curve p-256: */
#define NUM_ECC_BYTES (tc_uECC_WORD_SIZE*NUM_ECC_WORDS)

/* structure that represents an elliptic curve (e.g. p256):*/
struct tc_uECC_Curve_t;
typedef const struct tc_uECC_Curve_t * tc_uECC_Curve;
struct tc_uECC_Curve_t {
  wordcount_t num_words;
  wordcount_t num_bytes;
  bitcount_t num_n_bits;
  tc_uECC_word_t p[NUM_ECC_WORDS];
  tc_uECC_word_t n[NUM_ECC_WORDS];
  tc_uECC_word_t G[NUM_ECC_WORDS * 2];
  tc_uECC_word_t b[NUM_ECC_WORDS];
  void (*double_jacobian)(tc_uECC_word_t * X1, tc_uECC_word_t * Y1, tc_uECC_word_t * Z1,
  tc_uECC_Curve curve);
  void (*x_side)(tc_uECC_word_t *result, const tc_uECC_word_t *x, tc_uECC_Curve curve);
  void (*mmod_fast)(tc_uECC_word_t *result, tc_uECC_word_t *product);
};

/*
 * @brief computes doubling of point ion jacobian coordinates, in place.
 * @param X1 IN/OUT -- x coordinate
 * @param Y1 IN/OUT -- y coordinate
 * @param Z1 IN/OUT -- z coordinate
 * @param curve IN -- elliptic curve
 */
void double_jacobian_default(tc_uECC_word_t * X1, tc_uECC_word_t * Y1,
           tc_uECC_word_t * Z1, tc_uECC_Curve curve);

/*
 * @brief Computes x^3 + ax + b. result must not overlap x.
 * @param result OUT -- x^3 + ax + b
 * @param x IN -- value of x
 * @param curve IN -- elliptic curve
 */
void x_side_default(tc_uECC_word_t *result, const tc_uECC_word_t *x,
        tc_uECC_Curve curve);

/*
 * @brief Computes result = product % curve_p
 * from http://www.nsa.gov/ia/_files/nist-routines.pdf
 * @param result OUT -- product % curve_p
 * @param product IN -- value to be reduced mod curve_p
 */
void vli_mmod_fast_secp256r1(unsigned int *result, unsigned int *product);

/* Bytes to words ordering: */
#define BYTES_TO_WORDS_8(a, b, c, d, e, f, g, h) 0x##d##c##b##a, 0x##h##g##f##e
#define BYTES_TO_WORDS_4(a, b, c, d) 0x##d##c##b##a
#define BITS_TO_WORDS(num_bits) \
  ((num_bits + ((tc_uECC_WORD_SIZE * 8) - 1)) / (tc_uECC_WORD_SIZE * 8))
#define BITS_TO_BYTES(num_bits) ((num_bits + 7) / 8)

/* definition of curve NIST p-256: */
static const struct tc_uECC_Curve_t curve_secp256r1 = {
  NUM_ECC_WORDS,
  NUM_ECC_BYTES,
  256, /* num_n_bits */ {
    BYTES_TO_WORDS_8(FF, FF, FF, FF, FF, FF, FF, FF),
    BYTES_TO_WORDS_8(FF, FF, FF, FF, 00, 00, 00, 00),
          BYTES_TO_WORDS_8(00, 00, 00, 00, 00, 00, 00, 00),
          BYTES_TO_WORDS_8(01, 00, 00, 00, FF, FF, FF, FF)
  }, {
    BYTES_TO_WORDS_8(51, 25, 63, FC, C2, CA, B9, F3),
              BYTES_TO_WORDS_8(84, 9E, 17, A7, AD, FA, E6, BC),
              BYTES_TO_WORDS_8(FF, FF, FF, FF, FF, FF, FF, FF),
              BYTES_TO_WORDS_8(00, 00, 00, 00, FF, FF, FF, FF)
  }, {
    BYTES_TO_WORDS_8(96, C2, 98, D8, 45, 39, A1, F4),
                BYTES_TO_WORDS_8(A0, 33, EB, 2D, 81, 7D, 03, 77),
                BYTES_TO_WORDS_8(F2, 40, A4, 63, E5, E6, BC, F8),
                BYTES_TO_WORDS_8(47, 42, 2C, E1, F2, D1, 17, 6B),

                BYTES_TO_WORDS_8(F5, 51, BF, 37, 68, 40, B6, CB),
                BYTES_TO_WORDS_8(CE, 5E, 31, 6B, 57, 33, CE, 2B),
                BYTES_TO_WORDS_8(16, 9E, 0F, 7C, 4A, EB, E7, 8E),
                BYTES_TO_WORDS_8(9B, 7F, 1A, FE, E2, 42, E3, 4F)
  }, {
    BYTES_TO_WORDS_8(4B, 60, D2, 27, 3E, 3C, CE, 3B),
                BYTES_TO_WORDS_8(F6, B0, 53, CC, B0, 06, 1D, 65),
                BYTES_TO_WORDS_8(BC, 86, 98, 76, 55, BD, EB, B3),
                BYTES_TO_WORDS_8(E7, 93, 3A, AA, D8, 35, C6, 5A)
  },
        &double_jacobian_default,
        &x_side_default,
        &vli_mmod_fast_secp256r1
};

tc_uECC_Curve tc_uECC_secp256r1(void);

/*
 * @brief Generates a random integer in the range 0 < random < top.
 * Both random and top have num_words words.
 * @param random OUT -- random integer in the range 0 < random < top
 * @param top IN -- upper limit
 * @param num_words IN -- number of words
 * @return a random integer in the range 0 < random < top
 */
int tc_uECC_generate_random_int(tc_uECC_word_t *random, const tc_uECC_word_t *top,
           wordcount_t num_words);


/* tc_uECC_RNG_Function type
 * The RNG function should fill 'size' random bytes into 'dest'. It should
 * return 1 if 'dest' was filled with random data, or 0 if the random data could
 * not be generated. The filled-in values should be either truly random, or from
 * a cryptographically-secure PRNG.
 *
 * A correctly functioning RNG function must be set (using tc_uECC_set_rng())
 * before calling tc_uECC_make_key() or tc_uECC_sign().
 *
 * Setting a correctly functioning RNG function improves the resistance to
 * side-channel attacks for tc_uECC_shared_secret().
 *
 * A correct RNG function is set by default. If you are building on another
 * POSIX-compliant system that supports /dev/random or /dev/urandom, you can
 * define tc_uECC_POSIX to use the predefined RNG.
 */
typedef int(*tc_uECC_RNG_Function)(uint8_t *dest, unsigned int size);

/*
 * @brief Set the function that will be used to generate random bytes. The RNG
 * function should return 1 if the random data was generated, or 0 if the random
 * data could not be generated.
 *
 * @note On platforms where there is no predefined RNG function, this must be
 * called before tc_uECC_make_key() or tc_uECC_sign() are used.
 *
 * @param rng_function IN -- function that will be used to generate random bytes
 */
void tc_uECC_set_rng(tc_uECC_RNG_Function rng_function);

/*
 * @brief provides current tc_uECC_RNG_Function.
 * @return Returns the function that will be used to generate random bytes.
 */
tc_uECC_RNG_Function tc_uECC_get_rng(void);

/*
 * @brief computes the size of a private key for the curve in bytes.
 * @param curve IN -- elliptic curve
 * @return size of a private key for the curve in bytes.
 */
int tc_uECC_curve_private_key_size(tc_uECC_Curve curve);

/*
 * @brief computes the size of a public key for the curve in bytes.
 * @param curve IN -- elliptic curve
 * @return the size of a public key for the curve in bytes.
 */
int tc_uECC_curve_public_key_size(tc_uECC_Curve curve);

/*
 * @brief Compute the corresponding public key for a private key.
 * @param private_key IN -- The private key to compute the public key for
 * @param public_key OUT -- Will be filled in with the corresponding public key
 * @param curve
 * @return Returns 1 if key was computed successfully, 0 if an error occurred.
 */
int tc_uECC_compute_public_key(const uint8_t *private_key,
          uint8_t *public_key, tc_uECC_Curve curve);

/*
 * @brief Compute public-key.
 * @return corresponding public-key.
 * @param result OUT -- public-key
 * @param private_key IN -- private-key
 * @param curve IN -- elliptic curve
 */
tc_uECC_word_t EccPoint_compute_public_key(tc_uECC_word_t *result,
          tc_uECC_word_t *private_key, tc_uECC_Curve curve);

/*
 * @brief Regularize the bitcount for the private key so that attackers cannot
 * use a side channel attack to learn the number of leading zeros.
 * @return Regularized k
 * @param k IN -- private-key
 * @param k0 IN/OUT -- regularized k
 * @param k1 IN/OUT -- regularized k
 * @param curve IN -- elliptic curve
 */
tc_uECC_word_t regularize_k(const tc_uECC_word_t * const k, tc_uECC_word_t *k0,
       tc_uECC_word_t *k1, tc_uECC_Curve curve);

/*
 * @brief Point multiplication algorithm using Montgomery's ladder with co-Z
 * coordinates. See http://eprint.iacr.org/2011/338.pdf.
 * @note Result may overlap point.
 * @param result OUT -- returns scalar*point
 * @param point IN -- elliptic curve point
 * @param scalar IN -- scalar
 * @param initial_Z IN -- initial value for z
 * @param num_bits IN -- number of bits in scalar
 * @param curve IN -- elliptic curve
 */
void EccPoint_mult(tc_uECC_word_t * result, const tc_uECC_word_t * point,
       const tc_uECC_word_t * scalar, const tc_uECC_word_t * initial_Z,
       bitcount_t num_bits, tc_uECC_Curve curve);

/*
 * @brief Constant-time comparison to zero - secure way to compare long integers
 * @param vli IN -- very long integer
 * @param num_words IN -- number of words in the vli
 * @return 1 if vli == 0, 0 otherwise.
 */
tc_uECC_word_t tc_uECC_vli_isZero(const tc_uECC_word_t *vli, wordcount_t num_words);

/*
 * @brief Check if 'point' is the point at infinity
 * @param point IN -- elliptic curve point
 * @param curve IN -- elliptic curve
 * @return if 'point' is the point at infinity, 0 otherwise.
 */
tc_uECC_word_t EccPoint_isZero(const tc_uECC_word_t *point, tc_uECC_Curve curve);

/*
 * @brief computes the sign of left - right, in constant time.
 * @param left IN -- left term to be compared
 * @param right IN -- right term to be compared
 * @param num_words IN -- number of words
 * @return the sign of left - right
 */
cmpresult_t tc_uECC_vli_cmp(const tc_uECC_word_t *left, const tc_uECC_word_t *right,
       wordcount_t num_words);

/*
 * @brief computes sign of left - right, not in constant time.
 * @note should not be used if inputs are part of a secret
 * @param left IN -- left term to be compared
 * @param right IN -- right term to be compared
 * @param num_words IN -- number of words
 * @return the sign of left - right
 */
cmpresult_t tc_uECC_vli_cmp_unsafe(const tc_uECC_word_t *left, const tc_uECC_word_t *right,
        wordcount_t num_words);

/*
 * @brief Computes result = (left - right) % mod.
 * @note Assumes that (left < mod) and (right < mod), and that result does not
 * overlap mod.
 * @param result OUT -- (left - right) % mod
 * @param left IN -- leftright term in modular subtraction
 * @param right IN -- right term in modular subtraction
 * @param mod IN -- mod
 * @param num_words IN -- number of words
 */
void tc_uECC_vli_modSub(tc_uECC_word_t *result, const tc_uECC_word_t *left,
         const tc_uECC_word_t *right, const tc_uECC_word_t *mod,
         wordcount_t num_words);

/*
 * @brief Computes P' = (x1', y1', Z3), P + Q = (x3, y3, Z3) or
 * P => P', Q => P + Q
 * @note assumes Input P = (x1, y1, Z), Q = (x2, y2, Z)
 * @param X1 IN -- x coordinate of P
 * @param Y1 IN -- y coordinate of P
 * @param X2 IN -- x coordinate of Q
 * @param Y2 IN -- y coordinate of Q
 * @param curve IN -- elliptic curve
 */
void XYcZ_add(tc_uECC_word_t * X1, tc_uECC_word_t * Y1, tc_uECC_word_t * X2,
        tc_uECC_word_t * Y2, tc_uECC_Curve curve);

/*
 * @brief Computes (x1 * z^2, y1 * z^3)
 * @param X1 IN -- previous x1 coordinate
 * @param Y1 IN -- previous y1 coordinate
 * @param Z IN -- z value
 * @param curve IN -- elliptic curve
 */
void apply_z(tc_uECC_word_t * X1, tc_uECC_word_t * Y1, const tc_uECC_word_t * const Z,
       tc_uECC_Curve curve);

/*
 * @brief Check if bit is set.
 * @return Returns nonzero if bit 'bit' of vli is set.
 * @warning It is assumed that the value provided in 'bit' is within the
 * boundaries of the word-array 'vli'.
 * @note The bit ordering layout assumed for vli is: {31, 30, ..., 0},
 * {63, 62, ..., 32}, {95, 94, ..., 64}, {127, 126,..., 96} for a vli consisting
 * of 4 tc_uECC_word_t elements.
 */
tc_uECC_word_t tc_uECC_vli_testBit(const tc_uECC_word_t *vli, bitcount_t bit);

/*
 * @brief Computes result = product % mod, where product is 2N words long.
 * @param result OUT -- product % mod
 * @param mod IN -- module
 * @param num_words IN -- number of words
 * @warning Currently only designed to work for curve_p or curve_n.
 */
void tc_uECC_vli_mmod(tc_uECC_word_t *result, tc_uECC_word_t *product,
       const tc_uECC_word_t *mod, wordcount_t num_words);

/*
 * @brief Computes modular product (using curve->mmod_fast)
 * @param result OUT -- (left * right) mod % curve_p
 * @param left IN -- left term in product
 * @param right IN -- right term in product
 * @param curve IN -- elliptic curve
 */
void tc_uECC_vli_modMult_fast(tc_uECC_word_t *result, const tc_uECC_word_t *left,
         const tc_uECC_word_t *right, tc_uECC_Curve curve);

/*
 * @brief Computes result = left - right.
 * @note Can modify in place.
 * @param result OUT -- left - right
 * @param left IN -- left term in subtraction
 * @param right IN -- right term in subtraction
 * @param num_words IN -- number of words
 * @return borrow
 */
tc_uECC_word_t tc_uECC_vli_sub(tc_uECC_word_t *result, const tc_uECC_word_t *left,
       const tc_uECC_word_t *right, wordcount_t num_words);

/*
 * @brief Constant-time comparison function(secure way to compare long ints)
 * @param left IN -- left term in comparison
 * @param right IN -- right term in comparison
 * @param num_words IN -- number of words
 * @return Returns 0 if left == right, 1 otherwise.
 */
tc_uECC_word_t tc_uECC_vli_equal(const tc_uECC_word_t *left, const tc_uECC_word_t *right,
         wordcount_t num_words);

/*
 * @brief Computes (left * right) % mod
 * @param result OUT -- (left * right) % mod
 * @param left IN -- left term in product
 * @param right IN -- right term in product
 * @param mod IN -- mod
 * @param num_words IN -- number of words
 */
void tc_uECC_vli_modMult(tc_uECC_word_t *result, const tc_uECC_word_t *left,
          const tc_uECC_word_t *right, const tc_uECC_word_t *mod,
                wordcount_t num_words);

/*
 * @brief Computes (1 / input) % mod
 * @note All VLIs are the same size.
 * @note See "Euclid's GCD to Montgomery Multiplication to the Great Divide"
 * @param result OUT -- (1 / input) % mod
 * @param input IN -- value to be modular inverted
 * @param mod IN -- mod
 * @param num_words -- number of words
 */
void tc_uECC_vli_modInv(tc_uECC_word_t *result, const tc_uECC_word_t *input,
         const tc_uECC_word_t *mod, wordcount_t num_words);

/*
 * @brief Sets dest = src.
 * @param dest OUT -- destination buffer
 * @param src IN --  origin buffer
 * @param num_words IN -- number of words
 */
void tc_uECC_vli_set(tc_uECC_word_t *dest, const tc_uECC_word_t *src,
      wordcount_t num_words);

/*
 * @brief Computes (left + right) % mod.
 * @note Assumes that (left < mod) and right < mod), and that result does not
 * overlap mod.
 * @param result OUT -- (left + right) % mod.
 * @param left IN -- left term in addition
 * @param right IN -- right term in addition
 * @param mod IN -- mod
 * @param num_words IN -- number of words
 */
void tc_uECC_vli_modAdd(tc_uECC_word_t *result,  const tc_uECC_word_t *left,
             const tc_uECC_word_t *right, const tc_uECC_word_t *mod,
           wordcount_t num_words);

/*
 * @brief Counts the number of bits required to represent vli.
 * @param vli IN -- very long integer
 * @param max_words IN -- number of words
 * @return number of bits in given vli
 */
bitcount_t tc_uECC_vli_numBits(const tc_uECC_word_t *vli,
          const wordcount_t max_words);

/*
 * @brief Erases (set to 0) vli
 * @param vli IN -- very long integer
 * @param num_words IN -- number of words
 */
void tc_uECC_vli_clear(tc_uECC_word_t *vli, wordcount_t num_words);

/*
 * @brief check if it is a valid point in the curve
 * @param point IN -- point to be checked
 * @param curve IN -- elliptic curve
 * @return 0 if point is valid
 * @exception returns -1 if it is a point at infinity
 * @exception returns -2 if x or y is smaller than p,
 * @exception returns -3 if y^2 != x^3 + ax + b.
 */
int tc_uECC_valid_point(const tc_uECC_word_t *point, tc_uECC_Curve curve);

/*
 * @brief Check if a public key is valid.
 * @param public_key IN -- The public key to be checked.
 * @return returns 0 if the public key is valid
 * @exception returns -1 if it is a point at infinity
 * @exception returns -2 if x or y is smaller than p,
 * @exception returns -3 if y^2 != x^3 + ax + b.
 * @exception returns -4 if public key is the group generator.
 *
 * @note Note that you are not required to check for a valid public key before
 * using any other tc_uECC functions. However, you may wish to avoid spending CPU
 * time computing a shared secret or verifying a signature using an invalid
 * public key.
 */
int tc_uECC_valid_public_key(const uint8_t *public_key, tc_uECC_Curve curve);

 /*
  * @brief Converts an integer in tc_uECC native format to big-endian bytes.
  * @param bytes OUT -- bytes representation
  * @param num_bytes IN -- number of bytes
  * @param native IN -- tc_uECC native representation
  */
void tc_uECC_vli_nativeToBytes(uint8_t *bytes, int num_bytes,
              const unsigned int *native);

/*
 * @brief Converts big-endian bytes to an integer in tc_uECC native format.
 * @param native OUT -- tc_uECC native representation
 * @param bytes IN -- bytes representation
 * @param num_bytes IN -- number of bytes
 */
void tc_uECC_vli_bytesToNative(unsigned int *native, const uint8_t *bytes,
          int num_bytes);

#ifdef __cplusplus
}
#endif

#endif /* __TC_UECC_H__ */