Cryptography Reference
In-Depth Information
512. The hash function should have a security strength at least equal to that provided
by the ECDLP on the EC subgroup of order
n
so that, for example, if
n
is a 256-bit
prime (see Table
11.1
) then we would use a hash function with a
256-bit output,
such as SHA-256 (in our implementation belowwe will actually use the same length,
as we did in the case of DSA). Given these parameters, the ECDSA algorithm based
on an elliptic curve defined over a prime field may be described as follows:
≥
Definition 11.5
The Elliptic Curve Digital Signature Algorithm
is defined as the
signature scheme:
ECDSA
=
(
Gen
ECDSA
,
Sign
ECDSA
,
Ve r
ECDSA
)
with the following algorithms:
•
Gen
ECDSA
.
Input
: The EC domain parameters
(
p
,
a
,
b
,
G
,
n
,
h
)
.
Output
:
(
d
,
Q
)
, with
d
∈[
1
,
n
−
1
]
the private key and
Q
∈
E
(
F
p
)
the public
key.
1.
Pick
a (pseudo-) random
d
←[
1
,
n
−
1
]
.
:=
∈
(
F
p
)
2.
Compute
Q
dG
E
.
3.
Output
(
,
)
d
Q
.
•
Sign
ECDSA
.
Input
: The ECdomain parameters, the hash function
H
, a private key
d
∈[
1
,
n
−
1
]
}
∗
.
and a message
m
∈{
0
,
1
Output
: A signature
(
r
,
s
)
of the message
m
.
1.
Choose
k
←[
1
,
n
−
1
]
.
2.
Compute
R
:=
kG
∈
E
(
F
p
)
.
3.
r
:=
x
(
R
)
mod
n
;
if
r
=
0
then go to
step 1.
}
∗
to
4.
Compute
e
:=
H
(
m
)
(as in 9.4.1 we assume that
H
maps
{
0
,
1
Z
n
).
k
−
1
5.
Compute
s
:=
(
e
+
dr
)
mod
n
;
if
s
=
0
then go to
step 1.
6.
Output
(
r
,
s
)
.
•
Ve r
ECDSA
.
Input
: The EC domain parameters, the hash function
H
, a public key
Q
∈
E
(
F
p
)
,
a message
m
, and a signature
(
r
,
s
)
.
Output
:Abit
b
∈{
0
,
1
}
.If
b
=
1 the signature is
valid
, otherwise it is
invalid
.
1.
Check
that 0
n
.
If
either of these conditions does not
hold
then output
0, otherwise
compute
:
<
r
<
n
and 0
<
s
<
2.
e
:=
H
(
m
)
.
s
−
1
mod
n
.
3.
w
:=
4.
u
1
:=
e
w
mod
n
.
u
2
:=
w
5.
r
mod
n
.
:=
+
∈
(
F
p
)
6.
R
u
1
G
u
2
Q
E
.
7.
If
R
=
O
and
x
(
R
)
mod
n
=
r
then output
1, otherwise
output
0.
