From the Wikipedia page on the subject, I get, on a theoretical level, how the process of encrypting and decrypting a message works. The article states that:
In a public-key encryption system, any person can encrypt a message using the public key of the receiver, but such a message can be decrypted only with the receiver's private key.
So far, so good. In very simplistic terms, I could have my private that that is
123 and use its md5 hash (
202cb962ac59075b964b07152d234b70) as public key. So, I can always regenerate the public key knowing the private key but not vice versa. Then, talking about signing a message, it is written that
Message authentication involves hashing the message to produce a "digest," and encrypting the digest with the private key to produce a digital signature. Thereafter anyone can verify this signature by (1) computing the hash of the message, (2) decrypting the signature with the signer's public key, and (3) comparing the computed digest with the decrypted digest
The part that I don't get is
decrypting the signature with the signer's public key. Isn't it stated in the first part that only a private key can decrypt a message?
As far as I understand, the kind of algorithm used here is something different from the "md5 hash" I proposed earlier because you can decrypt a message encrypted with the public key by knowing the private key and decrypt a message encrypted with the private key by knowing the public key.
How do such algorithms work?