Cryptography Reference
In-Depth Information
from DSA. It is a standard from several organizations including NIST and ANSI (see
Refs. [3, 8]).
Public parameters
: we use finite fields of two possible types: either a field of
characteristic two or a large prime field. The public parameters consist of the
field cardinality
q
, the selected field representation (in the characteristic two
case, i.e. an irreducible polynomial over
Z
2
), an elliptic curve defined by two
field elements
a
and
b
, a prime number
n
larger than 2
160
, and an element
G
of the elliptic curve of order
n
. The elliptic curve equation over GF(
q
)is
y
2
x
3
ax
2
b
in the characteristic two case and
y
2
x
3
b
in the prime field case. Public parameters are subject to many security criteria.
Setup
: pick an integer
d
in [1
+
xy
=
+
+
=
+
ax
+
,
−
=
dG
. Output (
K
p
,
=
n
1], compute
Q
K
s
)
d
).
Signature generation
: pick
k
in [1
(
Q
,
,
n
−
1] at random and compute
(
x
1
,
y
1
)
=
kG
r
=
x
1
mod
n
H
(
M
)
+
dr
s
=
mod
n
k
Here
x
1
is simply a standard way to convert a field element
x
1
into an integer.
If
r
=
0or
s
=
0, try again. Output the signature
σ
=
(
r
,
s
)
Verification
: check that
Q
=
O
,
Q
∈
C
, and
nQ
=
O
. Check that
r
and
s
are in
H
(
M
)
s
[1
,
n
−
1] and that
r
=
x
1
mod
n
for (
x
1
,
y
1
)
=
u
1
G
+
u
2
Q
,
u
1
=
mod
r
s
n
, and
u
2
=
mod
n
.
(See Fig. 10.8). The
H
hash function is the same standard hash function as usual, i.e.
SHA-1.
Adversary
Message
M
M
r
,
s
M
,
r
,
s
M
r
,
s
M
Signature
Verification
k
∈
Z
n
r
= (
k
.
G
)
1
mod
n
s
=
compare
r
and
H
(
M
s
G
+
s
Q
1
r
mod
n
H
(
M
)+
dr
k
mod
n
Secret key
d
Public key
Q
Q
AUTHENTICATED
Q
=
d
.
G
mod
p
Generator
Figure 10.8.
ECDSA.
Search WWH ::
Custom Search