Cryptography Reference
In-Depth Information
•
(
,
−
)
=
The adversary chooses two integers
u
,
v
such that gcd
v
p
1
1.
•
The adversary computes:
g
u
y
v
mod
p
rv
−
1
mod
r
:=
,
s
:= −
(
p
−
1
),
m
:=
su
mod
(
p
−
1
).
•
The adversary outputs
(
r
,
s
)
as a signature of
m
.
•
(
m
,
r
,
s
)
is accepted by the verification algorithm because
y
r
r
s
y
r
g
su
mod
(
p
−
1
)
y
sv
mod
(
p
−
1
)
≡
y
r
g
m
y
−
r
g
m
≡
≡
(
mod
p
).
9.3 The “Hash-then-Decrypt” Paradigm
The RSA and Elgamal signature schemes we have just seen are highly insecure
because they are vulnerable to key-only attacks. There is a generic method to turn
these and other insecure schemes into schemes in which these straightforward attacks
no longer work and hence which are, in principle, more secure—although the security
of many of them has not been proved. The basic idea is to use the so-called “hash-
then-decrypt paradigm”, namely, instead of directly applying a decryption algorithm
such as RSA to the message in order to obtain the signature, the message
m
is first
hashed by means of a hash function
H
and then the decryption function is applied
to
H
in order to obtain the signature of
m
.
1
We will return to the security aspect in a moment but let us first mention that this
procedure has some other advantages that have also contributed to this methodology
being adopted in practice for several standards. One of them is that messages are
usually not elements of the domain of the decryption function and they may be bit
strings too long to be injectively mapped into that domain. The use of a hash function
that maps strings of arbitrary length to strings of a short fixed length—which can
be converted to elements in the decryption function domain—is very convenient
because it allows large messages to be signed in one pass. Another clear advantage is
efficiency. Hash functions such as SHA-256 are much more efficient than decryption
functions such as the RSA function and, once the message is hashed, the decryption
function only has to be applied once, independently of message length.
(
m
)
1
Observe that the term 'decrypt' must not be taken literally here and that this terminology is
often used even when the signing algorithm is not a decryption algorithm like in the RSA case; an
alternative terminology is “hash-then-sign” and we may also speak of “hash-then-invert” when—
as happens with RSA—signing is carried out by applying the inverse of a (candidate) trapdoor
permutation.
