linux/lib/crypto/mpi/ec.c

/* ec.c -  Elliptic Curve functions
 * Copyright (C) 2007 Free Software Foundation, Inc.
 * Copyright (C) 2013 g10 Code GmbH
 *
 * This file is part of Libgcrypt.
 *
 * Libgcrypt is free software; you can redistribute it and/or modify
 * it under the terms of the GNU Lesser General Public License as
 * published by the Free Software Foundation; either version 2.1 of
 * the License, or (at your option) any later version.
 *
 * Libgcrypt is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU Lesser General Public License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public
 * License along with this program; if not, see <http://www.gnu.org/licenses/>.
 */

#include "mpi-internal.h"
#include "longlong.h"

#define point_init(a) …
#define point_free(a) …

#define log_error(fmt, ...) …
#define log_fatal(fmt, ...) …

#define DIM(v) …


/* Create a new point option.  NBITS gives the size in bits of one
 * coordinate; it is only used to pre-allocate some resources and
 * might also be passed as 0 to use a default value.
 */
MPI_POINT mpi_point_new(unsigned int nbits)
{ … }
EXPORT_SYMBOL_GPL(…);

/* Release the point object P.  P may be NULL. */
void mpi_point_release(MPI_POINT p)
{ … }
EXPORT_SYMBOL_GPL(…);

/* Initialize the fields of a point object.  gcry_mpi_point_free_parts
 * may be used to release the fields.
 */
void mpi_point_init(MPI_POINT p)
{ … }
EXPORT_SYMBOL_GPL(…);

/* Release the parts of a point object. */
void mpi_point_free_parts(MPI_POINT p)
{ … }
EXPORT_SYMBOL_GPL(…);

/* Set the value from S into D.  */
static void point_set(MPI_POINT d, MPI_POINT s)
{ … }

static void point_resize(MPI_POINT p, struct mpi_ec_ctx *ctx)
{ … }

static void point_swap_cond(MPI_POINT d, MPI_POINT s, unsigned long swap,
		struct mpi_ec_ctx *ctx)
{ … }


/* W = W mod P.  */
static void ec_mod(MPI w, struct mpi_ec_ctx *ec)
{ … }

static void ec_addm(MPI w, MPI u, MPI v, struct mpi_ec_ctx *ctx)
{ … }

static void ec_subm(MPI w, MPI u, MPI v, struct mpi_ec_ctx *ec)
{ … }

static void ec_mulm(MPI w, MPI u, MPI v, struct mpi_ec_ctx *ctx)
{ … }

/* W = 2 * U mod P.  */
static void ec_mul2(MPI w, MPI u, struct mpi_ec_ctx *ctx)
{ … }

static void ec_powm(MPI w, const MPI b, const MPI e,
		struct mpi_ec_ctx *ctx)
{ … }

/* Shortcut for
 * ec_powm(B, B, mpi_const(MPI_C_TWO), ctx);
 * for easier optimization.
 */
static void ec_pow2(MPI w, const MPI b, struct mpi_ec_ctx *ctx)
{ … }

/* Shortcut for
 * ec_powm(B, B, mpi_const(MPI_C_THREE), ctx);
 * for easier optimization.
 */
static void ec_pow3(MPI w, const MPI b, struct mpi_ec_ctx *ctx)
{ … }

static void ec_invm(MPI x, MPI a, struct mpi_ec_ctx *ctx)
{ … }

static void mpih_set_cond(mpi_ptr_t wp, mpi_ptr_t up,
		mpi_size_t usize, unsigned long set)
{ … }

/* Routines for 2^255 - 19.  */

#define LIMB_SIZE_25519 …

static void ec_addm_25519(MPI w, MPI u, MPI v, struct mpi_ec_ctx *ctx)
{ … }

static void ec_subm_25519(MPI w, MPI u, MPI v, struct mpi_ec_ctx *ctx)
{ … }

static void ec_mulm_25519(MPI w, MPI u, MPI v, struct mpi_ec_ctx *ctx)
{ … }

static void ec_mul2_25519(MPI w, MPI u, struct mpi_ec_ctx *ctx)
{ … }

static void ec_pow2_25519(MPI w, const MPI b, struct mpi_ec_ctx *ctx)
{ … }

/* Routines for 2^448 - 2^224 - 1.  */

#define LIMB_SIZE_448 …
#define LIMB_SIZE_HALF_448 …

static void ec_addm_448(MPI w, MPI u, MPI v, struct mpi_ec_ctx *ctx)
{ … }

static void ec_subm_448(MPI w, MPI u, MPI v, struct mpi_ec_ctx *ctx)
{ … }

static void ec_mulm_448(MPI w, MPI u, MPI v, struct mpi_ec_ctx *ctx)
{ … }

static void ec_mul2_448(MPI w, MPI u, struct mpi_ec_ctx *ctx)
{ … }

static void ec_pow2_448(MPI w, const MPI b, struct mpi_ec_ctx *ctx)
{ … }

struct field_table { … };

static const struct field_table field_table[] = …;

/* Force recomputation of all helper variables.  */
static void mpi_ec_get_reset(struct mpi_ec_ctx *ec)
{ … }

/* Accessor for helper variable.  */
static int ec_get_a_is_pminus3(struct mpi_ec_ctx *ec)
{ … }

/* Accessor for helper variable.  */
static MPI ec_get_two_inv_p(struct mpi_ec_ctx *ec)
{ … }

static const char *const curve25519_bad_points[] = …;

static const char *const curve448_bad_points[] = …;

static const char *const *bad_points_table[] = …;

static void mpi_ec_coefficient_normalize(MPI a, MPI p)
{ … }

/* This function initialized a context for elliptic curve based on the
 * field GF(p).  P is the prime specifying this field, A is the first
 * coefficient.  CTX is expected to be zeroized.
 */
void mpi_ec_init(struct mpi_ec_ctx *ctx, enum gcry_mpi_ec_models model,
			enum ecc_dialects dialect,
			int flags, MPI p, MPI a, MPI b)
{ … }
EXPORT_SYMBOL_GPL(…);

void mpi_ec_deinit(struct mpi_ec_ctx *ctx)
{ … }
EXPORT_SYMBOL_GPL(…);

/* Compute the affine coordinates from the projective coordinates in
 * POINT.  Set them into X and Y.  If one coordinate is not required,
 * X or Y may be passed as NULL.  CTX is the usual context. Returns: 0
 * on success or !0 if POINT is at infinity.
 */
int mpi_ec_get_affine(MPI x, MPI y, MPI_POINT point, struct mpi_ec_ctx *ctx)
{ … }
EXPORT_SYMBOL_GPL(…);

/*  RESULT = 2 * POINT  (Weierstrass version). */
static void dup_point_weierstrass(MPI_POINT result,
		MPI_POINT point, struct mpi_ec_ctx *ctx)
{ … }

/*  RESULT = 2 * POINT  (Montgomery version). */
static void dup_point_montgomery(MPI_POINT result,
				MPI_POINT point, struct mpi_ec_ctx *ctx)
{ … }

/*  RESULT = 2 * POINT  (Twisted Edwards version). */
static void dup_point_edwards(MPI_POINT result,
		MPI_POINT point, struct mpi_ec_ctx *ctx)
{ … }

/*  RESULT = 2 * POINT  */
static void
mpi_ec_dup_point(MPI_POINT result, MPI_POINT point, struct mpi_ec_ctx *ctx)
{ … }

/* RESULT = P1 + P2  (Weierstrass version).*/
static void add_points_weierstrass(MPI_POINT result,
		MPI_POINT p1, MPI_POINT p2,
		struct mpi_ec_ctx *ctx)
{ … }

/* RESULT = P1 + P2  (Montgomery version).*/
static void add_points_montgomery(MPI_POINT result,
		MPI_POINT p1, MPI_POINT p2,
		struct mpi_ec_ctx *ctx)
{ … }

/* RESULT = P1 + P2  (Twisted Edwards version).*/
static void add_points_edwards(MPI_POINT result,
		MPI_POINT p1, MPI_POINT p2,
		struct mpi_ec_ctx *ctx)
{ … }

/* Compute a step of Montgomery Ladder (only use X and Z in the point).
 * Inputs:  P1, P2, and x-coordinate of DIF = P1 - P1.
 * Outputs: PRD = 2 * P1 and  SUM = P1 + P2.
 */
static void montgomery_ladder(MPI_POINT prd, MPI_POINT sum,
		MPI_POINT p1, MPI_POINT p2, MPI dif_x,
		struct mpi_ec_ctx *ctx)
{ … }

/* RESULT = P1 + P2 */
void mpi_ec_add_points(MPI_POINT result,
		MPI_POINT p1, MPI_POINT p2,
		struct mpi_ec_ctx *ctx)
{ … }
EXPORT_SYMBOL_GPL(…);

/* Scalar point multiplication - the main function for ECC.  If takes
 * an integer SCALAR and a POINT as well as the usual context CTX.
 * RESULT will be set to the resulting point.
 */
void mpi_ec_mul_point(MPI_POINT result,
			MPI scalar, MPI_POINT point,
			struct mpi_ec_ctx *ctx)
{ … }
EXPORT_SYMBOL_GPL(…);

/* Return true if POINT is on the curve described by CTX.  */
int mpi_ec_curve_point(MPI_POINT point, struct mpi_ec_ctx *ctx)
{ … }
EXPORT_SYMBOL_GPL(…);