The authenticity of many legal, financial, and other documents
is determined by the presence or absence of an authorized handwritten signature.
And photocopies do not count. For computerized message systems to replace the
physical transport of paper and ink documents, a method must be found to allow
documents to be signed in an unforgeable way.
The problem of devising a replacement for handwritten
signatures is a difficult one. Basically, what is needed is a system by which
one party can send a signed message to another party in such a way that the
following conditions hold:
-
The receiver can verify the claimed identity of the sender.
-
The sender cannot later repudiate the contents of the message.
-
The receiver cannot possibly have concocted the message himself.
The first requirement is needed, for example, in financial
systems. When a customer's computer orders a bank's computer to buy a ton of
gold, the bank's computer needs to be able to make sure that the computer giving
the order really belongs to the company whose account is to be debited. In other
words, the bank has to authenticate the customer (and the customer has to
authenticate the bank).
The second requirement is needed to protect the bank against
fraud. Suppose that the bank buys the ton of gold, and immediately thereafter
the price of gold drops sharply. A dishonest customer might sue the bank,
claiming that he never issued any order to buy gold. When the bank produces the
message in court, the customer denies having sent it. The property that no party
to a contract can later deny having signed it is called nonrepudiation. The digital signature schemes that we
will now study help provide it.
The third requirement is needed to protect the customer in the
event that the price of gold shoots up and the bank tries to construct a signed
message in which the customer asked for one bar of gold instead of one ton. In
this fraud scenario, the bank just keeps the rest of the gold for itself.
Symmetric-Key Signatures
One approach to digital signatures is to have a central
authority that knows everything and whom everyone trusts, say Big Brother (BB). Each user then
chooses a secret key and carries it by hand to BB's office. Thus, only Alice and BB know Alice's secret key, KA, and so
on.
When Alice wants to send a signed plaintext message, P, to her banker, Bob, she generates KA(B, RA, t, P), where B is Bob's
identity, RA is a random number chosen by Alice, t is a timestamp to ensure freshness, and KA(B, RA, t, P) is the message encrypted with her key, KA. BB sees that the message is from Alice, decrypts it,
and sends a message to Bob as shown. The message to Bob contains the plaintext
of Alice's message and also the signed message KBB (A, t, P). Bob now carries out Alice's request.
Public-Key Signatures
A structural problem with using symmetric-key cryptography for
digital signatures is that everyone has to agree to trust Big Brother.
Furthermore, Big Brother gets to read all signed messages. The most logical
candidates for running the Big Brother server are the government, the banks, the
accountants, and the lawyers. Unfortunately, none of these organizations inspire
total confidence in all citizens. Hence, it would be nice if signing documents
did not require a trusted authority.
Fortunately, public-key cryptography can make an important
contribution in this area. Let us assume that the public-key encryption and
decryption algorithms have the property that E(D(P)) = P in addition, of
course, to the usual property that D(E(P)) = P. (RSA has this property, so the assumption is not
unreasonable.) Assuming that this is the case, Alice can send a signed plaintext
message, P, to Bob by transmitting EB(DA(P)). Note carefully that
Alice knows her own (private) key, DA, as well as Bob's public key, EB, so
constructing this message is something Alice can do.
