hash_to_curve.c | Explore in Territory

/* 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. */

#include <openssl/ec.h>

#include <openssl/digest.h>
#include <openssl/err.h>
#include <openssl/nid.h>

#include <assert.h>

#include "internal.h"
#include "../fipsmodule/bn/internal.h"
#include "../fipsmodule/ec/internal.h"
#include "../internal.h"


// This file implements hash-to-curve, as described in RFC 9380.
//
// This hash-to-curve implementation is written generically with the
// expectation that we will eventually wish to support other curves. If it
// becomes a performance bottleneck, some possible optimizations by
// specializing it to the curve:
//
// - Rather than using a generic |felem_exp|, specialize the exponentation to
//   c2 with a faster addition chain.
//
// - |felem_mul| and |felem_sqr| are indirect calls to generic Montgomery
//   code. Given the few curves, we could specialize
//   |map_to_curve_simple_swu|. But doing this reasonably without duplicating
//   code in C is difficult. (C++ templates would be useful here.)
//
// - P-521's Z and c2 have small power-of-two absolute values. We could save
//   two multiplications in SSWU. (Other curves have reasonable values of Z
//   and inconvenient c2.) This is unlikely to be worthwhile without C++
//   templates to make specializing more convenient.

// expand_message_xmd implements the operation described in section 5.3.1 of
// RFC 9380. It returns one on success and zero on error.
static int expand_message_xmd(const EVP_MD *md, uint8_t *out, size_t out_len,
                              const uint8_t *msg, size_t msg_len,
                              const uint8_t *dst, size_t dst_len) { … }

// num_bytes_to_derive determines the number of bytes to derive when hashing to
// a number modulo |modulus|. See the hash_to_field operation defined in
// section 5.2 of RFC 9380.
static int num_bytes_to_derive(size_t *out, const BIGNUM *modulus, unsigned k) { … }

// big_endian_to_words decodes |in| as a big-endian integer and writes the
// result to |out|. |num_words| must be large enough to contain the output.
static void big_endian_to_words(BN_ULONG *out, size_t num_words,
                                const uint8_t *in, size_t len) { … }

// hash_to_field implements the operation described in section 5.2
// of RFC 9380, with count = 2. |k| is the security factor.
static int hash_to_field2(const EC_GROUP *group, const EVP_MD *md,
                          EC_FELEM *out1, EC_FELEM *out2, const uint8_t *dst,
                          size_t dst_len, unsigned k, const uint8_t *msg,
                          size_t msg_len) { … }

// hash_to_scalar behaves like |hash_to_field2| but returns a value modulo the
// group order rather than a field element. |k| is the security factor.
static int hash_to_scalar(const EC_GROUP *group, const EVP_MD *md,
                          EC_SCALAR *out, const uint8_t *dst, size_t dst_len,
                          unsigned k, const uint8_t *msg, size_t msg_len) { … }

static inline void mul_A(const EC_GROUP *group, EC_FELEM *out,
                         const EC_FELEM *in) { … }

// sgn0 implements the operation described in section 4.1.2 of RFC 9380.
static BN_ULONG sgn0(const EC_GROUP *group, const EC_FELEM *a) { … }

OPENSSL_UNUSED static int is_3mod4(const EC_GROUP *group) { … }

// sqrt_ratio_3mod4 implements the operation described in appendix F.2.1.2
// of RFC 9380.
static BN_ULONG sqrt_ratio_3mod4(const EC_GROUP *group, const EC_FELEM *Z,
                                 const BN_ULONG *c1, size_t num_c1,
                                 const EC_FELEM *c2, EC_FELEM *out_y,
                                 const EC_FELEM *u, const EC_FELEM *v) { … }

// map_to_curve_simple_swu implements the operation described in section 6.6.2
// of RFC 9380, using the straight-line implementation in appendix F.2.
static void map_to_curve_simple_swu(const EC_GROUP *group, const EC_FELEM *Z,
                                    const BN_ULONG *c1, size_t num_c1,
                                    const EC_FELEM *c2, EC_JACOBIAN *out,
                                    const EC_FELEM *u) { … }

static int hash_to_curve(const EC_GROUP *group, const EVP_MD *md,
                         const EC_FELEM *Z, const EC_FELEM *c2, unsigned k,
                         EC_JACOBIAN *out, const uint8_t *dst, size_t dst_len,
                         const uint8_t *msg, size_t msg_len) { … }

static int felem_from_u8(const EC_GROUP *group, EC_FELEM *out, uint8_t a) { … }

// kP256Sqrt10 is sqrt(10) in P-256's field. It was computed as follows in
// python3:
//
// p =  2**256 - 2**224 + 2**192 + 2**96 - 1
// c2 = pow(10, (p+1)//4, p)
// assert pow(c2, 2, p) == 10
// ", ".join("0x%02x" % b for b in c2.to_bytes(256//8, 'big'))
static const uint8_t kP256Sqrt10[] = …;

// kP384Sqrt12 is sqrt(12) in P-384's field. It was computed as follows in
// python3:
//
// p = 2**384 - 2**128 - 2**96 + 2**32 - 1
// c2 = pow(12, (p+1)//4, p)
// assert pow(c2, 2, p) == 12
// ", ".join("0x%02x" % b for b in c2.to_bytes(384//8, 'big'))
static const uint8_t kP384Sqrt12[] = …;

int ec_hash_to_curve_p256_xmd_sha256_sswu(const EC_GROUP *group,
                                          EC_JACOBIAN *out, const uint8_t *dst,
                                          size_t dst_len, const uint8_t *msg,
                                          size_t msg_len) { … }

int EC_hash_to_curve_p256_xmd_sha256_sswu(const EC_GROUP *group, EC_POINT *out,
                                          const uint8_t *dst, size_t dst_len,
                                          const uint8_t *msg, size_t msg_len) { … }

int ec_hash_to_curve_p384_xmd_sha384_sswu(const EC_GROUP *group,
                                          EC_JACOBIAN *out, const uint8_t *dst,
                                          size_t dst_len, const uint8_t *msg,
                                          size_t msg_len) { … }

int EC_hash_to_curve_p384_xmd_sha384_sswu(const EC_GROUP *group, EC_POINT *out,
                                          const uint8_t *dst, size_t dst_len,
                                          const uint8_t *msg, size_t msg_len) { … }

int ec_hash_to_scalar_p384_xmd_sha384(
    const EC_GROUP *group, EC_SCALAR *out, const uint8_t *dst, size_t dst_len,
    const uint8_t *msg, size_t msg_len) { … }

int ec_hash_to_curve_p384_xmd_sha512_sswu_draft07(
    const EC_GROUP *group, EC_JACOBIAN *out, const uint8_t *dst,
    size_t dst_len, const uint8_t *msg, size_t msg_len) { … }

int ec_hash_to_scalar_p384_xmd_sha512_draft07(
    const EC_GROUP *group, EC_SCALAR *out, const uint8_t *dst, size_t dst_len,
    const uint8_t *msg, size_t msg_len) { … }
chromium/third_party/boringssl/src/crypto/ec_extra/hash_to_curve.c
