Cryptography Reference
In-Depth Information
an elliptic curve. Thus, the arithmetic to be performed for actually computing an
ECDSA signature is entirely different from that used for DSA.
The ECDSA standard is defined for elliptic curves over prime fields
Z
p
and Ga-
lois fields
GF
(2
m
). The former is often preferred in practice, and we will only in-
troduce this one in what follows.
Key Generation
The keys for the ECDSA are computed as follows:
Key Generation for ECDSA
1. Use an elliptic curve
E
with
modulus
p
coefficients
a
and
b
a point
A
which generates a cyclic group of prime order
q
2. Choose a random integer
d
with 0
<
d
<
q
.
3. Compute
B
=
dA
.
The keys are now:
k
pub
=(
p
,
a
,
b
,
q
,
A
,
B
)
k
pr
=(
d
)
Note that we have set up a discrete logarithm problem where the integer
d
is the
private key and the result of the scalar multiplication, point
B
, is the public key.
Similar to DSA, the cyclic group has an order
q
which should have a size of at least
160 bit or more for higher security levels.
Signature and Verification
Like DSA, an ECDSA signature consists of a pair of integers (
r
,
s
). Each value has
the same bit length as
q
, which makes for fairly compact signatures. Using the public
and private key, the signature for a message
x
is computed as follows:
ECDSA Signature Generation
1. Choose an integer as random ephemeral key
k
E
with 0
<
k
E
<
q
.
2. Compute
R
=
k
E
A
.
3. Let
r
=
x
R
.
4. Compute
s
r
)
k
E
−
1
≡
(
h
(
x
)+
d
·
mod
q
.
