How digital signatures work I understand how public/private key cryptography works, and I understand how one-way hashing algorithms work.

I have read through this explanation of how digital signatures work, but something still isn't clear to me. Can someone please help me understand how the receiver of a message that has been digitally signed can be sure that the message has come from the claimed sender, unaltered.

Here's my own breakdown of the explanation in the linked article, which assumes the receiver is using some sort of program ("the program") to receive the message, and verify the signature.

The SENDER of the message sends to the RECEIVER:


A PLAINTEXT copy of the original message
A digital signature which consists of an ENCRYPTED hash of the original document, encrypted using the signer's private key
A PLAINTEXT copy of the signer's public key


The RECEIVER receives the message, and verifies that it is unaltered and from the claimed sender by:


Using the PLAINTEXT public key received in the message, the receiver decrypts the hash. The receiver then re-hashes the original document, and ensures that both hashes match
The program also validates that the public key used in the signature belongs to the signer


What's going on in step 2, above? How does the receiver perform this verification step? I can follow everything up to this point, but based on what's been explained up to that point, it would very easy for someone to intercept the message being sent, rip out the signature, create a new hash, attach a new public key, and send it on its way. So at step 2 above, how can the RECEIVER be sure that the message they are looking at is both unaltered and from the intended sender? How do they "verify" it at that point in the process?

Thanks in advance.
The article is oversimplifying matters. In a real-world scenario, either…


The recipient already has a copy of the public key, or can retrieve a copy from a trusted source. Either way, they can confirm the key is correct by comparing it with the "known good" copy they already have. (This is roughly how PGP works.) Or…
The key has a signature attached to it, signed by a trusted central authority. (This is roughly how SSL/TLS works.)


Either way, your analysis is entirely correct -- attaching a signature and public key to a message doesn't confirm anything on its own.