Bigint
-libraries for Javascript
Having a leet second here.
Arithmetic on arbitrarily big natural numbers in Javascript is my current pet project (guess where this is going). Not a lot of people are doing it, because it tends to be slow. I've found four implementations floating around the Web so far:
- by David Shapiro: http://ohdave.com/rsa/
- by Leemon Baird: http://www.leemon.com/crypto/BigInt.html
- by Tom Wu, notably used by Google as one of their V8 benchmarks: http://www-cs-students.stanford.edu/~tjw/jsbn/
- by Masanao Izumo: http://www.onicos.com/staff/iz/amuse/javascript/expert/BigInt.txt
A bunch of nice pointers for possible optimizations can be found in a post on StackOverflow by someone apparently looking to implement something Diffie-Hellmanish:
Specifically:
- Hasenplaugh (gotta love the name) et al. have a faster variant of Barret reduction. (Also: talk slides.)
- A run-down of performance characteristics of different reduction methods by Johnson et al.
- Microsoft Research combines Karatsuba and Montgomery on FPGAs
Unrelated but discovered along the way:
- The
Stanford Javascript Crypto Library
appears to have a nice implementation of AES and some friends: http://bitwiseshiftleft.github.com/sjcl/