Cryptography Reference
In-Depth Information
./
./
./
3
./
./
./
3
3
3
Figure 15.3
Lamport's one-time signature system.
p
=
h
(
f
(
u
10
)
,f
(
u
11
)
,f
(
u
20
)
,f
(
u
21
)
,...,f
(
u
n
0
)
,f
(
u
n
1
))
In this notation,
h
represents a cryptographic hash function. To digitally sign
message
m
, each bit
m
i
is signed individually using [
u
i
0
,u
i
1
]. The index
i
runs
from 1 to
n
. More specifically, the signature for
m
i
is the pair [
u
im
i
,f
(
u
im
i
)],
where
m
i
represents the complement of
m
i
.Soif
m
i
=0, then this bit is signed
with [
u
i
0
,f
(
u
i
1
)],andif
m
i
=1, then it is signed with [
u
i
1
,f
(
u
i
0
)]. The resulting
signature
s
consists of [
u
im
i
,f
(
u
im
i
)] for all
n
bits of the message:
s
=[
u
1
m
1
,f
(
u
1
m
1
)]
,
[
u
2
m
2
,f
(
u
2
m
2
)]
,...,
[
u
nm
n
,f
(
u
nm
n
)]
The signature
s
can be verified by computing all images
f
(
u
ij
), hashing all of
these values to
p
, and comparing
p
with the public key
p
. The signature is valid if
and only if
p
=
p
.
