What is a digital signature?

A digital signature is an extra chunk of data send along with an (encrypted) message which tells the receiver that the message is coming from the one who claims to have sent it. It ensures that the message has not been tampered with by a man-in-the-middle, a person who spies on the communication line and intercepts messages. You also have a proof that the sender is the one who holds the private key of a public-private key pair.

It goes as follows:

   - Two parties, A and B.  A wants to send a message M to B.
  
      +-----+                              +-----+
      |  A  |                              |  B  |
      +-----+                              +-----+
 - holds private key PVT of       - holds public key PUB of
   public-private key pair          public-private key pair
 
Sender:
   1. A calculates a message digest MD on M
   2. A encrypts that message digest MD with his private
      key PVT (A is the only one that has the private key
      that belongs to him!) = digital signature DS 
   3. A sends message M and DS to B
 
Receiver:
   1. B receives the message M and digital signature DS
   2. B decrypts the digital signature DS with the public
      key PUB and gets MD
   3. B calculates a message digest on M = MD2
   4. B compares MD with MD2.  Equality means that the
      sender must have had access to the private key of 
      the PVT-PUB key pair.

But who says this public/private pair belongs to me? I could have identified myself as someone else, generate such a pair and distribute the public key to a sender who believes I am someone else and trick him with this above process claiming to be that someone else…

That’s where digital certificates come in. Check out What is a digital certificate?