The message signing feature and encoding wasn’t designed by Satoshi, but by me, so you can direct all blame for quirks and lack of documentation here. You’re right that it predates the BIP process, so the code is really the specification I’m afraid, though with many reimplementations there are probably several languages to choose from.
It is roughly:
- Serialize the string “Bitcoin Signed Message:\n” plus the message being signed in the P2P protocol serialization format (which means: prepending each with a CompactSize-encoding of the number of bytes that follow)
- Double-SHA256 hash that serialization.
- Construct an ECDSA signature with that double-SHA256 as hashed message z, and the address’ key as private key d (with corresponding public key Q), resulting in two integers (r, s).
- That signature is encoded as a “recoverable signature”, which consists of a header byte plus 32-byte big-endian encodings of r and s. This header bytes is there to assist the verifier in recovering the public key from the signature. It can be computed by running the verification algorithm:
- Let u_1 = s^{-1}z\, (\operatorname{mod}\, n)
- Let u_2 = r^{-1}z\, (\operatorname{mod}\, n)
- Let R = u_1G + u_2Q
- From the result the “recid” can be derived:
- The X coordinate of R must now either be r (recid=0 or 1) or r + n (recid=2 or 3).
- The Y coordinate of R must be even (recid=0 or 2) or odd (recid=1 or 3)
- The header byte equals the recid + 27 for uncompressed Q and recid + 31 for compressed Q.