From bb87f7b0e81b89104221b7558e9676b6f176d74f Mon Sep 17 00:00:00 2001 From: Matthias Schiffer Date: Sat, 19 Mar 2016 00:47:14 +0100 Subject: Optimize ecc_25519_scalarmult_base We can elide one multiplication assuming that Z == 1 for the default base. --- src/ec25519.c | 52 ++++++++++++++++++++++++++++++++++++++++++++++++++-- 1 file changed, 50 insertions(+), 2 deletions(-) (limited to 'src') diff --git a/src/ec25519.c b/src/ec25519.c index ad43f30..0ed3741 100644 --- a/src/ec25519.c +++ b/src/ec25519.c @@ -842,6 +842,38 @@ void ecc_25519_add(ecc_25519_work_t *out, const ecc_25519_work_t *in1, const ecc mult(out->Z, F, G); } +/** Adds two points of the Elliptic Curve, assuming that in2->Z == 1 */ +static void ecc_25519_add1(ecc_25519_work_t *out, const ecc_25519_work_t *in1, const ecc_25519_work_t *in2) { + const uint32_t j = UINT32_C(60833); + const uint32_t k = UINT32_C(121665); + uint32_t A[32], B[32], C[32], D[32], E[32], F[32], G[32], H[32], t0[32], t1[32]; + + sub(t0, in1->Y, in1->X); + mult_int(t1, j, t0); + sub(t0, in2->Y, in2->X); + mult(A, t0, t1); + + add(t0, in1->Y, in1->X); + mult_int(t1, j, t0); + add(t0, in2->Y, in2->X); + mult(B, t0, t1); + + mult_int(t0, k, in2->T); + mult(C, in1->T, t0); + + mult_int(D, 2*j, in1->Z); + + sub(E, B, A); + add(F, D, C); + sub(G, D, C); + add(H, B, A); + + mult(out->X, E, F); + mult(out->Y, G, H); + mult(out->T, E, H); + mult(out->Z, F, G); +} + void ecc_25519_sub(ecc_25519_work_t *out, const ecc_25519_work_t *in1, const ecc_25519_work_t *in2) { ecc_25519_work_t in2_neg; @@ -874,9 +906,25 @@ void ecc_25519_scalarmult(ecc_25519_work_t *out, const ecc_int256_t *n, const ec } void ecc_25519_scalarmult_base_bits(ecc_25519_work_t *out, const ecc_int256_t *n, unsigned bits) { - ecc_25519_scalarmult_bits(out, n, &ecc_25519_work_default_base, bits); + ecc_25519_work_t Q2, Q2p; + ecc_25519_work_t cur = ecc_25519_work_identity; + int b, pos; + + if (bits > 256) + bits = 256; + + for (pos = bits - 1; pos >= 0; --pos) { + b = n->p[pos / 8] >> (pos & 7); + b &= 1; + + ecc_25519_double(&Q2, &cur); + ecc_25519_add1(&Q2p, &Q2, &ecc_25519_work_default_base); + selectw(&cur, &Q2, &Q2p, b); + } + + *out = cur; } void ecc_25519_scalarmult_base(ecc_25519_work_t *out, const ecc_int256_t *n) { - ecc_25519_scalarmult(out, n, &ecc_25519_work_default_base); + ecc_25519_scalarmult_base_bits(out, n, 256); } -- cgit v1.2.3