Cryptography Reference
In-Depth Information
cannot perform manipulations
within
an individual block, we do not have protection
for the whole message.
Hence, for performance as well as for security reasons we would like to have
one
short signature
for a message of arbitrary length. The solution to this problem is
hash functions. If we had a hash function that somehow computes a fingerprint of
the message
x
, we could perform the signature operation as shown in Figure 11.2
. . .
x
1
x
2
x
x
n
3
h
sig
k
pr
s
Fig. 11.2
Signing of long messages with a hash function
Assuming we possess such a hash function, we now describe a basic protocol for
a digital signature scheme with a hash function. Bob wants to send a digitally signed
message to Alice.
Basic Protocol for Digital Signatures with a Hash Function:
Alice
Bob
k
pub
,
B
←−−−−−−−−−−
z
=
h
(
x
)
s
= sig
k
pr
,
B
(
z
)
(
x
,
s
)
←−−−−−−−−−−
z
=
h
(
x
)
ver
k
pub
,
B
(
s
,
z
)=true/false
Bob computes the hash of the message
x
and signs the hash value
z
with his
private key
k
pr
,
B
. On the receiving side, Alice computes the hash value
z
of the
received message
x
. She verifies the signature
s
with Bob's public key
k
pub
,
B
.We
note that both the signature generation and the verification operate on the hash value
z
rather than on the message itself. Hence, the hash value represents the message.
The hash is sometimes referred to as the
message digest
or the
fingerprint
of the
message.
Before we discuss the security properties of hash functions in the next section,
we can now get a rough feeling for a desirable input-output behavior of hash func-
tions: We want to be able to apply a hash function to messages
x
of any size, and
