16.4. Digital Signatures


Short documents

Since the encipher function can be made public in a public key cipher, such as RSA, you can use it to sign documents.

Suppose that you have created an RSA cipher with parameters n, e and d. Publish n and e.

The same proof that shows D(E(x)) ≡ x (mod n) also shows that E(D(x)) ≡ x (mod n).

Given a short document M, convert it into a number x. We assume that the document size is small enough so that x < n. To sign M, compute N = D(M) and publish pair (N, M).

Anyone can check to see that you have signed M by computing E(N). If E(N) = M, then the signature is valid. Notice that it is not possible to alter the document without rendering the signature invalid.

Forging a signature on M requires computing D(M), which is presumably difficult without knowing d.


Long documents

To sign a large document, break it into small pieces.

There are some practical issues. For example, the pieces need to be given sequence numbers so that a forger cannot reorder the pieces. The sequence numbers must be part of each document piece so that they are also enciphered, and cannot be rearranged.