Cryptography Reference
In-Depth Information
Remarks 11.1
1. Observe first that a correctly generated signature is declared valid by the ver-
ification algorithm (with valid corresponding to output 1). Indeed, in this case
we have that
u
1
G
+
u
2
Q
=
(
u
1
G
+
u
2
dG
)
=
(
u
1
+
u
2
d
)
G
=
kG
because
s
−
1
u
1
+
u
2
d
≡
(
e
+
dr
)
≡
k
(
mod
n
)
and hence
x
(
u
1
G
+
u
2
Q
)
mod
n
=
r
, which is the condition that must be verified for the signature
to be declared valid.
2. If the signature
x
(
kG
)
mod
n
=
is also a
valid signature for
m
. However, this is not regarded as a forgery because the
same message is signed in both cases.
3. The cofactor
h
in the domain parameters was not explicitly used in the ECDSA
algorithms. However, this parameter is required in several standards such as, for
example, [75]. The reason is that maximum sizes for
h
(relative to the size of
n
)
are specified in the standard and these sizes should be taken into account either
when generating the domain parameters or when validating them.
4. We have defined ECDSA for prime fields but we mention that there is also a
version of the scheme that works on curves defined over binary fields
(
r
,
s
)
is valid for the message
m
then
(
r
,
−
s
mod
n
)
F
2
m
.
5. Observe that the signing algorithm does not make use of the
y
-coordinate of
the point
R
computed therein. Thus in ECDSA it is not necessary to use point
compression as no elliptic curve points—only the
x
-coordinate of a point and a
value deduced from it—are included in the signature.
11.4.2.2 The Security of ECDSA
The ECDSA private key can be recovered from the corresponding public key by
solving a DL problem, so hardness of this problem in the subgroup of order
n
gen-
erated by
G
is an obvious necessary condition for the scheme to be secure. Another
necessary condition is that the “ephemeral key”
k
generated by the signing algo-
rithm be truly random. As we have seen when discussing Elgamal signatures, an
extreme case in which this condition is violated (except with negligible probability)
is when the same value of
k
is used to sign two different messages
m
,
m
1
. Then the
corresponding signatures
(
r
,
s
)
and
(
r
1
,
s
1
)
satisfy:
=
r
1
=
(
)
1.
r
x
kG
mod
n
,
k
−
1
:=
(
(
)
+
)
2.
s
H
m
dr
mod
n
,
k
−
1
3.
s
1
:=
(
H
(
m
1
)
+
dr
)
mod
n
,
fromwhich, working in the field
F
n
= Z
n
, we can eliminate
k
and obtain
s
1
(
H
(
m
)
+
dr
)
≡
s
(
H
(
m
1
)
+
dr
)(
mod
n
)
which, in turn, gives:
r
−
1
s
1
)
−
1
mod
n
d
=
(
s
1
H
(
m
)
−
sH
(
m
1
))
(
s
−
,
and recovers the private key. We also see that if an adversary is able to guess
k
then
it can obtain the private key, thus the random number generator used to produce
k
should be unpredictable. A failure to use a random value for the ephemeral key in the