path: root/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)  mpi_point_init((a))
#define point_free(a)  mpi_point_free_parts((a))

#define log_error(fmt, ...) pr_err(fmt, ##__VA_ARGS__)
#define log_fatal(fmt, ...) pr_err(fmt, ##__VA_ARGS__)

#define DIM(v) (sizeof(v)/sizeof((v)[0]))


/* 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)
{
	MPI_POINT p;

	(void)nbits;  /* Currently not used.  */

	p = kmalloc(sizeof(*p), GFP_KERNEL);
	if (p)
		mpi_point_init(p);
	return p;
}
EXPORT_SYMBOL_GPL(mpi_point_new);

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

/* 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)
{
	p->x = mpi_new(0);
	p->y = mpi_new(0);
	p->z = mpi_new(0);
}
EXPORT_SYMBOL_GPL(mpi_point_init);

/* Release the parts of a point object. */
void mpi_point_free_parts(MPI_POINT p)
{
	mpi_free(p->x); p->x = NULL;
	mpi_free(p->y); p->y = NULL;
	mpi_free(p->z); p->z = NULL;
}
EXPORT_SYMBOL_GPL(mpi_point_free_parts);

/* Set the value from S into D.  */
static void point_set(MPI_POINT d, MPI_POINT s)
{
	mpi_set(d->x, s->x);
	mpi_set(d->y, s->y);
	mpi_set(d->z, s->z);
}

static void point_resize(MPI_POINT p, struct mpi_ec_ctx *ctx)
{
	size_t nlimbs = ctx->p->nlimbs;

	mpi_resize(p->x, nlimbs);
	p->x->nlimbs = nlimbs;
	mpi_resize(p->z, nlimbs);
	p->z->nlimbs = nlimbs;

	if (ctx->model != MPI_EC_MONTGOMERY) {
		mpi_resize(p->y, nlimbs);
		p->y->nlimbs = nlimbs;
	}
}

static void point_swap_cond(MPI_POINT d, MPI_POINT s, unsigned long swap,
		struct mpi_ec_ctx *ctx)
{
	mpi_swap_cond(d->x, s->x, swap);
	if (ctx->model != MPI_EC_MONTGOMERY)
		mpi_swap_cond(d->y, s->y, swap);
	mpi_swap_cond(d->z, s->z, swap);
}


/* W = W mod P.  */
static void ec_mod(MPI w, struct mpi_ec_ctx *ec)
{
	if (ec->t.p_barrett)
		mpi_mod_barrett(w, w, ec->t.p_barrett);
	else
		mpi_mod(w, w, ec->p);
}

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

static void ec_subm(MPI w, MPI u, MPI v, struct mpi_ec_ctx *ec)
{
	mpi_sub(w, u, v);
	while (w->sign)
		mpi_add(w, w, ec->p);
	/*ec_mod(w, ec);*/
}

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

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

static void ec_powm(MPI w, const MPI b, const MPI e,
		struct mpi_ec_ctx *ctx)
{
	mpi_powm(w, b, e, ctx->p);
	/* mpi_abs(w); */
}

/* 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)
{
	/* Using mpi_mul is slightly faster (at least on amd64).  */
	/* mpi_powm(w, b, mpi_const(MPI_C_TWO), ctx->p); */
	ec_mulm(w, b, b, 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)
{
	mpi_powm(w, b, mpi_const(MPI_C_THREE), ctx->p);
}

static void ec_invm(MPI x, MPI a, struct mpi_ec_ctx *ctx)
{
	if (!mpi_invm(x, a, ctx->p))
		log_error("ec_invm: inverse does not exist:\n");
}

static void mpih_set_cond(mpi_ptr_t wp, mpi_ptr_t up,
		mpi_size_t usize, unsigned long set)
{
	mpi_size_t i;
	mpi_limb_t mask = ((mpi_limb_t)0) - set;
	mpi_limb_t x;

	for (i = 0; i < usize; i++) {
		x = mask & (wp[i] ^ up[i]);
		wp[i] = wp[i] ^ x;
	}
}

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

#define LIMB_SIZE_25519 ((256+BITS_PER_MPI_LIMB-1)/BITS_PER_MPI_LIMB)

static void ec_addm_25519(MPI w, MPI u, MPI v, struct mpi_ec_ctx *ctx)
{
	mpi_ptr_t wp, up, vp;
	mpi_size_t wsize = LIMB_SIZE_25519;
	mpi_limb_t n[LIMB_SIZE_25519];
	mpi_limb_t borrow;

	if (w->nlimbs != wsize || u->nlimbs != wsize || v->nlimbs != wsize)
		log_bug("addm_25519: different sizes\n");

	memset(n, 0, sizeof(n));
	up = u->d;
	vp = v->d;
	wp = w->d;

	mpihelp_add_n(wp, up, vp, wsize);
	borrow = mpihelp_sub_n(wp, wp, ctx->p->d, wsize);
	mpih_set_cond(n, ctx->p->d, wsize, (borrow != 0UL));
	mpihelp_add_n(wp, wp, n, wsize);
	wp[LIMB_SIZE_25519-1] &= ~((mpi_limb_t)1 << (255 % BITS_PER_MPI_LIMB));
}

static void ec_subm_25519(MPI w, MPI u, MPI v, struct mpi_ec_ctx *ctx)
{
	mpi_ptr_t wp, up, vp;
	mpi_size_t wsize = LIMB_SIZE_25519;
	mpi_limb_t n[LIMB_SIZE_25519];
	mpi_limb_t borrow;

	if (w->nlimbs != wsize || u->nlimbs != wsize || v->nlimbs != wsize)
		log_bug("subm_25519: different sizes\n");

	memset(n, 0, sizeof(n));
	up = u->d;
	vp = v->d;
	wp = w->d;

	borrow = mpihelp_sub_n(wp, up, vp, wsize);
	mpih_set_cond(n, ctx->p->d, wsize, (borrow != 0UL));
	mpihelp_add_n(wp, wp, n, wsize);
	wp[LIMB_SIZE_25519-1] &= ~((mpi_limb_t)1 << (255 % BITS_PER_MPI_LIMB));
}

static void ec_mulm_25519(MPI w, MPI u, MPI v, struct mpi_ec_ctx *ctx)
{
	mpi_ptr_t wp, up, vp;
	mpi_size_t wsize = LIMB_SIZE_25519;
	mpi_limb_t n[LIMB_SIZE_25519*2];
	mpi_limb_t m[LIMB_SIZE_25519+1];
	mpi_limb_t cy;
	int msb;

	(void)ctx;
	if (w->nlimbs != wsize || u->nlimbs != wsize || v->nlimbs != wsize)
		log_bug("mulm_25519: different sizes\n");

	up = u->d;
	vp = v->d;
	wp = w->d;

	mpihelp_mul_n(n, up, vp, wsize);
	memcpy(wp, n, wsize * BYTES_PER_MPI_LIMB);
	wp[LIMB_SIZE_25519-1] &= ~((mpi_limb_t)1 << (255 % BITS_PER_MPI_LIMB));

	memcpy(m, n+LIMB_SIZE_25519-1, (wsize+1) * BYTES_PER_MPI_LIMB);
	mpihelp_rshift(m, m, LIMB_SIZE_25519+1, (255 % BITS_PER_MPI_LIMB));

	memcpy(n, m, wsize * BYTES_PER_MPI_LIMB);
	cy = mpihelp_lshift(m, m, LIMB_SIZE_25519, 4);
	m[LIMB_SIZE_25519] = cy;
	cy = mpihelp_add_n(m, m, n, wsize);
	m[LIMB_SIZE_25519] += cy;
	cy = mpihelp_add_n(m, m, n, wsize);
	m[LIMB_SIZE_25519] += cy;
	cy = mpihelp_add_n(m, m, n, wsize);
	m[LIMB_SIZE_25519] += cy;

	cy = mpihelp_add_n(wp, wp, m, wsize);
	m[LIMB_SIZE_25519] += cy;

	memset(m, 0, wsize * BYTES_PER_MPI_LIMB);
	msb = (wp[LIMB_SIZE_25519-1] >> (255 % BITS_PER_MPI_LIMB));
	m[0] = (m[LIMB_SIZE_25519] * 2 + msb) * 19;
	wp[LIMB_SIZE_25519-1] &= ~((mpi_limb_t)1 << (255 % BITS_PER_MPI_LIMB));
	mpihelp_add_n(wp, wp, m, wsize);

	m[0] = 0;
	cy = mpihelp_sub_n(wp, wp, ctx->p->d, wsize);
	mpih_set_cond(m, ctx->p->d, wsize, (cy != 0UL));
	mpihelp_add_n(wp, wp, m, wsize);
}

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

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

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

#define LIMB_SIZE_448 ((448+BITS_PER_MPI_LIMB-1)/BITS_PER_MPI_LIMB)
#define LIMB_SIZE_HALF_448 ((LIMB_SIZE_448+1)/2)

static void ec_addm_448(MPI w, MPI u, MPI v, struct mpi_ec_ctx *ctx)
{
	mpi_ptr_t wp, up, vp;
	mpi_size_t wsize = LIMB_SIZE_448;
	mpi_limb_t n[LIMB_SIZE_448];
	mpi_limb_t cy;

	if (w->nlimbs != wsize || u->nlimbs != wsize || v->nlimbs != wsize)
		log_bug("addm_448: different sizes\n");

	memset(n, 0, sizeof(n));
	up = u->d;
	vp = v->d;
	wp = w->d;

	cy = mpihelp_add_n(wp, up, vp, wsize);
	mpih_set_cond(n, ctx->p->d, wsize, (cy != 0UL));
	mpihe