summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorMatthias Schiffer <mschiffer@universe-factory.net>2016-03-19 00:47:14 +0100
committerMatthias Schiffer <mschiffer@universe-factory.net>2016-03-19 00:51:39 +0100
commitbb87f7b0e81b89104221b7558e9676b6f176d74f (patch)
tree4dc391a758a74b856154091274157d5a2397644f
parent26cbc55f783b5ab6541f24c8f69f595595125aca (diff)
downloadlibuecc-bb87f7b0e81b89104221b7558e9676b6f176d74f.zip
libuecc-bb87f7b0e81b89104221b7558e9676b6f176d74f.tar
Optimize ecc_25519_scalarmult_base
We can elide one multiplication assuming that Z == 1 for the default base.
-rw-r--r--src/ec25519.c52
1 files changed, 50 insertions, 2 deletions
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);
}