Next: Exercises and Projects Up: Mathematical Models in Public-Key Previous: Cryptosystems Based on Discrete

# Digital Signatures

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:

• The signature is unique and unforgeable. It is proof that the signer deliberately signed the document. It convinces the recipient of the document and any third party, say a judge, that it has been signed by the claimed signer.
• The signature is not reusable. It is part of the document and can not be moved to another document. If the document is altered or the signature is moved to another document then the signature is no longer valid.

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

• Pick a random , with .
• Compute and where

• Sign the message m with .
Since anyone can verify Alice's signature:
• Get Alice's public key ( and p are public).
• Compute and .
• Accept the signature as valid only if .

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

• Pick a random nonzero .
• Compute
• Sign the message m with .
To verify Alice's signature for the message m, the receiver can
• Get Alice's public key .
• Compute

• Accept the signature as valid only if .
To see why this works, note that

1exThus

Since q is prime and , we see that the map in the multiplicative group generated by is a permutation. Thus

Reducing both sides modulo q (after they are reduced modulo p), we have .

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 .

Next: Exercises and Projects Up: Mathematical Models in Public-Key Previous: Cryptosystems Based on Discrete

Shuhong Gao
Sun Oct 17 11:04:53 EDT 1999