Positive value for ECC (was: ecc: effort so that we can enable barret reduction)
NIIBE Yutaka
gniibe at fsij.org
Tue Apr 5 04:46:59 CEST 2016
On 12/09/2015 12:12 PM, NIIBE Yutaka wrote:
> Following patch is the one which allow a user to enable
> GCRYPT_BARRETT. With this patch, it goes well for make check.
>
> IIUC, the implementation of Barrett reduction assumes positive MPI.
>
> It would be worth to consider applying this when someone claims it
> doesn't work with GCRYPT_BARRETT.
I think that it's worth to keep the value as positive for ECC
computation (even if we don't enable GCRYPT_BARRETT).
Here is a patch to keep the value positive in ECC computation.
I'm going to commit this if no objection.
diff --git a/cipher/ecc-curves.c b/cipher/ecc-curves.c
index 91f29cc..3488ed3 100644
--- a/cipher/ecc-curves.c
+++ b/cipher/ecc-curves.c
@@ -560,9 +560,17 @@ _gcry_ecc_fill_in_curve (unsigned int nbits, const char *name,
if (!curve->p)
curve->p = scanval (domain_parms[idx].p);
if (!curve->a)
- curve->a = scanval (domain_parms[idx].a);
+ {
+ curve->a = scanval (domain_parms[idx].a);
+ if (curve->a->sign)
+ mpi_add (curve->a, curve->p, curve->a);
+ }
if (!curve->b)
- curve->b = scanval (domain_parms[idx].b);
+ {
+ curve->b = scanval (domain_parms[idx].b);
+ if (curve->b->sign)
+ mpi_add (curve->b, curve->p, curve->b);
+ }
if (!curve->n)
curve->n = scanval (domain_parms[idx].n);
if (!curve->h)
diff --git a/cipher/ecc-eddsa.c b/cipher/ecc-eddsa.c
index 2a52b78..f91f848 100644
--- a/cipher/ecc-eddsa.c
+++ b/cipher/ecc-eddsa.c
@@ -251,7 +251,7 @@ _gcry_ecc_eddsa_recover_x (gcry_mpi_t x, gcry_mpi_t y, int sign, mpi_ec_t ec)
mpi_mulm (t, x, x, ec->p);
mpi_mulm (t, t, v, ec->p);
/* -t == u ? x = x * sqrt(-1) */
- mpi_neg (t, t);
+ mpi_sub (t, ec->p, t);
if (!mpi_cmp (t, u))
{
static gcry_mpi_t m1; /* Fixme: this is not thread-safe. */
@@ -263,7 +263,7 @@ _gcry_ecc_eddsa_recover_x (gcry_mpi_t x, gcry_mpi_t y, int sign, mpi_ec_t ec)
mpi_mulm (t, x, x, ec->p);
mpi_mulm (t, t, v, ec->p);
/* -t == u ? x = x * sqrt(-1) */
- mpi_neg (t, t);
+ mpi_sub (t, ec->p, t);
if (!mpi_cmp (t, u))
rc = GPG_ERR_INV_OBJ;
}
@@ -835,7 +835,7 @@ _gcry_ecc_eddsa_verify (gcry_mpi_t input, ECC_public_key *pkey,
_gcry_mpi_ec_mul_point (&Ia, s, &pkey->E.G, ctx);
_gcry_mpi_ec_mul_point (&Ib, h, &Q, ctx);
- _gcry_mpi_neg (Ib.x, Ib.x);
+ _gcry_mpi_sub (Ib.x, ctx->p, Ib.x);
_gcry_mpi_ec_add_points (&Ia, &Ia, &Ib, ctx);
rc = _gcry_ecc_eddsa_encodepoint (&Ia, ctx, s, h, 0, &tbuf, &tlen);
if (rc)
diff --git a/cipher/ecc.c b/cipher/ecc.c
index 8dbf5bd..759ca42 100644
--- a/cipher/ecc.c
+++ b/cipher/ecc.c
@@ -783,10 +783,7 @@ ecc_check_secret_key (gcry_sexp_t keyparms)
curvename = sexp_nth_string (l1, 1);
if (curvename)
{
- rc = _gcry_ecc_update_curve_param (curvename,
- &sk.E.model, &sk.E.dialect,
- &sk.E.p, &sk.E.a, &sk.E.b,
- &mpi_g, &sk.E.n, &sk.E.h);
+ rc = _gcry_ecc_fill_in_curve (0, curvename, &sk.E, NULL);
if (rc)
goto leave;
}
diff --git a/mpi/ec.c b/mpi/ec.c
index f0b8374..26dd947 100644
--- a/mpi/ec.c
+++ b/mpi/ec.c
@@ -275,8 +275,9 @@ ec_addm (gcry_mpi_t w, gcry_mpi_t u, gcry_mpi_t v, mpi_ec_t ctx)
static void
ec_subm (gcry_mpi_t w, gcry_mpi_t u, gcry_mpi_t v, mpi_ec_t ec)
{
- (void)ec;
mpi_sub (w, u, v);
+ while (w->sign)
+ mpi_add (w, w, ec->p);
/*ec_mod (w, ec);*/
}
@@ -811,10 +812,7 @@ dup_point_edwards (mpi_point_t result, mpi_point_t point, mpi_ec_t ctx)
/* E = aC */
if (ctx->dialect == ECC_DIALECT_ED25519)
- {
- mpi_set (E, C);
- _gcry_mpi_neg (E, E);
- }
+ mpi_sub (E, ctx->p, C);
else
ec_mulm (E, ctx->a, C, ctx);
@@ -1092,11 +1090,7 @@ add_points_edwards (mpi_point_t result,
/* Y_3 = A · G · (D - aC) */
if (ctx->dialect == ECC_DIALECT_ED25519)
{
- /* Using ec_addm (Y3, D, C, ctx) is possible but a litte bit
- slower because a subm does currently skip the mod step. */
- mpi_set (Y3, C);
- _gcry_mpi_neg (Y3, Y3);
- ec_subm (Y3, D, Y3, ctx);
+ ec_addm (Y3, D, C, ctx);
}
else
{
@@ -1218,7 +1212,7 @@ sub_points_edwards (mpi_point_t result,
{
mpi_point_t p2i = _gcry_mpi_point_new (0);
point_set (p2i, p2);
- _gcry_mpi_neg (p2i->x, p2i->x);
+ mpi_sub (p2i->x, ctx->p, p2i->x);
add_points_edwards (result, p1, p2i, ctx);
_gcry_mpi_point_release (p2i);
}
@@ -1538,10 +1532,7 @@ _gcry_mpi_ec_curve_point (gcry_mpi_point_t point, mpi_ec_t ctx)
ec_pow2 (x, x, ctx);
ec_pow2 (y, y, ctx);
if (ctx->dialect == ECC_DIALECT_ED25519)
- {
- mpi_set (w, x);
- _gcry_mpi_neg (w, w);
- }
+ mpi_sub (w, ctx->p, x);
else
ec_mulm (w, ctx->a, x, ctx);
ec_addm (w, w, y, ctx);
diff --git a/tests/t-mpi-point.c b/tests/t-mpi-point.c
index 55c6b66..84da7cc 100644
--- a/tests/t-mpi-point.c
+++ b/tests/t-mpi-point.c
@@ -130,8 +130,8 @@ static struct
{
"Ed25519",
"0x7FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFED",
- "-0x01",
- "-0x2DFC9311D490018C7338BF8688861767FF8FF5B2BEBE27548A14B235ECA6874A",
+ "0x7FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEC",
+ "0x52036CEE2B6FFE738CC740797779E89800700A4D4141D8AB75EB4DCA135978A3",
"0x1000000000000000000000000000000014DEF9DEA2F79CD65812631A5CF5D3ED",
"0x216936D3CD6E53FEC0A4E231FDD6DC5C692CC7609525A7B2C9562D608F25D51A",
"0x6666666666666666666666666666666666666666666666666666666666666658",
--
More information about the Gcrypt-devel
mailing list