next up previous
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:

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 tex2html_wrap_inline1648 and the decryption function tex2html_wrap_inline1650 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) tex2html_wrap_inline1658 and use the ciphertext tex2html_wrap_inline1660 as her signature for the message m. Anyone, seeing the message m and the signature s, can compute tex2html_wrap_inline1668 and accept the signature if and only if tex2html_wrap_inline1670. 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 tex2html_wrap_inline1676 for tex2html_wrap_inline1678 (which is presumably hard). So if Bob shows m and s to a judge and if tex2html_wrap_inline1684, 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 tex2html_wrap_inline948 represent valid messages. In this case, one could easily forge a signature as follows. Pick tex2html_wrap_inline1678 at random and compute tex2html_wrap_inline1690 where k is Alice's public key. Then with high probability, m is a valid message and in this case, since tex2html_wrap_inline1684 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 tex2html_wrap_inline948 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 tex2html_wrap_inline1260 is infeasible, and tex2html_wrap_inline1708 is a primitive element. Also suppose that Alice chooses a random integer tex2html_wrap_inline1710 as her private key and tex2html_wrap_inline1712 as her public key. To sign a message tex2html_wrap_inline1714, Alice can

Since tex2html_wrap_inline1730 anyone can verify Alice's signature:

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 tex2html_wrap_inline1760 and L is a multiple of 64. Suppose tex2html_wrap_inline1708 has order q: i.e., tex2html_wrap_inline1770 but tex2html_wrap_inline1772. A user, say Alice, has a random nonzero integer tex2html_wrap_inline1774 as her private key and tex2html_wrap_inline1712 as her public key. To sign a message tex2html_wrap_inline1778, Alice can

To verify Alice's signature tex2html_wrap_inline1728 for the message m, the receiver can To see why this works, note that
Since q is prime and tex2html_wrap_inline1804, we see that the map tex2html_wrap_inline1806 in the multiplicative group generated by tex2html_wrap_inline898 is a permutation. Thus
Reducing both sides modulo q (after they are reduced modulo p), we have tex2html_wrap_inline1816.

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 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 .

next up previous
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