Digital Signatures

RSA signatures
--------------

  Very closely related to public keys is the concept of digital signatures.
  One problem with corresponding electronically, such as via a large scale
  computer network, is that messages can easily be forged - you usually cannot
  be certain that the sender of a received message is actually the person
  claimed in the message.  A public key cryptosystem, however, can be used to
  provide positive identification of any sender who has a public key. If, for
  exaple Mary has filed a public key in some public access file, she can
  digitally sign a message by encrypting it with her private decryption key
  before publishing the message.  Anybody can reveal the plaintext by decrypting
  the message with Mary's public encryption key; if the plaintext is revealed,
  then Mary must have authored the message.

  One can take this idea a step further, Mary can encrypt a message with her
  private key, then encrypt it again with your public key.  To reveal the plaintext,
  you must decrypt the message with your private key, then decrypt it with Mary's
  public key.  The result is a message which only Mary could have sent, and
  only you can read!


An Example:

     The Sender has a Public Key, a Private Key, and a public, non-invertible hashing
     function.

     To sign a docuent, the Sender runs the text through the hashing function,
     giving a few lines of text (called a message digest), which is then encrypted
     using the private key, giving a digital signature.  This signature is then appended
     to the original text, and both are sent. 

     The receiver decrypts the signature (using the Sender's public key) changing it back
     into a message digest. If this works, then it proves that the Sender signed the
     docuent, because only the Sender has his private key.  The receiver then hashes the
     docuent data into a message digest.  If the message digest is the same as the
     message digest created when the signature was decrypted, then the receiver knows that
     the signed data has not been changed. 


   Message - - - - - - - - - - - - - - - - - -
     |                                        |
     |                                        |
     v                                        v
   hash                                      hash
     |                                        |
     |                                        |
     v                                        v
   Msg Digest                              Msg Digest
     |                                        || 
     |                                        || 
     v                                        || 
   Private Key                                || 
     |                                        || 
     |                                        ||
     v                                        ||
   Signature --------> Public Key -------> msg digest