Can you always derive a public Bitcoin address from a message and a random signature? Let's say my Bitcoin address is 1Nu5mzpUD9A7daZ76QJEsBfkBjCWVLh7pJ and I sign the message random-challenge with its private key.

The result is :

IAjU1mpvy70Li2Q1jDaNJKaQudaAJia1oF9SYJ8HGGuNffT9ERmc77WgPMONPLHKAhO8d0bhDF5Nvn+AUzS6R04=


Bitcoin uses a unique property of ECDSQ which allow to calculate the public key from the message and signature. So if I send to the recipient the above message and signatures he/she will be able to get my address 1Nu5mzpUD9A7daZ76QJEsBfkBjCWVLh7pJ

Now, if I send the same signature and a completely different message, will it derive all the time a valid random Bitcoin address ? And if yes, doesn't this have some serious security implication allowing people to prove they control an address without having the private key ?
Now, if I send the same signature and a completely different message, will it derive all the time a valid random Bitcoin address ?


Yes.


  And if yes, doesn't this have some serious security implication allowing people to prove they control an address without having the private key ?


No. In order to prove you control an address, you must do much more than just produce a signature generated by that address. Otherwise, if you were in possession of anyone else's proof, you could claim it as your own.

The validation process consists of three steps:

1) Ensure the signature correctly signs the message.

2) Ensure the public key used for the signatures matches the Bitcoin address you are expecting proof of.

3) Make sure the signed payload actually proves the person you think controls the address.

Your mutilation would break step 1. Since you're changing the message, the signature no longer signs the message.

The verifymessage command does steps 1 and 2. Step 3 must be done by higher-level code depending on the context.