Cryptography Reference
In-Depth Information
4.3Digital Signatures
Language is only the instrument of science, and words are but the signs of
ideas; I wish, however, that the instrument might be less apt to decay, and the
signs might be permanent, like the things which they denote.
Samuel Johnson
(1709-84), English poet, critic, and lexicographer
— from preface of
A Dictionary of the English Language
(1755)
We had a brief introduction to the notion of a digital signature when we
mentioned applications of OFB mode on page 136. Now it is time to dig deeper
into this significant application. First, we ask: Why do we want a digital
signature in cryptography? This is best answered by bringing in Alice, Bob, and
Mallory to give us an illustration. They will demonstrate the issues surrounding
entity authentication
, meaning verification of the identity and data origin of a
legitimate entity in a protocol by another legitimate entity; and
impersonation
,
meaning the assumption of the identity of a legitimate entity by an adversary.
Suppose that Alice wishes to send a message
m
to Bob, whose public key is
e
, using a PKC. Suppose further that Mallory, impersonating Bob, sends Alice
his public key
e
and Alice assumes this is Bob's public key. She sends
m
e
,
which Mallory intercepts, and using his private key
d
computes (
m
e
)
d
=
m
.
Then he encrypts
m
with Bob's public key and sends
m
e
to Bob. Neither Alice
nor Bob knows that they have been duped by Mallory. This is illustrated in
Diagram 4.4.
Diagram 4.4 (Impersonation Attack on PKCs)
D
d
(
c
)=
m
e
←−−−−−−−−−
−−−−−−−−−→
E
e
(
m
)=
c
✞
☛
✟
✞
Alice
Mallory
−−−−−−−−→
Bob
✝
✆
✝
✆
E
e
(
m
)=
c
✡
✠
This provides an answer to our question above. We need a mechanism for
authentication to thwart impersonation; we need digital signatures, which are
formally defined below.
Digital Signature Schemes (DSS)
Let
M
be a
message space
,
K
a
keyspace
, and
S
a set of bitstrings of fixed
length, called a
signature space
.For
k
∈
K
, to produce a digital signature, we
have a
digital signature algorithm
,
sig
k
:
M
→
S
.
To verify the signature, we have a
digital verification algorithm
,
ver
k
:
M
×
S
→{
0
,
1
}
=
F
2
,
where
ver
k
(
m, c
) = 1, when sig
k
(
m
)=
c
is authentic, and
ver
k
(
m, c
) = 0 when
it is not. A
digital signature scheme
(DSS) is comprised of a digital signature
algorithm and a digital verification algorithm.
Criteria for a Secure DSS
Search WWH ::
Custom Search