Cryptography Reference
In-Depth Information
What we showed so far is that the expression
u
1
A
+
u
2
B
is equal to
k
E
A
if the
correct signature and key (and message) have been used. But this is exactly the
condition that we check in the verification process by comparing the
x
-coordinates
of
P
=
u
1
A
+
u
2
B
and
R
=
k
E
A
.
Using the small elliptic curve from Chap. 9, we look at a simple ECDSA exam-
ple.
Example 10.5.
Bob wants to send a message to Alice that is to be signed with the
ECDSA algorithm. The signature and verification process is as follows:
Alice
Bob
choose
E
with
p
= 17,
a
= 2,
b
=
2, and
A
=(5
,
1) with
q
= 19
choose
d
= 7
compute
B
=
dA
= 7
·
(5
,
1)=
(0
,
6)
(
p
,
a
,
b
,
q
,
A
,
B
)=
←−−−−−−−−−−−−
(17
,
2
,
2
,
19
,
(5
,
1)
,
(0
,
6))
sign:
compute hash of message
h
(
x
)=
26
choose ephemeral key
k
E
= 10
R
= 10
·
(5
,
1)=(7
,
11)
r
=
x
R
= 7
s
=(26 + 7
·
·
≡
7)
2
17 mod 19
(
x
,
(
r
,
s
))=(
x
,
(7
,
17))
←−−−−−−−−−−−−−
verify:
w
= 17
−
1
9 mod 19
u
1
= 9
·
26
≡
6 mod 19
u
2
= 9
·
7
≡
6 mod 19
P
= 6
·
(5
,
1)+6
·
(0
,
6)=(7
,
11)
x
P
≡
r
mod 19 =
⇒
valid signature
≡
Note that we chose the elliptic curve
E
:
y
2
x
3
+ 2
x
+ 2 mod 17
≡
which is discussed in Sect. 9.2. Because all points of the curve form a cyclic group
of order 19, i.e., a prime, there are no subgroups and hence in this case
q
= #
E
= 19.
10.5.2 Computational Aspects
We discuss now the computations involved in the three stages of the ECDSA
scheme.
