Use key recovery for message signatures

Instead of encoding the public key inside the signature string, use
key recovery to do verification. This allows 88-character base64-encoded
signature strings instead of 188-character ones.