From nobody Wed Oct 8 09:26:48 2025 Received: from szxga07-in.huawei.com (szxga07-in.huawei.com [45.249.212.35]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 80BC528B50E; Mon, 30 Jun 2025 13:27:39 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=45.249.212.35 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1751290063; cv=none; b=pHO5PcLN0XBgtrw4/mWHDT6EGYRSW8nqGX1+Tcgs+gyLto4whJz9/iHBtUulbw90qjZsL+sKmBIDRebHvyP0NqMikpOOQBABt6pGy2TW28+7uduhdBI5d8yBLqeqD2VeCSBjWNwKN35LyMQyGS9ED4ZLp9paJL+nPgYLqZnpnDk= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1751290063; c=relaxed/simple; bh=pgorgsgSpE7KOSwKVYLzqGKY42pc5SdHvbGwtU2jDcM=; h=From:To:CC:Subject:Date:Message-ID:In-Reply-To:References: MIME-Version:Content-Type; b=H0kvm8mjZ4ZG4baR3jw+dsG3Sm9o9VzCR4S+OJxVYLoUDeevV4zpzOGqC1Tts8TkLXVGWArE2imOBRC+EnNvUtAfAEye3uM2FsYq3LeF/1cRJnT7eNI+V3nqK73H3139e8QfCfIrCtBva/OEJkXPY0FTA7+c6Yrt3nBdICQUFy8= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=quarantine dis=none) header.from=huawei.com; spf=pass smtp.mailfrom=huawei.com; arc=none smtp.client-ip=45.249.212.35 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=quarantine dis=none) header.from=huawei.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=huawei.com Received: from mail.maildlp.com (unknown [172.19.162.112]) by szxga07-in.huawei.com (SkyGuard) with ESMTP id 4bW6Np1142z29dy6; Mon, 30 Jun 2025 21:25:46 +0800 (CST) Received: from kwepemh100007.china.huawei.com (unknown [7.202.181.92]) by mail.maildlp.com (Postfix) with ESMTPS id AF20514027A; Mon, 30 Jun 2025 21:27:30 +0800 (CST) Received: from huawei.com (10.67.174.33) by kwepemh100007.china.huawei.com (7.202.181.92) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.2.1544.11; Mon, 30 Jun 2025 21:27:29 +0800 From: Gu Bowen To: Herbert Xu , David Howells , David Woodhouse , Lukas Wunner , Ignat Korchagin , "David S . Miller" , Jarkko Sakkinen , Maxime Coquelin , Alexandre Torgue , Eric Biggers , "Jason A . Donenfeld" , Ard Biesheuvel , Tianjia Zhang , Dan Carpenter CC: , , , , , Lu Jialin , GONG Ruiqi , Gu Bowen Subject: [PATCH RFC 1/4] Revert "Revert "lib/mpi: Extend the MPI library"" Date: Mon, 30 Jun 2025 21:39:31 +0800 Message-ID: <20250630133934.766646-2-gubowen5@huawei.com> X-Mailer: git-send-email 2.25.1 In-Reply-To: <20250630133934.766646-1-gubowen5@huawei.com> References: <20250630133934.766646-1-gubowen5@huawei.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable X-ClientProxiedBy: kwepems500001.china.huawei.com (7.221.188.70) To kwepemh100007.china.huawei.com (7.202.181.92) Content-Type: text/plain; charset="utf-8" This reverts commit fca5cb4dd2b4a9423cb6d112cc71c33899955a1f. Reintroduce the mpi library based on libgcrypt to support sm2. Signed-off-by: Gu Bowen --- include/linux/mpi.h | 65 +++++++ lib/crypto/mpi/Makefile | 1 + lib/crypto/mpi/mpi-add.c | 50 +++++ lib/crypto/mpi/mpi-bit.c | 143 +++++++++++++++ lib/crypto/mpi/mpi-cmp.c | 46 ++++- lib/crypto/mpi/mpi-div.c | 29 +++ lib/crypto/mpi/mpi-internal.h | 10 + lib/crypto/mpi/mpi-inv.c | 143 +++++++++++++++ lib/crypto/mpi/mpi-mod.c | 144 +++++++++++++++ lib/crypto/mpi/mpicoder.c | 336 ++++++++++++++++++++++++++++++++++ lib/crypto/mpi/mpih-mul.c | 25 +++ lib/crypto/mpi/mpiutil.c | 182 ++++++++++++++++++ 12 files changed, 1164 insertions(+), 10 deletions(-) create mode 100644 lib/crypto/mpi/mpi-inv.c diff --git a/include/linux/mpi.h b/include/linux/mpi.h index 47be46f36435..9ad7e7231ee9 100644 --- a/include/linux/mpi.h +++ b/include/linux/mpi.h @@ -40,33 +40,87 @@ struct gcry_mpi { typedef struct gcry_mpi *MPI; =20 #define mpi_get_nlimbs(a) ((a)->nlimbs) +#define mpi_has_sign(a) ((a)->sign) =20 /*-- mpiutil.c --*/ MPI mpi_alloc(unsigned nlimbs); +void mpi_clear(MPI a); void mpi_free(MPI a); int mpi_resize(MPI a, unsigned nlimbs); =20 +static inline MPI mpi_new(unsigned int nbits) +{ + return mpi_alloc((nbits + BITS_PER_MPI_LIMB - 1) / BITS_PER_MPI_LIMB); +} + MPI mpi_copy(MPI a); +MPI mpi_alloc_like(MPI a); +void mpi_snatch(MPI w, MPI u); +MPI mpi_set(MPI w, MPI u); +MPI mpi_set_ui(MPI w, unsigned long u); +MPI mpi_alloc_set_ui(unsigned long u); +void mpi_swap_cond(MPI a, MPI b, unsigned long swap); + +/* Constants used to return constant MPIs. See mpi_init if you + * want to add more constants. + */ +#define MPI_NUMBER_OF_CONSTANTS 6 +enum gcry_mpi_constants { + MPI_C_ZERO, + MPI_C_ONE, + MPI_C_TWO, + MPI_C_THREE, + MPI_C_FOUR, + MPI_C_EIGHT +}; + +MPI mpi_const(enum gcry_mpi_constants no); =20 /*-- mpicoder.c --*/ + +/* Different formats of external big integer representation. */ +enum gcry_mpi_format { + GCRYMPI_FMT_NONE =3D 0, + GCRYMPI_FMT_STD =3D 1, /* Twos complement stored without length. */ + GCRYMPI_FMT_PGP =3D 2, /* As used by OpenPGP (unsigned only). */ + GCRYMPI_FMT_SSH =3D 3, /* As used by SSH (like STD but with length). */ + GCRYMPI_FMT_HEX =3D 4, /* Hex format. */ + GCRYMPI_FMT_USG =3D 5, /* Like STD but unsigned. */ + GCRYMPI_FMT_OPAQUE =3D 8 /* Opaque format (some functions only). */ +}; + MPI mpi_read_raw_data(const void *xbuffer, size_t nbytes); MPI mpi_read_from_buffer(const void *buffer, unsigned *ret_nread); +int mpi_fromstr(MPI val, const char *str); +MPI mpi_scanval(const char *string); MPI mpi_read_raw_from_sgl(struct scatterlist *sgl, unsigned int len); void *mpi_get_buffer(MPI a, unsigned *nbytes, int *sign); int mpi_read_buffer(MPI a, uint8_t *buf, unsigned buf_len, unsigned *nbyte= s, int *sign); int mpi_write_to_sgl(MPI a, struct scatterlist *sg, unsigned nbytes, int *sign); +int mpi_print(enum gcry_mpi_format format, unsigned char *buffer, + size_t buflen, size_t *nwritten, MPI a); =20 /*-- mpi-mod.c --*/ int mpi_mod(MPI rem, MPI dividend, MPI divisor); =20 +/* Context used with Barrett reduction. */ +struct barrett_ctx_s; +typedef struct barrett_ctx_s *mpi_barrett_t; + +mpi_barrett_t mpi_barrett_init(MPI m, int copy); +void mpi_barrett_free(mpi_barrett_t ctx); +void mpi_mod_barrett(MPI r, MPI x, mpi_barrett_t ctx); +void mpi_mul_barrett(MPI w, MPI u, MPI v, mpi_barrett_t ctx); + /*-- mpi-pow.c --*/ int mpi_powm(MPI res, MPI base, MPI exp, MPI mod); =20 /*-- mpi-cmp.c --*/ int mpi_cmp_ui(MPI u, ulong v); int mpi_cmp(MPI u, MPI v); +int mpi_cmpabs(MPI u, MPI v); =20 /*-- mpi-sub-ui.c --*/ int mpi_sub_ui(MPI w, MPI u, unsigned long vval); @@ -76,9 +130,16 @@ void mpi_normalize(MPI a); unsigned mpi_get_nbits(MPI a); int mpi_test_bit(MPI a, unsigned int n); int mpi_set_bit(MPI a, unsigned int n); +void mpi_set_highbit(MPI a, unsigned int n); +void mpi_clear_highbit(MPI a, unsigned int n); +void mpi_clear_bit(MPI a, unsigned int n); +void mpi_rshift_limbs(MPI a, unsigned int count); int mpi_rshift(MPI x, MPI a, unsigned int n); +void mpi_lshift_limbs(MPI a, unsigned int count); +void mpi_lshift(MPI x, MPI a, unsigned int n); =20 /*-- mpi-add.c --*/ +void mpi_add_ui(MPI w, MPI u, unsigned long v); int mpi_add(MPI w, MPI u, MPI v); int mpi_sub(MPI w, MPI u, MPI v); int mpi_addm(MPI w, MPI u, MPI v, MPI m); @@ -91,6 +152,10 @@ int mpi_mulm(MPI w, MPI u, MPI v, MPI m); /*-- mpi-div.c --*/ int mpi_tdiv_r(MPI rem, MPI num, MPI den); int mpi_fdiv_r(MPI rem, MPI dividend, MPI divisor); +void mpi_fdiv_q(MPI quot, MPI dividend, MPI divisor); + +/*-- mpi-inv.c --*/ +int mpi_invm(MPI x, MPI a, MPI n); =20 /* inline functions */ =20 diff --git a/lib/crypto/mpi/Makefile b/lib/crypto/mpi/Makefile index 9ad84079025a..477debd7ed50 100644 --- a/lib/crypto/mpi/Makefile +++ b/lib/crypto/mpi/Makefile @@ -19,6 +19,7 @@ mpi-y =3D \ mpi-cmp.o \ mpi-sub-ui.o \ mpi-div.o \ + mpi-inv.o \ mpi-mod.o \ mpi-mul.o \ mpih-cmp.o \ diff --git a/lib/crypto/mpi/mpi-add.c b/lib/crypto/mpi/mpi-add.c index 3015140d4860..020371891991 100644 --- a/lib/crypto/mpi/mpi-add.c +++ b/lib/crypto/mpi/mpi-add.c @@ -13,6 +13,56 @@ =20 #include "mpi-internal.h" =20 +/**************** + * Add the unsigned integer V to the mpi-integer U and store the + * result in W. U and V may be the same. + */ +void mpi_add_ui(MPI w, MPI u, unsigned long v) +{ + mpi_ptr_t wp, up; + mpi_size_t usize, wsize; + int usign, wsign; + + usize =3D u->nlimbs; + usign =3D u->sign; + wsign =3D 0; + + /* If not space for W (and possible carry), increase space. */ + wsize =3D usize + 1; + if (w->alloced < wsize) + mpi_resize(w, wsize); + + /* These must be after realloc (U may be the same as W). */ + up =3D u->d; + wp =3D w->d; + + if (!usize) { /* simple */ + wp[0] =3D v; + wsize =3D v ? 1:0; + } else if (!usign) { /* mpi is not negative */ + mpi_limb_t cy; + cy =3D mpihelp_add_1(wp, up, usize, v); + wp[usize] =3D cy; + wsize =3D usize + cy; + } else { + /* The signs are different. Need exact comparison to determine + * which operand to subtract from which. + */ + if (usize =3D=3D 1 && up[0] < v) { + wp[0] =3D v - up[0]; + wsize =3D 1; + } else { + mpihelp_sub_1(wp, up, usize, v); + /* Size can decrease with at most one limb. */ + wsize =3D usize - (wp[usize-1] =3D=3D 0); + wsign =3D 1; + } + } + + w->nlimbs =3D wsize; + w->sign =3D wsign; +} + int mpi_add(MPI w, MPI u, MPI v) { mpi_ptr_t wp, up, vp; diff --git a/lib/crypto/mpi/mpi-bit.c b/lib/crypto/mpi/mpi-bit.c index 934d81311360..4790d5b8a216 100644 --- a/lib/crypto/mpi/mpi-bit.c +++ b/lib/crypto/mpi/mpi-bit.c @@ -32,6 +32,7 @@ void mpi_normalize(MPI a) for (; a->nlimbs && !a->d[a->nlimbs - 1]; a->nlimbs--) ; } +EXPORT_SYMBOL_GPL(mpi_normalize); =20 /**************** * Return the number of bits in A. @@ -97,6 +98,85 @@ int mpi_set_bit(MPI a, unsigned int n) } EXPORT_SYMBOL_GPL(mpi_set_bit); =20 +/**************** + * Set bit N of A. and clear all bits above + */ +void mpi_set_highbit(MPI a, unsigned int n) +{ + unsigned int i, limbno, bitno; + + limbno =3D n / BITS_PER_MPI_LIMB; + bitno =3D n % BITS_PER_MPI_LIMB; + + if (limbno >=3D a->nlimbs) { + for (i =3D a->nlimbs; i < a->alloced; i++) + a->d[i] =3D 0; + mpi_resize(a, limbno+1); + a->nlimbs =3D limbno+1; + } + a->d[limbno] |=3D (A_LIMB_1<d[limbno] &=3D ~(A_LIMB_1 << bitno); + a->nlimbs =3D limbno+1; +} +EXPORT_SYMBOL_GPL(mpi_set_highbit); + +/**************** + * clear bit N of A and all bits above + */ +void mpi_clear_highbit(MPI a, unsigned int n) +{ + unsigned int limbno, bitno; + + limbno =3D n / BITS_PER_MPI_LIMB; + bitno =3D n % BITS_PER_MPI_LIMB; + + if (limbno >=3D a->nlimbs) + return; /* not allocated, therefore no need to clear bits :-) */ + + for ( ; bitno < BITS_PER_MPI_LIMB; bitno++) + a->d[limbno] &=3D ~(A_LIMB_1 << bitno); + a->nlimbs =3D limbno+1; +} + +/**************** + * Clear bit N of A. + */ +void mpi_clear_bit(MPI a, unsigned int n) +{ + unsigned int limbno, bitno; + + limbno =3D n / BITS_PER_MPI_LIMB; + bitno =3D n % BITS_PER_MPI_LIMB; + + if (limbno >=3D a->nlimbs) + return; /* Don't need to clear this bit, it's far too left. */ + a->d[limbno] &=3D ~(A_LIMB_1 << bitno); +} +EXPORT_SYMBOL_GPL(mpi_clear_bit); + + +/**************** + * Shift A by COUNT limbs to the right + * This is used only within the MPI library + */ +void mpi_rshift_limbs(MPI a, unsigned int count) +{ + mpi_ptr_t ap =3D a->d; + mpi_size_t n =3D a->nlimbs; + unsigned int i; + + if (count >=3D n) { + a->nlimbs =3D 0; + return; + } + + for (i =3D 0; i < n - count; i++) + ap[i] =3D ap[i+count]; + ap[i] =3D 0; + a->nlimbs -=3D count; +} + /* * Shift A by N bits to the right. */ @@ -173,3 +253,66 @@ int mpi_rshift(MPI x, MPI a, unsigned int n) return 0; } EXPORT_SYMBOL_GPL(mpi_rshift); + +/**************** + * Shift A by COUNT limbs to the left + * This is used only within the MPI library + */ +void mpi_lshift_limbs(MPI a, unsigned int count) +{ + mpi_ptr_t ap; + int n =3D a->nlimbs; + int i; + + if (!count || !n) + return; + + RESIZE_IF_NEEDED(a, n+count); + + ap =3D a->d; + for (i =3D n-1; i >=3D 0; i--) + ap[i+count] =3D ap[i]; + for (i =3D 0; i < count; i++) + ap[i] =3D 0; + a->nlimbs +=3D count; +} + +/* + * Shift A by N bits to the left. + */ +void mpi_lshift(MPI x, MPI a, unsigned int n) +{ + unsigned int nlimbs =3D (n/BITS_PER_MPI_LIMB); + unsigned int nbits =3D (n%BITS_PER_MPI_LIMB); + + if (x =3D=3D a && !n) + return; /* In-place shift with an amount of zero. */ + + if (x !=3D a) { + /* Copy A to X. */ + unsigned int alimbs =3D a->nlimbs; + int asign =3D a->sign; + mpi_ptr_t xp, ap; + + RESIZE_IF_NEEDED(x, alimbs+nlimbs+1); + xp =3D x->d; + ap =3D a->d; + MPN_COPY(xp, ap, alimbs); + x->nlimbs =3D alimbs; + x->flags =3D a->flags; + x->sign =3D asign; + } + + if (nlimbs && !nbits) { + /* Shift a full number of limbs. */ + mpi_lshift_limbs(x, nlimbs); + } else if (n) { + /* We use a very dump approach: Shift left by the number of + * limbs plus one and than fix it up by an rshift. + */ + mpi_lshift_limbs(x, nlimbs+1); + mpi_rshift(x, x, BITS_PER_MPI_LIMB - nbits); + } + + MPN_NORMALIZE(x->d, x->nlimbs); +} diff --git a/lib/crypto/mpi/mpi-cmp.c b/lib/crypto/mpi/mpi-cmp.c index ceaebe181cd7..0835b6213235 100644 --- a/lib/crypto/mpi/mpi-cmp.c +++ b/lib/crypto/mpi/mpi-cmp.c @@ -45,28 +45,54 @@ int mpi_cmp_ui(MPI u, unsigned long v) } EXPORT_SYMBOL_GPL(mpi_cmp_ui); =20 -int mpi_cmp(MPI u, MPI v) +static int do_mpi_cmp(MPI u, MPI v, int absmode) { - mpi_size_t usize, vsize; + mpi_size_t usize; + mpi_size_t vsize; + int usign; + int vsign; int cmp; =20 mpi_normalize(u); mpi_normalize(v); + usize =3D u->nlimbs; vsize =3D v->nlimbs; - if (!u->sign && v->sign) + usign =3D absmode ? 0 : u->sign; + vsign =3D absmode ? 0 : v->sign; + + /* Compare sign bits. */ + + if (!usign && vsign) return 1; - if (u->sign && !v->sign) + if (usign && !vsign) return -1; - if (usize !=3D vsize && !u->sign && !v->sign) + + /* U and V are either both positive or both negative. */ + + if (usize !=3D vsize && !usign && !vsign) return usize - vsize; - if (usize !=3D vsize && u->sign && v->sign) - return vsize - usize; + if (usize !=3D vsize && usign && vsign) + return vsize + usize; if (!usize) return 0; cmp =3D mpihelp_cmp(u->d, v->d, usize); - if (u->sign) - return -cmp; - return cmp; + if (!cmp) + return 0; + if ((cmp < 0?1:0) =3D=3D (usign?1:0)) + return 1; + + return -1; +} + +int mpi_cmp(MPI u, MPI v) +{ + return do_mpi_cmp(u, v, 0); } EXPORT_SYMBOL_GPL(mpi_cmp); + +int mpi_cmpabs(MPI u, MPI v) +{ + return do_mpi_cmp(u, v, 1); +} +EXPORT_SYMBOL_GPL(mpi_cmpabs); diff --git a/lib/crypto/mpi/mpi-div.c b/lib/crypto/mpi/mpi-div.c index 6e5044e72595..05a67d43ebc2 100644 --- a/lib/crypto/mpi/mpi-div.c +++ b/lib/crypto/mpi/mpi-div.c @@ -15,6 +15,7 @@ #include "longlong.h" =20 int mpi_tdiv_qr(MPI quot, MPI rem, MPI num, MPI den); +void mpi_fdiv_qr(MPI quot, MPI rem, MPI dividend, MPI divisor); =20 int mpi_fdiv_r(MPI rem, MPI dividend, MPI divisor) { @@ -46,6 +47,34 @@ int mpi_fdiv_r(MPI rem, MPI dividend, MPI divisor) return err; } =20 +void mpi_fdiv_q(MPI quot, MPI dividend, MPI divisor) +{ + MPI tmp =3D mpi_alloc(mpi_get_nlimbs(quot)); + mpi_fdiv_qr(quot, tmp, dividend, divisor); + mpi_free(tmp); +} + +void mpi_fdiv_qr(MPI quot, MPI rem, MPI dividend, MPI divisor) +{ + int divisor_sign =3D divisor->sign; + MPI temp_divisor =3D NULL; + + if (quot =3D=3D divisor || rem =3D=3D divisor) { + temp_divisor =3D mpi_copy(divisor); + divisor =3D temp_divisor; + } + + mpi_tdiv_qr(quot, rem, dividend, divisor); + + if ((divisor_sign ^ dividend->sign) && rem->nlimbs) { + mpi_sub_ui(quot, quot, 1); + mpi_add(rem, rem, divisor); + } + + if (temp_divisor) + mpi_free(temp_divisor); +} + /* If den =3D=3D quot, den needs temporary storage. * If den =3D=3D rem, den needs temporary storage. * If num =3D=3D quot, num needs temporary storage. diff --git a/lib/crypto/mpi/mpi-internal.h b/lib/crypto/mpi/mpi-internal.h index 8a4f49e3043c..e6cf87659e29 100644 --- a/lib/crypto/mpi/mpi-internal.h +++ b/lib/crypto/mpi/mpi-internal.h @@ -67,6 +67,14 @@ static inline int RESIZE_IF_NEEDED(MPI a, unsigned b) (d)[_i] =3D (s)[_i]; \ } while (0) =20 +#define MPN_COPY_INCR(d, s, n) \ + do { \ + mpi_size_t _i; \ + for (_i =3D 0; _i < (n); _i++) \ + (d)[_i] =3D (s)[_i]; \ + } while (0) + + #define MPN_COPY_DECR(d, s, n) \ do { \ mpi_size_t _i; \ @@ -174,6 +182,8 @@ int mpihelp_mul(mpi_ptr_t prodp, mpi_ptr_t up, mpi_size= _t usize, void mpih_sqr_n_basecase(mpi_ptr_t prodp, mpi_ptr_t up, mpi_size_t size); void mpih_sqr_n(mpi_ptr_t prodp, mpi_ptr_t up, mpi_size_t size, mpi_ptr_t tspace); +void mpihelp_mul_n(mpi_ptr_t prodp, + mpi_ptr_t up, mpi_ptr_t vp, mpi_size_t size); =20 int mpihelp_mul_karatsuba_case(mpi_ptr_t prodp, mpi_ptr_t up, mpi_size_t usize, diff --git a/lib/crypto/mpi/mpi-inv.c b/lib/crypto/mpi/mpi-inv.c new file mode 100644 index 000000000000..61e37d18f793 --- /dev/null +++ b/lib/crypto/mpi/mpi-inv.c @@ -0,0 +1,143 @@ +/* mpi-inv.c - MPI functions + * Copyright (C) 1998, 2001, 2002, 2003 Free Software Foundation, Inc. + * + * 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" + +/**************** + * Calculate the multiplicative inverse X of A mod N + * That is: Find the solution x for + * 1 =3D (a*x) mod n + */ +int mpi_invm(MPI x, MPI a, MPI n) +{ + /* Extended Euclid's algorithm (See TAOCP Vol II, 4.5.2, Alg X) + * modified according to Michael Penk's solution for Exercise 35 + * with further enhancement + */ + MPI u, v, u1, u2 =3D NULL, u3, v1, v2 =3D NULL, v3, t1, t2 =3D NULL, t3; + unsigned int k; + int sign; + int odd; + + if (!mpi_cmp_ui(a, 0)) + return 0; /* Inverse does not exists. */ + if (!mpi_cmp_ui(n, 1)) + return 0; /* Inverse does not exists. */ + + u =3D mpi_copy(a); + v =3D mpi_copy(n); + + for (k =3D 0; !mpi_test_bit(u, 0) && !mpi_test_bit(v, 0); k++) { + mpi_rshift(u, u, 1); + mpi_rshift(v, v, 1); + } + odd =3D mpi_test_bit(v, 0); + + u1 =3D mpi_alloc_set_ui(1); + if (!odd) + u2 =3D mpi_alloc_set_ui(0); + u3 =3D mpi_copy(u); + v1 =3D mpi_copy(v); + if (!odd) { + v2 =3D mpi_alloc(mpi_get_nlimbs(u)); + mpi_sub(v2, u1, u); /* U is used as const 1 */ + } + v3 =3D mpi_copy(v); + if (mpi_test_bit(u, 0)) { /* u is odd */ + t1 =3D mpi_alloc_set_ui(0); + if (!odd) { + t2 =3D mpi_alloc_set_ui(1); + t2->sign =3D 1; + } + t3 =3D mpi_copy(v); + t3->sign =3D !t3->sign; + goto Y4; + } else { + t1 =3D mpi_alloc_set_ui(1); + if (!odd) + t2 =3D mpi_alloc_set_ui(0); + t3 =3D mpi_copy(u); + } + + do { + do { + if (!odd) { + if (mpi_test_bit(t1, 0) || mpi_test_bit(t2, 0)) { + /* one is odd */ + mpi_add(t1, t1, v); + mpi_sub(t2, t2, u); + } + mpi_rshift(t1, t1, 1); + mpi_rshift(t2, t2, 1); + mpi_rshift(t3, t3, 1); + } else { + if (mpi_test_bit(t1, 0)) + mpi_add(t1, t1, v); + mpi_rshift(t1, t1, 1); + mpi_rshift(t3, t3, 1); + } +Y4: + ; + } while (!mpi_test_bit(t3, 0)); /* while t3 is even */ + + if (!t3->sign) { + mpi_set(u1, t1); + if (!odd) + mpi_set(u2, t2); + mpi_set(u3, t3); + } else { + mpi_sub(v1, v, t1); + sign =3D u->sign; u->sign =3D !u->sign; + if (!odd) + mpi_sub(v2, u, t2); + u->sign =3D sign; + sign =3D t3->sign; t3->sign =3D !t3->sign; + mpi_set(v3, t3); + t3->sign =3D sign; + } + mpi_sub(t1, u1, v1); + if (!odd) + mpi_sub(t2, u2, v2); + mpi_sub(t3, u3, v3); + if (t1->sign) { + mpi_add(t1, t1, v); + if (!odd) + mpi_sub(t2, t2, u); + } + } while (mpi_cmp_ui(t3, 0)); /* while t3 !=3D 0 */ + /* mpi_lshift( u3, k ); */ + mpi_set(x, u1); + + mpi_free(u1); + mpi_free(v1); + mpi_free(t1); + if (!odd) { + mpi_free(u2); + mpi_free(v2); + mpi_free(t2); + } + mpi_free(u3); + mpi_free(v3); + mpi_free(t3); + + mpi_free(u); + mpi_free(v); + return 1; +} +EXPORT_SYMBOL_GPL(mpi_invm); diff --git a/lib/crypto/mpi/mpi-mod.c b/lib/crypto/mpi/mpi-mod.c index d5fdaec3d0b6..5a6475f58fa7 100644 --- a/lib/crypto/mpi/mpi-mod.c +++ b/lib/crypto/mpi/mpi-mod.c @@ -5,9 +5,153 @@ * This file is part of Libgcrypt. */ =20 + #include "mpi-internal.h" +#include "longlong.h" + +/* Context used with Barrett reduction. */ +struct barrett_ctx_s { + MPI m; /* The modulus - may not be modified. */ + int m_copied; /* If true, M needs to be released. */ + int k; + MPI y; + MPI r1; /* Helper MPI. */ + MPI r2; /* Helper MPI. */ + MPI r3; /* Helper MPI allocated on demand. */ +}; + + =20 int mpi_mod(MPI rem, MPI dividend, MPI divisor) { return mpi_fdiv_r(rem, dividend, divisor); } + +/* This function returns a new context for Barrett based operations on + * the modulus M. This context needs to be released using + * _gcry_mpi_barrett_free. If COPY is true M will be transferred to + * the context and the user may change M. If COPY is false, M may not + * be changed until gcry_mpi_barrett_free has been called. + */ +mpi_barrett_t mpi_barrett_init(MPI m, int copy) +{ + mpi_barrett_t ctx; + MPI tmp; + + mpi_normalize(m); + ctx =3D kcalloc(1, sizeof(*ctx), GFP_KERNEL); + if (!ctx) + return NULL; + + if (copy) { + ctx->m =3D mpi_copy(m); + ctx->m_copied =3D 1; + } else + ctx->m =3D m; + + ctx->k =3D mpi_get_nlimbs(m); + tmp =3D mpi_alloc(ctx->k + 1); + + /* Barrett precalculation: y =3D floor(b^(2k) / m). */ + mpi_set_ui(tmp, 1); + mpi_lshift_limbs(tmp, 2 * ctx->k); + mpi_fdiv_q(tmp, tmp, m); + + ctx->y =3D tmp; + ctx->r1 =3D mpi_alloc(2 * ctx->k + 1); + ctx->r2 =3D mpi_alloc(2 * ctx->k + 1); + + return ctx; +} + +void mpi_barrett_free(mpi_barrett_t ctx) +{ + if (ctx) { + mpi_free(ctx->y); + mpi_free(ctx->r1); + mpi_free(ctx->r2); + if (ctx->r3) + mpi_free(ctx->r3); + if (ctx->m_copied) + mpi_free(ctx->m); + kfree(ctx); + } +} + + +/* R =3D X mod M + * + * Using Barrett reduction. Before using this function + * _gcry_mpi_barrett_init must have been called to do the + * precalculations. CTX is the context created by this precalculation + * and also conveys M. If the Barret reduction could no be done a + * straightforward reduction method is used. + * + * We assume that these conditions are met: + * Input: x =3D(x_2k-1 ...x_0)_b + * m =3D(m_k-1 ....m_0)_b with m_k-1 !=3D 0 + * Output: r =3D x mod m + */ +void mpi_mod_barrett(MPI r, MPI x, mpi_barrett_t ctx) +{ + MPI m =3D ctx->m; + int k =3D ctx->k; + MPI y =3D ctx->y; + MPI r1 =3D ctx->r1; + MPI r2 =3D ctx->r2; + int sign; + + mpi_normalize(x); + if (mpi_get_nlimbs(x) > 2*k) { + mpi_mod(r, x, m); + return; + } + + sign =3D x->sign; + x->sign =3D 0; + + /* 1. q1 =3D floor( x / b^k-1) + * q2 =3D q1 * y + * q3 =3D floor( q2 / b^k+1 ) + * Actually, we don't need qx, we can work direct on r2 + */ + mpi_set(r2, x); + mpi_rshift_limbs(r2, k-1); + mpi_mul(r2, r2, y); + mpi_rshift_limbs(r2, k+1); + + /* 2. r1 =3D x mod b^k+1 + * r2 =3D q3 * m mod b^k+1 + * r =3D r1 - r2 + * 3. if r < 0 then r =3D r + b^k+1 + */ + mpi_set(r1, x); + if (r1->nlimbs > k+1) /* Quick modulo operation. */ + r1->nlimbs =3D k+1; + mpi_mul(r2, r2, m); + if (r2->nlimbs > k+1) /* Quick modulo operation. */ + r2->nlimbs =3D k+1; + mpi_sub(r, r1, r2); + + if (mpi_has_sign(r)) { + if (!ctx->r3) { + ctx->r3 =3D mpi_alloc(k + 2); + mpi_set_ui(ctx->r3, 1); + mpi_lshift_limbs(ctx->r3, k + 1); + } + mpi_add(r, r, ctx->r3); + } + + /* 4. while r >=3D m do r =3D r - m */ + while (mpi_cmp(r, m) >=3D 0) + mpi_sub(r, r, m); + + x->sign =3D sign; +} + + +void mpi_mul_barrett(MPI w, MPI u, MPI v, mpi_barrett_t ctx) +{ + mpi_mul(w, u, v); + mpi_mod_barrett(w, w, ctx); +} diff --git a/lib/crypto/mpi/mpicoder.c b/lib/crypto/mpi/mpicoder.c index dde01030807d..3cb6bd148fa9 100644 --- a/lib/crypto/mpi/mpicoder.c +++ b/lib/crypto/mpi/mpicoder.c @@ -25,6 +25,7 @@ #include #include "mpi-internal.h" =20 +#define MAX_EXTERN_SCAN_BYTES (16*1024*1024) #define MAX_EXTERN_MPI_BITS 16384 =20 /** @@ -109,6 +110,112 @@ MPI mpi_read_from_buffer(const void *xbuffer, unsigne= d *ret_nread) } EXPORT_SYMBOL_GPL(mpi_read_from_buffer); =20 +/**************** + * Fill the mpi VAL from the hex string in STR. + */ +int mpi_fromstr(MPI val, const char *str) +{ + int sign =3D 0; + int prepend_zero =3D 0; + int i, j, c, c1, c2; + unsigned int nbits, nbytes, nlimbs; + mpi_limb_t a; + + if (*str =3D=3D '-') { + sign =3D 1; + str++; + } + + /* Skip optional hex prefix. */ + if (*str =3D=3D '0' && str[1] =3D=3D 'x') + str +=3D 2; + + nbits =3D strlen(str); + if (nbits > MAX_EXTERN_SCAN_BYTES) { + mpi_clear(val); + return -EINVAL; + } + nbits *=3D 4; + if ((nbits % 8)) + prepend_zero =3D 1; + + nbytes =3D (nbits+7) / 8; + nlimbs =3D (nbytes+BYTES_PER_MPI_LIMB-1) / BYTES_PER_MPI_LIMB; + + if (val->alloced < nlimbs) + mpi_resize(val, nlimbs); + + i =3D BYTES_PER_MPI_LIMB - (nbytes % BYTES_PER_MPI_LIMB); + i %=3D BYTES_PER_MPI_LIMB; + j =3D val->nlimbs =3D nlimbs; + val->sign =3D sign; + for (; j > 0; j--) { + a =3D 0; + for (; i < BYTES_PER_MPI_LIMB; i++) { + if (prepend_zero) { + c1 =3D '0'; + prepend_zero =3D 0; + } else + c1 =3D *str++; + + if (!c1) { + mpi_clear(val); + return -EINVAL; + } + c2 =3D *str++; + if (!c2) { + mpi_clear(val); + return -EINVAL; + } + if (c1 >=3D '0' && c1 <=3D '9') + c =3D c1 - '0'; + else if (c1 >=3D 'a' && c1 <=3D 'f') + c =3D c1 - 'a' + 10; + else if (c1 >=3D 'A' && c1 <=3D 'F') + c =3D c1 - 'A' + 10; + else { + mpi_clear(val); + return -EINVAL; + } + c <<=3D 4; + if (c2 >=3D '0' && c2 <=3D '9') + c |=3D c2 - '0'; + else if (c2 >=3D 'a' && c2 <=3D 'f') + c |=3D c2 - 'a' + 10; + else if (c2 >=3D 'A' && c2 <=3D 'F') + c |=3D c2 - 'A' + 10; + else { + mpi_clear(val); + return -EINVAL; + } + a <<=3D 8; + a |=3D c; + } + i =3D 0; + val->d[j-1] =3D a; + } + + return 0; +} +EXPORT_SYMBOL_GPL(mpi_fromstr); + +MPI mpi_scanval(const char *string) +{ + MPI a; + + a =3D mpi_alloc(0); + if (!a) + return NULL; + + if (mpi_fromstr(a, string)) { + mpi_free(a); + return NULL; + } + mpi_normalize(a); + return a; +} +EXPORT_SYMBOL_GPL(mpi_scanval); + static int count_lzeros(MPI a) { mpi_limb_t alimb; @@ -414,3 +521,232 @@ MPI mpi_read_raw_from_sgl(struct scatterlist *sgl, un= signed int nbytes) return val; } EXPORT_SYMBOL_GPL(mpi_read_raw_from_sgl); + +/* Perform a two's complement operation on buffer P of size N bytes. */ +static void twocompl(unsigned char *p, unsigned int n) +{ + int i; + + for (i =3D n-1; i >=3D 0 && !p[i]; i--) + ; + if (i >=3D 0) { + if ((p[i] & 0x01)) + p[i] =3D (((p[i] ^ 0xfe) | 0x01) & 0xff); + else if ((p[i] & 0x02)) + p[i] =3D (((p[i] ^ 0xfc) | 0x02) & 0xfe); + else if ((p[i] & 0x04)) + p[i] =3D (((p[i] ^ 0xf8) | 0x04) & 0xfc); + else if ((p[i] & 0x08)) + p[i] =3D (((p[i] ^ 0xf0) | 0x08) & 0xf8); + else if ((p[i] & 0x10)) + p[i] =3D (((p[i] ^ 0xe0) | 0x10) & 0xf0); + else if ((p[i] & 0x20)) + p[i] =3D (((p[i] ^ 0xc0) | 0x20) & 0xe0); + else if ((p[i] & 0x40)) + p[i] =3D (((p[i] ^ 0x80) | 0x40) & 0xc0); + else + p[i] =3D 0x80; + + for (i--; i >=3D 0; i--) + p[i] ^=3D 0xff; + } +} + +int mpi_print(enum gcry_mpi_format format, unsigned char *buffer, + size_t buflen, size_t *nwritten, MPI a) +{ + unsigned int nbits =3D mpi_get_nbits(a); + size_t len; + size_t dummy_nwritten; + int negative; + + if (!nwritten) + nwritten =3D &dummy_nwritten; + + /* Libgcrypt does no always care to set clear the sign if the value + * is 0. For printing this is a bit of a surprise, in particular + * because if some of the formats don't support negative numbers but + * should be able to print a zero. Thus we need this extra test + * for a negative number. + */ + if (a->sign && mpi_cmp_ui(a, 0)) + negative =3D 1; + else + negative =3D 0; + + len =3D buflen; + *nwritten =3D 0; + if (format =3D=3D GCRYMPI_FMT_STD) { + unsigned char *tmp; + int extra =3D 0; + unsigned int n; + + tmp =3D mpi_get_buffer(a, &n, NULL); + if (!tmp) + return -EINVAL; + + if (negative) { + twocompl(tmp, n); + if (!(*tmp & 0x80)) { + /* Need to extend the sign. */ + n++; + extra =3D 2; + } + } else if (n && (*tmp & 0x80)) { + /* Positive but the high bit of the returned buffer is set. + * Thus we need to print an extra leading 0x00 so that the + * output is interpreted as a positive number. + */ + n++; + extra =3D 1; + } + + if (buffer && n > len) { + /* The provided buffer is too short. */ + kfree(tmp); + return -E2BIG; + } + if (buffer) { + unsigned char *s =3D buffer; + + if (extra =3D=3D 1) + *s++ =3D 0; + else if (extra) + *s++ =3D 0xff; + memcpy(s, tmp, n-!!extra); + } + kfree(tmp); + *nwritten =3D n; + return 0; + } else if (format =3D=3D GCRYMPI_FMT_USG) { + unsigned int n =3D (nbits + 7)/8; + + /* Note: We ignore the sign for this format. */ + /* FIXME: for performance reasons we should put this into + * mpi_aprint because we can then use the buffer directly. + */ + + if (buffer && n > len) + return -E2BIG; + if (buffer) { + unsigned char *tmp; + + tmp =3D mpi_get_buffer(a, &n, NULL); + if (!tmp) + return -EINVAL; + memcpy(buffer, tmp, n); + kfree(tmp); + } + *nwritten =3D n; + return 0; + } else if (format =3D=3D GCRYMPI_FMT_PGP) { + unsigned int n =3D (nbits + 7)/8; + + /* The PGP format can only handle unsigned integers. */ + if (negative) + return -EINVAL; + + if (buffer && n+2 > len) + return -E2BIG; + + if (buffer) { + unsigned char *tmp; + unsigned char *s =3D buffer; + + s[0] =3D nbits >> 8; + s[1] =3D nbits; + + tmp =3D mpi_get_buffer(a, &n, NULL); + if (!tmp) + return -EINVAL; + memcpy(s+2, tmp, n); + kfree(tmp); + } + *nwritten =3D n+2; + return 0; + } else if (format =3D=3D GCRYMPI_FMT_SSH) { + unsigned char *tmp; + int extra =3D 0; + unsigned int n; + + tmp =3D mpi_get_buffer(a, &n, NULL); + if (!tmp) + return -EINVAL; + + if (negative) { + twocompl(tmp, n); + if (!(*tmp & 0x80)) { + /* Need to extend the sign. */ + n++; + extra =3D 2; + } + } else if (n && (*tmp & 0x80)) { + n++; + extra =3D 1; + } + + if (buffer && n+4 > len) { + kfree(tmp); + return -E2BIG; + } + + if (buffer) { + unsigned char *s =3D buffer; + + *s++ =3D n >> 24; + *s++ =3D n >> 16; + *s++ =3D n >> 8; + *s++ =3D n; + if (extra =3D=3D 1) + *s++ =3D 0; + else if (extra) + *s++ =3D 0xff; + memcpy(s, tmp, n-!!extra); + } + kfree(tmp); + *nwritten =3D 4+n; + return 0; + } else if (format =3D=3D GCRYMPI_FMT_HEX) { + unsigned char *tmp; + int i; + int extra =3D 0; + unsigned int n =3D 0; + + tmp =3D mpi_get_buffer(a, &n, NULL); + if (!tmp) + return -EINVAL; + if (!n || (*tmp & 0x80)) + extra =3D 2; + + if (buffer && 2*n + extra + negative + 1 > len) { + kfree(tmp); + return -E2BIG; + } + if (buffer) { + unsigned char *s =3D buffer; + + if (negative) + *s++ =3D '-'; + if (extra) { + *s++ =3D '0'; + *s++ =3D '0'; + } + + for (i =3D 0; i < n; i++) { + unsigned int c =3D tmp[i]; + + *s++ =3D (c >> 4) < 10 ? '0'+(c>>4) : 'A'+(c>>4)-10; + c &=3D 15; + *s++ =3D c < 10 ? '0'+c : 'A'+c-10; + } + *s++ =3D 0; + *nwritten =3D s - buffer; + } else { + *nwritten =3D 2*n + extra + negative + 1; + } + kfree(tmp); + return 0; + } else + return -EINVAL; +} +EXPORT_SYMBOL_GPL(mpi_print); diff --git a/lib/crypto/mpi/mpih-mul.c b/lib/crypto/mpi/mpih-mul.c index a93647564054..e5f1c84e3c48 100644 --- a/lib/crypto/mpi/mpih-mul.c +++ b/lib/crypto/mpi/mpih-mul.c @@ -317,6 +317,31 @@ mpih_sqr_n(mpi_ptr_t prodp, mpi_ptr_t up, mpi_size_t s= ize, mpi_ptr_t tspace) } } =20 + +void mpihelp_mul_n(mpi_ptr_t prodp, + mpi_ptr_t up, mpi_ptr_t vp, mpi_size_t size) +{ + if (up =3D=3D vp) { + if (size < KARATSUBA_THRESHOLD) + mpih_sqr_n_basecase(prodp, up, size); + else { + mpi_ptr_t tspace; + tspace =3D mpi_alloc_limb_space(2 * size); + mpih_sqr_n(prodp, up, size, tspace); + mpi_free_limb_space(tspace); + } + } else { + if (size < KARATSUBA_THRESHOLD) + mul_n_basecase(prodp, up, vp, size); + else { + mpi_ptr_t tspace; + tspace =3D mpi_alloc_limb_space(2 * size); + mul_n(prodp, up, vp, size, tspace); + mpi_free_limb_space(tspace); + } + } +} + int mpihelp_mul_karatsuba_case(mpi_ptr_t prodp, mpi_ptr_t up, mpi_size_t usize, diff --git a/lib/crypto/mpi/mpiutil.c b/lib/crypto/mpi/mpiutil.c index 979ece5a81d2..c8ab00f6f4f4 100644 --- a/lib/crypto/mpi/mpiutil.c +++ b/lib/crypto/mpi/mpiutil.c @@ -20,6 +20,63 @@ =20 #include "mpi-internal.h" =20 +/* Constants allocated right away at startup. */ +static MPI constants[MPI_NUMBER_OF_CONSTANTS]; + +/* Initialize the MPI subsystem. This is called early and allows to + * do some initialization without taking care of threading issues. + */ +static int __init mpi_init(void) +{ + int idx; + unsigned long value; + + for (idx =3D 0; idx < MPI_NUMBER_OF_CONSTANTS; idx++) { + switch (idx) { + case MPI_C_ZERO: + value =3D 0; + break; + case MPI_C_ONE: + value =3D 1; + break; + case MPI_C_TWO: + value =3D 2; + break; + case MPI_C_THREE: + value =3D 3; + break; + case MPI_C_FOUR: + value =3D 4; + break; + case MPI_C_EIGHT: + value =3D 8; + break; + default: + pr_err("MPI: invalid mpi_const selector %d\n", idx); + return -EFAULT; + } + constants[idx] =3D mpi_alloc_set_ui(value); + constants[idx]->flags =3D (16|32); + } + + return 0; +} +postcore_initcall(mpi_init); + +/* Return a constant MPI descripbed by NO which is one of the + * MPI_C_xxx macros. There is no need to copy this returned value; it + * may be used directly. + */ +MPI mpi_const(enum gcry_mpi_constants no) +{ + if ((int)no < 0 || no > MPI_NUMBER_OF_CONSTANTS) + pr_err("MPI: invalid mpi_const selector %d\n", no); + if (!constants[no]) + pr_err("MPI: MPI subsystem not initialized\n"); + return constants[no]; +} +EXPORT_SYMBOL_GPL(mpi_const); + /**************** * Note: It was a bad idea to use the number of limbs to allocate * because on a alpha the limbs are large but we normally need @@ -106,6 +163,15 @@ int mpi_resize(MPI a, unsigned nlimbs) return 0; } =20 +void mpi_clear(MPI a) +{ + if (!a) + return; + a->nlimbs =3D 0; + a->flags =3D 0; +} +EXPORT_SYMBOL_GPL(mpi_clear); + void mpi_free(MPI a) { if (!a) @@ -146,5 +212,121 @@ MPI mpi_copy(MPI a) return b; } =20 +/**************** + * This function allocates an MPI which is optimized to hold + * a value as large as the one given in the argument and allocates it + * with the same flags as A. + */ +MPI mpi_alloc_like(MPI a) +{ + MPI b; + + if (a) { + b =3D mpi_alloc(a->nlimbs); + b->nlimbs =3D 0; + b->sign =3D 0; + b->flags =3D a->flags; + } else + b =3D NULL; + + return b; +} + + +/* Set U into W and release U. If W is NULL only U will be released. */ +void mpi_snatch(MPI w, MPI u) +{ + if (w) { + mpi_assign_limb_space(w, u->d, u->alloced); + w->nlimbs =3D u->nlimbs; + w->sign =3D u->sign; + w->flags =3D u->flags; + u->alloced =3D 0; + u->nlimbs =3D 0; + u->d =3D NULL; + } + mpi_free(u); +} + + +MPI mpi_set(MPI w, MPI u) +{ + mpi_ptr_t wp, up; + mpi_size_t usize =3D u->nlimbs; + int usign =3D u->sign; + + if (!w) + w =3D mpi_alloc(mpi_get_nlimbs(u)); + RESIZE_IF_NEEDED(w, usize); + wp =3D w->d; + up =3D u->d; + MPN_COPY(wp, up, usize); + w->nlimbs =3D usize; + w->flags =3D u->flags; + w->flags &=3D ~(16|32); /* Reset the immutable and constant flags. */ + w->sign =3D usign; + return w; +} +EXPORT_SYMBOL_GPL(mpi_set); + +MPI mpi_set_ui(MPI w, unsigned long u) +{ + if (!w) + w =3D mpi_alloc(1); + /* FIXME: If U is 0 we have no need to resize and thus possible + * allocating the limbs. + */ + RESIZE_IF_NEEDED(w, 1); + w->d[0] =3D u; + w->nlimbs =3D u ? 1 : 0; + w->sign =3D 0; + w->flags =3D 0; + return w; +} +EXPORT_SYMBOL_GPL(mpi_set_ui); + +MPI mpi_alloc_set_ui(unsigned long u) +{ + MPI w =3D mpi_alloc(1); + w->d[0] =3D u; + w->nlimbs =3D u ? 1 : 0; + w->sign =3D 0; + return w; +} + +/**************** + * Swap the value of A and B, when SWAP is 1. + * Leave the value when SWAP is 0. + * This implementation should be constant-time regardless of SWAP. + */ +void mpi_swap_cond(MPI a, MPI b, unsigned long swap) +{ + mpi_size_t i; + mpi_size_t nlimbs; + mpi_limb_t mask =3D ((mpi_limb_t)0) - swap; + mpi_limb_t x; + + if (a->alloced > b->alloced) + nlimbs =3D b->alloced; + else + nlimbs =3D a->alloced; + if (a->nlimbs > nlimbs || b->nlimbs > nlimbs) + return; + + for (i =3D 0; i < nlimbs; i++) { + x =3D mask & (a->d[i] ^ b->d[i]); + a->d[i] =3D a->d[i] ^ x; + b->d[i] =3D b->d[i] ^ x; + } + + x =3D mask & (a->nlimbs ^ b->nlimbs); + a->nlimbs =3D a->nlimbs ^ x; + b->nlimbs =3D b->nlimbs ^ x; + + x =3D mask & (a->sign ^ b->sign); + a->sign =3D a->sign ^ x; + b->sign =3D b->sign ^ x; +} + MODULE_DESCRIPTION("Multiprecision maths library"); MODULE_LICENSE("GPL"); --=20 2.25.1 From nobody Wed Oct 8 09:26:48 2025 Received: from szxga03-in.huawei.com (szxga03-in.huawei.com [45.249.212.189]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 487CD28B7EF; Mon, 30 Jun 2025 13:27:40 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=45.249.212.189 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1751290064; cv=none; b=dFmJaYZjVeWsam4mItz1OU4EkBnlt0PaipqQHGX1Csit7kYNKJXDo9kXDyKmoRZLeTqSd+Ze6XlOseQ834dmv4UEA8D5G8149VeS4qWJyaPxGcH5Qa0DPk4sWafuF5A05EgJXcHSh4TtmhIm+s5LjGFWis8PIrVQMOmf38IX1gQ= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1751290064; c=relaxed/simple; bh=/kdgOgMrTQiT1/QcY/sch7kM0/HJsni0LrY67SFLLAA=; h=From:To:CC:Subject:Date:Message-ID:In-Reply-To:References: MIME-Version:Content-Type; b=tql6NHj7brfaPQT9vWsnK5GncP3qZIq7T4Jc4MSoUOQ974XVkH9fJ8fwF3KF4LjXYrQDno3is6vY70Tb/3gQxMvQF9+dRvzOVtHTkV1iK6zL6I1eKE9XY1uHmAPQxaQcgz/Cn9IT8VqeA6cBe2S02uz/MleUH4XlZ6KPwiSUUIg= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=quarantine dis=none) header.from=huawei.com; spf=pass smtp.mailfrom=huawei.com; arc=none smtp.client-ip=45.249.212.189 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=quarantine dis=none) header.from=huawei.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=huawei.com Received: from mail.maildlp.com (unknown [172.19.162.254]) by szxga03-in.huawei.com (SkyGuard) with ESMTP id 4bW6LC3MVTzdbkp; Mon, 30 Jun 2025 21:23:31 +0800 (CST) Received: from kwepemh100007.china.huawei.com (unknown [7.202.181.92]) by mail.maildlp.com (Postfix) with ESMTPS id 82825180493; Mon, 30 Jun 2025 21:27:31 +0800 (CST) Received: from huawei.com (10.67.174.33) by kwepemh100007.china.huawei.com (7.202.181.92) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.2.1544.11; Mon, 30 Jun 2025 21:27:30 +0800 From: Gu Bowen To: Herbert Xu , David Howells , David Woodhouse , Lukas Wunner , Ignat Korchagin , "David S . Miller" , Jarkko Sakkinen , Maxime Coquelin , Alexandre Torgue , Eric Biggers , "Jason A . Donenfeld" , Ard Biesheuvel , Tianjia Zhang , Dan Carpenter CC: , , , , , Lu Jialin , GONG Ruiqi , Gu Bowen Subject: [PATCH RFC 2/4] Revert "Revert "lib/mpi: Introduce ec implementation to MPI library"" Date: Mon, 30 Jun 2025 21:39:32 +0800 Message-ID: <20250630133934.766646-3-gubowen5@huawei.com> X-Mailer: git-send-email 2.25.1 In-Reply-To: <20250630133934.766646-1-gubowen5@huawei.com> References: <20250630133934.766646-1-gubowen5@huawei.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Type: text/plain; charset="utf-8" Content-Transfer-Encoding: quoted-printable X-ClientProxiedBy: kwepems500001.china.huawei.com (7.221.188.70) To kwepemh100007.china.huawei.com (7.202.181.92) This reverts commit da4fe6815aca25603944a64b0965310512e867d0. Reintroduce ec implementation to MPI library to support sm2. Signed-off-by: Gu Bowen --- include/linux/mpi.h | 105 +++ lib/crypto/mpi/Makefile | 1 + lib/crypto/mpi/ec.c | 1507 +++++++++++++++++++++++++++++++++++++++ 3 files changed, 1613 insertions(+) create mode 100644 lib/crypto/mpi/ec.c diff --git a/include/linux/mpi.h b/include/linux/mpi.h index 9ad7e7231ee9..3317effe57ba 100644 --- a/include/linux/mpi.h +++ b/include/linux/mpi.h @@ -157,6 +157,111 @@ void mpi_fdiv_q(MPI quot, MPI dividend, MPI divisor); /*-- mpi-inv.c --*/ int mpi_invm(MPI x, MPI a, MPI n); =20 +/*-- 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 =3D x^3 + ax + b + */ + MPI_EC_WEIERSTRASS =3D 0, + /* The Montgomery equation is + * by^2 =3D x^3 + ax^2 + x + */ + MPI_EC_MONTGOMERY, + /* The Twisted Edwards equation is + * ax^2 + y^2 =3D 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 =3D 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 flagged 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 =3D 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 *ct= x); +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 */ =20 /** diff --git a/lib/crypto/mpi/Makefile b/lib/crypto/mpi/Makefile index 477debd7ed50..6e6ef9a34fe1 100644 --- a/lib/crypto/mpi/Makefile +++ b/lib/crypto/mpi/Makefile @@ -13,6 +13,7 @@ mpi-y =3D \ 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/crypto/mpi/ec.c b/lib/crypto/mpi/ec.c new file mode 100644 index 000000000000..4781f00982ef --- /dev/null +++ b/lib/crypto/mpi/ec.c @@ -0,0 +1,1507 @@ +/* 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 =3D 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 =3D mpi_new(0); + p->y =3D mpi_new(0); + p->z =3D 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 =3D NULL; + mpi_free(p->y); p->y =3D NULL; + mpi_free(p->z); p->z =3D 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 =3D ctx->p->nlimbs; + + mpi_resize(p->x, nlimbs); + p->x->nlimbs =3D nlimbs; + mpi_resize(p->z, nlimbs); + p->z->nlimbs =3D nlimbs; + + if (ctx->model !=3D MPI_EC_MONTGOMERY) { + mpi_resize(p->y, nlimbs); + p->y->nlimbs =3D 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 !=3D MPI_EC_MONTGOMERY) + mpi_swap_cond(d->y, s->y, swap); + mpi_swap_cond(d->z, s->z, swap); +} + + +/* W =3D 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 =3D 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 =3D ((mpi_limb_t)0) - set; + mpi_limb_t x; + + for (i =3D 0; i < usize; i++) { + x =3D mask & (wp[i] ^ up[i]); + wp[i] =3D 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 =3D LIMB_SIZE_25519; + mpi_limb_t n[LIMB_SIZE_25519]; + mpi_limb_t borrow; + + if (w->nlimbs !=3D wsize || u->nlimbs !=3D wsize || v->nlimbs !=3D wsize) + log_bug("addm_25519: different sizes\n"); + + memset(n, 0, sizeof(n)); + up =3D u->d; + vp =3D v->d; + wp =3D w->d; + + mpihelp_add_n(wp, up, vp, wsize); + borrow =3D mpihelp_sub_n(wp, wp, ctx->p->d, wsize); + mpih_set_cond(n, ctx->p->d, wsize, (borrow !=3D 0UL)); + mpihelp_add_n(wp, wp, n, wsize); + wp[LIMB_SIZE_25519-1] &=3D ~((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 =3D LIMB_SIZE_25519; + mpi_limb_t n[LIMB_SIZE_25519]; + mpi_limb_t borrow; + + if (w->nlimbs !=3D wsize || u->nlimbs !=3D wsize || v->nlimbs !=3D wsize) + log_bug("subm_25519: different sizes\n"); + + memset(n, 0, sizeof(n)); + up =3D u->d; + vp =3D v->d; + wp =3D w->d; + + borrow =3D mpihelp_sub_n(wp, up, vp, wsize); + mpih_set_cond(n, ctx->p->d, wsize, (borrow !=3D 0UL)); + mpihelp_add_n(wp, wp, n, wsize); + wp[LIMB_SIZE_25519-1] &=3D ~((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 =3D 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 !=3D wsize || u->nlimbs !=3D wsize || v->nlimbs !=3D wsize) + log_bug("mulm_25519: different sizes\n"); + + up =3D u->d; + vp =3D v->d; + wp =3D w->d; + + mpihelp_mul_n(n, up, vp, wsize); + memcpy(wp, n, wsize * BYTES_PER_MPI_LIMB); + wp[LIMB_SIZE_25519-1] &=3D ~((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 =3D mpihelp_lshift(m, m, LIMB_SIZE_25519, 4); + m[LIMB_SIZE_25519] =3D cy; + cy =3D mpihelp_add_n(m, m, n, wsize); + m[LIMB_SIZE_25519] +=3D cy; + cy =3D mpihelp_add_n(m, m, n, wsize); + m[LIMB_SIZE_25519] +=3D cy; + cy =3D mpihelp_add_n(m, m, n, wsize); + m[LIMB_SIZE_25519] +=3D cy; + + cy =3D mpihelp_add_n(wp, wp, m, wsize); + m[LIMB_SIZE_25519] +=3D cy; + + memset(m, 0, wsize * BYTES_PER_MPI_LIMB); + msb =3D (wp[LIMB_SIZE_25519-1] >> (255 % BITS_PER_MPI_LIMB)); + m[0] =3D (m[LIMB_SIZE_25519] * 2 + msb) * 19; + wp[LIMB_SIZE_25519-1] &=3D ~((mpi_limb_t)1 << (255 % BITS_PER_MPI_LIMB)); + mpihelp_add_n(wp, wp, m, wsize); + + m[0] =3D 0; + cy =3D mpihelp_sub_n(wp, wp, ctx->p->d, wsize); + mpih_set_cond(m, ctx->p->d, wsize, (cy !=3D 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 =3D LIMB_SIZE_448; + mpi_limb_t n[LIMB_SIZE_448]; + mpi_limb_t cy; + + if (w->nlimbs !=3D wsize || u->nlimbs !=3D wsize || v->nlimbs !=3D wsize) + log_bug("addm_448: different sizes\n"); + + memset(n, 0, sizeof(n)); + up =3D u->d; + vp =3D v->d; + wp =3D w->d; + + cy =3D mpihelp_add_n(wp, up, vp, wsize); + mpih_set_cond(n, ctx->p->d, wsize, (cy !=3D 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 =3D LIMB_SIZE_448; + mpi_limb_t n[LIMB_SIZE_448]; + mpi_limb_t borrow; + + if (w->nlimbs !=3D wsize || u->nlimbs !=3D wsize || v->nlimbs !=3D wsize) + log_bug("subm_448: different sizes\n"); + + memset(n, 0, sizeof(n)); + up =3D u->d; + vp =3D v->d; + wp =3D w->d; + + borrow =3D mpihelp_sub_n(wp, up, vp, wsize); + mpih_set_cond(n, ctx->p->d, wsize, (borrow !=3D 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 =3D 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 !=3D wsize || u->nlimbs !=3D wsize || v->nlimbs !=3D wsize) + log_bug("mulm_448: different sizes\n"); + + up =3D u->d; + vp =3D v->d; + wp =3D w->d; + + mpihelp_mul_n(n, up, vp, wsize); + + for (i =3D 0; i < (wsize + 1) / 2; i++) { + b0[i] =3D n[i]; + b1[i] =3D n[i+wsize/2]; + a2[i] =3D n[i+wsize]; + a3[i] =3D n[i+wsize+wsize/2]; + } + +#if (LIMB_SIZE_HALF_448 > LIMB_SIZE_448/2) + b0[LIMB_SIZE_HALF_448-1] &=3D ((mpi_limb_t)1UL << 32)-1; + a2[LIMB_SIZE_HALF_448-1] &=3D ((mpi_limb_t)1UL << 32)-1; + + b1_rest =3D 0; + a3_rest =3D 0; + + for (i =3D (wsize + 1) / 2 - 1; i >=3D 0; i--) { + mpi_limb_t b1v, a3v; + b1v =3D b1[i]; + a3v =3D a3[i]; + b1[i] =3D (b1_rest << 32) | (b1v >> 32); + a3[i] =3D (a3_rest << 32) | (a3v >> 32); + b1_rest =3D b1v & (((mpi_limb_t)1UL << 32)-1); + a3_rest =3D a3v & (((mpi_limb_t)1UL << 32)-1); + } +#endif + + cy =3D mpihelp_add_n(b0, b0, a2, LIMB_SIZE_HALF_448); + cy +=3D mpihelp_add_n(b0, b0, a3, LIMB_SIZE_HALF_448); + for (i =3D 0; i < (wsize + 1) / 2; i++) + wp[i] =3D b0[i]; +#if (LIMB_SIZE_HALF_448 > LIMB_SIZE_448/2) + wp[LIMB_SIZE_HALF_448-1] &=3D (((mpi_limb_t)1UL << 32)-1); +#endif + +#if (LIMB_SIZE_HALF_448 > LIMB_SIZE_448/2) + cy =3D b0[LIMB_SIZE_HALF_448-1] >> 32; +#endif + + cy =3D mpihelp_add_1(b1, b1, LIMB_SIZE_HALF_448, cy); + cy +=3D mpihelp_add_n(b1, b1, a2, LIMB_SIZE_HALF_448); + cy +=3D mpihelp_add_n(b1, b1, a3, LIMB_SIZE_HALF_448); + cy +=3D mpihelp_add_n(b1, b1, a3, LIMB_SIZE_HALF_448); +#if (LIMB_SIZE_HALF_448 > LIMB_SIZE_448/2) + b1_rest =3D 0; + for (i =3D (wsize + 1) / 2 - 1; i >=3D 0; i--) { + mpi_limb_t b1v =3D b1[i]; + b1[i] =3D (b1_rest << 32) | (b1v >> 32); + b1_rest =3D b1v & (((mpi_limb_t)1UL << 32)-1); + } + wp[LIMB_SIZE_HALF_448-1] |=3D (b1_rest << 32); +#endif + for (i =3D 0; i < wsize / 2; i++) + wp[i+(wsize + 1) / 2] =3D b1[i]; + +#if (LIMB_SIZE_HALF_448 > LIMB_SIZE_448/2) + cy =3D 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] =3D cy << 32; +#else + n[LIMB_SIZE_HALF_448] =3D cy; +#endif + n[0] =3D cy; + mpihelp_add_n(wp, wp, n, wsize); + + memset(n, 0, wsize * BYTES_PER_MPI_LIMB); + cy =3D mpihelp_sub_n(wp, wp, ctx->p->d, wsize); + mpih_set_cond(n, ctx->p->d, wsize, (cy !=3D 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[] =3D { + { + "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. */ +static void mpi_ec_get_reset(struct mpi_ec_ctx *ec) +{ + ec->t.valid.a_is_pminus3 =3D 0; + ec->t.valid.two_inv_p =3D 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 =3D 1; + tmp =3D mpi_alloc_like(ec->p); + mpi_sub_ui(tmp, ec->p, 3); + ec->t.a_is_pminus3 =3D !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 =3D 1; + if (!ec->t.two_inv_p) + ec->t.two_inv_p =3D 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[] =3D { + "0x7fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffed", + "0x0000000000000000000000000000000000000000000000000000000000000000", + "0x0000000000000000000000000000000000000000000000000000000000000001", + "0x00b8495f16056286fdb1329ceb8d09da6ac49ff1fae35616aeb8413b7c7aebe0", + "0x57119fd0dd4e22d8868e1c58c45c44045bef839c55b1d0b1248c50a3bc959c5f", + "0x7fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffec", + "0x7fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffee", + NULL +}; + +static const char *const curve448_bad_points[] =3D { + "0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffe" + "ffffffffffffffffffffffffffffffffffffffffffffffffffffffff", + "0x00000000000000000000000000000000000000000000000000000000" + "00000000000000000000000000000000000000000000000000000000", + "0x00000000000000000000000000000000000000000000000000000000" + "00000000000000000000000000000000000000000000000000000001", + "0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffe" + "fffffffffffffffffffffffffffffffffffffffffffffffffffffffe", + "0xffffffffffffffffffffffffffffffffffffffffffffffffffffffff" + "00000000000000000000000000000000000000000000000000000000", + NULL +}; + +static const char *const *bad_points_table[] =3D { + 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 =3D p->nlimbs; + a->sign =3D 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 =3D -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 =3D model; + ctx->dialect =3D dialect; + ctx->flags =3D flags; + if (dialect =3D=3D ECC_DIALECT_ED25519) + ctx->nbits =3D 256; + else + ctx->nbits =3D mpi_get_nbits(p); + ctx->p =3D mpi_copy(p); + ctx->a =3D mpi_copy(a); + ctx->b =3D mpi_copy(b); + + ctx->d =3D NULL; + ctx->t.two_inv_p =3D NULL; + + ctx->t.p_barrett =3D use_barrett > 0 ? mpi_barrett_init(ctx->p, 0) : NULL; + + mpi_ec_get_reset(ctx); + + if (model =3D=3D MPI_EC_MONTGOMERY) { + for (i =3D 0; i < DIM(bad_points_table); i++) { + MPI p_candidate =3D mpi_scanval(bad_points_table[i][0]); + int match_p =3D !mpi_cmp(ctx->p, p_candidate); + int j; + + mpi_free(p_candidate); + if (!match_p) + continue; + + for (j =3D 0; i < DIM(ctx->t.scratch) && bad_points_table[i][j]; j++) + ctx->t.scratch[j] =3D mpi_scanval(bad_points_table[i][j]); + } + } else { + /* Allocate scratch variables. */ + for (i =3D 0; i < DIM(ctx->t.scratch); i++) + ctx->t.scratch[i] =3D mpi_alloc_like(ctx->p); + } + + ctx->addm =3D ec_addm; + ctx->subm =3D ec_subm; + ctx->mulm =3D ec_mulm; + ctx->mul2 =3D ec_mul2; + ctx->pow2 =3D ec_pow2; + + for (i =3D 0; field_table[i].p; i++) { + MPI f_p; + + f_p =3D mpi_scanval(field_table[i].p); + if (!f_p) + break; + + if (!mpi_cmp(p, f_p)) { + ctx->addm =3D field_table[i].addm; + ctx->subm =3D field_table[i].subm; + ctx->mulm =3D field_table[i].mulm; + ctx->mul2 =3D field_table[i].mul2; + ctx->pow2 =3D field_table[i].pow2; + mpi_free(f_p); + + mpi_resize(ctx->a, ctx->p->nlimbs); + ctx->a->nlimbs =3D ctx->p->nlimbs; + + mpi_resize(ctx->b, ctx->p->nlimbs); + ctx->b->nlimbs =3D ctx->p->nlimbs; + + for (i =3D 0; i < DIM(ctx->t.scratch) && ctx->t.scratch[i]; i++) + ctx->t.scratch[i]->nlimbs =3D 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 =3D 0; i < DIM(ctx->t.scratch); i++) + mpi_free(ctx->t.scratch[i]); +} +EXPORT_SYMBOL_GPL(mpi_ec_deinit); + +/* 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 *ct= x) +{ + if (!mpi_cmp_ui(point->z, 0)) + return -1; + + switch (ctx->model) { + case MPI_EC_WEIERSTRASS: /* Using Jacobian coordinates. */ + { + MPI z1, z2, z3; + + z1 =3D mpi_new(0); + z2 =3D mpi_new(0); + ec_invm(z1, point->z, ctx); /* z1 =3D z^(-1) mod p */ + ec_mulm(z2, z1, z1, ctx); /* z2 =3D z^(-2) mod p */ + + if (x) + ec_mulm(x, point->x, z2, ctx); + + if (y) { + z3 =3D mpi_new(0); + ec_mulm(z3, z2, z1, ctx); /* z3 =3D 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 =3D mpi_new(0); + ec_invm(z, point->z, ctx); + + mpi_resize(z, ctx->p->nlimbs); + z->nlimbs =3D ctx->p->nlimbs; + + if (x) { + mpi_resize(x, ctx->p->nlimbs); + x->nlimbs =3D ctx->p->nlimbs; + ctx->mulm(x, point->x, z, ctx); + } + if (y) { + mpi_resize(y, ctx->p->nlimbs); + y->nlimbs =3D 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 =3D 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 =3D=3D 0 || P_z =3D=3D 0 =3D> [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 =3D 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 =3D 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 =3D 2YZ */ + ec_mulm(z3, point->y, point->z, ctx); + ec_mul2(z3, z3, ctx); + + /* L2 =3D 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 =3D 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 =3D 8Y^4 */ + /* T2: taken from above. */ + ec_pow2(t2, t2, ctx); + ec_mulm(l3, t2, mpi_const(MPI_C_EIGHT), ctx); + + /* Y3 =3D 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 =3D 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 =3D 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) =3D 2( X_1 : Y_1 : Z_1 ) */ + + /* B =3D (X_1 + Y_1)^2 */ + ctx->addm(B, X1, Y1, ctx); + ctx->pow2(B, B, ctx); + + /* C =3D X_1^2 */ + /* D =3D Y_1^2 */ + ctx->pow2(C, X1, ctx); + ctx->pow2(D, Y1, ctx); + + /* E =3D aC */ + if (ctx->dialect =3D=3D ECC_DIALECT_ED25519) + ctx->subm(E, ctx->p, C, ctx); + else + ctx->mulm(E, ctx->a, C, ctx); + + /* F =3D E + D */ + ctx->addm(F, E, D, ctx); + + /* H =3D Z_1^2 */ + ctx->pow2(H, Z1, ctx); + + /* J =3D F - 2H */ + ctx->mul2(J, H, ctx); + ctx->subm(J, F, J, ctx); + + /* X_3 =3D (B - C - D) =C2=B7 J */ + ctx->subm(X3, B, C, ctx); + ctx->subm(X3, X3, D, ctx); + ctx->mulm(X3, X3, J, ctx); + + /* Y_3 =3D F =C2=B7 (E - D) */ + ctx->subm(Y3, E, D, ctx); + ctx->mulm(Y3, Y3, F, ctx); + + /* Z_3 =3D F =C2=B7 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 =3D 2 * POINT */ +static 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 =3D 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 =3D !mpi_cmp_ui(z1, 1); + int z2_is_one =3D !mpi_cmp_ui(z2, 1); + + /* l1 =3D x1 z2^2 */ + /* l2 =3D 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 =3D l1 - l2 */ + ec_subm(l3, l1, l2, ctx); + /* l4 =3D y1 z2^3 */ + ec_powm(l4, z2, mpi_const(MPI_C_THREE), ctx); + ec_mulm(l4, l4, y1, ctx); + /* l5 =3D y2 z1^3 */ + ec_powm(l5, z1, mpi_const(MPI_C_THREE), ctx); + ec_mulm(l5, l5, y2, ctx); + /* l6 =3D 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 =3D l1 + l2 */ + ec_addm(l7, l1, l2, ctx); + /* l8 =3D l4 + l5 */ + ec_addm(l8, l4, l5, ctx); + /* z3 =3D z1 z2 l3 */ + ec_mulm(z3, z1, z2, ctx); + ec_mulm(z3, z3, l3, ctx); + /* x3 =3D 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 =3D l7 l3^2 - 2 x3 */ + ec_mul2(t1, x3, ctx); + ec_subm(l9, t2, t1, ctx); + /* y3 =3D (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 =3D 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 =3D 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) =3D (X_1 : Y_1 : Z_1) + (X_2 : Y_2 : Z_3) */ + + /* A =3D Z1 =C2=B7 Z2 */ + ctx->mulm(A, Z1, Z2, ctx); + + /* B =3D A^2 */ + ctx->pow2(B, A, ctx); + + /* C =3D X1 =C2=B7 X2 */ + ctx->mulm(C, X1, X2, ctx); + + /* D =3D Y1 =C2=B7 Y2 */ + ctx->mulm(D, Y1, Y2, ctx); + + /* E =3D d =C2=B7 C =C2=B7 D */ + ctx->mulm(E, ctx->b, C, ctx); + ctx->mulm(E, E, D, ctx); + + /* F =3D B - E */ + ctx->subm(F, B, E, ctx); + + /* G =3D B + E */ + ctx->addm(G, B, E, ctx); + + /* X_3 =3D A =C2=B7 F =C2=B7 ((X_1 + Y_1) =C2=B7 (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 =3D A =C2=B7 G =C2=B7 (D - aC) */ + if (ctx->dialect =3D=3D 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 =3D F =C2=B7 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 =3D P1 - P1. + * Outputs: PRD =3D 2 * P1 and SUM =3D 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 =3D 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 =3D=3D MPI_EC_EDWARDS) { + /* Simple left to right binary method. Algorithm 3.27 from + * {author=3D{Hankerson, Darrel and Menezes, Alfred J. and Vanstone, Sco= tt}, + * title =3D {Guide to Elliptic Curve Cryptography}, + * year =3D {2003}, isbn =3D {038795273X}, + * url =3D {http://www.cacr.math.uwaterloo.ca/ecc/}, + * publisher =3D {Springer-Verlag New York, Inc.}} + */ + unsigned int nbits; + int j; + + if (mpi_cmp(scalar, ctx->p) >=3D 0) + nbits =3D mpi_get_nbits(scalar); + else + nbits =3D 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 =3D nbits-1; j >=3D 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 =3D=3D 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; + + /* 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 =3D 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 =3D 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 =3D ctx->p->nlimbs; + + q1 =3D &p1; + q2 =3D &p2; + prd =3D &p1_; + sum =3D &p2_; + + for (j =3D nbits-1; j >=3D 0; j--) { + sw =3D 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); + swap(q1, prd); + swap(q2, sum); + } + + mpi_clear(result->y); + sw =3D (nbits & 1); + point_swap_cond(&p1, &p1_, sw, ctx); + + rsize =3D p1.z->nlimbs; + MPN_NORMALIZE(p1.z->d, rsize); + if (rsize =3D=3D 0) { + mpi_set_ui(result->x, 1); + mpi_set_ui(result->z, 0); + } else { + z1 =3D 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_); + return; + } + + x1 =3D mpi_alloc_like(ctx->p); + y1 =3D mpi_alloc_like(ctx->p); + h =3D mpi_alloc_like(ctx->p); + k =3D mpi_copy(scalar); + yy =3D mpi_copy(point->y); + + if (mpi_has_sign(k)) { + k->sign =3D 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 =3D mpi_alloc_like(ctx->p); + z3 =3D 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 =3D mpi_copy(mpi_const(MPI_C_ONE)); + + mpi_mul(h, k, mpi_const(MPI_C_THREE)); /* h =3D 3k */ + loops =3D 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 =3D 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 =3D NULL; + + p1.x =3D x1; x1 =3D NULL; + p1.y =3D y1; y1 =3D NULL; + p1.z =3D z1; z1 =3D NULL; + point_init(&p2); + point_init(&p1inv); + + /* Invert point: y =3D p - y mod p */ + point_set(&p1inv, &p1); + ec_subm(p1inv.y, ctx->p, p1inv.y, ctx); + + for (i =3D loops-2; i > 0; i--) { + mpi_ec_dup_point(result, result, ctx); + if (mpi_test_bit(h, i) =3D=3D 1 && mpi_test_bit(k, i) =3D=3D 0) { + point_set(&p2, result); + mpi_ec_add_points(result, &p2, &p1, ctx); + } + if (mpi_test_bit(h, i) =3D=3D 0 && mpi_test_bit(k, i) =3D=3D 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 =3D 0; + MPI x, y, w; + + x =3D mpi_new(0); + y =3D mpi_new(0); + w =3D 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) >=3D 0) + goto leave; + if (mpi_cmpabs(point->y, ctx->p) >=3D 0) + goto leave; + if (mpi_cmpabs(point->z, ctx->p) >=3D 0) + goto leave; + + switch (ctx->model) { + case MPI_EC_WEIERSTRASS: + { + MPI xxx; + + if (mpi_ec_get_affine(x, y, point, ctx)) + goto leave; + + xxx =3D mpi_new(0); + + /* y^2 =3D=3D x^3 + a=C2=B7x + 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 =3D 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 =3D=3D x^3 + a =C2=B7 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 =3D !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 =3D ctx->p->nlimbs; + + /* a =C2=B7 x^2 + y^2 - 1 - b =C2=B7 x^2 =C2=B7 y^2 =3D=3D 0 */ + ctx->pow2(x, x, ctx); + ctx->pow2(y, y, ctx); + if (ctx->dialect =3D=3D 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 =3D 1; + } + break; + } + +leave: + mpi_free(w); + mpi_free(x); + mpi_free(y); + + return res; +} +EXPORT_SYMBOL_GPL(mpi_ec_curve_point); --=20 2.25.1 From nobody Wed Oct 8 09:26:48 2025 Received: from szxga05-in.huawei.com (szxga05-in.huawei.com [45.249.212.191]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 1750B25C713; Mon, 30 Jun 2025 13:27:34 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=45.249.212.191 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1751290058; cv=none; b=H2gFn1/btFALwtUvUtcNp2tad97cXycMa1X4qGHQX3MQhy/tY9oWtTMPtjg7i1BBfBZMQm7Dge3ZdgNfQwWDXnp3/evZ7j0f/hCZ9KZIGsyE7PEZ9EvdZZXSxhmhq+h5shynfNx86NX0eSnHwAh1WqdNjjcFiQE9RbuK0P86Y8M= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1751290058; c=relaxed/simple; bh=rjc6QP2VMjA4I0BeMbJAbGURWYO4/OAh6XgZxfiSIDc=; h=From:To:CC:Subject:Date:Message-ID:In-Reply-To:References: MIME-Version:Content-Type; b=EjIpVOBSd+VN7NaZHAjfredLUZUWi5GR8lV1+o+UFPhWd05dJeeaRRzqjvA/5VmjOS0KaSUGNh4XK+EPT1hqIwuaHGU0QF7ylWv7vmNsjNzLxxzbBSDedUoQSTSva1R+Nlf6pUgYgakmggKSa9yNG7OL7wg7riSED/FQZ3X/HSc= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=quarantine dis=none) header.from=huawei.com; spf=pass smtp.mailfrom=huawei.com; arc=none smtp.client-ip=45.249.212.191 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=quarantine dis=none) header.from=huawei.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=huawei.com Received: from mail.maildlp.com (unknown [172.19.88.214]) by szxga05-in.huawei.com (SkyGuard) with ESMTP id 4bW6My0vcWz1R8CD; Mon, 30 Jun 2025 21:25:02 +0800 (CST) Received: from kwepemh100007.china.huawei.com (unknown [7.202.181.92]) by mail.maildlp.com (Postfix) with ESMTPS id 4ED7E1A0171; Mon, 30 Jun 2025 21:27:32 +0800 (CST) Received: from huawei.com (10.67.174.33) by kwepemh100007.china.huawei.com (7.202.181.92) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.2.1544.11; Mon, 30 Jun 2025 21:27:31 +0800 From: Gu Bowen To: Herbert Xu , David Howells , David Woodhouse , Lukas Wunner , Ignat Korchagin , "David S . Miller" , Jarkko Sakkinen , Maxime Coquelin , Alexandre Torgue , Eric Biggers , "Jason A . Donenfeld" , Ard Biesheuvel , Tianjia Zhang , Dan Carpenter CC: , , , , , Lu Jialin , GONG Ruiqi , Gu Bowen Subject: [PATCH RFC 3/4] crypto/sm2: Rework sm2 alg with sig_alg backend Date: Mon, 30 Jun 2025 21:39:33 +0800 Message-ID: <20250630133934.766646-4-gubowen5@huawei.com> X-Mailer: git-send-email 2.25.1 In-Reply-To: <20250630133934.766646-1-gubowen5@huawei.com> References: <20250630133934.766646-1-gubowen5@huawei.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable X-ClientProxiedBy: kwepems500001.china.huawei.com (7.221.188.70) To kwepemh100007.china.huawei.com (7.202.181.92) Content-Type: text/plain; charset="utf-8" Based on preivous sm2 implementations ea7ecb66440b("crypto: sm2 - introduce OSCCA SM2 asymmetric cipher algorithm"), rework sm2 alg with sig_alg backend. Signed-off-by: Gu Bowen --- crypto/Kconfig | 18 ++ crypto/Makefile | 8 + crypto/sm2.c | 492 +++++++++++++++++++++++++++++++++++++++ crypto/sm2signature.asn1 | 4 + crypto/testmgr.c | 6 + crypto/testmgr.h | 57 +++++ include/crypto/sm2.h | 31 +++ 7 files changed, 616 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 e1cfd0d4cc8f..7bd6f025d29d 100644 --- a/crypto/Kconfig +++ b/crypto/Kconfig @@ -344,6 +344,24 @@ config CRYPTO_ECRDSA One of the Russian cryptographic standard algorithms (called GOST algorithms). Only signature verification is implemented. =20 +config CRYPTO_SM2 + tristate "SM2 algorithm" + select CRYPTO_SM3 + select CRYPTO_SIG + 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" select CRYPTO_KPP diff --git a/crypto/Makefile b/crypto/Makefile index 017df3a2e4bb..e36953356f68 100644 --- a/crypto/Makefile +++ b/crypto/Makefile @@ -52,6 +52,14 @@ rsa_generic-y +=3D rsa-pkcs1pad.o rsa_generic-y +=3D rsassa-pkcs1.o obj-$(CONFIG_CRYPTO_RSA) +=3D rsa_generic.o =20 +$(obj)/sm2signature.asn1.o: $(obj)/sm2signature.asn1.c $(obj)/sm2signature= .asn1.h +$(obj)/sm2.o: $(obj)/sm2signature.asn1.h + +sm2_generic-y +=3D sm2signature.asn1.o +sm2_generic-y +=3D sm2.o + +obj-$(CONFIG_CRYPTO_SM2) +=3D sm2_generic.o + $(obj)/ecdsasignature.asn1.o: $(obj)/ecdsasignature.asn1.c $(obj)/ecdsasig= nature.asn1.h $(obj)/ecdsa-x962.o: $(obj)/ecdsasignature.asn1.h ecdsa_generic-y +=3D ecdsa.o diff --git a/crypto/sm2.c b/crypto/sm2.c new file mode 100644 index 000000000000..31e10fcee13c --- /dev/null +++ b/crypto/sm2.c @@ -0,0 +1,492 @@ +/* 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 + * + * Copyright (c) 2025, Huawei Tech. Co., Ltd. + * Authors: Gu Bowen + */ + +#include +#include +#include +#include +#include +#include +#include +#include +#include "sm2signature.asn1.h" + +/* The default user id as specified in GM/T 0009-2012 */ +#define SM2_DEFAULT_USERID "1234567812345678" +#define SM2_DEFAULT_USERID_LEN 16 + +#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 =3D { + .desc =3D "sm2p256v1", + .nbits =3D 256, + .fips =3D 0, + .model =3D MPI_EC_WEIERSTRASS, + .dialect =3D ECC_DIALECT_STANDARD, + .p =3D "0xfffffffeffffffffffffffffffffffffffffffff00000000fffffffffffff= fff", + .a =3D "0xfffffffeffffffffffffffffffffffffffffffff00000000fffffffffffff= ffc", + .b =3D "0x28e9fa9e9d9f5e344d5a9e4bcf6509a7f39789f515ab8f92ddbcbd414d940= e93", + .n =3D "0xfffffffeffffffffffffffffffffffff7203df6b21c6052b53bbf40939d54= 123", + .g_x =3D "0x32c4ae2c1f1981195f9904466a39c9948fe30bbff2660be1715a4589334c7= 4c7", + .g_y =3D "0xbc3736a2f4f6779c59bdcee36b692153d0a9877cc62a474002df32e52139f= 0a0", + .h =3D 1 +}; + +static int __sm2_set_pub_key(struct mpi_ec_ctx *ec, + const void *key, unsigned int keylen); + +static int sm2_ec_ctx_init(struct mpi_ec_ctx *ec) +{ + const struct ecc_domain_parms *ecp =3D &sm2_ecp; + MPI p, a, b; + MPI x, y; + int rc =3D -EINVAL; + + p =3D mpi_scanval(ecp->p); + a =3D mpi_scanval(ecp->a); + b =3D mpi_scanval(ecp->b); + if (!p || !a || !b) + goto free_p; + + x =3D mpi_scanval(ecp->g_x); + y =3D mpi_scanval(ecp->g_y); + if (!x || !y) + goto free; + + rc =3D -ENOMEM; + + ec->Q =3D mpi_point_new(0); + if (!ec->Q) + goto free; + + /* mpi_ec_setup_elliptic_curve */ + ec->G =3D mpi_point_new(0); + if (!ec->G) { + mpi_point_release(ec->Q); + goto free; + } + + mpi_set(ec->G->x, x); + mpi_set(ec->G->y, y); + mpi_set_ui(ec->G->z, 1); + + rc =3D -EINVAL; + ec->n =3D mpi_scanval(ecp->n); + if (!ec->n) { + mpi_point_release(ec->Q); + mpi_point_release(ec->G); + goto free; + } + + ec->h =3D ecp->h; + ec->name =3D ecp->desc; + mpi_ec_init(ec, ecp->model, ecp->dialect, 0, p, a, b); + + rc =3D 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_ec_deinit(ec); + + memset(ec, 0, sizeof(*ec)); +} + +/* 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; + unsigned char *buf; + MPI x, y; + + n =3D MPI_NBYTES(value); + buf =3D kmalloc(n, GFP_KERNEL); + if (!buf) + return -ENOMEM; + + rc =3D mpi_print(GCRYMPI_FMT_USG, buf, n, &n, value); + if (rc) + goto err_freebuf; + + rc =3D -EINVAL; + if (n < 1 || ((n - 1) % 2)) + goto err_freebuf; + /* No support for point compression */ + if (*buf !=3D 0x4) + goto err_freebuf; + + rc =3D -ENOMEM; + n =3D (n - 1) / 2; + x =3D mpi_read_raw_data(buf + 1, n); + if (!x) + goto err_freebuf; + y =3D mpi_read_raw_data(buf + 1 + n, n); + if (!y) + goto err_freex; + + mpi_normalize(x); + mpi_normalize(y); + mpi_set(result->x, x); + mpi_set(result->y, y); + mpi_set_ui(result->z, 1); + + rc =3D 0; + + mpi_free(y); +err_freex: + mpi_free(x); +err_freebuf: + kfree(buf); + return rc; +} + +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 =3D context; + + if (!value || !vlen) + return -EINVAL; + + sig->sig_r =3D 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 =3D context; + + if (!value || !vlen) + return -EINVAL; + + sig->sig_s =3D 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; + int err; + + in =3D mpi_get_buffer(m, &inlen, NULL); + if (!in) + return -EINVAL; + + if (inlen < pbytes) { + /* padding with zero */ + err =3D crypto_shash_update(desc, zero, pbytes - inlen) ?: + crypto_shash_update(desc, in, inlen); + } else if (inlen > pbytes) { + /* skip the starting zero */ + err =3D crypto_shash_update(desc, in + inlen - pbytes, pbytes); + } else { + err =3D crypto_shash_update(desc, in, inlen); + } + + kfree(in); + return err; +} + +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 =3D -EINVAL; + + x =3D mpi_new(0); + y =3D mpi_new(0); + + ret =3D mpi_ec_get_affine(x, y, point, ec) ? -EINVAL : + sm2_z_digest_update(desc, x, pbytes) ?: + sm2_z_digest_update(desc, y, pbytes); + + mpi_free(x); + mpi_free(y); + return ret; +} + +int sm2_compute_z_digest(struct shash_desc *desc, + const void *key, unsigned int keylen, void *dgst) +{ + struct mpi_ec_ctx *ec; + unsigned int bits_len; + unsigned int pbytes; + u8 entl[2]; + int err; + + ec =3D kmalloc(sizeof(*ec), GFP_KERNEL); + if (!ec) + return -ENOMEM; + + err =3D sm2_ec_ctx_init(ec); + if (err) + goto out_free_ec; + + err =3D __sm2_set_pub_key(ec, key, keylen); + if (err) + goto out_deinit_ec; + + bits_len =3D SM2_DEFAULT_USERID_LEN * 8; + entl[0] =3D bits_len >> 8; + entl[1] =3D bits_len & 0xff; + + pbytes =3D MPI_NBYTES(ec->p); + + /* ZA =3D H256(ENTLA | IDA | a | b | xG | yG | xA | yA) */ + err =3D crypto_shash_init(desc); + if (err) + goto out_deinit_ec; + + err =3D crypto_shash_update(desc, entl, 2); + if (err) + goto out_deinit_ec; + + err =3D crypto_shash_update(desc, SM2_DEFAULT_USERID, + SM2_DEFAULT_USERID_LEN); + if (err) + goto out_deinit_ec; + + err =3D 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); + if (err) + goto out_deinit_ec; + + err =3D crypto_shash_final(desc, dgst); + +out_deinit_ec: + sm2_ec_ctx_deinit(ec); +out_free_ec: + kfree(ec); + return err; +} +EXPORT_SYMBOL_GPL(sm2_compute_z_digest); + +static int _sm2_verify(struct mpi_ec_ctx *ec, MPI hash, MPI sig_r, MPI sig= _s) +{ + int rc =3D -EINVAL; + struct gcry_mpi_point sG, tP; + MPI t =3D NULL; + MPI x1 =3D NULL, y1 =3D NULL; + + mpi_point_init(&sG); + mpi_point_init(&tP); + x1 =3D mpi_new(0); + y1 =3D mpi_new(0); + t =3D 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 =3D (r + s) % n, t =3D=3D 0 */ + mpi_addm(t, sig_r, sig_s, ec->n); + if (mpi_cmp_ui(t, 0) =3D=3D 0) + goto leave; + + /* sG + tP =3D (x1, y1) */ + rc =3D -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 =3D (e + x1) % n */ + mpi_addm(t, hash, x1, ec->n); + + /* check R =3D=3D r */ + rc =3D -EKEYREJECTED; + if (mpi_cmp(t, sig_r)) + goto leave; + + rc =3D 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_verify(struct crypto_sig *tfm, + const void *src, unsigned int slen, + const void *digest, unsigned int dlen) +{ + struct mpi_ec_ctx *ec =3D crypto_sig_ctx(tfm); + struct sm2_signature_ctx sig; + MPI hash; + int ret; + + if (unlikely(!ec->Q)) + return -EINVAL; + + sig.sig_r =3D NULL; + sig.sig_s =3D NULL; + ret =3D asn1_ber_decoder(&sm2signature_decoder, &sig, src, slen); + if (ret) + goto error; + + ret =3D -ENOMEM; + hash =3D mpi_read_raw_data(digest, dlen); + if (!hash) + goto error; + + ret =3D _sm2_verify(ec, hash, sig.sig_r, sig.sig_s); + + mpi_free(hash); +error: + mpi_free(sig.sig_r); + mpi_free(sig.sig_s); + return ret; +} + +static int sm2_set_pub_key(struct crypto_sig *tfm, + const void *key, unsigned int keylen) +{ + struct mpi_ec_ctx *ec =3D crypto_sig_ctx(tfm); + + return __sm2_set_pub_key(ec, key, keylen); +} + +static int __sm2_set_pub_key(struct mpi_ec_ctx *ec, + const void *key, unsigned int keylen) +{ + MPI a; + int rc; + + /* include the uncompressed flag '0x04' */ + a =3D mpi_read_raw_data(key, keylen); + if (!a) + return -ENOMEM; + + mpi_normalize(a); + rc =3D sm2_ecc_os2ec(ec->Q, a); + mpi_free(a); + + return rc; +} + +static unsigned int sm2_max_size(struct crypto_sig *tfm) +{ + /* Unlimited max size */ + return PAGE_SIZE; +} + +static int sm2_init_tfm(struct crypto_sig *tfm) +{ + struct mpi_ec_ctx *ec =3D crypto_sig_ctx(tfm); + + return sm2_ec_ctx_init(ec); +} + +static void sm2_exit_tfm(struct crypto_sig *tfm) +{ + struct mpi_ec_ctx *ec =3D crypto_sig_ctx(tfm); + + sm2_ec_ctx_deinit(ec); +} + +static struct sig_alg sm2 =3D { + .verify =3D sm2_verify, + .set_pub_key =3D sm2_set_pub_key, + .max_size =3D sm2_max_size, + .init =3D sm2_init_tfm, + .exit =3D sm2_exit_tfm, + .base =3D { + .cra_name =3D "sm2", + .cra_driver_name =3D "sm2-generic", + .cra_priority =3D 100, + .cra_module =3D THIS_MODULE, + .cra_ctxsize =3D sizeof(struct mpi_ec_ctx), + }, +}; + +static int __init sm2_init(void) +{ + return crypto_register_sig(&sm2); +} + +static void __exit sm2_exit(void) +{ + crypto_unregister_sig(&sm2); +} + +subsys_initcall(sm2_init); +module_exit(sm2_exit); + +MODULE_LICENSE("GPL"); +MODULE_AUTHOR("Tianjia Zhang "); +MODULE_AUTHOR("Gu Bowen "); +MODULE_DESCRIPTION("SM2 generic algorithm"); +MODULE_ALIAS_CRYPTO("sm2-generic"); 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 ::=3D SEQUENCE { + sig_r INTEGER ({ sm2_get_signature_r }), + sig_s INTEGER ({ sm2_get_signature_s }) +} diff --git a/crypto/testmgr.c b/crypto/testmgr.c index 32f753d6c430..9fde36527711 100644 --- a/crypto/testmgr.c +++ b/crypto/testmgr.c @@ -5505,6 +5505,12 @@ static const struct alg_test_desc alg_test_descs[] = =3D { .suite =3D { .hash =3D __VECS(sha512_tv_template) } + }, { + .alg =3D "sm2", + .test =3D alg_test_sig, + .suite =3D { + .sig =3D __VECS(sm2_tv_template) + } }, { .alg =3D "sm3", .test =3D alg_test_hash, diff --git a/crypto/testmgr.h b/crypto/testmgr.h index 32d099ac9e73..68928b4fbd1c 100644 --- a/crypto/testmgr.h +++ b/crypto/testmgr.h @@ -6133,6 +6133,63 @@ static const struct hash_testvec hmac_streebog512_tv= _template[] =3D { }, }; =20 +/* + * SM2 test vectors. + */ +static const struct sig_testvec sm2_tv_template[] =3D { + { /* Generated from openssl */ + .key =3D + "\x04" + "\x8e\xa0\x33\x69\x91\x7e\x3d\xec\xad\x8e\xf0\x45\x5e\x13\x3e\x68" + "\x5b\x8c\xab\x5c\xc6\xc8\x50\xdf\x91\x00\xe0\x24\x73\x4d\x31\xf2" + "\x2e\xc0\xd5\x6b\xee\xda\x98\x93\xec\xd8\x36\xaa\xb9\xcf\x63\x82" + "\xef\xa7\x1a\x03\xed\x16\xba\x74\xb8\x8b\xf9\xe5\x70\x39\xa4\x70", + .key_len =3D 65, + .param_len =3D 0, + .c =3D + "\x30\x45" + "\x02\x20" + "\x70\xab\xb6\x7d\xd6\x54\x80\x64\x42\x7e\x2d\x05\x08\x36\xc9\x96" + "\x25\xc2\xbb\xff\x08\xe5\x43\x15\x5e\xf3\x06\xd9\x2b\x2f\x0a\x9f" + "\x02\x21" + "\x00" + "\xbf\x21\x5f\x7e\x5d\x3f\x1a\x4d\x8f\x84\xc2\xe9\xa6\x4c\xa4\x18" + "\xb2\xb8\x46\xf4\x32\x96\xfa\x57\xc6\x29\xd4\x89\xae\xcc\xda\xdb", + .c_size =3D 71, + .algo =3D OID_SM2_with_SM3, + .m =3D + "\x47\xa7\xbf\xd3\xda\xc4\x79\xee\xda\x8b\x4f\xe8\x40\x94\xd4\x32" + "\x8f\xf1\xcd\x68\x4d\xbd\x9b\x1d\xe0\xd8\x9a\x5d\xad\x85\x47\x5c", + .m_size =3D 32, + .public_key_vec =3D true, + }, + { /* From libgcrypt */ + .key =3D + "\x04" + "\x87\x59\x38\x9a\x34\xaa\xad\x07\xec\xf4\xe0\xc8\xc2\x65\x0a\x44" + "\x59\xc8\xd9\x26\xee\x23\x78\x32\x4e\x02\x61\xc5\x25\x38\xcb\x47" + "\x75\x28\x10\x6b\x1e\x0b\x7c\x8d\xd5\xff\x29\xa9\xc8\x6a\x89\x06" + "\x56\x56\xeb\x33\x15\x4b\xc0\x55\x60\x91\xef\x8a\xc9\xd1\x7d\x78", + .key_len =3D 65, + .param_len =3D 0, + .c =3D + "\x30\x44" + "\x02\x20" + "\xd9\xec\xef\xe8\x5f\xee\x3c\x59\x57\x8e\x5b\xab\xb3\x02\xe1\x42" + "\x4b\x67\x2c\x0b\x26\xb6\x51\x2c\x3e\xfc\xc6\x49\xec\xfe\x89\xe5" + "\x02\x20" + "\x43\x45\xd0\xa5\xff\xe5\x13\x27\x26\xd0\xec\x37\xad\x24\x1e\x9a" + "\x71\x9a\xa4\x89\xb0\x7e\x0f\xc4\xbb\x2d\x50\xd0\xe5\x7f\x7a\x68", + .c_size =3D 70, + .algo =3D OID_SM2_with_SM3, + .m =3D + "\x11\x22\x33\x44\x55\x66\x77\x88\x99\xaa\xbb\xcc\xdd\xee\xff\x00" + "\x12\x34\x56\x78\x9a\xbc\xde\xf0\x12\x34\x56\x78\x9a\xbc\xde\xf0", + .m_size =3D 32, + .public_key_vec =3D true, + }, +}; + /* Example vectors below taken from * http://www.oscca.gov.cn/UpFile/20101222141857786.pdf * diff --git a/include/crypto/sm2.h b/include/crypto/sm2.h new file mode 100644 index 000000000000..a93c6fd395ff --- /dev/null +++ b/include/crypto/sm2.h @@ -0,0 +1,31 @@ +/* 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 + * + * Copyright (c) 2025, Huawei Tech. Co., Ltd. + * Authors: Gu Bowen + */ + +#ifndef _CRYPTO_SM2_H +#define _CRYPTO_SM2_H + +struct shash_desc; + +#if IS_REACHABLE(CONFIG_CRYPTO_SM2) +int sm2_compute_z_digest(struct shash_desc *desc, + const void *key, unsigned int keylen, void *dgst); +#else +static inline int sm2_compute_z_digest(struct shash_desc *desc, + const void *key, unsigned int keylen, + void *dgst) +{ + return -EOPNOTSUPP; +} +#endif + +#endif /* _CRYPTO_SM2_H */ --=20 2.25.1 From nobody Wed Oct 8 09:26:48 2025 Received: from szxga07-in.huawei.com (szxga07-in.huawei.com [45.249.212.35]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id DB94F28BA96; Mon, 30 Jun 2025 13:27:40 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=45.249.212.35 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1751290063; cv=none; b=Zu0NVuRuM4nNLvSDn5bAwxpq6jCzSS0GOXXWaQZDEcouhCDjhFYvwUPmwyCFKD5Fu66f0AxxnAmkG2/W8Ul+zwYC17Q5RZ6VhPrUb+uV+i9PF5aruKHmA1Zuwznedno/2R99bLscg2MUpDZaaaXXpK4MzBDfUDtmPGLWGIBe9c4= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1751290063; c=relaxed/simple; bh=8EakdCfHL6yUQe8UlByAQRH/htDSv8SJZjFICWSy4tw=; h=From:To:CC:Subject:Date:Message-ID:In-Reply-To:References: MIME-Version:Content-Type; b=lpjO6qmGTqIAEPavG0N0NDN9vkk1ydM+hJnXbTXqRYm5GUCShlBG0XJHIL24O/KdY9mAlJAzcrfAbJsG2xAwB2cP6lv6dbCmoIVnhhVCy3myexuwFTc+uzxtG4S15QtscMIxhWyiqe3hI1CcDYPC33Y1IAigZCsdZjQyGDfMlCc= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=quarantine dis=none) header.from=huawei.com; spf=pass smtp.mailfrom=huawei.com; arc=none smtp.client-ip=45.249.212.35 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=quarantine dis=none) header.from=huawei.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=huawei.com Received: from mail.maildlp.com (unknown [172.19.163.44]) by szxga07-in.huawei.com (SkyGuard) with ESMTP id 4bW6Nr3lz4z29dyB; Mon, 30 Jun 2025 21:25:48 +0800 (CST) Received: from kwepemh100007.china.huawei.com (unknown [7.202.181.92]) by mail.maildlp.com (Postfix) with ESMTPS id 1E36F1401E9; Mon, 30 Jun 2025 21:27:33 +0800 (CST) Received: from huawei.com (10.67.174.33) by kwepemh100007.china.huawei.com (7.202.181.92) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.2.1544.11; Mon, 30 Jun 2025 21:27:32 +0800 From: Gu Bowen To: Herbert Xu , David Howells , David Woodhouse , Lukas Wunner , Ignat Korchagin , "David S . Miller" , Jarkko Sakkinen , Maxime Coquelin , Alexandre Torgue , Eric Biggers , "Jason A . Donenfeld" , Ard Biesheuvel , Tianjia Zhang , Dan Carpenter CC: , , , , , Lu Jialin , GONG Ruiqi , Gu Bowen Subject: [PATCH RFC 4/4] crypto/sm2: support SM2-with-SM3 verification of X.509 certificates Date: Mon, 30 Jun 2025 21:39:34 +0800 Message-ID: <20250630133934.766646-5-gubowen5@huawei.com> X-Mailer: git-send-email 2.25.1 In-Reply-To: <20250630133934.766646-1-gubowen5@huawei.com> References: <20250630133934.766646-1-gubowen5@huawei.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable X-ClientProxiedBy: kwepems500001.china.huawei.com (7.221.188.70) To kwepemh100007.china.huawei.com (7.202.181.92) Content-Type: text/plain; charset="utf-8" The digest is calculated during certificate parsing, but the public key of the signing certificate need to be obtained before calculating the digest to correctly calculate the Z value. By attempting to obtain the public key before computing the digest, the feasibility of doing so was tested and verified. Signed-off-by: Gu Bowen --- certs/system_keyring.c | 8 +++++++ crypto/asymmetric_keys/public_key.c | 7 ++++++ crypto/asymmetric_keys/x509_public_key.c | 27 +++++++++++++++++++++++- include/keys/system_keyring.h | 13 ++++++++++++ 4 files changed, 54 insertions(+), 1 deletion(-) diff --git a/certs/system_keyring.c b/certs/system_keyring.c index 9de610bf1f4b..adceb3f0928c 100644 --- a/certs/system_keyring.c +++ b/certs/system_keyring.c @@ -32,6 +32,14 @@ extern __initconst const u8 system_certificate_list[]; extern __initconst const unsigned long system_certificate_list_size; extern __initconst const unsigned long module_cert_size; =20 +struct key *find_asymmetric_pub_key(const struct asymmetric_key_id *id_0, + const struct asymmetric_key_id *id_1, + const struct asymmetric_key_id *id_2) +{ + return find_asymmetric_key(builtin_trusted_keys, id_0, + id_1, id_2, false); +} + /** * restrict_link_by_builtin_trusted - Restrict keyring addition by built-i= n CA * @dest_keyring: Keyring being linked to. diff --git a/crypto/asymmetric_keys/public_key.c b/crypto/asymmetric_keys/p= ublic_key.c index e5b177c8e842..ca0bb32e093a 100644 --- a/crypto/asymmetric_keys/public_key.c +++ b/crypto/asymmetric_keys/public_key.c @@ -134,6 +134,13 @@ software_key_determine_akcipher(const struct public_ke= y *pkey, n =3D snprintf(alg_name, CRYPTO_MAX_ALG_NAME, "%s(%s)", encoding, pkey->pkey_algo); return n >=3D CRYPTO_MAX_ALG_NAME ? -EINVAL : 0; + } else if (strcmp(pkey->pkey_algo, "sm2") =3D=3D 0) { + if (strcmp(encoding, "raw") !=3D 0) + return -EINVAL; + if (!hash_algo) + return -EINVAL; + if (strcmp(hash_algo, "sm3") !=3D 0) + return -EINVAL; } else if (strcmp(pkey->pkey_algo, "ecrdsa") =3D=3D 0) { if (strcmp(encoding, "raw") !=3D 0) return -EINVAL; diff --git a/crypto/asymmetric_keys/x509_public_key.c b/crypto/asymmetric_k= eys/x509_public_key.c index 8409d7d36cb4..62bbc423d632 100644 --- a/crypto/asymmetric_keys/x509_public_key.c +++ b/crypto/asymmetric_keys/x509_public_key.c @@ -7,6 +7,7 @@ =20 #define pr_fmt(fmt) "X.509: "fmt #include +#include #include #include #include @@ -28,6 +29,8 @@ int x509_get_sig_params(struct x509_certificate *cert) struct shash_desc *desc; size_t desc_size; int ret; + struct key *key; + struct public_key *pkey; =20 pr_devel("=3D=3D>%s()\n", __func__); =20 @@ -63,8 +66,30 @@ int x509_get_sig_params(struct x509_certificate *cert) =20 desc->tfm =3D tfm; =20 - ret =3D crypto_shash_digest(desc, cert->tbs, cert->tbs_size, + if (strcmp(cert->pub->pkey_algo, "sm2") =3D=3D 0) { + if (!sig->auth_ids[0] && !sig->auth_ids[1] && !sig->auth_ids[2]) + return -ENOKEY; + + key =3D find_asymmetric_pub_key(sig->auth_ids[0], sig->auth_ids[1], + sig->auth_ids[2]); + if (IS_ERR(key)) + pkey =3D cert->pub; + else + pkey =3D key->payload.data[asym_crypto]; + + ret =3D strcmp(sig->hash_algo, "sm3") !=3D 0 ? -EINVAL : + crypto_shash_init(desc) ?: + sm2_compute_z_digest(desc, pkey->key, + pkey->keylen, sig->digest) ?: + crypto_shash_init(desc) ?: + crypto_shash_update(desc, sig->digest, + sig->digest_size) ?: + crypto_shash_finup(desc, cert->tbs, cert->tbs_size, + sig->digest); + } else { + ret =3D crypto_shash_digest(desc, cert->tbs, cert->tbs_size, sig->digest); + } =20 if (ret < 0) goto error_2; diff --git a/include/keys/system_keyring.h b/include/keys/system_keyring.h index a6c2897bcc63..21b466e5d2f3 100644 --- a/include/keys/system_keyring.h +++ b/include/keys/system_keyring.h @@ -10,6 +10,8 @@ =20 #include =20 +struct asymmetric_key_id; + enum blacklist_hash_type { /* TBSCertificate hash */ BLACKLIST_HASH_X509_TBS =3D 1, @@ -19,6 +21,10 @@ enum blacklist_hash_type { =20 #ifdef CONFIG_SYSTEM_TRUSTED_KEYRING =20 +extern struct key *find_asymmetric_pub_key(const struct asymmetric_key_id = *id_0, + const struct asymmetric_key_id *id_1, + const struct asymmetric_key_id *id_2); + extern int restrict_link_by_builtin_trusted(struct key *keyring, const struct key_type *type, const union key_payload *payload, @@ -30,6 +36,13 @@ int restrict_link_by_digsig_builtin(struct key *dest_key= ring, extern __init int load_module_cert(struct key *keyring); =20 #else +static inline struct key *find_asymmetric_pub_key(const struct asymmetric_= key_id *id_0, + const struct asymmetric_key_id *id_1, + const struct asymmetric_key_id *id_2) +{ + return NULL; +} + #define restrict_link_by_builtin_trusted restrict_link_reject #define restrict_link_by_digsig_builtin restrict_link_reject =20 --=20 2.25.1