Suppose that you wish to transmit an electronic file. A natural question is how one can put a piece of information at the end of the file that serves the same role as a handwritten signature on a document. It turns out that the digital signature is one of the main applications of public-key cryptography.
Handwritten signatures have the following main features:
How do we realize a signature digitally? Since it is easy to copy, alter, or move a file on computers without leaving any trail, one needs to be very careful in designing a signature scheme. In keeping with the above properties of a handwritten signature, a digital signature should be a number that depends on some secret known only to the signer and on the content of the message being signed. It must also be verifiable: i.e., the recipient of the message (or any unbiased third party) should be able to distinguish between a forgery and a valid signature without requiring the signer to reveal any secret information (private key). Thus in a signature scheme, we need two algorithms: one used by the person signing the message and the other used by the recipient verifying the signature. In the following, we describe two methods based on the RSA and the ElGamal cryptosystems [8, ]. Incidentally, the recently adopted Digital Signature Algorithm (DSA) in the US Digital Signature Standard (DSS) [17] is a variation of ElGamal signature scheme, and we will describe it as well.
To describe the RSA digital signature scheme,
note that the encryption function 
and the
decryption function
in the RSA system are commutative: that is,
Suppose that a user Alice has public key k=(e,n) and private key (d,n)
for the RSA cryptosystem. Then Alice can use her private key
to encrypt a message (or a file) 
and use the ciphertext
as her signature for the message m.
Anyone, seeing the message m and the signature s, can
compute 
and accept the signature if and only if 
.
This proves that Alice indeed signed the message m,
since an adversary trying to forge a signature for Alice on a message m
would have to solve the equation 
for 
(which is presumably hard).
So if Bob shows m and s to a judge and if 
,
the judge should be convinced that no one but Alice could have signed the
statement.
There is one catch though -- and this occurs when all or a significant fraction of the
elements in 
represent valid messages. In this case,
one could easily forge a signature as follows.
Pick at random and compute 
where k is Alice's
public key. Then with high probability, m is a valid message and in this
case, since holds, s is a valid signature of Alice for m.
To avoid this possibility in practice, one adds some redundant information
to the message. Namely, we require the message to have some additional
structure
(e.g., it should be in some standard format).
Thus, a random element in will be a valid message with only vanishing
probability.
This comment also applies to the DSA and the ElGamal signature schemes discussed
below.
The ElGamal cryptosystem cannot, as it stands, be used to generate signatures,
but it can be modified to suit signature purposes. In this case, the signature
scheme is probabilistic in that there are many possible valid
signatures for every message and the verification algorithm accepts
any of the valid signatures as authentic.
Suppose that p is a large prime for which computing
discrete logarithms in 
is infeasible, and 
is
a primitive element. Also suppose that Alice chooses a random integer
as her private key and 
as
her public key. To sign a message 
, Alice can
, with 
.
and 
where
.
anyone can verify Alice's signature:
(
and p are public).
and 
.
.
The US Digital Signature Standard (DSS) was adopted on December 1, 1994.
In DSS, a digital signature algorithm (DSA) is proposed and it
is a variation of the ElGamal signature scheme. We describe DSA briefly
as follows. Choose primes p and q with q|(p-1) and
That is, q has 160 bits and p has L bits where 
and L is a multiple of 64.
Suppose has order q: i.e., 
but 
.
A user, say Alice, has a random nonzero integer 
as her
private key and as her public key.
To sign a message 
, Alice can
.
.
for the message m,
the receiver can
.
.
, we see that the map
in the multiplicative group generated by
is a permutation. Thus
.
Note that in the above signature scheme, the size of a signature equals (in RSA) or doubles (in both ElGamal and DSA) the size of the message being signed. This can be awkward in practice, especially if the message being signed is long. One way to overcome this problem is to first hash the message to a string of fixed size and then sign the hashed value of the message. Together with DSS, the National Institute of Standards and Technology (NIST) has also published a Secure Hash Standard (SHS) [17]. In SHS, a Secure Hash Algorithm (SHA) is proposed, which maps a message of arbitrary length to a binary string of length 160. We will not describe the details here, and the interested reader is referred to the references.
Public-key cryptography has many other applications, including identification, authentication, authorization, data integrity, and smart cards. In fact, NIST proposed in February 1997 a standard for entity authentication using public-key cryptography; the reader can consult the website at http://csrc.ncsl.nist.gov/fips. For further study we recommend the books [16, 22, 23, 24], and for the early history of cryptography, we suggest [11]. Computational number theory is nicely covered in [3, 5, 20]. Additional information on cryptographic methods, algorithms, and protocols can be found at http://www.ssh.fi/tech/crypto .