Cryptography Reference
In-Depth Information
(
SHA
(
x
)+
dr
)
k
E
−
1
s
≡
mod
q
which is equivalent to:
s
−
1
SHA
(
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
.
We can raise
α
to either side of the equation if we reduce modulo
p
:
k
E
u
1
+
du
2
α
mod
p
≡
α
mod
p
.
d
Since the public key value
β
was computed as
β
≡
α
mod
p
, we can write:
k
E
u
1
u
2
α
mod
p
≡
α
β
mod
p
.
We now reduce both sides of the equation modulo
q
:
k
E
u
1
u
2
(
α
mod
p
) mod
q
≡
(
α
β
mod
p
) mod
q
.
u
2
mod
p
) mod
q
,
this expression is identical to the condition for verifying a signature as valid:
k
E
mod
p
) mod
q
and
v
u
1
Since
r
was constructed as
r
≡
(
α
≡
(
α
β
r
≡
v
mod
q
.
Let's look at an example with small numbers.
Example 10.4.
Bob wants to send a message
x
to Alice which is to be signed with
the DSA algorithm. Suppose the hash value of
x
is
h
(
x
)=26. Then the signature
and verification process is as follows:
Alice
Bob
1. choose
p
= 59
2. choose
q
= 29
3. choose
= 3
4. choose private key
d
= 7
5. β = α
α
d
≡
4 mod 59
)=(59
,
29
,
3
,
4)
←−−−−−−−−−−−−−−−−
(
p
,
q
,
α
,
β
sign:
compute hash of message
h
(
x
)=26
1. choose ephemeral key
k
E
= 10
2.
r
=(3
10
mod 59)
≡
20 mod 29
3.
s
=(26 + 7
·
20)
·
3
≡
5 mod 29
(
x
,
(
r
,
s
))=(
x
,
(20
,
5))
←−−−−−−−−−−−−−−−−
verify:
1.
w
= 5
−
1
≡
6mod29
2.
u
1
= 6
·
26
≡
11 mod 29
3.
u
2
= 6
·
20
≡
4 mod 29
4.
v
=(3
11
·
4
4
mod 59) mod 29 = 20
5.
v
≡
r
mod 29 =
⇒
valid signature
