Securely verifying 2 messages from a source - which algorithm?

Question

I am working on a project where:

1. The sender sends a single 256-bit public key to multiple clients
2. The sender then sends a second message (of any size) over another medium to these clients
3. Clients will have sufficient details to pretend that they are the sender, except for the private key from the first public key
4. The first 256-bit public key must have a huge scope for randomness, as we will be SHA2'ing it and using it for passwords

I need to verify that the second message is from the sender, and not from a malicious client.

What is the type of encryption algorithm I am looking for? I want to embed a verifying key in this second message, so that non-malicious clients can verify that the sender (or someone with the private key) sent both messages, and not another client.

Answer 1

The cryptographic primitive you are looking for are public key signatures. They do exactly what you have described, but I'll add few remarks to your points:

• Re 1: The first channel you use has to be secure in some sense so no attacker can not pretend to be the server in the first step already. An example for such a secure connection would carrying it via usb stick by yourself if the other side knows you as a person. Or if they are all software installations of your code you can embed the public key in the source code (assuming the software arrives at the client in a secure fashion). Regarding the key size: 256bit keys are very short for most public key signature schemes. For elliptic curve schemes 256bit is lower minimum, for RSA you now need keys with 2048bit.
• Re 4: The public key will have a lot of entropy (the technical term for "huge scope for randomness"), but non the less it is bad practice to reuse keys for several applications. Why don't you just transmit the (independently generated) passwords in the first step already?