Cryptography Reference
In-Depth Information
m
d
(mod
n
)
26
147
(mod 253) = 104
.
d
≡
≡
Then 104 represents the digital signature for 26, and 26 may be either the
message or the hash value thereof.
15.2.1.3
Signature Verification Algorithm
For the purpose of signature verification, one must distinguish whether the RSA DSS
is used with appendix or with message recovery. In either case, the corresponding
algorithm (i.e.,
Verify
or
Recover
) is deterministic and efficient (i.e., it requires only
a modular exponentiation and optionally the invocation of a cryptographic hash
function).
DSS with Appendix
If RSA is used as a DSS with appendix, then the
Verify
algorithm must be employed
to verify the digital signature
s
that is transmitted together with the message
m
.
The algorithm takes as input a verification key (
n, e
), a message
m
, and a digital
signature
s
, and it generates as output one bit that indicates whether
s
is a valid
signature for
m
with respect to (
n, e
).TheRSA
Verify
algorithm operates in two
steps:
•
First, it computes
m
=RSA
n,e
(
s
)
s
e
(mod
n
)
.
≡
Second, it compares
m
either with
m
or
h
(
m
). The signature is valid if and
only if equality holds (i.e.,
m
=
m
or
m
=
h
(
m
)).
•
In our toy example, the RSA
Verify
algorithm computes
m
=RSA
253
,
3
(104)
104
3
(mod 253) = 26
≡
and returns
valid
(because
m
=26matches the message
m
=26that is originally
transmitted together with the signature
s
).
