When signing email with GPG, how does verification by the receiver work?

Question

I use GPG to sign my outgoing emails.

I understand how it works when I encrypt mail to send to someone else. Then I need his/her public key, encrypt it with that, and only he can decrypt it using his private key.

What I understand from signing my outgoing mail, I use my private key to do this. The receiver doesn't need to use GPG (to read the mail), and I don't need their public key. I suppose my public key is used by the receiver to check if the signature is legit, but maybe I misunderstand.

How can they use my public key to verify that my signature is valid?

Answer 1

There is a unique association between public and private key. That is, if the sender uses a certain private key to sign a message and you verify the signature using the corresponding public, then the signature verification will succeed only if the message has not been altered.¹

The verification procedure and nature of the association between public and private varies with the cryptosystem you are considering (RSA, DSA, etc.), but the statement above holds true for any asymmetric scheme.

What really matters is that the sender is the only one that can produce a valid signature because he/she is the only one who knows the private, but anyone knows the public, so anyone can verify the signature.

Upon signing, GPG adds a token to the text message which can be used to verify that the message has not been altered in transit: that's the signature. You don't need GPG to read the message because the text itself is not encrypted, there is only an extra token, which could be either a radix64-encoded blob at the end of the message or a text attachment with a similar structure.

GPG does not directly sign the message², it signs a cryptographic hash (SHA-1 or SHA-2 usually) of it. What happens upon verification is that the signature is verified using the public key of the sender to make sure the received hash was actually originated by the sender. If the hash calculated by the sender is considered authentic, it is compared with the hash calculated by the recipient. If both phases succeed, then the message is correctly signed.

---

[¹] actually, there is a theoretical possibility to break this rule by generating a so-called hash collision. That is to say, a different message with the same hash (see the last paragraph). Collisions have been generated for MD5, while finding one for SHA-3, SHA-2 and SHA-1 is considered unfeasible, although the security margin over the last one is becoming so thin it's advisable to stop using it now.

[²] for some cryptosystems, like DSA, signing a hash is the only possibility.

Answer 2

Signing data is to prove to someone else that it originated from you. By signing with your private key (that only you have) you ensure that anyone with your public key can verify the message. You don't use their public key, but they have yours.

The signature itself is a cryptographic hash of the entire message that is signed with your private key. Any change to the message would generate an incorrect hash. Since the sender should be the only one with the private key anyone in the middle of communication should not be able to reproduce that signature. The receiver uses calculates their own hash, then compares it to the one that was signed.

This is secure because if the message was altered and signed with a different private key the receiver would still be attempting to use the original sender's public key to decrypt. This would generate an incorrect value and the message would not be verified.