reply: reply: a realization of SM2 and questions about my subscription request of mailinglist

Sorry for so long to reply, I tried to fork a branch in gitlab(https://git.lysator.liu.se/nettle/nettle) but failed, seemed that I don’t have enough permissions, or should I push my code in github(https://github.com/gnutls/nettle) ? Here are the replies:

"zhongxuan (A)" zhongxuan2@huawei.com writes:

...

Anyway, I made a realization of SM2, Here is the first part of it, including the curve and sm2_add and sm2_mul in affine coordinate.

Thanks, I'm having a first read, see comments below. It would be good to have a link to the best english-language (and freely available) reference. I think you have told me earlier, and I've found https://datatracker.ietf.org/doc/html/draft-shen-sm2-ecdsa. It would be helpful with a reference in a comment, e.g., at the top of ecc-sm2.c.

Insert a opensource link of this elliptic curve at the top of ecc-sm2.c

...

And if it's convenient to you, I can push the other parts including keygen, crypt and sign.

I think it's a good first step to get basic scalar multiplication working, i.e., ecc_point_mul and ecc_point_mul_g working and tested.

Thus this sm2 is also a 'a + 3 mod p = 0' elliptic curve, the mul_a and mul_g function of secp256r1 can also work. We have tested the result with the geometric method like what in eccdata.c.

For signatures, are they similar to ECDSA, or something different? For encryption, how does that work?

Yes its similar to ECDSA, you can refer to this page: https://datatracker.ietf.org/doc/html/draft-shen-sm2-ecdsa Or there is an official public manual about this curve: http://www.gmbz.org.cn/main/postDetail.html?id=20180724110812 I'm not sure whether could you access these pdfs.

My initial comments on your patch inline below.

Regards, /Niels

...

--- /dev/null +++ b/ecc-sm2.c @@ -0,0 +1,261 @@ +/* ecc-sm2.c

• Compile time constant (but machine dependent) tables.

Anything that is machine dependent should be in ecc-sm2.h, generated by eccdata.

Removed.

...

• Copyright (c) Huawei Technologies Co., Ltd. 2022-2022. All rights reserved.
• This file is part of GNU Nettle.
• GNU Nettle is free software: you can redistribute it and/or
• modify it under the terms of either:

• * the GNU Lesser General Public License as published by the Free
  

•   Software Foundation; either version 3 of the License, or (at your
  

•   option) any later version.
  

• or

• * the GNU General Public License as published by the Free
  

•   Software Foundation; either version 2 of the License, or (at your
  

•   option) any later version.
  

• or both in parallel, as here.
• GNU Nettle 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
• General Public License for more details.
• You should have received copies of the GNU General Public License and
• the GNU Lesser General Public License along with this program. If
• not, see http://www.gnu.org/licenses/.

+*/

+/* Development of Nettle's ECC support was funded by the .SE +Internet Fund. */

+#if HAVE_CONFIG_H +# include "config.h" +#endif

+#include <string.h> +#include <assert.h>

+#include "sm2.h" +#include "sm2-internal.h" +#include "ecc-internal.h" +#include "ecc-sm2.h" +#include "ecc-curve.h"

+const char *nettle_sm2_a = +"fffffffeffffffffffffffffffffffffffffffff00000000fffffffffffffffc"; +const char *nettle_sm2_xG = +"32c4ae2c1f1981195f9904466a39c9948fe30bbff2660be1715a4589334c74c7"; +const char *nettle_sm2_yG = +"bc3736a2f4f6779c59bdcee36b692153d0a9877cc62a474002df32e52139f0a0";

These strings appear unused.

Yep, this base point is unused, removed. The nettle_sm2_a used to check whether a point is in sm2 curve, by checking y^2 = x^3 + ax + b.

...

+static void +ecc_sm2_inv (const struct ecc_modulo *p,

•               mp_limb_t *rp, const mp_limb_t *ap,
  

•               mp_limb_t *scratch) { #define a5m1 scratch 
  

+#define +t0 (scratch + ECC_LIMB_SIZE) #define a15m1 t0 #define a32m1 a5m1 +#define a62m1 (scratch + 2*ECC_LIMB_SIZE) #define a96m1 t0 #define +a3 (scratch + 3*ECC_LIMB_SIZE) #define tp (scratch + +4*ECC_LIMB_SIZE) +/*

• Addition chain for p - 2 = 2^{256} - 2^{224} + 2^{192} + 2^{96} -

+3

• 2^5 - 1 = 1 + 2 (2^4 - 1) = 1 + 2 (2^2+1)(2 + 1) 4 S + 3 M
• 2^{15} - 1 = (2^5 - 1) (1 + 2^5 (1 + 2^5) 10 S + 2 M
• 2^{16} - 1 = 1 + 2 (2^{15} - 1) S + M
• 2^{32} - 1 = (2^{16} + 1) (2^{16} - 1) 16 S + M
• 2^{31} - 1 = (2^{16} - 1) * 2^{15} + 2^{15} - 1
• 2^{62} - 1 = (2^{31} - 1) * 2^{31} + 2^{31} - 1
• 2^{94} - 1 = (2^{62} - 1) * 2^{32} + 2^{32} - 1
• 2^{96} - 1 = (2^{94} - 1) * 2^{2} + 3
• 2^{64} - 2^{32} - 1 = (2^{32} - 2) * 2^{32} + 2^{32} - 1
• 2^{160} - 2^{128} - 1 = (2^{64} - 2^{32} - 1) * 2^{96} + 2^{96} - 1
• 2^{254} - 2^{222} - 2^{94} + 2^{62} - 1 = (2^{160} - 2^{128} - 1) * 2^{94} + 2^{62} - 1
• 2^{256} - 2^{224} - 2^{96} + 2^{64} - 3 = (2^{254} - 2^{222} -
• 2^{94} + 2^{62} - 1) * 2^{2} + 1
• */
• ecc_mod_sqr (p, rp, ap, tp); /* a^2 */
• ecc_mod_mul (p, a3, rp, ap, tp); /* a^3 */
• ecc_mod_pow_2kp1 (p, t0, a3, 2, tp); /* a^{2^4 - 1} */
• ecc_mod_sqr (p, rp, t0, tp); /* a^{2^5 - 2} */
• ecc_mod_mul (p, a5m1, rp, ap, tp); /* a^{2^5 - 1}, a5m1 */
• ecc_mod_pow_2kp1 (p, rp, a5m1, 5, tp); /* a^{2^{10} - 1, a5m1*/
• ecc_mod_pow_2k_mul (p, a15m1, rp, 5, a5m1, tp); /* a^{2^{15} - 1}, a5m1 a15m1 */
• ecc_mod_sqr (p, rp, a15m1, tp); /* a^{2^{16} - 2}, a15m1 */
• ecc_mod_mul (p, rp, rp, ap, tp); /* a^{2^{16} - 1}, a15m1 */
• ecc_mod_pow_2kp1 (p, a32m1, rp, 16, tp); /* a^{2^{32} - 1}, a15m1, a32m1 */
• ecc_mod_pow_2k_mul (p, rp, rp, 15, a15m1, tp); /* a^{2^{31} - 1},
• a15m1 */
• ecc_mod_pow_2kp1 (p, a62m1, rp, 31, tp); /* a^{2^{62} - 1}, a62m1
• */ ecc_mod_pow_2k_mul (p, a96m1, a62m1, 32, a32m1, tp); /*
• a^{2^{94} - 1}, a62m1, a32m1 */ ecc_mod_pow_2k_mul (p, a96m1,
• a96m1, 2, a3, tp); /* a^{2^{96} - 1}, a96m1, a3 */
• ecc_mod_sqr (p, rp, rp, tp); /* a^{2^{32} - 2} */
• ecc_mod_pow_2k_mul (p, rp, rp, 32, a32m1, tp); /* a^{2^{64} -

+2^{32} - 1 */

• ecc_mod_pow_2k_mul (p, rp, rp, 96, a96m1, tp); /* a^{2^{160} -

+2^{128} - 1 */

• ecc_mod_pow_2k_mul (p, rp, rp, 94, a62m1, tp); /* a^{2^{254} -

+2^{222} - 2^{94} + 2^{62} - 1}, a62m1 */

• ecc_mod_pow_2k_mul (p, rp, rp, 2, ap, tp); /* a^{2^{256} - 2^{224}

+- 2^{96} + 2^{64} - 3} */ }

+void +sm2_get_order (mpz_t order) +{

• if (!order->_mp_d)
• return;
• const struct ecc_curve *ecc = nettle_get_sm2();
• mpz_set_n(order, ecc->q.m, ecc->q.size); }

Why is the sm2_get_order needed? It appears unused in the current patch.

Yes, this is a test interface, removed.

...

+static mp_limb_t SM2_P[8] = {

•    0xffffffff, 0xffffffff, 0x00000000, 0xffffffff,
  

•    0xffffffff, 0xffffffff, 0xffffffff, 0xfffffffe, };
  

Is this for 32-bit limb size? On which platform have you tested the code? Should probably use _nettle_sm2.p.m instead.

No, its still a 64-bit limb size, we use it in fast reduction, we will try to use a nettle interface instead.

I'm a bit confused, because this looks like 32-bit limbs, but elsewhere you shift by 32 bits which isn't valid for this limb size.

...

+static int sm2_bn_cmp(const mp_limb_t *a, const mp_limb_t *b) {

•    int i;
  

•    for (i = 7; i >= 0; i--) {
  

•            if (a[i] > b[i])
  

•                    return 1;
  

•            if (a[i] < b[i])
  

•                    return -1;
  

•    }
  

•    return 0;
  

+}

This will not be side-channel silent.

Seems that we can use mpn_cmp instead, though I don’t get the difference between mpn_cmp and this sm2_bn_cmp, is mpn_cmp also not side-channel silent?

...

+static void sm2_bn_sub(mp_limb_t *ret, const mp_limb_t *a, const +mp_limb_t *b) {

•    int i;
  

•    mp_limb_t r[8];
  

•    r[0] = ((uint64_t)1 << 32) + a[0] - b[0];
  

•    for (i = 1; i < 7; i++) {
  

•            r[i] = 0xffffffff + a[i] - b[i] + (r[i - 1] >> 32);
  

•            r[i - 1] &= 0xffffffff;
  

•    }
  

•    r[i] = a[i] - b[i] + (r[i - 1] >> 32) - 1;
  

•    r[i - 1] &= 0xffffffff;
  

•    memcpy(ret, r, 64);
  

+}

Is there some reason the general ecc_mod_sub can't work work?

Seems that it can't work. We use a fast reduction matrix, splitting a 64 bits limb into two 32 bits limbs. I also tried mpn_sub_n but seems it doesn’t work too. I am trying to optimize the calculation or use ecc_mod here instead.

...

+static void +ecc_sm2_modp (const struct ecc_modulo *p, mp_limb_t *rp, mp_limb_t +*xp) {

• uint64_t s[16] = {0};
• uint64_t d[8] = {0};
• uint64_t r[8] = {0};
• for (int i = 0; i < 8; i++) {
• s[2*i] = xp[i] & 0xffffffff;
• s[2*i+1] = xp[i] >> 32;
• }
• r[0] = s[0] + s[8] + s[9] + s[10] + s[11] + s[12] + ((s[13] +
• s[14]
• • s[15]) << 1); r[1] = s[1] + s[9] + s[10] + s[11] + s[12] + s[13]
• • ((s[14] + s[15]) << 1); r[2] = s[2]; r[3] = s[3] + s[8] + s[11]
• • s[12] + s[14] + s[15] + (s[13] << 1); r[4] = s[4] + s[9] + s[12]
• • s[13] + s[15] + (s[14] << 1); r[5] = s[5] + s[10] + s[13] +
• • s[14] (s[15] << 1); r[6] = s[6] + s[11] + s[14] + s[15]; r[7] =
• • s[7] +
• s[8] + s[9] + s[10] + s[11] + s[15] + ((s[12] + s[13] + s[14] +
• s[15]) << 1);
• for (int i = 1; i < 8; i++) {
• r[i] += r[i - 1] >> 32;
• r[i - 1] &= 0xffffffff;
• }
• d[2] = s[8] + s[9] + s[13] + s[14]; d[3] = d[2] >> 32; d[2] &=
• 0xffffffff; sm2_bn_sub(r, r, d);
• while (sm2_bn_cmp(r, SM2_P) >= 0) {
• sm2_bn_sub(r, r, SM2_P);
• }
• rp[0] = (r[0] & 0xffffffff) + ((r[1] & 0xffffffff) << 32); rp[1]
• = (r[2] & 0xffffffff) + ((r[3] & 0xffffffff) << 32); rp[2] = (r[4]
• & 0xffffffff) + ((r[5] & 0xffffffff) << 32); rp[3] = (r[6] &
• 0xffffffff) + ((r[7] & 0xffffffff) << 32); }

I would suggest starting with the general ecc_mod function (I think it should work for the modulo used with sm2). When that is in place, one can add optimized variants for 32-bit and/or 64-bit limbs to speed that up.

Here is a problem, ecc_mod stop in ' assert (bn < mn); ' in ecc-mod.c line 56, is sm2 different from other weierstrass curves or I made some mistakes? To avoid this I still use ecc_sm2_modp but change the cmp functions with mpn functions.

...

+const struct ecc_curve _nettle_sm2 = {

• {
• 256,
• ECC_LIMB_SIZE,
• ECC_BMODP_SIZE,
• ECC_REDC_SIZE,
• 4 * ECC_LIMB_SIZE,
• 4 * ECC_LIMB_SIZE,
• 0,
• ecc_p,
• ecc_Bmodp,
• ecc_Bmodp_shifted,
• ecc_redc_ppm1,
• ecc_pp1h,
• NULL,
• ecc_sm2_modp,
• ecc_sm2_inv,
• NULL,
• NULL,
• },
• {
• 256,
• ECC_LIMB_SIZE,
• ECC_BMODQ_SIZE,
• 0,
• ECC_MOD_INV_ITCH (ECC_LIMB_SIZE),
• 0,
• 0,
• ecc_q,
• ecc_Bmodq,
• ecc_Bmodq_shifted,
• NULL,
• ecc_qp1h,
• NULL,
• NULL,
• ecc_mod_inv,
• NULL,
• NULL,
• },
• ECC_REDC_SIZE == 0,
• ECC_PIPPENGER_K,
• ECC_PIPPENGER_C,
• ECC_ADD_JJA_ITCH (ECC_LIMB_SIZE),
• ECC_ADD_JJJ_ITCH (ECC_LIMB_SIZE),
• ECC_DUP_JJ_ITCH (ECC_LIMB_SIZE),
• ECC_MUL_A_ITCH (ECC_LIMB_SIZE),
• ECC_MUL_G_ITCH (ECC_LIMB_SIZE),
• ECC_J_TO_A_ITCH(ECC_LIMB_SIZE, 4 * ECC_LIMB_SIZE),
• ecc_add_jja,
• ecc_add_jjj,
• ecc_dup_jj,

I had expected pointers to new add and dup functions here, since existing functions assume a = -3.

Thus this sm2's p = 2^256 - x^224 - 2^96 + 2^64 - 1, which is also a 'a + 3 mod p = 0' elliptic curve, the add_jja, add_jjj, dup_jj can also work. We proved it by comparing with geometric method.

...

• ecc_mul_a,
• ecc_mul_g,
• ecc_j_to_a,
• ecc_b,
• ecc_unit,
• ecc_table

+};

+const struct ecc_curve *nettle_get_sm2(void) {

• return &_nettle_sm2;

+} diff --git a/eccdata.c b/eccdata.c index 4d8827f..71a524d 100644 --- a/eccdata.c +++ b/eccdata.c @@ -44,6 +44,9 @@

/* Affine coordinates, for simplicity. Infinity point, i.e., te neutral group element, is represented using the is_zero flag. */

+const char *nettle_sm2_a = +"fffffffeffffffffffffffffffffffffffffffff00000000fffffffffffffffc";

Do I get it right that sm2 uses a weierstrass curve, but with a different a value than the a = -3 used for the other weierstrass curves? For the eccdata program, I would suggest adding the a constant to the struct ecc_curve, and use the same formulas for all the weierstrass curves. E.g, add an argument to ecc_curve_init_str to set a, and let NULL mean the default of -3.

Now we add param a in eccdata first. Besides, I let NULL in EDWARDS curve, which means also -3 although EDWARDS don’t have a param a, would it be fine? Did some changes to ecc_dup to use same formulas in all weierstrass curves.

...

struct ecc_point { int is_zero; @@ -59,6 +62,8 @@ enum ecc_type ECC_TYPE_EDWARDS, /* -x^2 + y^2 = 1 - d x^2 y^2 */ ECC_TYPE_TWISTED_EDWARDS,

• /* y^2 = x^3 + ax + b (mod p) */
• ECC_TYPE_SM2, };

struct ecc_curve @@ -145,64 +150,111 @@ static void ecc_dup (const struct ecc_curve *ecc, struct ecc_point *r, const struct ecc_point *p) {

• if (ecc->type != ECC_TYPE_WEIERSTRASS)
• {

•  ecc_add (ecc, r, p, p);
  

•  return;
  

• }

• if (ecc->type != ECC_TYPE_WEIERSTRASS && ecc->type !=

• ECC_TYPE_SM2) {

• ecc_add (ecc, r, p, p);

• return;

• } if (ecc_zero_p (p)) ecc_set_zero (ecc, r);

• else if (ecc->type == ECC_TYPE_SM2) {

• mpz_t m, t, x, y, a;

• mpz_init (m);

• mpz_init (t);

• mpz_init (x);

• mpz_init (y);

• mpz_init_set_str(a, nettle_sm2_a, 16);

• /* m = (2 y)^-1 */

• mpz_mul_ui (m, p->y, 2);

• mpz_invert (m, m, ecc->p);

• /* t = 3x^2 + a */

• mpz_mul (t, p->x, p->x);

• mpz_mod (t, t, ecc->p);

• mpz_mul_ui (t, t, 3);

• mpz_mod (t, t, ecc->p);

• mpz_add(t, t, a);

• mpz_mod (t, t, ecc->p);

• /* t = t * m */

• mpz_mul (t, t, m);

• mpz_mod (t, t, ecc->p);

• /* x' = t^2 - 2 x */

• mpz_mul (x, t, t);

• mpz_submul_ui (x, p->x, 2);

• mpz_mod (x, x, ecc->p);

• /* y' = (x - x') * t - y */

• mpz_sub (y, p->x, x);

• mpz_mul (y, y, t);

• mpz_sub (y, y, p->y);

• mpz_mod (y, y, ecc->p);

• r->is_zero = 0;

• mpz_swap (x, r->x);

• mpz_swap (y, r->y);

• mpz_clear (m);

• mpz_clear (t);

• mpz_clear (x);

• mpz_clear (y);

• } else

• {

•  mpz_t m, t, x, y;
  

•  mpz_init (m);
  

•  mpz_init (t);
  

•  mpz_init (x);
  

•  mpz_init (y);
  

•  /* m = (2 y)^-1 */
  

•  mpz_mul_ui (m, p->y, 2);
  

•  mpz_invert (m, m, ecc->p);
  

•  /* t = 3 (x^2 - 1) * m */
  

•  mpz_mul (t, p->x, p->x);
  

•  mpz_mod (t, t, ecc->p);
  

•  mpz_sub_ui (t, t, 1);
  

•  mpz_mul_ui (t, t, 3);
  

•  mpz_mul (t, t, m);
  

•  mpz_mod (t, t, ecc->p);
  

•  /* x' = t^2 - 2 x */
  

•  mpz_mul (x, t, t);
  

•  mpz_submul_ui (x, p->x, 2);
  

•  mpz_mod (x, x, ecc->p);
  

•  /* y' = (x - x') * t - y */
  

•  mpz_sub (y, p->x, x);
  

•  mpz_mul (y, y, t);
  

•  mpz_sub (y, y, p->y);
  

•  mpz_mod (y, y, ecc->p);
  

•  r->is_zero = 0;
  

•  mpz_swap (x, r->x);
  

•  mpz_swap (y, r->y);
  

•  mpz_clear (m);
  

•  mpz_clear (t);
  

•  mpz_clear (x);
  

•  mpz_clear (y);
  

• }

• {
• mpz_t m, t, x, y;
• mpz_init (m);
• mpz_init (t);
• mpz_init (x);
• mpz_init (y);
• /* m = (2 y)^-1 */
• mpz_mul_ui (m, p->y, 2);
• mpz_invert (m, m, ecc->p);
• /* t = 3 (x^2 - 1) * m */
• mpz_mul (t, p->x, p->x);
• mpz_mod (t, t, ecc->p);
• mpz_sub_ui (t, t, 1);
• mpz_mul_ui (t, t, 3);
• mpz_mul (t, t, m);
• mpz_mod (t, t, ecc->p);
• /* x' = t^2 - 2 x */
• mpz_mul (x, t, t);
• mpz_submul_ui (x, p->x, 2);
• mpz_mod (x, x, ecc->p);
• /* y' = (x - x') * t - y */
• mpz_sub (y, p->x, x);
• mpz_mul (y, y, t);
• mpz_sub (y, y, p->y);
• mpz_mod (y, y, ecc->p);
• r->is_zero = 0;
• mpz_swap (x, r->x);
• mpz_swap (y, r->y);
• mpz_clear (m);
• mpz_clear (t);
• mpz_clear (x);
• mpz_clear (y);
• }

}

static void ecc_add (const struct ecc_curve *ecc, struct ecc_point *r, const struct ecc_point *p, const struct ecc_point *q) {

• if (ecc->type == ECC_TYPE_WEIERSTRASS)

• if (ecc->type == ECC_TYPE_WEIERSTRASS || ecc->type ==
• ECC_TYPE_SM2) { if (ecc_zero_p (p)) ecc_set (r, q);

@@ -760,6 +812,25 @@ ecc_curve_init (struct ecc_curve *ecc, const char *curve) "c0d8f97ea1ca9472b5d444285d0d4f5b" "32e236f86de51839"); }

• else if (!strcmp (curve, "sm2"))
• {

•  ecc_curve_init_str (ecc, ECC_TYPE_SM2,
  

•    /* p */
  

•    "fffffffeffffffffffffffffffffffff"
  

•    "ffffffff00000000ffffffffffffffff",
  

•    /* b */
  

•    "28e9fa9e9d9f5e344d5a9e4bcf6509a7"
  

•    "f39789f515ab8f92ddbcbd414d940e93",
  

•    /* q (order) */
  

•    "fffffffeffffffffffffffffffffffff"
  

•    "7203df6b21c6052b53bbf40939d54123",
  

•    /* g_x */
  

•    "32c4ae2c1f1981195f9904466a39c994"
  

•    "8fe30bbff2660be1715a4589334c74c7",
  

•    /* g_y */
  

•    "bc3736a2f4f6779c59bdcee36b692153"
  

•    "d0a9877cc62a474002df32e52139f0a0");
  

• } else { fprintf (stderr, "No known curve with name %s\n", curve); diff

--git a/sm2-add.c b/sm2-add.c new file mode 100644 index 0000000..f32676c --- /dev/null +++ b/sm2-add.c @@ -0,0 +1,67 @@ +/* sm2-mul.c

• Copyright (c) Huawei Technologies Co., Ltd. 2022-2022. All rights reserved.
• This file is part of GNU Nettle.
• GNU Nettle is free software: you can redistribute it and/or
• modify it under the terms of either:

• * the GNU Lesser General Public License as published by the Free
  

•   Software Foundation; either version 3 of the License, or (at your
  

•   option) any later version.
  

• or

• * the GNU General Public License as published by the Free
  

•   Software Foundation; either version 2 of the License, or (at your
  

•   option) any later version.
  

• or both in parallel, as here.
• GNU Nettle 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
• General Public License for more details.
• You should have received copies of the GNU General Public License and
• the GNU Lesser General Public License along with this program. If
• not, see http://www.gnu.org/licenses/.

+*/

+#if HAVE_CONFIG_H +# include "config.h" +#endif

+#include <string.h>

+#include "ecc.h" +#include "ecc-internal.h"

+#include "sm2.h" +#include "sm2-internal.h"

+int +sm2_add (struct ecc_point *r, const struct ecc_point *p,

•     const struct ecc_point *q)
  

What's the usecase for this function? If it is needed, it might be better with a general ecc_point_add.

Its just an encapsulation, we will remove it.

...

+{

• const struct ecc_curve *ecc = p->ecc;
• if (!sm2_check_point(p) || !sm2_check_point(q)) {
• return 0;
• }
• mp_size_t itch = 3*SM2_LIMB_SIZE + ecc->mul_itch; mp_limb_t
• *scratch = gmp_alloc_limbs (itch); mp_limb_t *pj = xalloc_limbs
• (3*ecc->p.size); mp_limb_t *qj = xalloc_limbs (3*ecc->p.size);
• ecc_a_to_j (ecc, pj, p->p); ecc_a_to_j (ecc, qj, q->p);
• ecc->add_hhh(p->ecc, scratch, pj, qj, scratch + 3*SM2_LIMB_SIZE);
• ecc->h_to_a (ecc, 0, r->p, scratch, scratch + 3*SM2_LIMB_SIZE);
• gmp_free_limbs (scratch, itch);
• free(pj);
• free(qj);
• return 1;

+} diff --git a/sm2-internal.h b/sm2-internal.h new file mode 100644 index 0000000..adcc379 --- /dev/null +++ b/sm2-internal.h @@ -0,0 +1,69 @@ +/* sm2-internal.h

• Things that are used only by the testsuite and benchmark, and
• not included in the library.

Is that right? The file is included by library files, e.g., ecc-sm2.c.

That’s not accurate, removed this.

...

• Copyright (c) Huawei Technologies Co., Ltd. 2022-2022. All rights reserved.
• This file is part of GNU Nettle.
• GNU Nettle is free software: you can redistribute it and/or
• modify it under the terms of either:

• * the GNU Lesser General Public License as published by the Free
  

•   Software Foundation; either version 3 of the License, or (at your
  

•   option) any later version.
  

• or

• * the GNU General Public License as published by the Free
  

•   Software Foundation; either version 2 of the License, or (at your
  

•   option) any later version.
  

• or both in parallel, as here.
• GNU Nettle 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
• General Public License for more details.
• You should have received copies of the GNU General Public License and
• the GNU Lesser General Public License along with this program. If
• not, see http://www.gnu.org/licenses/.

+*/

+#ifndef SM2_INTERNAL_H_INCLUDED +#define SM2_INTERNAL_H_INCLUDED

+#include <assert.h>

+#include "nettle-meta.h"

+#include "sm2.h"

+#ifdef __cplusplus +extern "C" { +#endif

+#define xalloc nettle_xalloc +#define xalloc_limbs nettle_xalloc_limbs

+#define SM2_LIMB_SIZE 4 +#define SM2_LIMB_BYTES 8

+#define IS_ILLEG_KEY(key) \

• (!(key)) || (((key)->ecc) != &_nettle_sm2) || !((key)->p)

+extern const char *nettle_sm2_a; +extern const char *nettle_sm2_xG; +extern const char *nettle_sm2_yG;

+void *xalloc(size_t size);

+mp_limb_t *xalloc_limbs(mp_size_t n);

Much of this looks questionable to me. SM2_LIMB_BYTES and SM2_LIMB_SIZE are machine dependent. Using corresponding elements of struct ecc_curve would be better than the nettle_sm2_a, nettle_sm2_xG and nettle_sm2_yG strings. (If there's no good place in the current struct ecc_curve to store the a constant, that should be added).

Yep, this should be changed. ALL macros machine dependent moved, I tried add para a in ecc_curve. Here is a problem, in the point check of ecc_point_set and test_ecc_point_valid_p

And xalloc functions are already defined for the testsuite and benchmark.

Removed.

...

+#ifdef __cplusplus +} +#endif

+#endif /* NETTLE_INTERNAL_H_INCLUDED */ diff --git a/sm2-lib.c b/sm2-lib.c new file mode 100644 index 0000000..0fefb20 --- /dev/null +++ b/sm2-lib.c @@ -0,0 +1,63 @@ +/* sm2-lib.c

• Things that are used only by the testsuite and benchmark, and
• not included in the library.

I'd prefer to not have this file. In particular, it's confusing with "lib" in the name when it's not part of the library.

The description is not accurate, file removed.

...

• Copyright (c) Huawei Technologies Co., Ltd. 2022-2022. All rights reserved.
• This file is part of GNU Nettle.
• GNU Nettle is free software: you can redistribute it and/or
• modify it under the terms of either:

• * the GNU Lesser General Public License as published by the Free
  

•   Software Foundation; either version 3 of the License, or (at your
  

•   option) any later version.
  

• or

• * the GNU General Public License as published by the Free
  

•   Software Foundation; either version 2 of the License, or (at your
  

•   option) any later version.
  

• or both in parallel, as here.
• GNU Nettle 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
• General Public License for more details.
• You should have received copies of the GNU General Public License and
• the GNU Lesser General Public License along with this program. If
• not, see http://www.gnu.org/licenses/.

+*/

+#if HAVE_CONFIG_H +# include "config.h" +#endif

+#include <assert.h> +#include <stdlib.h> +#include <stdio.h> +#include <string.h>

+#include "sm2-internal.h" +#include "ecc-internal.h"

+void * +xalloc(size_t size) +{

• void *p = malloc(size);
• if (size && !p) {

•  fprintf(stderr, "Virtual memory exhausted.\n");
  

•  abort();
  

• }
• return p;

+}

+mp_limb_t * +xalloc_limbs (mp_size_t n) +{

• return xalloc (n * sizeof (mp_limb_t)); }

diff --git a/sm2-mul.c b/sm2-mul.c new file mode 100644 index 0000000..f65d196 --- /dev/null +++ b/sm2-mul.c @@ -0,0 +1,64 @@ +/* sm2-mul.c

• Copyright (c) Huawei Technologies Co., Ltd. 2022-2022. All rights reserved.
• This file is part of GNU Nettle.
• GNU Nettle is free software: you can redistribute it and/or
• modify it under the terms of either:

• * the GNU Lesser General Public License as published by the Free
  

•   Software Foundation; either version 3 of the License, or (at your
  

•   option) any later version.
  

• or

• * the GNU General Public License as published by the Free
  

•   Software Foundation; either version 2 of the License, or (at your
  

•   option) any later version.
  

• or both in parallel, as here.
• GNU Nettle 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
• General Public License for more details.
• You should have received copies of the GNU General Public License and
• the GNU Lesser General Public License along with this program. If
• not, see http://www.gnu.org/licenses/.

+*/

+#if HAVE_CONFIG_H +# include "config.h" +#endif

+#include <string.h>

+#include "ecc.h" +#include "ecc-internal.h"

+#include "sm2.h" +#include "sm2-internal.h"

+int +sm2_mul (struct ecc_point *q, const struct ecc_scalar *n,

•     const struct ecc_point *p)
  

+{

• const struct ecc_curve *ecc = p->ecc;
• if (!sm2_check_point(p)) {
• return 0;
• }
• mp_size_t itch = 3*SM2_LIMB_SIZE + p->ecc->mul_itch;
• mp_limb_t *scratch = gmp_alloc_limbs (itch);
• mp_limb_t *pj = xalloc_limbs (3*SM2_LIMB_SIZE); ecc_a_to_j
• (p->ecc, pj, p->p);
• p->ecc->mul(p->ecc, scratch, n->p, pj, scratch + 3*SM2_LIMB_SIZE);
• p->ecc->h_to_a (p->ecc, 0, q->p, scratch, scratch +
• 3*SM2_LIMB_SIZE);
• gmp_free_limbs (scratch, itch);
• free(pj);
• return 1;

+}

I think the general ecc_point_mul (and other ecc_point_* functions) should be used also for sm2. The validation done by sm2_check_point should go in ecc_point_set (currently, handling various curves in that function is a bit messy handling, it would make sense to add a function pointer in ecc_curve for doing the point validation.

These encapsulations are removed. Add an ecc_point_check function from ecc_point_set, I wonder is there necessary to add a function pointer in ecc_curve?

...

diff --git a/sm2-point.c b/sm2-point.c new file mode 100644 index 0000000..0146692 --- /dev/null +++ b/sm2-point.c @@ -0,0 +1,105 @@ +/* sm2-point.c

• Copyright (c) Huawei Technologies Co., Ltd. 2022-2022. All rights reserved.
• This file is part of GNU Nettle.
• GNU Nettle is free software: you can redistribute it and/or
• modify it under the terms of either:

• * the GNU Lesser General Public License as published by the Free
  

•   Software Foundation; either version 3 of the License, or (at your
  

•   option) any later version.
  

• or

• * the GNU General Public License as published by the Free
  

•   Software Foundation; either version 2 of the License, or (at your
  

•   option) any later version.
  

• or both in parallel, as here.
• GNU Nettle 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
• General Public License for more details.
• You should have received copies of the GNU General Public License and
• the GNU Lesser General Public License along with this program. If
• not, see http://www.gnu.org/licenses/.

+*/

+#if HAVE_CONFIG_H +# include "config.h" +#endif

+#include <stdio.h> +#include <string.h> +#include <stdlib.h>

+#include "ecc.h" +#include "ecc-internal.h"

+#include "sm2.h" +#include "sm2-internal.h"

+int +sm2_check_point(const struct ecc_point *point) {

• mpz_t t, x, y, a;
• mpz_t lhs, rhs;
• int res;
• mp_size_t size;
• if (IS_ILLEG_KEY(point) != 0)
• return 0;
• size = point->ecc->p.size;
• /* First check range */
• if (mpn_cmp (point->p, point->ecc->p.m, size) >= 0

•  || mpn_cmp (point->p + size, point->ecc->p.m, size) >= 0)
  

• return 0;
• mpz_init (lhs);
• mpz_init (rhs);
• mpz_init_set_str(a, nettle_sm2_a, 16); mpz_roinit_n (x, point->p,
• size); mpz_roinit_n (y, point->p + size, size);
• mpz_mul (lhs, y, y);
• /* Check y^2 = x^3 + ax + b */
• mpz_mul (rhs, x, x);
• mpz_add (rhs, rhs, a);
• mpz_mul (rhs, rhs, x);
• mpz_add (rhs, rhs, mpz_roinit_n (t, point->ecc->b, size));
• res = mpz_congruent_p (lhs, rhs, mpz_roinit_n (t, point->ecc->p.m,
• size));
• mpz_clear (lhs);
• mpz_clear (rhs);
• mpz_clear (a);
• return res;

+}

+int +sm2_point_set (struct ecc_point *p, const mpz_t x, const mpz_t y) {

• if (p == NULL || p->p == NULL || x == NULL || y == NULL)
• return 0;
• p->ecc = &_nettle_sm2;
• mp_size_t size = p->ecc->p.size;
• mpz_limbs_copy (p->p, x, size);
• mpz_limbs_copy (p->p + size, y, size);
• if (!sm2_check_point(p)) {
• return 0;
• }
• return 1;

+} diff --git a/sm2.h b/sm2.h new file mode 100644 index 0000000..1443b68 --- /dev/null +++ b/sm2.h @@ -0,0 +1,65 @@ +/* sm2.h

• Copyright (c) Huawei Technologies Co., Ltd. 2022-2022. All rights reserved.
• This file is part of GNU Nettle.
• GNU Nettle is free software: you can redistribute it and/or
• modify it under the terms of either:

• * the GNU Lesser General Public License as published by the Free
  

•   Software Foundation; either version 3 of the License, or (at your
  

•   option) any later version.
  

• or

• * the GNU General Public License as published by the Free
  

•   Software Foundation; either version 2 of the License, or (at your
  

•   option) any later version.
  

• or both in parallel, as here.
• GNU Nettle 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
• General Public License for more details.
• You should have received copies of the GNU General Public License and
• the GNU Lesser General Public License along with this program. If
• not, see http://www.gnu.org/licenses/.

+*/

+#ifndef NETTLE_SM2_H_INCLUDED +#define NETTLE_SM2_H_INCLUDED

+#include "nettle-types.h" +#include "nettle-meta.h"

+#include "ecc.h"

+#ifdef __cplusplus +extern "C" { +#endif

+#define sm2_get_order nettle_sm2_get_order #define sm2_check_point +nettle_sm2_check_point #define sm2_point_set nettle_sm2_point_set +#define sm2_add nettle_sm2_add #define sm2_mul nettle_sm2_mul

+void +sm2_get_order(mpz_t order);

+int +sm2_check_point(const struct ecc_point *point);

+int +sm2_point_set (struct ecc_point *p, const mpz_t x, const mpz_t y);

+int +sm2_add (struct ecc_point *r, const struct ecc_point *p,

•     const struct ecc_point *q);
  

+int +sm2_mul (struct ecc_point *q, const struct ecc_scalar *n,

•     const struct ecc_point *p);
  

There are no curve-specific public functions like this for any of the other curves, so it would be nice if we could eliminate them and just use the ecc_point_* functions.

Sure.

...

+const struct ecc_curve * _NETTLE_ATTRIBUTE_PURE +nettle_get_sm2(void);

I think this declaration belongs in ecc_curve.h.

Moved.

...

+#ifdef __cplusplus +} +#endif

+#endif /* NETTLE_SM2_H_INCLUDED */

diff --git a/testsuite/Makefile.in b/testsuite/Makefile.in index c266282..6bda2b7 100644 --- a/testsuite/Makefile.in +++ b/testsuite/Makefile.in @@ -56,7 +56,8 @@ TS_HOGWEED_SOURCES = sexp-test.c sexp-format-test.c \ eddsa-compress-test.c eddsa-sign-test.c \ eddsa-verify-test.c ed25519-test.c ed448-test.c \ gostdsa-sign-test.c gostdsa-verify-test.c \

•      gostdsa-keygen-test.c gostdsa-vko-test.c
  

•      gostdsa-keygen-test.c gostdsa-vko-test.c \
  

•      sm2-base-test.c \
  
  

TS_SOURCES = $(TS_NETTLE_SOURCES) $(TS_HOGWEED_SOURCES) CXX_SOURCES = cxx-test.cxx diff --git a/testsuite/sm2-base-test.c b/testsuite/sm2-base-test.c new file mode 100644 index 0000000..be03970 --- /dev/null +++ b/testsuite/sm2-base-test.c @@ -0,0 +1,161 @@ +#include "testutils.h"

+char *order = +"fffffffeffffffffffffffffffffffff7203df6b21c6052b53bbf40939d54123";

If you add sm2 to the list ecc_curves in testutils.c, existing ecc tests will test sm2 as well. You will need to also update the test_ecc_point_valid_p function and the ecc_ref list in the same file.

Already added, seemed the ecc_mod is not compatible with sm2, I'm trying to figured out.

...

+char *pkey = +"81a2088f008d0e28dd4add66041cf1050cbaf053ab48f4284eb701152be5c310"; +char *xG = +"8ffdbc04ac27f21a41c878e171294962150fa9b3dece424d41abfa869260bbf0"; +char *yG = +"a6648a20e162a7ac07597f199d722ff965cfdfab1744aed669565b11bcf15cfe"; +char *xR = +"3e5641b3e68eb47e6fae1271057e1ea0faedbb49df0d690722eaca6e45f5a76c"; +char *yR = +"d0b0bf0d16a1e4dbc814a6e7b53c07a84997660b7ed0fa0cdeb93bf12000cdf6";

+char *Px = +"8070905f2cf1118ec1d41a0d07dd8dd4ac663bdbe4ad85df101d0baa875d4699"; +char *Py = +"5a947c2c3b2a4bf6113e4e609190209b64f672ddca99b6a7dbf55e2fbf7019a3"; +char *Qx = +"3dd60d9474b46d903f3daf7f532eb9e81a5ea97e2676dfca39493a218a223feb"; +char *Qy = +"dd8fe0b3cf91c793d1df27a30f707d5d46b170478e210de110f6954749b40994"; +char *Rx = +"df86af4b5b7830ac4d6730e93bc3a4dd67e303c3e2824eb76dc61b26e2884f7f"; +char *Ry = +"23d8e385c6f7aea20d38df11de924427b3cea394e648e4b19b4ba086addc490a";

+char *gx = +"32C4AE2C1F1981195F9904466A39C9948FE30BBFF2660BE1715A4589334C74C7"; +char *gy = +"BC3736A2F4F6779C59BDCEE36B692153D0A9877CC62A474002DF32E52139F0A0";

+void sm2_point_print (struct ecc_point *p); void test_get_order +(void); void test_add (void); void test_mul (void);

+void +sm2_point_print (struct ecc_point *p) {

• char str[1024];
• mpz_t x, y;
• mpz_init (x);
• mpz_init (y);
• ecc_point_get(p, x, y);
• mpz_get_str(str, 16, x);
• printf("Px : %s\n", str);
• mpz_get_str(str, 16, y);
• printf("Py : %s\n", str);
• mpz_clear(x);
• mpz_clear(y);

+}

+void +test_get_order (void) +{

• int ret = 0;
• mpz_t r, R;
• mpz_init(r);
• mpz_init_set_str(R, order, 16);
• sm2_get_order(r);
• ret = mpz_cmp(r, R);
• ASSERT(ret == 0);
• mpz_clear(r);
• mpz_clear(R);

+}

+void +test_get_order_NULL (void) +{

• mpz_t r;
• mpz_init(r);
• r->_mp_d = NULL;
• sm2_get_order(r);
• mpz_clear(r);

+}

+void +test_add (void) +{

• int ret = 0;
• const struct ecc_curve *ecc = nettle_get_sm2();
• struct ecc_point pointp, pointq, Res;
• mpz_t x, y;
• ecc_point_init (&pointp, ecc);
• ecc_point_init (&pointq, ecc);
• ecc_point_init (&Res, ecc);
• mpz_init (x);
• mpz_init (y);
• mpz_set_str(x, Px, 16);
• mpz_set_str(y, Py, 16);
• sm2_point_set(&pointp, x, y);
• mpz_set_str(x, Qx, 16);
• mpz_set_str(y, Qy, 16);
• sm2_point_set(&pointq, x, y);
• sm2_add(&Res, &pointp, &pointq);
• if (verbose)
• sm2_point_print (&Res);
• mpz_set_str(x, Rx, 16);
• mpz_set_str(y, Ry, 16);
• sm2_point_set(&pointq, x, y);
• ret = mpn_cmp(Res.p, pointq.p, SM2_LIMB_BYTES); ASSERT(ret == 0);
• ecc_point_clear(&pointp);
• ecc_point_clear(&pointq);
• ecc_point_clear(&Res);
• mpz_clear (x);
• mpz_clear (y);

+}

+void +test_mul (void) +{

• int ret = 0;
• const struct ecc_curve *ecc = nettle_get_sm2();
• struct ecc_point pub, pr, Res;
• struct ecc_scalar key;
• mpz_t x, y;
• ecc_point_init (&pub, ecc);
• ecc_point_init (&pr, ecc);
• ecc_point_init (&Res, ecc);
• ecc_scalar_init (&key, ecc);
• mpz_init (x);
• mpz_init (y);
• mpz_set_str(x, pkey, 16);
• ecc_scalar_set(&key, x);
• mpz_set_str(x, xG, 16);
• mpz_set_str(y, yG, 16);
• sm2_point_set(&pub, x, y);
• sm2_mul(&pr, &key, &pub);
• if (verbose)
• sm2_point_print (&pr);
• mpz_set_str(x, xR, 16);
• mpz_set_str(y, yR, 16);
• sm2_point_set(&Res, x, y);
• ret = mpn_cmp(Res.p, pr.p, SM2_LIMB_BYTES); ASSERT(ret == 0);
• ecc_point_clear(&pub);
• ecc_point_clear(&pr);
• ecc_point_clear(&Res);
• ecc_scalar_clear(&key);
• mpz_clear (x);
• mpz_clear (y);

+}

+void +test_main (void) +{

• test_get_order();
• test_get_order_NULL();
• test_add();
• test_mul();

+} diff --git a/testsuite/testutils.h b/testsuite/testutils.h index 3e23978..c2cf5e1 100644 --- a/testsuite/testutils.h +++ b/testsuite/testutils.h @@ -22,6 +22,8 @@ # include "ecc.h" # include "ecc-internal.h" # include "ecdsa.h" +# include "sm2.h" +# include "sm2-internal.h" # include "gmp-glue.h" # if NETTLE_USE_MINI_GMP # include "knuth-lfib.h"

-- Niels Möller. PGP key CB4962D070D77D7FCB8BA36271D8F1FF368C6677. Internet email is subject to wholesale government surveillance.