Cryptography Reference
In-Depth Information
tives, we have to apply public-key cryptography. The basic idea is that the person
who signs the message uses a private key, and the receiving party uses the matching
public key. The principle of a digital signature scheme is shown in Fig. 10.1.
Alice
Bob
k
pub
x
sig
k
pr
s
( , )
x s
x s
,
k
pub
ver
true / false
Fig. 10.1
Principle of digital signatures which involves signing and verifying a message
The process starts with Bob signing the message
x
. The signature algorithm is a
function of Bob's private key,
k
pr
. Hence, assuming he in fact keeps his private key
private, only Bob can sign a message
x
on his behalf. In order to relate a signature to
the message,
x
is also an input to the signature algorithm. After signing the message,
the signature
s
is appended to the message
x
and the pair (
x
,
s
) is sent to Alice. It
is important to note that a digital signature by itself is of no use unless it is accom-
panied by the message. A digital signature without the message is the equivalent of
a handwritten signature on a strip of paper without the contract or a check that is
supposed to be signed.
The digital signature itself is merely a (large) integer value, for instance, a string
of 2048 bits. The signature is only useful to Alice if she has means to
verify
whether
the signature is valid or not. For this, a verification function is needed which takes
both
x
and the signature
s
as inputs. In order to link the signature to Bob, the function
also requires his public key. Even though the verification function has long inputs,
its only output is the binary statement “true” or “false”. If
x
was actually signed
with the private key that belongs to the public verification key, the output is true,
otherwise it is false.
From these general observations we can easily develop a generic digital signature
protocol:
