Cryptography Reference
In-Depth Information
In step 3 the
x
-coordinate of the point
R
is assigned to the variable
r
.Themes-
sage
x
has to be hashed using the function
h
in order to compute
s
. The hash function
output length must be at least as long as
q
. More about the choice of the hash func-
tion will be said in Chap. 11. However, for now it is sufficient to know that the
hash function compresses
x
and computes a fingerprint which can be viewed as a
representative of
x
.
The signature verification process is as follows:
ECDSA Signature Verification
s
−
1
1. Compute auxiliary value
w
≡
mod
q
.
2. Compute auxiliary value
u
1
≡
w
·
h
(
x
) mod
q
.
3. Compute auxiliary value
u
2
≡
w
·
r
mod
q
.
4. Compute
P
=
u
1
A
+
u
2
B
.
5. The verification
ver
k
pub
(
x
,
(
r
,
s
)) follows from:
x
P
≡
r
mod
q
=
⇒
valid signature
≡
r
mod
q
=
⇒
invalid signature
In the last step, the notation
x
P
indicates the
x
-coordinate of the point
P
. The verifier
accepts a signature (
r
,
s
) only if the
x
P
has the same value as the signature parameter
r
modulo
q
. Otherwise, the signature should be considered invalid.
Proof.
We show that a signature (
r
,
s
) satisfies the verification condition
r
≡
x
P
mod
q
. We'll start with the signature parameter
s
:
(
h
(
x
)+
dr
)
k
E
−
1
s
≡
mod
q
which is equivalent to:
s
−
1
h
(
x
)+
ds
−
1
r
mod
q
.
k
E
≡
The right-hand side can be expressed in terms of the auxiliary values
u
1
and
u
2
:
k
E
≡
u
1
+
du
2
mod
q
.
Since the point
A
generates a cyclic group of order
q
, we can multiply both sides of
the equation with
A
:
k
E
A
=(
u
1
+
du
2
)
A
.
Since the group operation is associative, we can write
k
E
A
=
u
1
A
+
du
2
A
and
k
E
A
=
u
1
A
+
u
2
B
.
