user38458: Ledger Nano S and other pieces of Bitcoin software and hardware can sign messages using the private key associated with an address.
Doing this, I get the following output:
-----BEGIN BITCOIN SIGNED MESSAGE-----
Test
-----BEGIN SIGNATURE-----
1BqtNgMrDXnCek3cdDVSer4BK7knNTDTSR
ILoOBJK9kVKsdUOnJPPoDtrDtRSQw2pyMo+2r5bdUlNkSLDZLqMs8h9mfDm/alZo3DK6rKvTO0xRPrl6DPDpEik=
-----END BITCOIN SIGNED MESSAGE-----

What exactly is being signed? How is the signature generated? What is the hash preimage that goes into the ECDSA signing algorithm?

user10377: The message that was signed is "Test". Will use https://github.com/libbitcoin/libbitcoin-explorer/wiki/bx-message-validate command line interface below.
As you can see, I clearly do not have the private keys nor did I have access to the BTC blockchain, but I can validate the message was digitally signed by a person in control of the private key for BTC address 1BqtNgMrDXnCek3cdDVSer4BK7knNTDTSR without the need for possessing the associated BTC public key.
% echo -n "Test" | bx message-validate 1BqtNgMrDXnCek3cdDVSer4BK7knNTDTSR ILoOBJK9kVKsdUOnJPPoDtrDtRSQw2pyMo+2r5bdUlNkSLDZLqMs8h9mfDm/alZo3DK6rKvTO0xRPrl6DPDpEik=
The signature is valid.
Result when the message is changed:
% echo -n "Tested wrong message" | bx message-validate 1BqtNgMrDXnCek3cdDVSer4BK7knNTDTSR ILoOBJK9kVKsdUOnJPPoDtrDtRSQw2pyMo+2r5bdUlNkSLDZLqMs8h9mfDm/alZo3DK6rKvTO0xRPrl6DPDpEik=
The signature is not valid.
Result when the wrong public address is applied:
% echo -n "Test" | bx message-validate 1FZHv7fubXkMcgbDBUeehgPf28cHP86f7V ILoOBJK9kVKsdUOnJPPoDtrDtRSQw2pyMo+2r5bdUlNkSLDZLqMs8h9mfDm/alZo3DK6rKvTO0xRPrl6DPDpEik=
The signature is not valid.
This is the magic of Internet money. The math is documented a bit in the Andreas' Mastering Bitcoin Book. Also see How is Public Key extracted from (message, digital signature, address). 

user38458: The message that is signed is prepended with 
"\x18Bitcoin Signed Message:\n" + compactSizeEncoding( len(message) )

\x18 is Python syntax for unicode character 0x18. This new text string is then converted into a byte array by interpreting the string as UTF8. This will give you the correct hash preimage which is:
SHA256(SHA256(utf8.to_bytes("\x18Bitcoin Signed Message:\n" + compactSizeEnc( len(message) + message )) = 
559766ea41f2bc4125e5449200dbf7e902b724b66104820ca5b7fc59f30a19e0

You can see a Python code example here. The function msg_magic generates the hash preimage from the message. This Python code example does not correctly implement compactSizeEnc, however. So it only works with a message length up to 253 bytes.
The correct way of handling compactSizeEncoding is documented here.

38458: <p>Ledger Nano S and other pieces of Bitcoin software and hardware can sign messages using the private key associated with an address.</p>

<p>Doing this, I get the following output:</p>

<pre><code>-----BEGIN BITCOIN SIGNED MESSAGE-----
Test
-----BEGIN SIGNATURE-----
1BqtNgMrDXnCek3cdDVSer4BK7knNTDTSR
ILoOBJK9kVKsdUOnJPPoDtrDtRSQw2pyMo+2r5bdUlNkSLDZLqMs8h9mfDm/alZo3DK6rKvTO0xRPrl6DPDpEik=
-----END BITCOIN SIGNED MESSAGE-----
</code></pre>

<p>What exactly is being signed? How is the signature generated? What is the hash preimage that goes into the ECDSA signing algorithm?</p>
 10377: <p>The message that was signed is "Test". Will use <a href="https://github.com/libbitcoin/libbitcoin-explorer/wiki/bx-message-validate" rel="nofollow noreferrer">https://github.com/libbitcoin/libbitcoin-explorer/wiki/bx-message-validate</a> command line interface below.</p>

<p>As you can see, I clearly do not have the private keys nor did I have access to the BTC blockchain, but I can validate the message was digitally signed by a person in control of the private key for BTC address 1BqtNgMrDXnCek3cdDVSer4BK7knNTDTSR without the need for possessing the associated BTC public key.</p>

<p><strong>% echo -n "Test" | bx message-validate 1BqtNgMrDXnCek3cdDVSer4BK7knNTDTSR ILoOBJK9kVKsdUOnJPPoDtrDtRSQw2pyMo+2r5bdUlNkSLDZLqMs8h9mfDm/alZo3DK6rKvTO0xRPrl6DPDpEik=</strong></p>

<p><code>The signature is valid.</code></p>

<p><strong><em>Result when the message is changed:</em></strong></p>

<p>% echo -n <strong>"Tested wrong message"</strong> | bx message-validate 1BqtNgMrDXnCek3cdDVSer4BK7knNTDTSR ILoOBJK9kVKsdUOnJPPoDtrDtRSQw2pyMo+2r5bdUlNkSLDZLqMs8h9mfDm/alZo3DK6rKvTO0xRPrl6DPDpEik=</p>

<p><code>The signature is not valid.</code></p>

<p><strong><em>Result when the wrong public address is applied:</em></strong></p>

<p>% echo -n "Test" | bx message-validate <strong>1FZHv7fubXkMcgbDBUeehgPf28cHP86f7V</strong> ILoOBJK9kVKsdUOnJPPoDtrDtRSQw2pyMo+2r5bdUlNkSLDZLqMs8h9mfDm/alZo3DK6rKvTO0xRPrl6DPDpEik=</p>

<p><code>The signature is not valid.</code></p>

<p>This is the magic of Internet money. The math is documented a bit in the Andreas' <a href="https://github.com/bitcoinbook/bitcoinbook/blob/develop/ch06.asciidoc#ecdsa-math" rel="nofollow noreferrer"><strong>Mastering Bitcoin Book</strong></a>. Also see <a href="https://bitcoin.stackexchange.com/questions/81232/how-is-public-key-extracted-from-message-digital-signature-address">How is Public Key extracted from (message, digital signature, address)</a>. </p>
 38458: <p>The message that is signed is prepended with </p>

<pre><code>"\x18Bitcoin Signed Message:\n" + compactSizeEncoding( len(message) )
</code></pre>

<p>\x18 is Python syntax for unicode character <code>0x18</code>. This new text string is then converted into a byte array by interpreting the string as UTF8. This will give you the correct hash preimage which is:</p>

<pre><code>SHA256(SHA256(utf8.to_bytes("\x18Bitcoin Signed Message:\n" + compactSizeEnc( len(message) + message )) = 
559766ea41f2bc4125e5449200dbf7e902b724b66104820ca5b7fc59f30a19e0
</code></pre>

<p>You can see a Python code example <a href="https://github.com/nanotube/supybot-bitcoin-marketmonitor/blob/master/GPG/local/bitcoinsig.py" rel="nofollow noreferrer">here</a>. The function <code>msg_magic</code> generates the hash preimage from the message. This Python code example does not correctly implement compactSizeEnc, however. So it only works with a message length up to 253 bytes.</p>

<p>The correct way of handling compactSizeEncoding is documented <a href="https://en.bitcoin.it/wiki/Protocol_documentation#Variable_length_integer" rel="nofollow noreferrer">here</a>.</p>
