Cryptography Reference
In-Depth Information
DSS with Message Recovery
If RSA is used as a DSS with message recovery, then the
Recover
algorithm takes
as input a verification key (
n, e
) and a digital signature
s
, and it generates as output
either the message
m
or a notification indicating that
s
is not a valid signature for
m
with respect to (
n, e
).TheRSA
Recover
algorithm operates in two steps:
•
First, it computes
s
e
(mod
n
)
.
m
=RSA
n,e
(
s
)
≡
•
Second, it decides whether
m
is a valid message. In the positive case, it returns
m
, and in the negative case, it returns a notification that indicates that
s
is not
a valid signature for
m
with respect to (
n, e
).
The second step is important. If every message represented a valid message,
then an adversary could trivially find an existential forgery by selecting
s
∈
Z
n
and
claiming that it is an RSA signature (if somebody verifies the signature, he or she
computes
m
s
e
(mod
n
), and hence
s
is indeed a valid signature for
m
). If
m
represented a meaningful message, then the signatory would be in trouble (i.e., he or
she may be held accountable for the message and cannot repudiate having signed it).
Consequently, it is important that random messages are unlikely to be meaningful,
or—alternatively speaking—that the probability that a randomly chosen message is
meaningful is negligible. There are basically two possibilities to achieve this.
≡
•
One can use a natural language to construct messages to be signed. Natural
languages have generally enough redundancy so that a randomly chosen string
(over the alphabet in use) is not likely to be meaningful.
•
One can use a specific (redundancy) structure for messages to be signed. If, for
example, one digitally signs
m
m
instead of
m
, then one can easily verify
the structure of the message after its recovery (i.e., it must then consist of two
equal halves). It goes without saying that more efficient redundancy structures
are used in practice.
In our toy example, the RSA
Recover
algorithm computes
104
3
(mod 253) = 26
m
=RSA
253
,
3
(104)
≡
and decides whether
m
is a valid message. If, for example, valid messages must be
congruent to 6 modulo 20, then
m
=26is a valid message and is returned as a
result.
