Quote from: piuk on August 14, 2012, 09:49:55 AM

10 BTC bounty for anyone who can finish the function below (depends on bitcoin-js) and produce a verifyMessage as well.

I implemented this as you asked:

https://github.com/bitcoinjs/bitcoinjs-lib/commit/9b2f94a028a7bc9bed94e0722563e9ff1d8e8db8

When ErebusBat asked for this on IRC it seemed like a fairly innocent feature request, I had no idea what I was getting myself into. A few hours later I was implementing the Tonelli-Shanks algorithm (another JavaScript first I think?) and calculating Legendre symbols.

The reason for all the complexity? Bitcoin's message signing facility uses compact signatures which use public key extraction to recover the pubkey from the signature. The Bitcoin core devs happily do their little calls out to the OpenSSL API, not realizing they just pulled in pages worth of algorithms.

Public key extraction is also very computationally expensive. Generating compact signatures is even worse, as the algorithm does 1-4 test verifications while signing. There are some more optimizations I can do, but this will almost certainly be too slow to run on smartphones. (Unless you find a way to hook up BitcoinJS' BigInt to a native big integer implementation of course.)

There is still one bug I have to figure out related to our implementation of Shamir's trick. Hopefully I'll be able to do that this weekend. We could really use a proper suite of unit tests for bitcoinjs-lib. Undecided

(The four test cases at the bottom of message.js will obviously be removed once I officially release this.)