bitwiseshiftleft / sjcl

Stanford Javascript Crypto Library
http://bitwiseshiftleft.github.com/sjcl/
Other
7.18k stars 986 forks source link

Speed increase for first time ecc multiply #390

Closed Sc00bz closed 5 years ago

Sc00bz commented 5 years ago

Instead of doing 14 field inverts it does 1 field invert and 39 field multiplies.

I ran benchmarks and it's 1.8x faster on P-256 and 2.3x faster on P-521. Basically ran this multiple times on the old and new code and took averages.

k = new sjcl.bn("0123456789abcdef0123456789abcdef0123456789abcdef0123456789abcdef");
p0 = sjcl.ecc.curves.c256.G.mult(k);
p1 = sjcl.ecc.curves.c256.G.mult(k);
p2 = sjcl.ecc.curves.c256.G.mult(k);
p3 = sjcl.ecc.curves.c256.G.mult(k);
p4 = sjcl.ecc.curves.c256.G.mult(k);
s = performance.now();
p0.mult(k);
p1.mult(k);
p2.mult(k);
p3.mult(k);
p4.mult(k);
e = performance.now();
console.log(e - s);
k = new sjcl.bn("0123456789abcdef0123456789abcdef0123456789abcdef0123456789abcdef0123456789abcdef0123456789abcdef0123456789abcdef0123456789abcdef123");
p0 = sjcl.ecc.curves.c521.G.mult(k);
p1 = sjcl.ecc.curves.c521.G.mult(k);
p2 = sjcl.ecc.curves.c521.G.mult(k);
p3 = sjcl.ecc.curves.c521.G.mult(k);
p4 = sjcl.ecc.curves.c521.G.mult(k);
s = performance.now();
p0.mult(k);
p1.mult(k);
p2.mult(k);
p3.mult(k);
p4.mult(k);
e = performance.now();
console.log(e - s);
ggozad commented 5 years ago

This is a great enhancement. Tested with own tests as well and delivers a significant increase in speed. I have reviewed it to my ability and found no problems with the code, how can we get it merged?

Sc00bz commented 5 years ago

I'm pretty sure SJCL is no longer updated unless there's a bug like the fix for v1.0.8. We could try pinging the maintainers.