How does digital signature algorithms work in a private / public key environment?

Question

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?

Answer 1

In an asymmetric algorithm you have two keys. Lets call them A and B. Whatever you encrypt with A, you have to decrypt with B. Whatever you encrypt with B, you have to decrypt with A. (This is true for not all, but most asymmetric algorithms. Also, in practical implementations it is a bit more complicated, see techrafs comment.)

One of these keys are chosen to be private, and kept secret. The other is chosen to be public, and can be distributed.

When a message is signed, the digest is encrypted with the private key. Therefore it must be decrypted with the public key. The fact that it was encrypted with the private key proves the identity of the person who signs it - since only she should have the private key. The fact that it can be decrypted with the public key makes the signature useful, since anyone can verify it.

Note that our system where the MD5 hash of the private key is the public key would not work. How would you decrypt a message encrypted with the private key if you only have the MD5 hash of the private key? If you want to understand how it is actually done, have a look at RSA.

Answer 2

Asymmetric algorithms are designed to have a pair of keys: the public key, which is disseminated to anyone, and the private key, which is retained by the individual or system that generated the key pair. The keys are special in that ONLY the private key can decrypt messages encrypted with the public key, and only the public key can decrypt messages encrypted with the private key.

For any two people wishing to communicate securely, each will need to generate their OWN key pair, and share the public keys with each other. Then when they communicate, it looks something like this:

Each message originator in the above example is using Alice's public key to encrypt and send messages to Alice. Alice uses her private key to decrypt the messages and see what they are. If alice wants to respond to them, she can use her private key to encrypt it (but ANYONE with her public key could decrypt it), or use the public key, of say Mary, to send a message to Mary. Then only Mary could decrypt that message with her private key.

In regards to non-repudiation (sender cannot deny that they sent the message) and data integrity (prove that the message was unaltered), the process works like this:

1. Mary wishes to send a message and "sign" it proving that it came from her.

2. Mary hashes the message, (producing the message digest and encrypts it with her private key.

3. Mary can then send the message, along with the encrypted message digest as a signature

Anyone who wishes to verify the message, follows this process:

1. Take the message and hash it using the same algorithm that Mary used to generate the message digest

2. Decrypt the message digest that came with the message using Mary's public key

3. Compare the two hash values, if they are identical, then you know that the message was unaltered (verifying it's integrity,) and you proved that the message ALSO came from Mary (non-repudiation,) because the message digest could only have been decrypted properly using Mary's public key, which meant it HAD to have been encrypted with Mary's private key, and only Mary should have that key.

---

As far as how the shared-key algorithm produces the shared secret, I would look at Diffie-Hellman, https://en.wikipedia.org/wiki/Diffie%E2%80%93Hellman_key_exchange