From patchwork Sun Feb 16 08:59:23 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: "tianjia.zhang" X-Patchwork-Id: 198091 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-9.8 required=3.0 tests=HEADER_FROM_DIFFERENT_DOMAINS, INCLUDES_PATCH, MAILING_LIST_MULTI, SIGNED_OFF_BY, SPF_HELO_NONE, SPF_PASS, UNPARSEABLE_RELAY, USER_AGENT_GIT autolearn=unavailable autolearn_force=no version=3.4.0 Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id 61424C2BA83 for ; Sun, 16 Feb 2020 09:01:03 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by mail.kernel.org (Postfix) with ESMTP id 1C4512086A for ; Sun, 16 Feb 2020 09:01:03 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1725899AbgBPJBC (ORCPT ); Sun, 16 Feb 2020 04:01:02 -0500 Received: from out30-42.freemail.mail.aliyun.com ([115.124.30.42]:39619 "EHLO out30-42.freemail.mail.aliyun.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1726142AbgBPJBC (ORCPT ); Sun, 16 Feb 2020 04:01:02 -0500 X-Alimail-AntiSpam: AC=PASS; BC=-1|-1; BR=01201311R251e4; CH=green; DM=||false|; DS=||; FP=0|-1|-1|-1|0|-1|-1|-1; HT=e01f04391; MF=tianjia.zhang@linux.alibaba.com; NM=1; PH=DS; RN=7; SR=0; TI=SMTPD_---0Tq4G2ZE_1581843591; Received: from localhost(mailfrom:tianjia.zhang@linux.alibaba.com fp:SMTPD_---0Tq4G2ZE_1581843591) by smtp.aliyun-inc.com(127.0.0.1); Sun, 16 Feb 2020 16:59:52 +0800 From: Tianjia Zhang To: herbert@gondor.apana.org.au, davem@davemloft.net, ebiggers@kernel.org, pvanleeuwen@rambus.com, zohar@linux.ibm.com Cc: linux-crypto@vger.kernel.org, linux-kernel@vger.kernel.org Subject: [PATCH 2/7] lib/mpi: Introduce ec implementation to MPI library Date: Sun, 16 Feb 2020 16:59:23 +0800 Message-Id: <20200216085928.108838-3-tianjia.zhang@linux.alibaba.com> X-Mailer: git-send-email 2.17.1 In-Reply-To: <20200216085928.108838-1-tianjia.zhang@linux.alibaba.com> References: <20200216085928.108838-1-tianjia.zhang@linux.alibaba.com> MIME-Version: 1.0 Sender: linux-crypto-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: linux-crypto@vger.kernel.org The implementation of EC is introduced from libgcrypt as the basic algorithm of elliptic curve, which can be more perfectly integrated with MPI implementation. Some other algorithms will be developed based on mpi ecc, such as SM2. Signed-off-by: Tianjia Zhang --- include/linux/mpi.h | 105 +++ lib/mpi/Makefile | 1 + lib/mpi/ec.c | 1538 +++++++++++++++++++++++++++++++++++++++++++ 3 files changed, 1644 insertions(+) create mode 100644 lib/mpi/ec.c diff --git a/include/linux/mpi.h b/include/linux/mpi.h index 2dddf4c6e011..20a31d5c29d2 100644 --- a/include/linux/mpi.h +++ b/include/linux/mpi.h @@ -155,6 +155,111 @@ void mpi_fdiv_q(MPI quot, MPI dividend, MPI divisor); /*-- mpi-inv.c --*/ int mpi_invm(MPI x, MPI a, MPI n); +/*-- ec.c --*/ + +/* Object to represent a point in projective coordinates */ +struct gcry_mpi_point { + MPI x; + MPI y; + MPI z; +}; + +typedef struct gcry_mpi_point *MPI_POINT; + +/* Models describing an elliptic curve */ +enum gcry_mpi_ec_models { + /* The Short Weierstrass equation is + * y^2 = x^3 + ax + b + */ + MPI_EC_WEIERSTRASS = 0, + /* The Montgomery equation is + * by^2 = x^3 + ax^2 + x + */ + MPI_EC_MONTGOMERY, + /* The Twisted Edwards equation is + * ax^2 + y^2 = 1 + bx^2y^2 + * Note that we use 'b' instead of the commonly used 'd'. + */ + MPI_EC_EDWARDS +}; + +/* Dialects used with elliptic curves */ +enum ecc_dialects { + ECC_DIALECT_STANDARD = 0, + ECC_DIALECT_ED25519, + ECC_DIALECT_SAFECURVE +}; + +/* This context is used with all our EC functions. */ +struct mpi_ec_ctx { + enum gcry_mpi_ec_models model; /* The model describing this curve. */ + enum ecc_dialects dialect; /* The ECC dialect used with the curve. */ + int flags; /* Public key flags (not always used). */ + unsigned int nbits; /* Number of bits. */ + + /* Domain parameters. Note that they may not all be set and if set + * the MPIs may be flaged as constant. + */ + MPI p; /* Prime specifying the field GF(p). */ + MPI a; /* First coefficient of the Weierstrass equation. */ + MPI b; /* Second coefficient of the Weierstrass equation. */ + MPI_POINT G; /* Base point (generator). */ + MPI n; /* Order of G. */ + unsigned int h; /* Cofactor. */ + + /* The actual key. May not be set. */ + MPI_POINT Q; /* Public key. */ + MPI d; /* Private key. */ + + const char *name; /* Name of the curve. */ + + /* This structure is private to mpi/ec.c! */ + struct { + struct { + unsigned int a_is_pminus3:1; + unsigned int two_inv_p:1; + } valid; /* Flags to help setting the helper vars below. */ + + int a_is_pminus3; /* True if A = P - 3. */ + + MPI two_inv_p; + + mpi_barrett_t p_barrett; + + /* Scratch variables. */ + MPI scratch[11]; + + /* Helper for fast reduction. */ + /* int nist_nbits; /\* If this is a NIST curve, the # of bits. *\/ */ + /* MPI s[10]; */ + /* MPI c; */ + } t; + + /* Curve specific computation routines for the field. */ + void (*addm)(MPI w, MPI u, MPI v, struct mpi_ec_ctx *ctx); + void (*subm)(MPI w, MPI u, MPI v, struct mpi_ec_ctx *ec); + void (*mulm)(MPI w, MPI u, MPI v, struct mpi_ec_ctx *ctx); + void (*pow2)(MPI w, const MPI b, struct mpi_ec_ctx *ctx); + void (*mul2)(MPI w, MPI u, struct mpi_ec_ctx *ctx); +}; + +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); +void mpi_ec_deinit(struct mpi_ec_ctx *ctx); +MPI_POINT mpi_point_new(unsigned int nbits); +void mpi_point_release(MPI_POINT p); +void mpi_point_init(MPI_POINT p); +void mpi_point_free_parts(MPI_POINT p); +int mpi_ec_get_affine(MPI x, MPI y, MPI_POINT point, struct mpi_ec_ctx *ctx); +void mpi_ec_add_points(MPI_POINT result, + MPI_POINT p1, MPI_POINT p2, + struct mpi_ec_ctx *ctx); +void mpi_ec_mul_point(MPI_POINT result, + MPI scalar, MPI_POINT point, + struct mpi_ec_ctx *ctx); +int mpi_ec_curve_point(MPI_POINT point, struct mpi_ec_ctx *ctx); + /* inline functions */ /** diff --git a/lib/mpi/Makefile b/lib/mpi/Makefile index 5f40f93ff3d9..0d07e3d2e0f4 100644 --- a/lib/mpi/Makefile +++ b/lib/mpi/Makefile @@ -13,6 +13,7 @@ mpi-y = \ generic_mpih-rshift.o \ generic_mpih-sub1.o \ generic_mpih-add1.o \ + ec.o \ mpicoder.o \ mpi-add.o \ mpi-bit.o \ diff --git a/lib/mpi/ec.c b/lib/mpi/ec.c new file mode 100644 index 000000000000..359c1b58ed11 --- /dev/null +++ b/lib/mpi/ec.c @@ -0,0 +1,1538 @@ +/* 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 . + */ + +#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)); + mpihelp_sub_n(wp, wp, n, wsize); +} + +static void ec_subm_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 borrow; + + if (w->nlimbs != wsize || u->nlimbs != wsize || v->nlimbs != wsize) + log_bug("subm_448: 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); +} + +static void ec_mulm_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*2]; + mpi_limb_t a2[LIMB_SIZE_HALF_448]; + mpi_limb_t a3[LIMB_SIZE_HALF_448]; + mpi_limb_t b0[LIMB_SIZE_HALF_448]; + mpi_limb_t b1[LIMB_SIZE_HALF_448]; + mpi_limb_t cy; + int i; +#if (LIMB_SIZE_HALF_448 > LIMB_SIZE_448/2) + mpi_limb_t b1_rest, a3_rest; +#endif + + if (w->nlimbs != wsize || u->nlimbs != wsize || v->nlimbs != wsize) + log_bug("mulm_448: different sizes\n"); + + up = u->d; + vp = v->d; + wp = w->d; + + mpihelp_mul_n(n, up, vp, wsize); + + for (i = 0; i < (wsize + 1) / 2; i++) { + b0[i] = n[i]; + b1[i] = n[i+wsize/2]; + a2[i] = n[i+wsize]; + a3[i] = n[i+wsize+wsize/2]; + } + +#if (LIMB_SIZE_HALF_448 > LIMB_SIZE_448/2) + b0[LIMB_SIZE_HALF_448-1] &= ((mpi_limb_t)1UL << 32)-1; + a2[LIMB_SIZE_HALF_448-1] &= ((mpi_limb_t)1UL << 32)-1; + + b1_rest = 0; + a3_rest = 0; + + for (i = (wsize + 1) / 2 - 1; i >= 0; i--) { + mpi_limb_t b1v, a3v; + b1v = b1[i]; + a3v = a3[i]; + b1[i] = (b1_rest << 32) | (b1v >> 32); + a3[i] = (a3_rest << 32) | (a3v >> 32); + b1_rest = b1v & (((mpi_limb_t)1UL << 32)-1); + a3_rest = a3v & (((mpi_limb_t)1UL << 32)-1); + } +#endif + + cy = mpihelp_add_n(b0, b0, a2, LIMB_SIZE_HALF_448); + cy += mpihelp_add_n(b0, b0, a3, LIMB_SIZE_HALF_448); + for (i = 0; i < (wsize + 1) / 2; i++) + wp[i] = b0[i]; +#if (LIMB_SIZE_HALF_448 > LIMB_SIZE_448/2) + wp[LIMB_SIZE_HALF_448-1] &= (((mpi_limb_t)1UL << 32)-1); +#endif + +#if (LIMB_SIZE_HALF_448 > LIMB_SIZE_448/2) + cy = b0[LIMB_SIZE_HALF_448-1] >> 32; +#endif + + cy = mpihelp_add_1(b1, b1, LIMB_SIZE_HALF_448, cy); + cy += mpihelp_add_n(b1, b1, a2, LIMB_SIZE_HALF_448); + cy += mpihelp_add_n(b1, b1, a3, LIMB_SIZE_HALF_448); + cy += mpihelp_add_n(b1, b1, a3, LIMB_SIZE_HALF_448); +#if (LIMB_SIZE_HALF_448 > LIMB_SIZE_448/2) + b1_rest = 0; + for (i = (wsize + 1) / 2 - 1; i >= 0; i--) { + mpi_limb_t b1v = b1[i]; + b1[i] = (b1_rest << 32) | (b1v >> 32); + b1_rest = b1v & (((mpi_limb_t)1UL << 32)-1); + } + wp[LIMB_SIZE_HALF_448-1] |= (b1_rest << 32); +#endif + for (i = 0; i < wsize / 2; i++) + wp[i+(wsize + 1) / 2] = b1[i]; + +#if (LIMB_SIZE_HALF_448 > LIMB_SIZE_448/2) + cy = b1[LIMB_SIZE_HALF_448-1]; +#endif + + memset(n, 0, wsize * BYTES_PER_MPI_LIMB); + +#if (LIMB_SIZE_HALF_448 > LIMB_SIZE_448/2) + n[LIMB_SIZE_HALF_448-1] = cy << 32; +#else + n[LIMB_SIZE_HALF_448] = cy; +#endif + n[0] = cy; + mpihelp_add_n(wp, wp, n, wsize); + + memset(n, 0, wsize * BYTES_PER_MPI_LIMB); + cy = mpihelp_sub_n(wp, wp, ctx->p->d, wsize); + mpih_set_cond(n, ctx->p->d, wsize, (cy != 0UL)); + mpihelp_add_n(wp, wp, n, wsize); +} + +static void ec_mul2_448(MPI w, MPI u, struct mpi_ec_ctx *ctx) +{ + ec_addm_448(w, u, u, ctx); +} + +static void ec_pow2_448(MPI w, const MPI b, struct mpi_ec_ctx *ctx) +{ + ec_mulm_448(w, b, b, ctx); +} + +struct field_table { + const char *p; + + /* computation routines for the field. */ + void (*addm)(MPI w, MPI u, MPI v, struct mpi_ec_ctx *ctx); + void (*subm)(MPI w, MPI u, MPI v, struct mpi_ec_ctx *ctx); + void (*mulm)(MPI w, MPI u, MPI v, struct mpi_ec_ctx *ctx); + void (*mul2)(MPI w, MPI u, struct mpi_ec_ctx *ctx); + void (*pow2)(MPI w, const MPI b, struct mpi_ec_ctx *ctx); +}; + +static const struct field_table field_table[] = { + { + "0x7FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFED", + ec_addm_25519, + ec_subm_25519, + ec_mulm_25519, + ec_mul2_25519, + ec_pow2_25519 + }, + { + "0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFE" + "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF", + ec_addm_448, + ec_subm_448, + ec_mulm_448, + ec_mul2_448, + ec_pow2_448 + }, + { NULL, NULL, NULL, NULL, NULL, NULL }, +}; + +/* Force recomputation of all helper variables. */ +void mpi_ec_get_reset(struct mpi_ec_ctx *ec) +{ + ec->t.valid.a_is_pminus3 = 0; + ec->t.valid.two_inv_p = 0; +} + +/* Accessor for helper variable. */ +static int ec_get_a_is_pminus3(struct mpi_ec_ctx *ec) +{ + MPI tmp; + + if (!ec->t.valid.a_is_pminus3) { + ec->t.valid.a_is_pminus3 = 1; + tmp = mpi_alloc_like(ec->p); + mpi_sub_ui(tmp, ec->p, 3); + ec->t.a_is_pminus3 = !mpi_cmp(ec->a, tmp); + mpi_free(tmp); + } + + return ec->t.a_is_pminus3; +} + +/* Accessor for helper variable. */ +static MPI ec_get_two_inv_p(struct mpi_ec_ctx *ec) +{ + if (!ec->t.valid.two_inv_p) { + ec->t.valid.two_inv_p = 1; + if (!ec->t.two_inv_p) + ec->t.two_inv_p = mpi_alloc(0); + ec_invm(ec->t.two_inv_p, mpi_const(MPI_C_TWO), ec); + } + return ec->t.two_inv_p; +} + +static const char *const curve25519_bad_points[] = { + "0x7fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffed", + "0x0000000000000000000000000000000000000000000000000000000000000000", + "0x0000000000000000000000000000000000000000000000000000000000000001", + "0x00b8495f16056286fdb1329ceb8d09da6ac49ff1fae35616aeb8413b7c7aebe0", + "0x57119fd0dd4e22d8868e1c58c45c44045bef839c55b1d0b1248c50a3bc959c5f", + "0x7fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffec", + "0x7fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffee", + NULL +}; + +static const char *const curve448_bad_points[] = { + "0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffe" + "ffffffffffffffffffffffffffffffffffffffffffffffffffffffff", + "0x00000000000000000000000000000000000000000000000000000000" + "00000000000000000000000000000000000000000000000000000000", + "0x00000000000000000000000000000000000000000000000000000000" + "00000000000000000000000000000000000000000000000000000001", + "0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffe" + "fffffffffffffffffffffffffffffffffffffffffffffffffffffffe", + "0xffffffffffffffffffffffffffffffffffffffffffffffffffffffff" + "00000000000000000000000000000000000000000000000000000000", + NULL +}; + +static const char *const *bad_points_table[] = { + curve25519_bad_points, + curve448_bad_points, +}; + +static void mpi_ec_coefficient_normalize(MPI a, MPI p) +{ + if (a->sign) { + mpi_resize(a, p->nlimbs); + mpihelp_sub_n(a->d, p->d, a->d, p->nlimbs); + a->nlimbs = p->nlimbs; + a->sign = 0; + } +} + +/* 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) +{ + int i; + static int use_barrett = -1 /* TODO: 1 or -1 */; + + mpi_ec_coefficient_normalize(a, p); + mpi_ec_coefficient_normalize(b, p); + + /* Fixme: Do we want to check some constraints? e.g. a < p */ + + ctx->model = model; + ctx->dialect = dialect; + ctx->flags = flags; + if (dialect == ECC_DIALECT_ED25519) + ctx->nbits = 256; + else + ctx->nbits = mpi_get_nbits(p); + ctx->p = mpi_copy(p); + ctx->a = mpi_copy(a); + ctx->b = mpi_copy(b); + + ctx->t.p_barrett = use_barrett > 0 ? mpi_barrett_init(ctx->p, 0) : NULL; + + mpi_ec_get_reset(ctx); + + if (model == MPI_EC_MONTGOMERY) { + for (i = 0; i < DIM(bad_points_table); i++) { + MPI p_candidate = mpi_scanval(bad_points_table[i][0]); + int match_p = !mpi_cmp(ctx->p, p_candidate); + int j; + + mpi_free(p_candidate); + if (!match_p) + continue; + + for (j = 0; i < DIM(ctx->t.scratch) && bad_points_table[i][j]; j++) + ctx->t.scratch[j] = mpi_scanval(bad_points_table[i][j]); + } + } else { + /* Allocate scratch variables. */ + for (i = 0; i < DIM(ctx->t.scratch); i++) + ctx->t.scratch[i] = mpi_alloc_like(ctx->p); + } + + ctx->addm = ec_addm; + ctx->subm = ec_subm; + ctx->mulm = ec_mulm; + ctx->mul2 = ec_mul2; + ctx->pow2 = ec_pow2; + + for (i = 0; field_table[i].p; i++) { + MPI f_p; + + f_p = mpi_scanval(field_table[i].p); + if (!f_p) + break; + + if (!mpi_cmp(p, f_p)) { + ctx->addm = field_table[i].addm; + ctx->subm = field_table[i].subm; + ctx->mulm = field_table[i].mulm; + ctx->mul2 = field_table[i].mul2; + ctx->pow2 = field_table[i].pow2; + mpi_free(f_p); + + mpi_resize(ctx->a, ctx->p->nlimbs); + ctx->a->nlimbs = ctx->p->nlimbs; + + mpi_resize(ctx->b, ctx->p->nlimbs); + ctx->b->nlimbs = ctx->p->nlimbs; + + for (i = 0; i < DIM(ctx->t.scratch) && ctx->t.scratch[i]; i++) + ctx->t.scratch[i]->nlimbs = ctx->p->nlimbs; + + break; + } + + mpi_free(f_p); + } +} +EXPORT_SYMBOL_GPL(mpi_ec_init); + +void mpi_ec_deinit(struct mpi_ec_ctx *ctx) +{ + int i; + + mpi_barrett_free(ctx->t.p_barrett); + + /* Domain parameter. */ + mpi_free(ctx->p); + mpi_free(ctx->a); + mpi_free(ctx->b); + mpi_point_release(ctx->G); + mpi_free(ctx->n); + + /* The key. */ + mpi_point_release(ctx->Q); + mpi_free(ctx->d); + + /* Private data of ec.c. */ + mpi_free(ctx->t.two_inv_p); + + for (i = 0; i < DIM(ctx->t.scratch); i++) + mpi_free(ctx->t.scratch[i]); +} +EXPORT_SYMBOL_GPL(mpi_ec_deinit); + + +/* This function returns a new context for elliptic curve based on the + * field GF(p). P is the prime specifying this field, A is the first + * coefficient, B is the second coefficient, and MODEL is the model + * for the curve. This function is only used within Libgcrypt and not + * part of the public API. + * + * This context needs to be released using mpi_ec_free. + */ +struct mpi_ec_ctx *mpi_ec_new(enum gcry_mpi_ec_models model, + enum ecc_dialects dialect, int flags, + MPI p, MPI a, MPI b) +{ + struct mpi_ec_ctx *ctx; + + ctx = kcalloc(1, sizeof(*ctx), GFP_KERNEL); + if (ctx) + mpi_ec_init(ctx, model, dialect, flags, p, a, b); + + return ctx; +} + +void mpi_ec_free(struct mpi_ec_ctx *ctx) +{ + if (ctx) { + mpi_ec_deinit(ctx); + kfree(ctx); + } +} + +/* 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) +{ + if (!mpi_cmp_ui(point->z, 0)) + return -1; + + switch (ctx->model) { + case MPI_EC_WEIERSTRASS: /* Using Jacobian coordinates. */ + { + MPI z1, z2, z3; + + z1 = mpi_new(0); + z2 = mpi_new(0); + ec_invm(z1, point->z, ctx); /* z1 = z^(-1) mod p */ + ec_mulm(z2, z1, z1, ctx); /* z2 = z^(-2) mod p */ + + if (x) + ec_mulm(x, point->x, z2, ctx); + + if (y) { + z3 = mpi_new(0); + ec_mulm(z3, z2, z1, ctx); /* z3 = z^(-3) mod p */ + ec_mulm(y, point->y, z3, ctx); + mpi_free(z3); + } + + mpi_free(z2); + mpi_free(z1); + } + return 0; + + case MPI_EC_MONTGOMERY: + { + if (x) + mpi_set(x, point->x); + + if (y) { + log_fatal("%s: Getting Y-coordinate on %s is not supported\n", + "mpi_ec_get_affine", "Montgomery"); + return -1; + } + } + return 0; + + case MPI_EC_EDWARDS: + { + MPI z; + + z = mpi_new(0); + ec_invm(z, point->z, ctx); + + mpi_resize(z, ctx->p->nlimbs); + z->nlimbs = ctx->p->nlimbs; + + if (x) { + mpi_resize(x, ctx->p->nlimbs); + x->nlimbs = ctx->p->nlimbs; + ctx->mulm(x, point->x, z, ctx); + } + if (y) { + mpi_resize(y, ctx->p->nlimbs); + y->nlimbs = ctx->p->nlimbs; + ctx->mulm(y, point->y, z, ctx); + } + + mpi_free(z); + } + return 0; + + default: + return -1; + } +} +EXPORT_SYMBOL_GPL(mpi_ec_get_affine); + +/* RESULT = 2 * POINT (Weierstrass version). */ +static void dup_point_weierstrass(MPI_POINT result, + MPI_POINT point, struct mpi_ec_ctx *ctx) +{ +#define x3 (result->x) +#define y3 (result->y) +#define z3 (result->z) +#define t1 (ctx->t.scratch[0]) +#define t2 (ctx->t.scratch[1]) +#define t3 (ctx->t.scratch[2]) +#define l1 (ctx->t.scratch[3]) +#define l2 (ctx->t.scratch[4]) +#define l3 (ctx->t.scratch[5]) + + if (!mpi_cmp_ui(point->y, 0) || !mpi_cmp_ui(point->z, 0)) { + /* P_y == 0 || P_z == 0 => [1:1:0] */ + mpi_set_ui(x3, 1); + mpi_set_ui(y3, 1); + mpi_set_ui(z3, 0); + } else { + if (ec_get_a_is_pminus3(ctx)) { + /* Use the faster case. */ + /* L1 = 3(X - Z^2)(X + Z^2) */ + /* T1: used for Z^2. */ + /* T2: used for the right term. */ + ec_pow2(t1, point->z, ctx); + ec_subm(l1, point->x, t1, ctx); + ec_mulm(l1, l1, mpi_const(MPI_C_THREE), ctx); + ec_addm(t2, point->x, t1, ctx); + ec_mulm(l1, l1, t2, ctx); + } else { + /* Standard case. */ + /* L1 = 3X^2 + aZ^4 */ + /* T1: used for aZ^4. */ + ec_pow2(l1, point->x, ctx); + ec_mulm(l1, l1, mpi_const(MPI_C_THREE), ctx); + ec_powm(t1, point->z, mpi_const(MPI_C_FOUR), ctx); + ec_mulm(t1, t1, ctx->a, ctx); + ec_addm(l1, l1, t1, ctx); + } + /* Z3 = 2YZ */ + ec_mulm(z3, point->y, point->z, ctx); + ec_mul2(z3, z3, ctx); + + /* L2 = 4XY^2 */ + /* T2: used for Y2; required later. */ + ec_pow2(t2, point->y, ctx); + ec_mulm(l2, t2, point->x, ctx); + ec_mulm(l2, l2, mpi_const(MPI_C_FOUR), ctx); + + /* X3 = L1^2 - 2L2 */ + /* T1: used for L2^2. */ + ec_pow2(x3, l1, ctx); + ec_mul2(t1, l2, ctx); + ec_subm(x3, x3, t1, ctx); + + /* L3 = 8Y^4 */ + /* T2: taken from above. */ + ec_pow2(t2, t2, ctx); + ec_mulm(l3, t2, mpi_const(MPI_C_EIGHT), ctx); + + /* Y3 = L1(L2 - X3) - L3 */ + ec_subm(y3, l2, x3, ctx); + ec_mulm(y3, y3, l1, ctx); + ec_subm(y3, y3, l3, ctx); + } + +#undef x3 +#undef y3 +#undef z3 +#undef t1 +#undef t2 +#undef t3 +#undef l1 +#undef l2 +#undef l3 +} + +/* RESULT = 2 * POINT (Montgomery version). */ +static void dup_point_montgomery(MPI_POINT result, + MPI_POINT point, struct mpi_ec_ctx *ctx) +{ + (void)result; + (void)point; + (void)ctx; + log_fatal("%s: %s not yet supported\n", + "mpi_ec_dup_point", "Montgomery"); +} + +/* RESULT = 2 * POINT (Twisted Edwards version). */ +static void dup_point_edwards(MPI_POINT result, + MPI_POINT point, struct mpi_ec_ctx *ctx) +{ +#define X1 (point->x) +#define Y1 (point->y) +#define Z1 (point->z) +#define X3 (result->x) +#define Y3 (result->y) +#define Z3 (result->z) +#define B (ctx->t.scratch[0]) +#define C (ctx->t.scratch[1]) +#define D (ctx->t.scratch[2]) +#define E (ctx->t.scratch[3]) +#define F (ctx->t.scratch[4]) +#define H (ctx->t.scratch[5]) +#define J (ctx->t.scratch[6]) + + /* Compute: (X_3 : Y_3 : Z_3) = 2( X_1 : Y_1 : Z_1 ) */ + + /* B = (X_1 + Y_1)^2 */ + ctx->addm(B, X1, Y1, ctx); + ctx->pow2(B, B, ctx); + + /* C = X_1^2 */ + /* D = Y_1^2 */ + ctx->pow2(C, X1, ctx); + ctx->pow2(D, Y1, ctx); + + /* E = aC */ + if (ctx->dialect == ECC_DIALECT_ED25519) + ctx->subm(E, ctx->p, C, ctx); + else + ctx->mulm(E, ctx->a, C, ctx); + + /* F = E + D */ + ctx->addm(F, E, D, ctx); + + /* H = Z_1^2 */ + ctx->pow2(H, Z1, ctx); + + /* J = F - 2H */ + ctx->mul2(J, H, ctx); + ctx->subm(J, F, J, ctx); + + /* X_3 = (B - C - D) · J */ + ctx->subm(X3, B, C, ctx); + ctx->subm(X3, X3, D, ctx); + ctx->mulm(X3, X3, J, ctx); + + /* Y_3 = F · (E - D) */ + ctx->subm(Y3, E, D, ctx); + ctx->mulm(Y3, Y3, F, ctx); + + /* Z_3 = F · J */ + ctx->mulm(Z3, F, J, ctx); + +#undef X1 +#undef Y1 +#undef Z1 +#undef X3 +#undef Y3 +#undef Z3 +#undef B +#undef C +#undef D +#undef E +#undef F +#undef H +#undef J +} + +/* RESULT = 2 * POINT */ +void mpi_ec_dup_point(MPI_POINT result, MPI_POINT point, struct mpi_ec_ctx *ctx) +{ + switch (ctx->model) { + case MPI_EC_WEIERSTRASS: + dup_point_weierstrass(result, point, ctx); + break; + case MPI_EC_MONTGOMERY: + dup_point_montgomery(result, point, ctx); + break; + case MPI_EC_EDWARDS: + dup_point_edwards(result, point, ctx); + break; + } +} + +/* RESULT = P1 + P2 (Weierstrass version).*/ +static void add_points_weierstrass(MPI_POINT result, + MPI_POINT p1, MPI_POINT p2, + struct mpi_ec_ctx *ctx) +{ +#define x1 (p1->x) +#define y1 (p1->y) +#define z1 (p1->z) +#define x2 (p2->x) +#define y2 (p2->y) +#define z2 (p2->z) +#define x3 (result->x) +#define y3 (result->y) +#define z3 (result->z) +#define l1 (ctx->t.scratch[0]) +#define l2 (ctx->t.scratch[1]) +#define l3 (ctx->t.scratch[2]) +#define l4 (ctx->t.scratch[3]) +#define l5 (ctx->t.scratch[4]) +#define l6 (ctx->t.scratch[5]) +#define l7 (ctx->t.scratch[6]) +#define l8 (ctx->t.scratch[7]) +#define l9 (ctx->t.scratch[8]) +#define t1 (ctx->t.scratch[9]) +#define t2 (ctx->t.scratch[10]) + + if ((!mpi_cmp(x1, x2)) && (!mpi_cmp(y1, y2)) && (!mpi_cmp(z1, z2))) { + /* Same point; need to call the duplicate function. */ + mpi_ec_dup_point(result, p1, ctx); + } else if (!mpi_cmp_ui(z1, 0)) { + /* P1 is at infinity. */ + mpi_set(x3, p2->x); + mpi_set(y3, p2->y); + mpi_set(z3, p2->z); + } else if (!mpi_cmp_ui(z2, 0)) { + /* P2 is at infinity. */ + mpi_set(x3, p1->x); + mpi_set(y3, p1->y); + mpi_set(z3, p1->z); + } else { + int z1_is_one = !mpi_cmp_ui(z1, 1); + int z2_is_one = !mpi_cmp_ui(z2, 1); + + /* l1 = x1 z2^2 */ + /* l2 = x2 z1^2 */ + if (z2_is_one) + mpi_set(l1, x1); + else { + ec_pow2(l1, z2, ctx); + ec_mulm(l1, l1, x1, ctx); + } + if (z1_is_one) + mpi_set(l2, x2); + else { + ec_pow2(l2, z1, ctx); + ec_mulm(l2, l2, x2, ctx); + } + /* l3 = l1 - l2 */ + ec_subm(l3, l1, l2, ctx); + /* l4 = y1 z2^3 */ + ec_powm(l4, z2, mpi_const(MPI_C_THREE), ctx); + ec_mulm(l4, l4, y1, ctx); + /* l5 = y2 z1^3 */ + ec_powm(l5, z1, mpi_const(MPI_C_THREE), ctx); + ec_mulm(l5, l5, y2, ctx); + /* l6 = l4 - l5 */ + ec_subm(l6, l4, l5, ctx); + + if (!mpi_cmp_ui(l3, 0)) { + if (!mpi_cmp_ui(l6, 0)) { + /* P1 and P2 are the same - use duplicate function. */ + mpi_ec_dup_point(result, p1, ctx); + } else { + /* P1 is the inverse of P2. */ + mpi_set_ui(x3, 1); + mpi_set_ui(y3, 1); + mpi_set_ui(z3, 0); + } + } else { + /* l7 = l1 + l2 */ + ec_addm(l7, l1, l2, ctx); + /* l8 = l4 + l5 */ + ec_addm(l8, l4, l5, ctx); + /* z3 = z1 z2 l3 */ + ec_mulm(z3, z1, z2, ctx); + ec_mulm(z3, z3, l3, ctx); + /* x3 = l6^2 - l7 l3^2 */ + ec_pow2(t1, l6, ctx); + ec_pow2(t2, l3, ctx); + ec_mulm(t2, t2, l7, ctx); + ec_subm(x3, t1, t2, ctx); + /* l9 = l7 l3^2 - 2 x3 */ + ec_mul2(t1, x3, ctx); + ec_subm(l9, t2, t1, ctx); + /* y3 = (l9 l6 - l8 l3^3)/2 */ + ec_mulm(l9, l9, l6, ctx); + ec_powm(t1, l3, mpi_const(MPI_C_THREE), ctx); /* fixme: Use saved value*/ + ec_mulm(t1, t1, l8, ctx); + ec_subm(y3, l9, t1, ctx); + ec_mulm(y3, y3, ec_get_two_inv_p(ctx), ctx); + } + } + +#undef x1 +#undef y1 +#undef z1 +#undef x2 +#undef y2 +#undef z2 +#undef x3 +#undef y3 +#undef z3 +#undef l1 +#undef l2 +#undef l3 +#undef l4 +#undef l5 +#undef l6 +#undef l7 +#undef l8 +#undef l9 +#undef t1 +#undef t2 +} + +/* RESULT = P1 + P2 (Montgomery version).*/ +static void add_points_montgomery(MPI_POINT result, + MPI_POINT p1, MPI_POINT p2, + struct mpi_ec_ctx *ctx) +{ + (void)result; + (void)p1; + (void)p2; + (void)ctx; + log_fatal("%s: %s not yet supported\n", + "mpi_ec_add_points", "Montgomery"); +} + +/* 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) +{ +#define X1 (p1->x) +#define Y1 (p1->y) +#define Z1 (p1->z) +#define X2 (p2->x) +#define Y2 (p2->y) +#define Z2 (p2->z) +#define X3 (result->x) +#define Y3 (result->y) +#define Z3 (result->z) +#define A (ctx->t.scratch[0]) +#define B (ctx->t.scratch[1]) +#define C (ctx->t.scratch[2]) +#define D (ctx->t.scratch[3]) +#define E (ctx->t.scratch[4]) +#define F (ctx->t.scratch[5]) +#define G (ctx->t.scratch[6]) +#define tmp (ctx->t.scratch[7]) + + point_resize(result, ctx); + + /* Compute: (X_3 : Y_3 : Z_3) = (X_1 : Y_1 : Z_1) + (X_2 : Y_2 : Z_3) */ + + /* A = Z1 · Z2 */ + ctx->mulm(A, Z1, Z2, ctx); + + /* B = A^2 */ + ctx->pow2(B, A, ctx); + + /* C = X1 · X2 */ + ctx->mulm(C, X1, X2, ctx); + + /* D = Y1 · Y2 */ + ctx->mulm(D, Y1, Y2, ctx); + + /* E = d · C · D */ + ctx->mulm(E, ctx->b, C, ctx); + ctx->mulm(E, E, D, ctx); + + /* F = B - E */ + ctx->subm(F, B, E, ctx); + + /* G = B + E */ + ctx->addm(G, B, E, ctx); + + /* X_3 = A · F · ((X_1 + Y_1) · (X_2 + Y_2) - C - D) */ + ctx->addm(tmp, X1, Y1, ctx); + ctx->addm(X3, X2, Y2, ctx); + ctx->mulm(X3, X3, tmp, ctx); + ctx->subm(X3, X3, C, ctx); + ctx->subm(X3, X3, D, ctx); + ctx->mulm(X3, X3, F, ctx); + ctx->mulm(X3, X3, A, ctx); + + /* Y_3 = A · G · (D - aC) */ + if (ctx->dialect == ECC_DIALECT_ED25519) { + ctx->addm(Y3, D, C, ctx); + } else { + ctx->mulm(Y3, ctx->a, C, ctx); + ctx->subm(Y3, D, Y3, ctx); + } + ctx->mulm(Y3, Y3, G, ctx); + ctx->mulm(Y3, Y3, A, ctx); + + /* Z_3 = F · G */ + ctx->mulm(Z3, F, G, ctx); + + +#undef X1 +#undef Y1 +#undef Z1 +#undef X2 +#undef Y2 +#undef Z2 +#undef X3 +#undef Y3 +#undef Z3 +#undef A +#undef B +#undef C +#undef D +#undef E +#undef F +#undef G +#undef tmp +} + +/* 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) +{ + ctx->addm(sum->x, p2->x, p2->z, ctx); + ctx->subm(p2->z, p2->x, p2->z, ctx); + ctx->addm(prd->x, p1->x, p1->z, ctx); + ctx->subm(p1->z, p1->x, p1->z, ctx); + ctx->mulm(p2->x, p1->z, sum->x, ctx); + ctx->mulm(p2->z, prd->x, p2->z, ctx); + ctx->pow2(p1->x, prd->x, ctx); + ctx->pow2(p1->z, p1->z, ctx); + ctx->addm(sum->x, p2->x, p2->z, ctx); + ctx->subm(p2->z, p2->x, p2->z, ctx); + ctx->mulm(prd->x, p1->x, p1->z, ctx); + ctx->subm(p1->z, p1->x, p1->z, ctx); + ctx->pow2(sum->x, sum->x, ctx); + ctx->pow2(sum->z, p2->z, ctx); + ctx->mulm(prd->z, p1->z, ctx->a, ctx); /* CTX->A: (a-2)/4 */ + ctx->mulm(sum->z, sum->z, dif_x, ctx); + ctx->addm(prd->z, p1->x, prd->z, ctx); + ctx->mulm(prd->z, prd->z, p1->z, ctx); +} + +/* RESULT = P1 + P2 */ +void mpi_ec_add_points(MPI_POINT result, + MPI_POINT p1, MPI_POINT p2, + struct mpi_ec_ctx *ctx) +{ + switch (ctx->model) { + case MPI_EC_WEIERSTRASS: + add_points_weierstrass(result, p1, p2, ctx); + break; + case MPI_EC_MONTGOMERY: + add_points_montgomery(result, p1, p2, ctx); + break; + case MPI_EC_EDWARDS: + add_points_edwards(result, p1, p2, ctx); + break; + } +} +EXPORT_SYMBOL_GPL(mpi_ec_add_points); + +/* 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) +{ + MPI x1, y1, z1, k, h, yy; + unsigned int i, loops; + struct gcry_mpi_point p1, p2, p1inv; + + if (ctx->model == MPI_EC_EDWARDS) { + /* Simple left to right binary method. Algorithm 3.27 from + * {author={Hankerson, Darrel and Menezes, Alfred J. and Vanstone, Scott}, + * title = {Guide to Elliptic Curve Cryptography}, + * year = {2003}, isbn = {038795273X}, + * url = {http://www.cacr.math.uwaterloo.ca/ecc/}, + * publisher = {Springer-Verlag New York, Inc.}} + */ + unsigned int nbits; + int j; + + if (mpi_cmp(scalar, ctx->p) >= 0) + nbits = mpi_get_nbits(scalar); + else + nbits = mpi_get_nbits(ctx->p); + + mpi_set_ui(result->x, 0); + mpi_set_ui(result->y, 1); + mpi_set_ui(result->z, 1); + point_resize(point, ctx); + + point_resize(result, ctx); + point_resize(point, ctx); + + for (j = nbits-1; j >= 0; j--) { + mpi_ec_dup_point(result, result, ctx); + if (mpi_test_bit(scalar, j)) + mpi_ec_add_points(result, result, point, ctx); + } + return; + } else if (ctx->model == MPI_EC_MONTGOMERY) { + unsigned int nbits; + int j; + struct gcry_mpi_point p1_, p2_; + MPI_POINT q1, q2, prd, sum; + unsigned long sw; + mpi_size_t rsize; + int scalar_copied = 0; + + /* Compute scalar point multiplication with Montgomery Ladder. + * Note that we don't use Y-coordinate in the points at all. + * RESULT->Y will be filled by zero. + */ + + nbits = mpi_get_nbits(scalar); + point_init(&p1); + point_init(&p2); + point_init(&p1_); + point_init(&p2_); + mpi_set_ui(p1.x, 1); + mpi_free(p2.x); + p2.x = mpi_copy(point->x); + mpi_set_ui(p2.z, 1); + + point_resize(&p1, ctx); + point_resize(&p2, ctx); + point_resize(&p1_, ctx); + point_resize(&p2_, ctx); + + mpi_resize(point->x, ctx->p->nlimbs); + point->x->nlimbs = ctx->p->nlimbs; + + q1 = &p1; + q2 = &p2; + prd = &p1_; + sum = &p2_; + + for (j = nbits-1; j >= 0; j--) { + MPI_POINT t; + + sw = mpi_test_bit(scalar, j); + point_swap_cond(q1, q2, sw, ctx); + montgomery_ladder(prd, sum, q1, q2, point->x, ctx); + point_swap_cond(prd, sum, sw, ctx); + t = q1; q1 = prd; prd = t; + t = q2; q2 = sum; sum = t; + } + + mpi_clear(result->y); + sw = (nbits & 1); + point_swap_cond(&p1, &p1_, sw, ctx); + + rsize = p1.z->nlimbs; + MPN_NORMALIZE(p1.z->d, rsize); + if (rsize == 0) { + mpi_set_ui(result->x, 1); + mpi_set_ui(result->z, 0); + } else { + z1 = mpi_new(0); + ec_invm(z1, p1.z, ctx); + ec_mulm(result->x, p1.x, z1, ctx); + mpi_set_ui(result->z, 1); + mpi_free(z1); + } + + point_free(&p1); + point_free(&p2); + point_free(&p1_); + point_free(&p2_); + if (scalar_copied) + mpi_free(scalar); + return; + } + + x1 = mpi_alloc_like(ctx->p); + y1 = mpi_alloc_like(ctx->p); + h = mpi_alloc_like(ctx->p); + k = mpi_copy(scalar); + yy = mpi_copy(point->y); + + if (mpi_has_sign(k)) { + k->sign = 0; + ec_invm(yy, yy, ctx); + } + + if (!mpi_cmp_ui(point->z, 1)) { + mpi_set(x1, point->x); + mpi_set(y1, yy); + } else { + MPI z2, z3; + + z2 = mpi_alloc_like(ctx->p); + z3 = mpi_alloc_like(ctx->p); + ec_mulm(z2, point->z, point->z, ctx); + ec_mulm(z3, point->z, z2, ctx); + ec_invm(z2, z2, ctx); + ec_mulm(x1, point->x, z2, ctx); + ec_invm(z3, z3, ctx); + ec_mulm(y1, yy, z3, ctx); + mpi_free(z2); + mpi_free(z3); + } + z1 = mpi_copy(mpi_const(MPI_C_ONE)); + + mpi_mul(h, k, mpi_const(MPI_C_THREE)); /* h = 3k */ + loops = mpi_get_nbits(h); + if (loops < 2) { + /* If SCALAR is zero, the above mpi_mul sets H to zero and thus + * LOOPs will be zero. To avoid an underflow of I in the main + * loop we set LOOP to 2 and the result to (0,0,0). + */ + loops = 2; + mpi_clear(result->x); + mpi_clear(result->y); + mpi_clear(result->z); + } else { + mpi_set(result->x, point->x); + mpi_set(result->y, yy); + mpi_set(result->z, point->z); + } + mpi_free(yy); yy = NULL; + + p1.x = x1; x1 = NULL; + p1.y = y1; y1 = NULL; + p1.z = z1; z1 = NULL; + point_init(&p2); + point_init(&p1inv); + + /* Invert point: y = p - y mod p */ + point_set(&p1inv, &p1); + ec_subm(p1inv.y, ctx->p, p1inv.y, ctx); + + for (i = loops-2; i > 0; i--) { + mpi_ec_dup_point(result, result, ctx); + if (mpi_test_bit(h, i) == 1 && mpi_test_bit(k, i) == 0) { + point_set(&p2, result); + mpi_ec_add_points(result, &p2, &p1, ctx); + } + if (mpi_test_bit(h, i) == 0 && mpi_test_bit(k, i) == 1) { + point_set(&p2, result); + mpi_ec_add_points(result, &p2, &p1inv, ctx); + } + } + + point_free(&p1); + point_free(&p2); + point_free(&p1inv); + mpi_free(h); + mpi_free(k); +} +EXPORT_SYMBOL_GPL(mpi_ec_mul_point); + +/* Return true if POINT is on the curve described by CTX. */ +int mpi_ec_curve_point(MPI_POINT point, struct mpi_ec_ctx *ctx) +{ + int res = 0; + MPI x, y, w; + + x = mpi_new(0); + y = mpi_new(0); + w = mpi_new(0); + + /* Check that the point is in range. This needs to be done here and + * not after conversion to affine coordinates. + */ + if (mpi_cmpabs(point->x, ctx->p) >= 0) + goto leave; + if (mpi_cmpabs(point->y, ctx->p) >= 0) + goto leave; + if (mpi_cmpabs(point->z, ctx->p) >= 0) + goto leave; + + switch (ctx->model) { + case MPI_EC_WEIERSTRASS: + { + MPI xxx; + + if (mpi_ec_get_affine(x, y, point, ctx)) + goto leave; + + xxx = mpi_new(0); + + /* y^2 == x^3 + a·x + b */ + ec_pow2(y, y, ctx); + + ec_pow3(xxx, x, ctx); + ec_mulm(w, ctx->a, x, ctx); + ec_addm(w, w, ctx->b, ctx); + ec_addm(w, w, xxx, ctx); + + if (!mpi_cmp(y, w)) + res = 1; + + mpi_free(xxx); + } + break; + + case MPI_EC_MONTGOMERY: + { +#define xx y + /* With Montgomery curve, only X-coordinate is valid. */ + if (mpi_ec_get_affine(x, NULL, point, ctx)) + goto leave; + + /* The equation is: b * y^2 == x^3 + a · x^2 + x */ + /* We check if right hand is quadratic residue or not by + * Euler's criterion. + */ + /* CTX->A has (a-2)/4 and CTX->B has b^-1 */ + ec_mulm(w, ctx->a, mpi_const(MPI_C_FOUR), ctx); + ec_addm(w, w, mpi_const(MPI_C_TWO), ctx); + ec_mulm(w, w, x, ctx); + ec_pow2(xx, x, ctx); + ec_addm(w, w, xx, ctx); + ec_addm(w, w, mpi_const(MPI_C_ONE), ctx); + ec_mulm(w, w, x, ctx); + ec_mulm(w, w, ctx->b, ctx); +#undef xx + /* Compute Euler's criterion: w^(p-1)/2 */ +#define p_minus1 y + ec_subm(p_minus1, ctx->p, mpi_const(MPI_C_ONE), ctx); + mpi_rshift(p_minus1, p_minus1, 1); + ec_powm(w, w, p_minus1, ctx); + + res = !mpi_cmp_ui(w, 1); +#undef p_minus1 + } + break; + + case MPI_EC_EDWARDS: + { + if (mpi_ec_get_affine(x, y, point, ctx)) + goto leave; + + mpi_resize(w, ctx->p->nlimbs); + w->nlimbs = ctx->p->nlimbs; + + /* a · x^2 + y^2 - 1 - b · x^2 · y^2 == 0 */ + ctx->pow2(x, x, ctx); + ctx->pow2(y, y, ctx); + if (ctx->dialect == ECC_DIALECT_ED25519) + ctx->subm(w, ctx->p, x, ctx); + else + ctx->mulm(w, ctx->a, x, ctx); + ctx->addm(w, w, y, ctx); + ctx->mulm(x, x, y, ctx); + ctx->mulm(x, x, ctx->b, ctx); + ctx->subm(w, w, x, ctx); + if (!mpi_cmp_ui(w, 1)) + res = 1; + } + break; + } + +leave: + mpi_free(w); + mpi_free(x); + mpi_free(y); + + return res; +} +EXPORT_SYMBOL_GPL(mpi_ec_curve_point); From patchwork Sun Feb 16 08:59:24 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: "tianjia.zhang" X-Patchwork-Id: 198090 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-9.8 required=3.0 tests=HEADER_FROM_DIFFERENT_DOMAINS, INCLUDES_PATCH, MAILING_LIST_MULTI, SIGNED_OFF_BY, SPF_HELO_NONE, SPF_PASS, UNPARSEABLE_RELAY, USER_AGENT_GIT autolearn=unavailable autolearn_force=no version=3.4.0 Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id 2AE27C2BA83 for ; Sun, 16 Feb 2020 09:05:26 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by mail.kernel.org (Postfix) with ESMTP id D8A9D206E2 for ; Sun, 16 Feb 2020 09:05:25 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1725926AbgBPJFZ (ORCPT ); Sun, 16 Feb 2020 04:05:25 -0500 Received: from out30-131.freemail.mail.aliyun.com ([115.124.30.131]:46873 "EHLO out30-131.freemail.mail.aliyun.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1726719AbgBPJFZ (ORCPT ); Sun, 16 Feb 2020 04:05:25 -0500 X-Alimail-AntiSpam: AC=PASS; BC=-1|-1; BR=01201311R421e4; CH=green; DM=||false|; DS=||; FP=0|-1|-1|-1|0|-1|-1|-1; HT=e01e04400; MF=tianjia.zhang@linux.alibaba.com; NM=1; PH=DS; RN=7; SR=0; TI=SMTPD_---0Tq4ZmUp_1581843592; Received: from localhost(mailfrom:tianjia.zhang@linux.alibaba.com fp:SMTPD_---0Tq4ZmUp_1581843592) by smtp.aliyun-inc.com(127.0.0.1); Sun, 16 Feb 2020 16:59:53 +0800 From: Tianjia Zhang To: herbert@gondor.apana.org.au, davem@davemloft.net, ebiggers@kernel.org, pvanleeuwen@rambus.com, zohar@linux.ibm.com Cc: linux-crypto@vger.kernel.org, linux-kernel@vger.kernel.org Subject: [PATCH 3/7] crypto: sm2 - introduce OSCCA SM2 asymmetric cipher algorithm Date: Sun, 16 Feb 2020 16:59:24 +0800 Message-Id: <20200216085928.108838-4-tianjia.zhang@linux.alibaba.com> X-Mailer: git-send-email 2.17.1 In-Reply-To: <20200216085928.108838-1-tianjia.zhang@linux.alibaba.com> References: <20200216085928.108838-1-tianjia.zhang@linux.alibaba.com> Sender: linux-crypto-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: linux-crypto@vger.kernel.org This new module implement the SM2 public key algorithm. It was published by State Encryption Management Bureau, China. List of specifications for SM2 elliptic curve public key cryptography: * GM/T 0003.1-2012 * GM/T 0003.2-2012 * GM/T 0003.3-2012 * GM/T 0003.4-2012 * GM/T 0003.5-2012 IETF: https://tools.ietf.org/html/draft-shen-sm2-ecdsa-02 oscca: http://www.oscca.gov.cn/sca/xxgk/2010-12/17/content_1002386.shtml scctc: http://www.gmbz.org.cn/main/bzlb.html Signed-off-by: Tianjia Zhang --- crypto/Kconfig | 17 + crypto/Makefile | 8 + crypto/sm2.c | 1145 ++++++++++++++++++++++++++++++++++++++ crypto/sm2signature.asn1 | 4 + include/crypto/sm2.h | 25 + 5 files changed, 1199 insertions(+) create mode 100644 crypto/sm2.c create mode 100644 crypto/sm2signature.asn1 create mode 100644 include/crypto/sm2.h diff --git a/crypto/Kconfig b/crypto/Kconfig index 5575d48473bd..4a58673c85dd 100644 --- a/crypto/Kconfig +++ b/crypto/Kconfig @@ -264,6 +264,23 @@ config CRYPTO_ECRDSA standard algorithms (called GOST algorithms). Only signature verification is implemented. +config CRYPTO_SM2 + tristate "SM2 algorithm" + select CRYPTO_SM3 + select CRYPTO_AKCIPHER + select CRYPTO_MANAGER + select MPILIB + select ASN1 + help + Generic implementation of the SM2 public key algorithm. It was + published by State Encryption Management Bureau, China. + as specified by OSCCA GM/T 0003.1-2012 -- 0003.5-2012. + + References: + https://tools.ietf.org/html/draft-shen-sm2-ecdsa-02 + http://www.oscca.gov.cn/sca/xxgk/2010-12/17/content_1002386.shtml + http://www.gmbz.org.cn/main/bzlb.html + config CRYPTO_CURVE25519 tristate "Curve25519 algorithm" select CRYPTO_KPP diff --git a/crypto/Makefile b/crypto/Makefile index 4ca12b6044f7..b279483fba50 100644 --- a/crypto/Makefile +++ b/crypto/Makefile @@ -42,6 +42,14 @@ rsa_generic-y += rsa_helper.o rsa_generic-y += rsa-pkcs1pad.o obj-$(CONFIG_CRYPTO_RSA) += rsa_generic.o +$(obj)/sm2signature.asn1.o: $(obj)/sm2signature.asn1.c $(obj)/sm2signature.asn1.h +$(obj)/sm2.o: $(obj)/sm2signature.asn1.h + +sm2_generic-y += sm2signature.asn1.o +sm2_generic-y += sm2.o + +obj-$(CONFIG_CRYPTO_SM2) += sm2_generic.o + crypto_acompress-y := acompress.o crypto_acompress-y += scompress.o obj-$(CONFIG_CRYPTO_ACOMP2) += crypto_acompress.o diff --git a/crypto/sm2.c b/crypto/sm2.c new file mode 100644 index 000000000000..0410975554d1 --- /dev/null +++ b/crypto/sm2.c @@ -0,0 +1,1145 @@ +/* SPDX-License-Identifier: GPL-2.0-or-later */ +/* + * SM2 asymmetric public-key algorithm + * as specified by OSCCA GM/T 0003.1-2012 -- 0003.5-2012 SM2 and + * described at https://tools.ietf.org/html/draft-shen-sm2-ecdsa-02 + * + * Copyright (c) 2020, Alibaba Group. + * Authors: Tianjia Zhang + */ + +#include +#include +#include +#include +#include +#include +#include +#include +#include "sm2signature.asn1.h" + +#define MPI_NBYTES(m) ((mpi_get_nbits(m) + 7) / 8) + +struct ecc_domain_parms { + const char *desc; /* Description of the curve. */ + unsigned int nbits; /* Number of bits. */ + unsigned int fips:1; /* True if this is a FIPS140-2 approved curve */ + + /* The model describing this curve. This is mainly used to select + * the group equation. + */ + enum gcry_mpi_ec_models model; + + /* The actual ECC dialect used. This is used for curve specific + * optimizations and to select encodings etc. + */ + enum ecc_dialects dialect; + + const char *p; /* The prime defining the field. */ + const char *a, *b; /* The coefficients. For Twisted Edwards + * Curves b is used for d. For Montgomery + * Curves (a,b) has ((A-2)/4,B^-1). + */ + const char *n; /* The order of the base point. */ + const char *g_x, *g_y; /* Base point. */ + unsigned int h; /* Cofactor. */ +}; + +static const struct ecc_domain_parms sm2_ecp = { + .desc = "sm2p256v1", + .nbits = 256, + .fips = 0, + .model = MPI_EC_WEIERSTRASS, + .dialect = ECC_DIALECT_STANDARD, + .p = "0xfffffffeffffffffffffffffffffffffffffffff00000000ffffffffffffffff", + .a = "0xfffffffeffffffffffffffffffffffffffffffff00000000fffffffffffffffc", + .b = "0x28e9fa9e9d9f5e344d5a9e4bcf6509a7f39789f515ab8f92ddbcbd414d940e93", + .n = "0xfffffffeffffffffffffffffffffffff7203df6b21c6052b53bbf40939d54123", + .g_x = "0x32c4ae2c1f1981195f9904466a39c9948fe30bbff2660be1715a4589334c74c7", + .g_y = "0xbc3736a2f4f6779c59bdcee36b692153d0a9877cc62a474002df32e52139f0a0", + .h = 1 +}; + +static int sm2_ec_ctx_init(struct mpi_ec_ctx *ec) +{ + const struct ecc_domain_parms *ecp = &sm2_ecp; + MPI p, a, b; + MPI x, y; + int rc = -EINVAL; + + p = mpi_scanval(ecp->p); + a = mpi_scanval(ecp->a); + b = mpi_scanval(ecp->b); + if (!p || !a || !b) + goto free_p; + + x = mpi_scanval(ecp->g_x); + y = mpi_scanval(ecp->g_y); + if (!x || !y) + goto free; + + /* mpi_ec_setup_elliptic_curve */ + ec->G = mpi_point_new(0); + if (!ec->G) + goto free; + + mpi_set(ec->G->x, x); + mpi_set(ec->G->y, y); + mpi_set_ui(ec->G->z, 1); + + ec->n = mpi_scanval(ecp->n); + if (!ec->n) { + mpi_point_release(ec->G); + goto free; + } + + ec->h = ecp->h; + ec->name = ecp->desc; + mpi_ec_init(ec, ecp->model, ecp->dialect, 0, p, a, b); + + rc = 0; + +free: + mpi_free(x); + mpi_free(y); +free_p: + mpi_free(p); + mpi_free(a); + mpi_free(b); + + return rc; +} + +static void sm2_ec_ctx_deinit(struct mpi_ec_ctx *ec) +{ + mpi_free(ec->n); + mpi_point_release(ec->G); + + mpi_ec_deinit(ec); + + memset(ec, 0, sizeof(*ec)); +} + +static int sm2_ec_ctx_reset(struct mpi_ec_ctx *ec) +{ + sm2_ec_ctx_deinit(ec); + return sm2_ec_ctx_init(ec); +} + +static unsigned char *sm2_ecc_ec2os(MPI x, MPI y, MPI p, unsigned int *plen) +{ + int rc; + int pbytes = (mpi_get_nbits(p)+7)/8; + size_t n; + unsigned char *buf, *ptr; + + buf = kmalloc(1 + 2*pbytes, GFP_KERNEL); + if (!buf) + return NULL; + *buf = 04; /* Uncompressed point. */ + ptr = buf+1; + rc = mpi_print(GCRYMPI_FMT_USG, ptr, pbytes, &n, x); + if (rc) { + kfree(buf); + return NULL; + } + if (n < pbytes) { + memmove(ptr+(pbytes-n), ptr, n); + memset(ptr, 0, (pbytes-n)); + } + ptr += pbytes; + rc = mpi_print(GCRYMPI_FMT_USG, ptr, pbytes, &n, y); + if (rc) { + kfree(buf); + return NULL; + } + if (n < pbytes) { + memmove(ptr+(pbytes-n), ptr, n); + memset(ptr, 0, (pbytes-n)); + } + + if (plen) + *plen = 1 + 2 * pbytes; + return buf; +} + +/* Convert POINT into affine coordinates using the context CTX and + * return a newly allocated MPI. If the conversion is not possible + * NULL is returned. This function won't print an error message. + */ +static unsigned char * +sm2_mpi_ec_ec2os(MPI_POINT point, struct mpi_ec_ctx *ec, unsigned int *plen) +{ + MPI g_x, g_y; + unsigned char *result; + + g_x = mpi_new(0); + g_y = mpi_new(0); + if (mpi_ec_get_affine(g_x, g_y, point, ec)) + result = NULL; + else + result = sm2_ecc_ec2os(g_x, g_y, ec->p, plen); + mpi_free(g_x); + mpi_free(g_y); + + return result; +} + +/* RESULT must have been initialized and is set on success to the + * point given by VALUE. + */ +static int sm2_ecc_os2ec(MPI_POINT result, MPI value) +{ + int rc; + size_t n; + const unsigned char *buf; + unsigned char *buf_memory; + MPI x, y; + + n = (mpi_get_nbits(value)+7)/8; + buf_memory = kmalloc(n, GFP_KERNEL); + rc = mpi_print(GCRYMPI_FMT_USG, buf_memory, n, &n, value); + if (rc) { + kfree(buf_memory); + return rc; + } + buf = buf_memory; + + if (n < 1) { + kfree(buf_memory); + return -EINVAL; + } + if (*buf != 4) { + kfree(buf_memory); + return -EINVAL; /* No support for point compression. */ + } + if (((n-1)%2)) { + kfree(buf_memory); + return -EINVAL; + } + n = (n-1)/2; + x = mpi_read_raw_data(buf + 1, n); + if (!x) { + kfree(buf_memory); + return -ENOMEM; + } + y = mpi_read_raw_data(buf + 1 + n, n); + kfree(buf_memory); + if (!y) { + mpi_free(x); + return -ENOMEM; + } + + mpi_normalize(x); + mpi_normalize(y); + + mpi_set(result->x, x); + mpi_set(result->y, y); + mpi_set_ui(result->z, 1); + + mpi_free(x); + mpi_free(y); + + return 0; +} + +/* + * Generate a random secret exponent K less than Q. + */ +static MPI sm2_gen_k(MPI q) +{ + MPI k = NULL; + unsigned int nbits = mpi_get_nbits(q); + unsigned int nbytes = (nbits+7)/8; + char rndbuf[128]; + int use_rng = 1; + + if (nbytes > sizeof(rndbuf)) + return NULL; + if (crypto_get_default_rng()) + use_rng = 0; + + for (;;) { + + if (k) { + mpi_free(k); + k = NULL; + } + + if (use_rng) { + if (crypto_rng_get_bytes(crypto_default_rng, + rndbuf, nbytes)) + goto ret; + } else { + get_random_bytes(rndbuf, nbytes); + } + + k = mpi_read_raw_data(rndbuf, nbytes); + if (!k) + goto ret; + + /* Make sure we have the requested number of bits. This code + * looks a bit funny but it is easy to understand if you + * consider that mpi_set_highbit clears all higher bits. We + * don't have a clear_highbit, thus we first set the high bit + * and then clear it again. + */ + if (mpi_test_bit(k, nbits-1)) + mpi_set_highbit(k, nbits-1); + else { + mpi_set_highbit(k, nbits-1); + mpi_clear_bit(k, nbits-1); + } + + if (!(mpi_cmp(k, q) < 0)) /* check: k < q */ + continue; + if (!(mpi_cmp_ui(k, 0) > 0)) /* check: k > 0 */ + continue; + + break; /* okay */ + } +ret: + if (use_rng) + crypto_put_default_rng(); + return k; +} + +static MPI sm2_cipher_encode(MPI c1, MPI c3, MPI c2) +{ + unsigned int n; + unsigned char *buf, *p; + unsigned int nwritten; + int rc; + MPI result = NULL; + + n = mpi_get_size(c1) + mpi_get_size(c3) + mpi_get_size(c2); + + buf = kmalloc(n, GFP_KERNEL); + if (!buf) + return NULL; + + p = buf; + rc = mpi_read_buffer(c1, p, mpi_get_size(c1), &nwritten, NULL); + if (rc) + goto err; + p += nwritten; + rc = mpi_read_buffer(c3, p, mpi_get_size(c3), &nwritten, NULL); + if (rc) + goto err; + p += nwritten; + rc = mpi_read_buffer(c2, p, mpi_get_size(c2), &nwritten, NULL); + if (rc) + goto err; + + result = mpi_read_raw_data(buf, p + nwritten - buf); + +err: + kfree(buf); + return result; +} + +static int sm2_cipher_decode(MPI c, MPI *c1, MPI *c3, MPI *c2) +{ + unsigned char *buf, *p; + unsigned int n; + + buf = mpi_get_buffer(c, &n, NULL); + if (!buf) + return -ENOMEM; + if (n < 65 + SM3_DIGEST_SIZE) + return -EINVAL; + + p = buf; + /* '0x04' + 2 * 256 bits */ + *c1 = mpi_read_raw_data(p, 65); + p += 65; + *c3 = mpi_read_raw_data(p, SM3_DIGEST_SIZE); + p += SM3_DIGEST_SIZE; + *c2 = mpi_read_raw_data(p, buf + n - p); + + kfree(buf); + + if (!*c1 || !*c3 || !*c2) { + mpi_free(*c1); + mpi_free(*c3); + mpi_free(*c2); + return -EINVAL; + } + return 0; +} + +static MPI sm2_signature_encode(MPI hash, MPI r, MPI s) +{ + unsigned char *buf; + unsigned int nwritten; + unsigned int n; + int rc; + MPI result = NULL; + + /* both r and s are 256 bits */ + n = SM3_DIGEST_SIZE + 32 * 2; + buf = kzalloc(n, GFP_KERNEL); + if (!buf) + return NULL; + + rc = mpi_read_buffer(hash, buf, SM3_DIGEST_SIZE, &nwritten, NULL); + if (rc) + goto err; + rc = mpi_read_buffer(r, buf + SM3_DIGEST_SIZE, 32, &nwritten, NULL); + if (rc) + goto err; + rc = mpi_read_buffer(s, buf + SM3_DIGEST_SIZE + 32, + 32, &nwritten, NULL); + if (rc) + goto err; + + result = mpi_read_raw_data(buf, n); + +err: + kfree(buf); + return result; +} + +struct sm2_signature_ctx { + MPI sig_r; + MPI sig_s; +}; + +int sm2_get_signature_r(void *context, size_t hdrlen, unsigned char tag, + const void *value, size_t vlen) +{ + struct sm2_signature_ctx *sig = context; + + if (!value || !vlen) + return -EINVAL; + + sig->sig_r = mpi_read_raw_data(value, vlen); + if (!sig->sig_r) + return -ENOMEM; + + return 0; +} + +int sm2_get_signature_s(void *context, size_t hdrlen, unsigned char tag, + const void *value, size_t vlen) +{ + struct sm2_signature_ctx *sig = context; + + if (!value || !vlen) + return -EINVAL; + + sig->sig_s = mpi_read_raw_data(value, vlen); + if (!sig->sig_s) + return -ENOMEM; + + return 0; +} + +static int sm2_z_digest_update(struct shash_desc *desc, + MPI m, unsigned int pbytes) +{ + static const unsigned char zero[32]; + unsigned char *in; + unsigned int inlen; + + in = mpi_get_buffer(m, &inlen, NULL); + if (!in) + return -EINVAL; + + if (inlen < pbytes) { + /* padding with zero */ + crypto_sm3_update(desc, zero, pbytes - inlen); + crypto_sm3_update(desc, in, inlen); + } else if (inlen > pbytes) { + /* skip the starting zero */ + crypto_sm3_update(desc, in + inlen - pbytes, pbytes); + } else { + crypto_sm3_update(desc, in, inlen); + } + + kfree(in); + return 0; +} + +static int sm2_z_digest_update_point(struct shash_desc *desc, + MPI_POINT point, struct mpi_ec_ctx *ec, unsigned int pbytes) +{ + MPI x, y; + int ret = -EINVAL; + + x = mpi_new(0); + y = mpi_new(0); + + if (!mpi_ec_get_affine(x, y, point, ec) && + !sm2_z_digest_update(desc, x, pbytes) && + !sm2_z_digest_update(desc, y, pbytes)) + ret = 0; + + mpi_free(x); + mpi_free(y); + return ret; +} + +int sm2_compute_z_digest(struct crypto_akcipher *tfm, + const unsigned char *id, size_t id_len, + unsigned char dgst[SM3_DIGEST_SIZE]) +{ + struct mpi_ec_ctx *ec = akcipher_tfm_ctx(tfm); + uint16_t bits_len; + unsigned char entl[2]; + SHASH_DESC_ON_STACK(desc, NULL); + unsigned int pbytes; + + if (id_len > (USHRT_MAX / 8) || !ec->Q) + return -EINVAL; + + bits_len = (uint16_t)(id_len * 8); + entl[0] = bits_len >> 8; + entl[1] = bits_len & 0xff; + + pbytes = MPI_NBYTES(ec->p); + + /* ZA = H256(ENTLA | IDA | a | b | xG | yG | xA | yA) */ + sm3_base_init(desc); + crypto_sm3_update(desc, entl, 2); + crypto_sm3_update(desc, id, id_len); + + if (sm2_z_digest_update(desc, ec->a, pbytes) || + sm2_z_digest_update(desc, ec->b, pbytes) || + sm2_z_digest_update_point(desc, ec->G, ec, pbytes) || + sm2_z_digest_update_point(desc, ec->Q, ec, pbytes)) + return -EINVAL; + + crypto_sm3_finup(desc, NULL, 0, dgst); + return 0; +} +EXPORT_SYMBOL(sm2_compute_z_digest); + +/* Key derivation function from X9.63/SECG */ +static void kdf_x9_63(const void *in, size_t inlen, void *out, size_t outlen) +{ + int mdlen = SM3_DIGEST_SIZE; + u32 counter = 1; + u32 counter_be; + unsigned char dgst[SM3_DIGEST_SIZE]; + unsigned char *pout = out; + size_t rlen = outlen; + size_t len; + SHASH_DESC_ON_STACK(desc, NULL); + + while (rlen > 0) { + counter_be = cpu_to_be32(counter); + counter++; + + sm3_base_init(desc); + crypto_sm3_update(desc, in, inlen); + crypto_sm3_finup(desc, (const u8 *)&counter_be, + sizeof(counter_be), dgst); + + len = mdlen < rlen ? mdlen : rlen; /* min(mdlen, rlen) */ + memcpy(pout, dgst, len); + rlen -= len; + pout += len; + } +} + +static int _sm2_enc(struct mpi_ec_ctx *ec, MPI m, MPI *c1, MPI *c3, MPI *c2) +{ + int rc; + MPI k = NULL; + MPI x2, y2; + struct gcry_mpi_point kG, kP; + unsigned char *in = NULL; + unsigned int inlen; + unsigned int len; + unsigned char *x1y1 = NULL; + unsigned char *x2y2 = NULL; + unsigned char *cipher = NULL; + int i; + + mpi_point_init(&kG); + mpi_point_init(&kP); + x2 = mpi_new(0); + y2 = mpi_new(0); + + rc = -ENOMEM; + in = mpi_get_buffer(m, &inlen, NULL); + if (!in) + goto leave; + + cipher = kmalloc(inlen, GFP_KERNEL); + if (!cipher) + goto leave; + + /* rand k in [1, n-1] */ + k = sm2_gen_k(ec->n); + if (k == NULL) + goto leave; + + /* [k]G = (x1, y1) */ + mpi_ec_mul_point(&kG, k, ec->G, ec); + x1y1 = sm2_mpi_ec_ec2os(&kG, ec, &len); + if (x1y1 == NULL) + goto leave; + *c1 = mpi_read_raw_data(x1y1, len); + if (*c1 == NULL) + goto leave; + + /* [k]P = (x2, y2) */ + rc = -EINVAL; + mpi_ec_mul_point(&kP, k, ec->Q, ec); + if (mpi_ec_get_affine(x2, y2, &kP, ec)) + goto leave; + + /* t = KDF(x2 || y2, klen) */ + rc = -ENOMEM; + x2y2 = sm2_ecc_ec2os(x2, y2, ec->p, &len); + if (x2y2 == NULL) + goto leave; + + /* skip the prefix '0x04' */ + kdf_x9_63(x2y2 + 1, len - 1, cipher, inlen); + + /* cipher = t xor in */ + for (i = 0; i < inlen; i++) + cipher[i] ^= in[i]; + + *c2 = mpi_read_raw_data(cipher, inlen); + if (*c2 == NULL) { + rc = -ENOMEM; + goto leave; + } + + /* hash(x2 || IN || y2) */ + do { + SHASH_DESC_ON_STACK(desc, NULL); + unsigned char dgst[SM3_DIGEST_SIZE]; + + sm3_base_init(desc); + crypto_sm3_update(desc, x2y2 + 1, MPI_NBYTES(x2)); + crypto_sm3_update(desc, in, inlen); + crypto_sm3_finup(desc, x2y2 + 1 + MPI_NBYTES(x2), + MPI_NBYTES(y2), dgst); + + *c3 = mpi_read_raw_data(dgst, sizeof(dgst)); + if (*c3 == NULL) { + rc = -ENOMEM; + goto leave; + } + } while (0); + + rc = 0; + +leave: + if (rc) { + if (*c1) + mpi_free(*c1); + if (*c2) + mpi_free(*c2); + if (*c3) + mpi_free(*c3); + *c1 = NULL; + *c2 = NULL; + *c3 = NULL; + } + + kfree(x2y2); + kfree(x1y1); + mpi_free(k); + + kfree(cipher); + kfree(in); + + mpi_point_free_parts(&kG); + mpi_point_free_parts(&kP); + mpi_free(x2); + mpi_free(y2); + + return rc; +} + +static int _sm2_dec(struct mpi_ec_ctx *ec, MPI c1, MPI c3, MPI c2, MPI *m) +{ + int rc; + MPI x2, y2; + struct gcry_mpi_point point_c1; + struct gcry_mpi_point kP; + unsigned char *x2y2 = NULL; + unsigned char *in = NULL; + unsigned int inlen; + unsigned char *plain = NULL; + unsigned int len; + unsigned char *hash = NULL; + int i; + + mpi_point_init(&point_c1); + mpi_point_init(&kP); + x2 = mpi_new(0); + y2 = mpi_new(0); + + rc = -ENOMEM; + in = mpi_get_buffer(c2, &inlen, NULL); + if (!in) + goto leave; + + plain = kmalloc(inlen, GFP_KERNEL); + if (!plain) + goto leave; + + rc = sm2_ecc_os2ec(&point_c1, c1); + if (rc) + goto leave; + + rc = -EINVAL; + if (!mpi_ec_curve_point(&point_c1, ec)) + goto leave; + + /* [d]C1 = (x2, y2), C1 = [k]G */ + mpi_ec_mul_point(&kP, ec->d, &point_c1, ec); + if (mpi_ec_get_affine(x2, y2, &kP, ec)) + goto leave; + + /* t = KDF(x2 || y2, inlen) */ + x2y2 = sm2_ecc_ec2os(x2, y2, ec->p, &len); + /* skip the prefix '0x04' */ + kdf_x9_63(x2y2 + 1, len - 1, plain, inlen); + + /* plain = C2 xor t */ + for (i = 0; i < inlen; i++) + plain[i] ^= in[i]; + + /* Hash(x2 || IN || y2) == C3 */ + do { + SHASH_DESC_ON_STACK(desc, NULL); + unsigned char dgst[SM3_DIGEST_SIZE]; + + sm3_base_init(desc); + crypto_sm3_update(desc, x2y2 + 1, MPI_NBYTES(x2)); + crypto_sm3_update(desc, plain, inlen); + crypto_sm3_finup(desc, x2y2 + 1 + MPI_NBYTES(x2), + MPI_NBYTES(y2), dgst); + + rc = -EINVAL; + hash = mpi_get_buffer(c3, &len, NULL); + if (len != sizeof(dgst) || memcmp(dgst, hash, len) != 0) + goto leave; + } while (0); + + rc = -ENOMEM; + *m = mpi_read_raw_data(plain, inlen); + if (*m == NULL) + goto leave; + + rc = 0; + +leave: + kfree(hash); + kfree(x2y2); + if (plain) { + memset(plain, 0, inlen); + kfree(plain); + } + kfree(in); + + mpi_point_free_parts(&point_c1); + mpi_point_free_parts(&kP); + mpi_free(x2); + mpi_free(y2); + + return rc; +} + +static int _sm2_sign(struct mpi_ec_ctx *ec, MPI hash, MPI *r, MPI *s) +{ + int rc = -EINVAL; + struct gcry_mpi_point kG; + MPI sig_r = NULL; + MPI sig_s = NULL; + MPI tmp = NULL; + MPI k = NULL; + MPI rk = NULL; + MPI x1 = NULL; + + mpi_point_init(&kG); + x1 = mpi_new(0); + sig_r = mpi_new(0); + sig_s = mpi_new(0); + rk = mpi_new(0); + tmp = mpi_new(0); + + for (;;) { + /* rand k in [1, n-1] */ + k = sm2_gen_k(ec->n); + if (k == NULL) + goto leave; + + /* [k]G = (x1, y1) */ + mpi_ec_mul_point(&kG, k, ec->G, ec); + if (mpi_ec_get_affine(x1, NULL, &kG, ec)) + goto leave; + + /* r = (e + x1) % n */ + mpi_addm(sig_r, hash, x1, ec->n); + + /* r != 0 && r + k != n */ + if (mpi_cmp_ui(sig_r, 0) == 0) + continue; + mpi_add(rk, sig_r, k); + if (mpi_cmp(rk, ec->n) == 0) + continue; + + /* s = ((d + 1)^-1 * (k - rd)) % n */ + mpi_addm(sig_s, ec->d, mpi_const(MPI_C_ONE), ec->n); + mpi_invm(sig_s, sig_s, ec->n); + mpi_mulm(tmp, sig_r, ec->d, ec->n); + mpi_subm(tmp, k, tmp, ec->n); + mpi_mulm(sig_s, sig_s, tmp, ec->n); + + break; + } + + *r = sig_r; + *s = sig_s; + rc = 0; + +leave: + if (rc) { + mpi_free(sig_r); + mpi_free(sig_s); + } + mpi_point_free_parts(&kG); + mpi_free(x1); + mpi_free(k); + mpi_free(rk); + mpi_free(tmp); + + return rc; +} + +static int _sm2_verify(struct mpi_ec_ctx *ec, MPI hash, MPI sig_r, MPI sig_s) +{ + int rc = -EINVAL; + struct gcry_mpi_point sG, tP; + MPI t = NULL; + MPI x1 = NULL, y1 = NULL; + + mpi_point_init(&sG); + mpi_point_init(&tP); + x1 = mpi_new(0); + y1 = mpi_new(0); + t = mpi_new(0); + + /* r, s in [1, n-1] */ + if (mpi_cmp_ui(sig_r, 1) < 0 || mpi_cmp(sig_r, ec->n) > 0 || + mpi_cmp_ui(sig_s, 1) < 0 || mpi_cmp(sig_s, ec->n) > 0) { + goto leave; + } + + /* t = (r + s) % n, t == 0 */ + mpi_addm(t, sig_r, sig_s, ec->n); + if (mpi_cmp_ui(t, 0) == 0) + goto leave; + + /* sG + tP = (x1, y1) */ + rc = -EBADMSG; + mpi_ec_mul_point(&sG, sig_s, ec->G, ec); + mpi_ec_mul_point(&tP, t, ec->Q, ec); + mpi_ec_add_points(&sG, &sG, &tP, ec); + if (mpi_ec_get_affine(x1, y1, &sG, ec)) + goto leave; + + /* R = (e + x1) % n */ + mpi_addm(t, hash, x1, ec->n); + + /* check R == r */ + rc = -EKEYREJECTED; + if (mpi_cmp(t, sig_r)) + goto leave; + + rc = 0; + +leave: + mpi_point_free_parts(&sG); + mpi_point_free_parts(&tP); + mpi_free(x1); + mpi_free(y1); + mpi_free(t); + + return rc; +} + +static int sm2_enc(struct akcipher_request *req) +{ + struct crypto_akcipher *tfm = crypto_akcipher_reqtfm(req); + struct mpi_ec_ctx *ec = akcipher_tfm_ctx(tfm); + MPI m, c; + MPI c1 = NULL, c3 = NULL, c2 = NULL; + int ret = 0; + int sign; + + if (unlikely(!ec->Q)) + return -EINVAL; + + m = mpi_read_raw_from_sgl(req->src, req->src_len); + if (!m) + return -ENOMEM; + + ret = _sm2_enc(ec, m, &c1, &c3, &c2); + if (ret) + goto err_free_m; + + ret = -EFAULT; + c = sm2_cipher_encode(c1, c3, c2); + if (!c) + goto err_free_c; + + ret = mpi_write_to_sgl(c, req->dst, req->dst_len, &sign); + if (ret) + goto err_free_cipher; + + if (sign < 0) + ret = -EBADMSG; + +err_free_cipher: + mpi_free(c); +err_free_c: + mpi_free(c1); + mpi_free(c3); + mpi_free(c2); +err_free_m: + mpi_free(m); + return ret; +} + +static int sm2_dec(struct akcipher_request *req) +{ + struct crypto_akcipher *tfm = crypto_akcipher_reqtfm(req); + struct mpi_ec_ctx *ec = akcipher_tfm_ctx(tfm); + MPI m, c; + MPI c1 = NULL, c3 = NULL, c2 = NULL; + int ret = 0; + int sign; + + if (unlikely(!ec->d)) + return -EINVAL; + + c = mpi_read_raw_from_sgl(req->src, req->src_len); + if (!c) + return -ENOMEM; + + ret = sm2_cipher_decode(c, &c1, &c3, &c2); + if (ret) + goto err_free_cipher; + + ret = _sm2_dec(ec, c1, c3, c2, &m); + if (ret) + goto err_free_c; + + ret = mpi_write_to_sgl(m, req->dst, req->dst_len, &sign); + if (ret) + goto err_free_m; + + if (sign < 0) + ret = -EBADMSG; + +err_free_m: + mpi_free(m); +err_free_c: + mpi_free(c1); + mpi_free(c3); + mpi_free(c2); +err_free_cipher: + mpi_free(c); + return ret; +} + +static int sm2_sign(struct akcipher_request *req) +{ + struct crypto_akcipher *tfm = crypto_akcipher_reqtfm(req); + struct mpi_ec_ctx *ec = akcipher_tfm_ctx(tfm); + MPI hash, c; + MPI r = NULL, s = NULL; + int ret = 0; + int sign; + + if (unlikely(!ec->d)) + return -EINVAL; + + hash = mpi_read_raw_from_sgl(req->src, req->src_len); + if (!hash) + return -ENOMEM; + + ret = _sm2_sign(ec, hash, &r, &s); + if (ret) + goto err_free_hash; + + ret = -EFAULT; + c = sm2_signature_encode(hash, r, s); + if (!c) + goto err_free_r; + + ret = mpi_write_to_sgl(c, req->dst, req->dst_len, &sign); + if (ret) + goto err_free_c; + + if (sign < 0) + ret = -EBADMSG; + +err_free_c: + mpi_free(c); +err_free_r: + mpi_free(r); + mpi_free(s); +err_free_hash: + mpi_free(hash); + return ret; +} + +static int sm2_verify(struct akcipher_request *req) +{ + struct crypto_akcipher *tfm = crypto_akcipher_reqtfm(req); + struct mpi_ec_ctx *ec = akcipher_tfm_ctx(tfm); + unsigned char *buffer; + struct sm2_signature_ctx sig; + MPI hash; + int ret; + + if (unlikely(!ec->Q)) + return -EINVAL; + + buffer = kmalloc(req->src_len + req->dst_len, GFP_KERNEL); + if (!buffer) + return -ENOMEM; + + sg_pcopy_to_buffer(req->src, + sg_nents_for_len(req->src, req->src_len + req->dst_len), + buffer, req->src_len + req->dst_len, 0); + + sig.sig_r = NULL; + sig.sig_s = NULL; + ret = asn1_ber_decoder(&sm2signature_decoder, &sig, buffer, req->src_len); + if (ret) + goto error; + + ret = -ENOMEM; + hash = mpi_read_raw_data(buffer + req->src_len, req->dst_len); + if (!hash) + goto error; + + ret = _sm2_verify(ec, hash, sig.sig_r, sig.sig_s); + + mpi_free(hash); +error: + mpi_free(sig.sig_r); + mpi_free(sig.sig_s); + kfree(buffer); + return ret; +} + +static int sm2_set_pub_key(struct crypto_akcipher *tfm, const void *key, + unsigned int keylen) +{ + struct mpi_ec_ctx *ec = akcipher_tfm_ctx(tfm); + MPI a; + int rc; + + rc = sm2_ec_ctx_reset(ec); + if (rc) + return rc; + + ec->Q = mpi_point_new(0); + if (!ec->Q) + return -ENOMEM; + + /* include the uncompressed flag '0x04' */ + rc = -ENOMEM; + a = mpi_read_raw_data(key, keylen); + if (!a) + goto error; + + mpi_normalize(a); + rc = sm2_ecc_os2ec(ec->Q, a); + mpi_free(a); + if (rc) + goto error; + + return 0; + +error: + mpi_point_release(ec->Q); + ec->Q = NULL; + return rc; +} + +static int sm2_set_priv_key(struct crypto_akcipher *tfm, const void *key, + unsigned int keylen) +{ + struct mpi_ec_ctx *ec = akcipher_tfm_ctx(tfm); + int rc; + + rc = sm2_ec_ctx_reset(ec); + if (rc) + return rc; + + ec->d = mpi_read_raw_data(key, keylen); + if (!ec->d) + return -ENOMEM; + + /* compute pubkey if it not exist */ + if (!ec->Q) { + ec->Q = mpi_point_new(0); + if (!ec->Q) + return -ENOMEM; + mpi_ec_mul_point(ec->Q, ec->d, ec->G, ec); + } + + return 0; +} + +static unsigned int sm2_max_size(struct crypto_akcipher *tfm) +{ + /* Unlimited max size */ + return PAGE_SIZE; +} + +static void sm2_exit_tfm(struct crypto_akcipher *tfm) +{ + struct mpi_ec_ctx *ec = akcipher_tfm_ctx(tfm); + + mpi_ec_deinit(ec); +} + +static struct akcipher_alg sm2 = { + .encrypt = sm2_enc, + .decrypt = sm2_dec, + .sign = sm2_sign, + .verify = sm2_verify, + .set_priv_key = sm2_set_priv_key, + .set_pub_key = sm2_set_pub_key, + .max_size = sm2_max_size, + .exit = sm2_exit_tfm, + .base = { + .cra_name = "sm2", + .cra_driver_name = "sm2-generic", + .cra_priority = 100, + .cra_module = THIS_MODULE, + .cra_ctxsize = sizeof(struct mpi_ec_ctx), + }, +}; + +static int sm2_init(void) +{ + return crypto_register_akcipher(&sm2); +} + +static void sm2_exit(void) +{ + crypto_unregister_akcipher(&sm2); +} + +subsys_initcall(sm2_init); +module_exit(sm2_exit); + +MODULE_ALIAS_CRYPTO("sm2"); +MODULE_LICENSE("GPL"); +MODULE_DESCRIPTION("SM2 generic algorithm"); diff --git a/crypto/sm2signature.asn1 b/crypto/sm2signature.asn1 new file mode 100644 index 000000000000..ab8c0b754d21 --- /dev/null +++ b/crypto/sm2signature.asn1 @@ -0,0 +1,4 @@ +Sm2Signature ::= SEQUENCE { + sig_r INTEGER ({ sm2_get_signature_r }), + sig_s INTEGER ({ sm2_get_signature_s }) +} diff --git a/include/crypto/sm2.h b/include/crypto/sm2.h new file mode 100644 index 000000000000..af452556dcd4 --- /dev/null +++ b/include/crypto/sm2.h @@ -0,0 +1,25 @@ +/* SPDX-License-Identifier: GPL-2.0-or-later */ +/* + * sm2.h - SM2 asymmetric public-key algorithm + * as specified by OSCCA GM/T 0003.1-2012 -- 0003.5-2012 SM2 and + * described at https://tools.ietf.org/html/draft-shen-sm2-ecdsa-02 + * + * Copyright (c) 2020, Alibaba Group. + * Written by Tianjia Zhang + */ + +#ifndef _CRYPTO_SM2_H +#define _CRYPTO_SM2_H + +#include +#include + +/* The default user id as specified in GM/T 0009-2012 */ +#define SM2_DEFAULT_USERID "1234567812345678" +#define SM2_DEFAULT_USERID_LEN 16 + +extern int sm2_compute_z_digest(struct crypto_akcipher *tfm, + const unsigned char *id, size_t id_len, + unsigned char dgst[SM3_DIGEST_SIZE]); + +#endif /* _CRYPTO_SM2_H */ From patchwork Sun Feb 16 08:59:26 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: "tianjia.zhang" X-Patchwork-Id: 198093 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-9.8 required=3.0 tests=HEADER_FROM_DIFFERENT_DOMAINS, INCLUDES_PATCH, MAILING_LIST_MULTI, SIGNED_OFF_BY, SPF_HELO_NONE, SPF_PASS, UNPARSEABLE_RELAY, USER_AGENT_GIT autolearn=unavailable autolearn_force=no version=3.4.0 Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id C515CC2BA83 for ; Sun, 16 Feb 2020 09:00:05 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by mail.kernel.org (Postfix) with ESMTP id A58FB22522 for ; Sun, 16 Feb 2020 09:00:05 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1726178AbgBPJAC (ORCPT ); Sun, 16 Feb 2020 04:00:02 -0500 Received: from out30-56.freemail.mail.aliyun.com ([115.124.30.56]:58615 "EHLO out30-56.freemail.mail.aliyun.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1726203AbgBPJAC (ORCPT ); Sun, 16 Feb 2020 04:00:02 -0500 X-Alimail-AntiSpam: AC=PASS; BC=-1|-1; BR=01201311R151e4; CH=green; DM=||false|; DS=||; FP=0|-1|-1|-1|0|-1|-1|-1; HT=e01e07417; MF=tianjia.zhang@linux.alibaba.com; NM=1; PH=DS; RN=7; SR=0; TI=SMTPD_---0Tq4ZmV._1581843595; Received: from localhost(mailfrom:tianjia.zhang@linux.alibaba.com fp:SMTPD_---0Tq4ZmV._1581843595) by smtp.aliyun-inc.com(127.0.0.1); Sun, 16 Feb 2020 16:59:55 +0800 From: Tianjia Zhang To: herbert@gondor.apana.org.au, davem@davemloft.net, ebiggers@kernel.org, pvanleeuwen@rambus.com, zohar@linux.ibm.com Cc: linux-crypto@vger.kernel.org, linux-kernel@vger.kernel.org Subject: [PATCH 5/7] crypto: testmgr - Add SM2 test vectors Date: Sun, 16 Feb 2020 16:59:26 +0800 Message-Id: <20200216085928.108838-6-tianjia.zhang@linux.alibaba.com> X-Mailer: git-send-email 2.17.1 In-Reply-To: <20200216085928.108838-1-tianjia.zhang@linux.alibaba.com> References: <20200216085928.108838-1-tianjia.zhang@linux.alibaba.com> Sender: linux-crypto-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: linux-crypto@vger.kernel.org Add testmgr tests and vectors for SM2 asymmetric cipher. Signed-off-by: Tianjia Zhang --- crypto/testmgr.c | 7 +++++++ crypto/testmgr.h | 16 ++++++++++++++++ 2 files changed, 23 insertions(+) diff --git a/crypto/testmgr.c b/crypto/testmgr.c index db9b5ac878e7..ecc6b27c1dd3 100644 --- a/crypto/testmgr.c +++ b/crypto/testmgr.c @@ -5050,6 +5050,13 @@ static const struct alg_test_desc alg_test_descs[] = { .suite = { .hash = __VECS(sha512_tv_template) } + }, { + .alg = "sm2", + .test = alg_test_akcipher, + .fips_allowed = 1, + .suite = { + .akcipher = __VECS(sm2_tv_template) + } }, { .alg = "sm3", .test = alg_test_hash, diff --git a/crypto/testmgr.h b/crypto/testmgr.h index 48da646651cb..d46720b07fcf 100644 --- a/crypto/testmgr.h +++ b/crypto/testmgr.h @@ -809,6 +809,22 @@ static const struct akcipher_testvec pkcs1pad_rsa_tv_template[] = { } }; +/* + * SM2 test vectors. + */ +static const struct akcipher_testvec sm2_tv_template[] = { + { + .key = + "\xbd\xca\x64\x55\xa5\x5b\x9c\x27\x22\xd0\xf5\x80\xf7\xf3\xc5\x63" + "\x3c\xbf\xce\xe8\x55\x17\xaa\xa5\x7f\x11\x9b\x4b\x25\x56\x9b\x43", + .m = "\x39\xb3\x2c\x59\x82\xc7\xdf\x11\x8a\x64\x2d", + .c = NULL, + .key_len = 32, + .m_size = 11, + .c_size = 0, + } +}; + static const struct kpp_testvec dh_tv_template[] = { { .secret = From patchwork Sun Feb 16 08:59:28 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: "tianjia.zhang" X-Patchwork-Id: 198092 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-7.0 required=3.0 tests=HEADER_FROM_DIFFERENT_DOMAINS, INCLUDES_PATCH, MAILING_LIST_MULTI, SIGNED_OFF_BY, SPF_HELO_NONE, SPF_PASS, UNPARSEABLE_RELAY, UNWANTED_LANGUAGE_BODY, USER_AGENT_GIT autolearn=ham autolearn_force=no version=3.4.0 Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id A206CC76199 for ; Sun, 16 Feb 2020 09:00:11 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by mail.kernel.org (Postfix) with ESMTP id 85489206E2 for ; Sun, 16 Feb 2020 09:00:11 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1726766AbgBPJAK (ORCPT ); Sun, 16 Feb 2020 04:00:10 -0500 Received: from out30-45.freemail.mail.aliyun.com ([115.124.30.45]:54952 "EHLO out30-45.freemail.mail.aliyun.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1726222AbgBPJAK (ORCPT ); Sun, 16 Feb 2020 04:00:10 -0500 X-Alimail-AntiSpam: AC=PASS; BC=-1|-1; BR=01201311R221e4; CH=green; DM=||false|; DS=||; FP=0|-1|-1|-1|0|-1|-1|-1; HT=e01f04455; MF=tianjia.zhang@linux.alibaba.com; NM=1; PH=DS; RN=7; SR=0; TI=SMTPD_---0Tq4XVIu_1581843596; Received: from localhost(mailfrom:tianjia.zhang@linux.alibaba.com fp:SMTPD_---0Tq4XVIu_1581843596) by smtp.aliyun-inc.com(127.0.0.1); Sun, 16 Feb 2020 16:59:57 +0800 From: Tianjia Zhang To: herbert@gondor.apana.org.au, davem@davemloft.net, ebiggers@kernel.org, pvanleeuwen@rambus.com, zohar@linux.ibm.com Cc: linux-crypto@vger.kernel.org, linux-kernel@vger.kernel.org Subject: [PATCH 7/7] X.509: support OSCCA sm2-with-sm3 certificate verification Date: Sun, 16 Feb 2020 16:59:28 +0800 Message-Id: <20200216085928.108838-8-tianjia.zhang@linux.alibaba.com> X-Mailer: git-send-email 2.17.1 In-Reply-To: <20200216085928.108838-1-tianjia.zhang@linux.alibaba.com> References: <20200216085928.108838-1-tianjia.zhang@linux.alibaba.com> Sender: linux-crypto-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: linux-crypto@vger.kernel.org The digital certificate format based on SM2 crypto algorithm as specified in GM/T 0015-2012. It was published by State Encryption Management Bureau, China. The method of generating Other User Information is defined as ZA=H256(ENTLA || IDA || a || b || xG || yG || xA || yA), it also specified in https://tools.ietf.org/html/draft-shen-sm2-ecdsa-02. The x509 certificate supports sm2-with-sm3 type certificate verification. Because certificate verification requires ZA in addition to tbs data, ZA also depends on elliptic curve parameters and public key data, so you need to access tbs in sig and calculate ZA. Finally calculate the digest of the signature and complete the verification work. The calculation process of ZA is declared in specifications GM/T 0009-2012 and GM/T 0003.2-2012. Signed-off-by: Tianjia Zhang --- crypto/asymmetric_keys/public_key.c | 61 ++++++++++++++++++++++++ crypto/asymmetric_keys/x509_public_key.c | 2 + include/crypto/public_key.h | 1 + 3 files changed, 64 insertions(+) diff --git a/crypto/asymmetric_keys/public_key.c b/crypto/asymmetric_keys/public_key.c index d7f43d4ea925..a51b09ee484d 100644 --- a/crypto/asymmetric_keys/public_key.c +++ b/crypto/asymmetric_keys/public_key.c @@ -17,6 +17,11 @@ #include #include #include +#ifdef CONFIG_CRYPTO_SM2 +#include +#include +#include "x509_parser.h" +#endif MODULE_DESCRIPTION("In-software asymmetric public-key subtype"); MODULE_AUTHOR("Red Hat, Inc."); @@ -245,6 +250,54 @@ static int software_key_eds_op(struct kernel_pkey_params *params, return ret; } +#ifdef CONFIG_CRYPTO_SM2 +static int cert_sig_digest_update(const struct public_key_signature *sig, + struct crypto_akcipher *tfm_pkey) +{ + struct x509_certificate *cert = sig->cert; + struct crypto_shash *tfm; + struct shash_desc *desc; + size_t desc_size; + unsigned char dgst[SM3_DIGEST_SIZE]; + int ret; + + if (!cert) + return -EINVAL; + + ret = sm2_compute_z_digest(tfm_pkey, SM2_DEFAULT_USERID, + SM2_DEFAULT_USERID_LEN, dgst); + if (ret) + return ret; + + tfm = crypto_alloc_shash(sig->hash_algo, 0, 0); + if (IS_ERR(tfm)) + return PTR_ERR(tfm); + + desc_size = crypto_shash_descsize(tfm) + sizeof(*desc); + desc = kzalloc(desc_size, GFP_KERNEL); + if (!desc) + goto error_free_tfm; + + desc->tfm = tfm; + + ret = crypto_shash_init(desc); + if (ret < 0) + goto error_free_desc; + + ret = crypto_shash_update(desc, dgst, SM3_DIGEST_SIZE); + if (ret < 0) + goto error_free_desc; + + ret = crypto_shash_finup(desc, cert->tbs, cert->tbs_size, sig->digest); + +error_free_desc: + kfree(desc); +error_free_tfm: + crypto_free_shash(tfm); + return ret; +} +#endif + /* * Verify a signature using a public key. */ @@ -298,6 +351,14 @@ int public_key_verify_signature(const struct public_key *pkey, if (ret) goto error_free_key; +#ifdef CONFIG_CRYPTO_SM2 + if (strcmp(sig->pkey_algo, "sm2") == 0) { + ret = cert_sig_digest_update(sig, tfm); + if (ret) + goto error_free_key; + } +#endif + sg_init_table(src_sg, 2); sg_set_buf(&src_sg[0], sig->s, sig->s_size); sg_set_buf(&src_sg[1], sig->digest, sig->digest_size); diff --git a/crypto/asymmetric_keys/x509_public_key.c b/crypto/asymmetric_keys/x509_public_key.c index d964cc82b69c..feccec08b244 100644 --- a/crypto/asymmetric_keys/x509_public_key.c +++ b/crypto/asymmetric_keys/x509_public_key.c @@ -30,6 +30,8 @@ int x509_get_sig_params(struct x509_certificate *cert) pr_devel("==>%s()\n", __func__); + sig->cert = cert; + if (!cert->pub->pkey_algo) cert->unsupported_key = true; diff --git a/include/crypto/public_key.h b/include/crypto/public_key.h index 0588ef3bc6ff..27775e617e38 100644 --- a/include/crypto/public_key.h +++ b/include/crypto/public_key.h @@ -44,6 +44,7 @@ struct public_key_signature { const char *pkey_algo; const char *hash_algo; const char *encoding; + void *cert; /* For certificate */ }; extern void public_key_signature_free(struct public_key_signature *sig);