Cryptography Reference
In-Depth Information
Let us now verify these signatures:
> DSAVer(dparams, dsakey[2], m1, sig1, messagetype = 'text');
"Valid"
> DSAVer(dparams, dsakey[2], m2, sig2);
"Valid"
Verification is successful and the signatures are accepted.
We close this study of DSA by mentioning that there is also an elliptic curve
version of the algorithm called ECDSA. The main difference with the DSA algo-
rithm we have seen is that ECDSA operates on an elliptic curve group instead of
on a subgroup of
Z
p
. An introduction to elliptic curve cryptography is presented in
9.5 CMA Secure Signature Schemes
We are now going to look at signature schemes that, in contrast with the preceding
ones, can be proved to be UF-CMA secure under reasonable assumptions and that,
moreover, are reasonably efficient so that they can be used in practice. The most
important of these schemes are RSA-based and, since plain RSA signatures are,
as we have seen, extremely weak from the security viewpoint, we take the hashed
version of RSA signatures as starting point in the search for such secure schemes.
9.5.1 FDH Signatures
The basic idea in the quest for RSA-based secure signatures is to obtain a security
reductionwhich shows that a PPT algorithm that breaks such a signature scheme leads
to an algorithm that inverts the RSA function for a randomly chosen point in its range.
This will show that such an algorithm cannot exist assuming that the RSA problem is
hard. However, such a proof seems difficult to obtain for the basic version of hashed
RSA signatures described in Sect.
9.3.1
even assuming that the hash function used
is collision resistant. One important obstacle for such a proof is the fact that this
function may have an output length much smaller than the size of the RSA modulus
used. SHA-256, for example, has a 256-bit output length and, if used together with
a 2048-bit RSA-modulus
n
, then the set
S
}
∗
}
={
SHA-256
(
m
)
|
m
∈{
0
,
1
is a tiny
subset
4
of
Z
n
. Indeed, there are at most 2
256
elements in
S
and 2
2048
elements in
Z
n
, so the probability that a randomly chosen element of
Z
n
happens to belong to
2
256
2
2048
1
2
1792
. This probability is so tiny that, even assuming that the RSA
function is one-way, it is perfectly possible that it could be easy to invert the function
S
is
≤
=
4
As is done in Sect.
9.3.1
, we assume that
H
maps
{
0
,
1
}
∗
to
Z
n
by identifying a bit string with the
integer it defines.
