Cryptography Reference
In-Depth Information
ECDSA implementation in Sony's PS3 console allowed a key-recovery attack that
was presented by a group named “Fail Overflow” at the 27th Chaos Communication
Congress held in Berlin in 2010.
Other conditions that are necessary for the security of ECDSA refer to the hash
function
H
that should be one-way and collision resistant. If
H
is not one-way, then
an adversary
A
may forge a signature as follows:
•
A
picks an integer
u
←[
1
,
n
−
1
]
.
•
A
sets
r
:=
x
(
uG
+
Q
)
mod
n
and
s
:=
r
.
•
A
sets
e
:=
ur
mod
n
and finds a message
m
such that
H
(
m
)
=
e
.
Then
(
r
,
r
)
is a valid signature for
m
because in the verification algorithm we have
er
−
1
mod
n
rr
−
1
mod
n
that
u
1
=
=
u
and
u
2
=
=
1. Thus
R
=
uG
+
Q
and
x
r
, so that verification succeeds.
On the other hand, if the hash function
H
is not collision resistant, then it is
trivial to construct, in a chosen message attack, a signature forgery from a collision
between two messages
m
(
R
)
mod
n
=
x
(
uG
+
Q
)
mod
n
=
m
1
exactly in the same way we have seen for hashed RSA
the same hash value as
m
(see also the collision attack of Example 5.12).
When all these necessary conditions are satisfied and, moreover, the elliptic curve
group is modeled as a generic group, then it was proved by Brown (see [42]) that
ECDSA is unforgeable under a chosen message attack. We see that this security
reduction assumes the ideal condition that the group is generic and, although this is
not satisfied in practice, the proof gives a good indication that reinforces the reputa-
tion of ECDSA as a secure scheme, which was already high because no substantial
weaknesses have been found. Note that the generic group hypothesis is not applicable
in the case of DSA because in
,
Z
p
there are subexponential index calculus algorithms
for the DLP.
11.4.3 ECDSA in Maple
Here we give a Maple implementation of ECDSA over a prime field
F
p
. We will
use precomputed domain parameters which can be taken, for example, from [75] or
[174] and for implementing the algorithms we will mainly follow [173] with some
We will start with a function to test the domain parameters. The parameters con-
tained in [75, 174] often include a seed that can be used to verify that the parameters
have been generated from it, but we shall not include this seed in our parameter set
and we will just check that they define an elliptic curve over a prime field and a base
point of prime order on this curve and, moreover, that the embedding degree is
100
as required in [173]. The cofactor
h
will always be equal to 1 in the examples we
will use.
The next function tests the domain parameters and, as usual, makes use of several
previously defined functions. The input is a list
≥
[
,
,
,
[
x
G
,
y
G
]
,
]
p
a
b
n
whose elements
