diff options
author | Niels Möller <nisse@lysator.liu.se> | 2020-11-03 20:05:49 +0100 |
---|---|---|
committer | Niels Möller <nisse@lysator.liu.se> | 2020-11-03 20:05:49 +0100 |
commit | 1b954ce1dd4b82c4f5e5efac2aa6ce0575402a1e (patch) | |
tree | 03d2413b4a103f91679bce23847e7ef4b9483faa | |
parent | 77490b93b7dff520646f1bee9280447c0af1242a (diff) | |
download | nettle-1b954ce1dd4b82c4f5e5efac2aa6ce0575402a1e.tar.gz |
Reduce scratch need for ecc_add_th
-rw-r--r-- | ChangeLog | 3 | ||||
-rw-r--r-- | ecc-add-th.c | 52 | ||||
-rw-r--r-- | ecc-internal.h | 2 |
3 files changed, 29 insertions, 28 deletions
@@ -1,7 +1,8 @@ 2020-11-03 Niels Möller <nisse@lysator.liu.se> * ecc-add-eh.c (ecc_add_eh): Reduce scratch need. - * ecc-internal.h (ECC_ADD_EH_ITCH): Now 4*size. + * ecc-add-th.c (ecc_add_th): Analogous changes. + * ecc-internal.h (ECC_ADD_EH_ITCH, ECC_ADD_TH_ITCH): Now 4*size. 2020-11-02 Niels Möller <nisse@lysator.liu.se> diff --git a/ecc-add-th.c b/ecc-add-th.c index 92028052..e99e0763 100644 --- a/ecc-add-th.c +++ b/ecc-add-th.c @@ -76,38 +76,38 @@ ecc_add_th (const struct ecc_curve *ecc, We have different sign for E, hence swapping F and G, because our ecc->b corresponds to -b above. */ -#define C (scratch) -#define D (scratch + 1*ecc->p.size) -#define T (scratch + 2*ecc->p.size) -#define E (scratch + 3*ecc->p.size) -#define B (scratch + 4*ecc->p.size) -#define F D -#define G E - - ecc_mod_mul (&ecc->p, C, x1, x2, C); - ecc_mod_mul (&ecc->p, D, y1, y2, D); +#define T scratch +#define E (scratch + 1*ecc->p.size) +#define F E +#define C (scratch + 2*ecc->p.size) +#define D (scratch + 3*ecc->p.size) +#define B D + + /* Use T as scratch, clobber E */ + ecc_mod_mul (&ecc->p, C, x1, x2, T); /* C */ + ecc_mod_mul (&ecc->p, D, y1, y2, T); /* C, D */ ecc_mod_add (&ecc->p, x3, x1, y1); ecc_mod_add (&ecc->p, y3, x2, y2); - ecc_mod_mul (&ecc->p, T, x3, y3, T); + ecc_mod_mul (&ecc->p, T, x3, y3, T); /* C, D, T */ ecc_mod_sub (&ecc->p, T, T, C); ecc_mod_sub (&ecc->p, T, T, D); - ecc_mod_mul (&ecc->p, x3, C, D, x3); - ecc_mod_mul (&ecc->p, E, x3, ecc->b, E); + /* Can now use x3 as scratch, without breaking in-place operation. */ + ecc_mod_mul (&ecc->p, T, T, z1, x3); - ecc_mod_add (&ecc->p, C, D, C); - ecc_mod_sqr (&ecc->p, B, z1, B); - ecc_mod_sub (&ecc->p, F, B, E); - ecc_mod_add (&ecc->p, G, B, E); + ecc_mod_mul (&ecc->p, E, C, D, x3); /* C, D, T, E */ + ecc_mod_mul (&ecc->p, E, E, ecc->b, x3); + + ecc_mod_add (&ecc->p, C, D, C); /* C, T, E */ + ecc_mod_mul (&ecc->p, C, C, z1, x3); - /* x3 */ - ecc_mod_mul (&ecc->p, B, G, T, B); - ecc_mod_mul (&ecc->p, x3, B, z1, x3); + ecc_mod_sqr (&ecc->p, B, z1, x3); /* C, T, E, B */ + ecc_mod_add (&ecc->p, x3, B, E); /* C, T, G */ + ecc_mod_sub (&ecc->p, F, B, E); - /* y3 */ - ecc_mod_mul (&ecc->p, B, F, z1, B); - ecc_mod_mul (&ecc->p, y3, B, C, y3); /* Clobbers z1 in case r == p. */ + /* Can now use y3 as scratch, without breaking in-place operation. */ + ecc_mod_mul (&ecc->p, y3, C, F, y3); /* T G */ - /* z3 */ - ecc_mod_mul (&ecc->p, B, F, G, B); - mpn_copyi (z3, B, ecc->p.size); + /* Can use C--D as scratch */ + ecc_mod_mul (&ecc->p, z3, x3, F, C); /* T */ + ecc_mod_mul (&ecc->p, x3, x3, T, C); } diff --git a/ecc-internal.h b/ecc-internal.h index abe25f64..8aa5f7ec 100644 --- a/ecc-internal.h +++ b/ecc-internal.h @@ -451,7 +451,7 @@ curve448_eh_to_x (mp_limb_t *xp, const mp_limb_t *p, #define ECC_ADD_JJJ_ITCH(size) (8*(size)) #define ECC_ADD_EH_ITCH(size) (4*(size)) #define ECC_ADD_EHH_ITCH(size) (7*(size)) -#define ECC_ADD_TH_ITCH(size) (6*(size)) +#define ECC_ADD_TH_ITCH(size) (4*(size)) #define ECC_ADD_THH_ITCH(size) (7*(size)) #define ECC_MUL_G_ITCH(size) (9*(size)) #define ECC_MUL_G_EH_ITCH(size) (9*(size)) |