How do I verify a message came from me? I have many clients and a single server, and on each of these clients I want to be able to verify a message did indeed come from my server. My idea was to send some sort of key with cryptographic significance.

For example, say I wanted to send a boolean from the server to the client, I could send a message like this:

{
    "boolean": true,
    "key": 30
}


In this trivial example, the significance of the key is that it is divisible by 3. So the client would perform a check like this:



if payload["key"] % 3 == 0:
    valid = True
else:
    valid = False


Is this a good idea provided I use a more secure algorithm? If so, what would you suggest?

If not, how should I go about verifying the authenticity of the message?

Thanks.

EDIT:

My understanding of the HMAC approach is as follows:

Firstly you generate a key which will be stored on the server and all of the clients. For example,



import random
key = bytes(hex(random.getrandbits(128)).encode("utf-8"))


Then, on the server when you want to send a message to a client, you generate a HMAC as follows and send it along with the message:



import hmac
import hashlib
h = hmac.new(key, str(payload["key"]).encode("utf-8"), hashlib.sha3_256).hexdigest()


Then on the client, you run this again with your key and if they match then it is a valid message.

I have two problems with this approach. Firstly, there are only two possible HMACs - one for true and one for false. Additionally, hardcoding the secret key into the client doesn't sound like the best of ideas.
Yes, this is a way to establish authenticity through the use of a so-called "shared secret".

In practice you could do it using the HMAC algorithm and a shared key between the server and clients.

Notice that here, there is a problem with shared keys: that is that the whole system is not secure as soon as one client is breached.
There are also other ways to establish authenticity of messages without this problem by the mean of public key cryptography.
In this case your server would be the only one knowing the secret key, and would sign its messages with it, so that the clients, knowing the public key of the server could verify the authenticity of the messages. 
Typical algorithms to do so are ECDSA or Ed25519.

Edit

As requested, here are more details regarding how these would work in practice:

HMAC

This is almost exactly as you described in your own edit.


You create a secret HMAC key, which you store on both the server and the clients.
You have a message which you want to authenticate, so you just "HMAC" it on the server using the secret HMAC key, and you send both the message and the HMAC digest to your client(s).
The client receives the message and the HMAC digest and computes the HMAC digest of the message, and then verifies it matches the one it received.


There is just one slight caveat I have with your way:
you pass the value str(payload["key"]).encode("utf-8") as the msg in your HMAC call, but what is contained in your payload["key"] value? 
You would rather have your payload itself being passed to the HMAC and then append the hexdigest to the message, thus you'd have a structure a bit like this for your messages:

{
"payload": {
    "boolean": true,
    },
"mac": {
    "hmac-digest": "6eb6a866856dc7ea74c0d6bd41993106f696cc5091f88f188efbb23def6d248b"
    }
}


Now, as you said in your edit, HMAC values being deterministic, if you authenticate twice the same message, you'd get twice the same digest.
But HMAC is about protecting authenticity of the messages, not confidentiality. (Notice that with HMAC, you get both authenticity and integrity of the message.)

Also, it is true that HMACed messages are trivially vulnerable to replay attacks, but so are public-key signed message.
Adding a replay protection to your protocol is not that easy, and usually requires being stateful. 

To have replay attack protection, you'd typically need to have a message index value, and keep track (thus being stateful) of the said index on each clients. (And reject any message that does not increase the index value.) 

{
"payload": {
    "boolean": true,
    "index": 12 
    },
"mac": {
    "hmac-digest": "a1b0271d1eea012c81f06488645ce026914e095d9d770d7d213efbd968be3fe2"
    }
}


But notice that this is still vulnerable to replay attacks between clients, if all clients are not getting the same message at the same time...

Thus, you might want to include sender and receiver data in your payload, so that these are authenticated as well... as you can see the complexity of your protocol is increasing relatively fast!

Public key crypto

So, if you are to use public key crypto to authenticate your messages, the process would only differ slightly from the previous workflow:


You create a private key and its corresponding public key on the server and store them there.
You store the public key of the server on each of your clients.
You have a message which you want to authenticate, so you sign it on the server side using the private key, and you send both the message and the signature to your client(s).
The client receives the message and the signature and uses the public key of the server to verify that the signature was indeed produced by someone knowing the server's private key.


There a multiple algorithm to do so:
- ECDSA
- Ed25519
- RSA-PSS

Notice that the same caveats as with HMAC applies here: you might need to authenticate more than just the message to avoid replay attacks and any other abuse of your protocol.