/* Copyright (c) 2020, Google Inc. * * Permission to use, copy, modify, and/or distribute this software for any * purpose with or without fee is hereby granted, provided that the above * copyright notice and this permission notice appear in all copies. * * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY * SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION * OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN * CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. */ // An implementation of the NIST P-256 elliptic curve point multiplication. // 256-bit Montgomery form for 64 and 32-bit. Field operations are generated by // Fiat, which lives in //third_party/fiat. #include <openssl/base.h> #include <openssl/bn.h> #include <openssl/ec.h> #include <openssl/err.h> #include <openssl/mem.h> #include <assert.h> #include <string.h> #include "../../internal.h" #include "../delocate.h" #include "./internal.h" #if defined(BORINGSSL_HAS_UINT128) #include "../../../third_party/fiat/p256_64.h" #elif defined(OPENSSL_64_BIT) #include "../../../third_party/fiat/p256_64_msvc.h" #else #include "../../../third_party/fiat/p256_32.h" #endif // utility functions, handwritten #if defined(OPENSSL_64_BIT) #define FIAT_P256_NLIMBS … fiat_p256_limb_t; fiat_p256_felem; static const fiat_p256_felem fiat_p256_one = …; #else // 64BIT; else 32BIT #define FIAT_P256_NLIMBS … typedef uint32_t fiat_p256_limb_t; typedef uint32_t fiat_p256_felem[FIAT_P256_NLIMBS]; static const fiat_p256_felem fiat_p256_one = { 0x1, 0x0, 0x0, 0xffffffff, 0xffffffff, 0xffffffff, 0xfffffffe, 0x0}; #endif // 64BIT static fiat_p256_limb_t fiat_p256_nz( const fiat_p256_limb_t in1[FIAT_P256_NLIMBS]) { … } static void fiat_p256_copy(fiat_p256_limb_t out[FIAT_P256_NLIMBS], const fiat_p256_limb_t in1[FIAT_P256_NLIMBS]) { … } static void fiat_p256_cmovznz(fiat_p256_limb_t out[FIAT_P256_NLIMBS], fiat_p256_limb_t t, const fiat_p256_limb_t z[FIAT_P256_NLIMBS], const fiat_p256_limb_t nz[FIAT_P256_NLIMBS]) { … } static void fiat_p256_from_words(fiat_p256_felem out, const BN_ULONG in[32 / sizeof(BN_ULONG)]) { … } static void fiat_p256_from_generic(fiat_p256_felem out, const EC_FELEM *in) { … } static void fiat_p256_to_generic(EC_FELEM *out, const fiat_p256_felem in) { … } // fiat_p256_inv_square calculates |out| = |in|^{-2} // // Based on Fermat's Little Theorem: // a^p = a (mod p) // a^{p-1} = 1 (mod p) // a^{p-3} = a^{-2} (mod p) static void fiat_p256_inv_square(fiat_p256_felem out, const fiat_p256_felem in) { … } // Group operations // ---------------- // // Building on top of the field operations we have the operations on the // elliptic curve group itself. Points on the curve are represented in Jacobian // coordinates. // // Both operations were transcribed to Coq and proven to correspond to naive // implementations using Affine coordinates, for all suitable fields. In the // Coq proofs, issues of constant-time execution and memory layout (aliasing) // conventions were not considered. Specification of affine coordinates: // <https://github.com/mit-plv/fiat-crypto/blob/79f8b5f39ed609339f0233098dee1a3c4e6b3080/src/Spec/WeierstrassCurve.v#L28> // As a sanity check, a proof that these points form a commutative group: // <https://github.com/mit-plv/fiat-crypto/blob/79f8b5f39ed609339f0233098dee1a3c4e6b3080/src/Curves/Weierstrass/AffineProofs.v#L33> // fiat_p256_point_double calculates 2*(x_in, y_in, z_in) // // The method is taken from: // http://hyperelliptic.org/EFD/g1p/auto-shortw-jacobian-3.html#doubling-dbl-2001-b // // Coq transcription and correctness proof: // <https://github.com/mit-plv/fiat-crypto/blob/79f8b5f39ed609339f0233098dee1a3c4e6b3080/src/Curves/Weierstrass/Jacobian.v#L93> // <https://github.com/mit-plv/fiat-crypto/blob/79f8b5f39ed609339f0233098dee1a3c4e6b3080/src/Curves/Weierstrass/Jacobian.v#L201> // // Outputs can equal corresponding inputs, i.e., x_out == x_in is allowed. // while x_out == y_in is not (maybe this works, but it's not tested). static void fiat_p256_point_double(fiat_p256_felem x_out, fiat_p256_felem y_out, fiat_p256_felem z_out, const fiat_p256_felem x_in, const fiat_p256_felem y_in, const fiat_p256_felem z_in) { … } // fiat_p256_point_add calculates (x1, y1, z1) + (x2, y2, z2) // // The method is taken from: // http://hyperelliptic.org/EFD/g1p/auto-shortw-jacobian-3.html#addition-add-2007-bl, // adapted for mixed addition (z2 = 1, or z2 = 0 for the point at infinity). // // Coq transcription and correctness proof: // <https://github.com/mit-plv/fiat-crypto/blob/79f8b5f39ed609339f0233098dee1a3c4e6b3080/src/Curves/Weierstrass/Jacobian.v#L135> // <https://github.com/mit-plv/fiat-crypto/blob/79f8b5f39ed609339f0233098dee1a3c4e6b3080/src/Curves/Weierstrass/Jacobian.v#L205> // // This function includes a branch for checking whether the two input points // are equal, (while not equal to the point at infinity). This case never // happens during single point multiplication, so there is no timing leak for // ECDH or ECDSA signing. static void fiat_p256_point_add(fiat_p256_felem x3, fiat_p256_felem y3, fiat_p256_felem z3, const fiat_p256_felem x1, const fiat_p256_felem y1, const fiat_p256_felem z1, const int mixed, const fiat_p256_felem x2, const fiat_p256_felem y2, const fiat_p256_felem z2) { … } #include "./p256_table.h" // fiat_p256_select_point_affine selects the |idx-1|th point from a // precomputation table and copies it to out. If |idx| is zero, the output is // the point at infinity. static void fiat_p256_select_point_affine( const fiat_p256_limb_t idx, size_t size, const fiat_p256_felem pre_comp[/*size*/][2], fiat_p256_felem out[3]) { … } // fiat_p256_select_point selects the |idx|th point from a precomputation table // and copies it to out. static void fiat_p256_select_point(const fiat_p256_limb_t idx, size_t size, const fiat_p256_felem pre_comp[/*size*/][3], fiat_p256_felem out[3]) { … } // fiat_p256_get_bit returns the |i|th bit in |in|. static crypto_word_t fiat_p256_get_bit(const EC_SCALAR *in, int i) { … } // OPENSSL EC_METHOD FUNCTIONS // Takes the Jacobian coordinates (X, Y, Z) of a point and returns (X', Y') = // (X/Z^2, Y/Z^3). static int ec_GFp_nistp256_point_get_affine_coordinates( const EC_GROUP *group, const EC_JACOBIAN *point, EC_FELEM *x_out, EC_FELEM *y_out) { … } static void ec_GFp_nistp256_add(const EC_GROUP *group, EC_JACOBIAN *r, const EC_JACOBIAN *a, const EC_JACOBIAN *b) { … } static void ec_GFp_nistp256_dbl(const EC_GROUP *group, EC_JACOBIAN *r, const EC_JACOBIAN *a) { … } static void ec_GFp_nistp256_point_mul(const EC_GROUP *group, EC_JACOBIAN *r, const EC_JACOBIAN *p, const EC_SCALAR *scalar) { … } static void ec_GFp_nistp256_point_mul_base(const EC_GROUP *group, EC_JACOBIAN *r, const EC_SCALAR *scalar) { … } static void ec_GFp_nistp256_point_mul_public(const EC_GROUP *group, EC_JACOBIAN *r, const EC_SCALAR *g_scalar, const EC_JACOBIAN *p, const EC_SCALAR *p_scalar) { … } static int ec_GFp_nistp256_cmp_x_coordinate(const EC_GROUP *group, const EC_JACOBIAN *p, const EC_SCALAR *r) { … } DEFINE_METHOD_FUNCTION(EC_METHOD, EC_GFp_nistp256_method) { … }
Codebase Browser
chromium