Cryptography Reference
In-Depth Information
x
mod
p
is satisfied. Otherwise, the verification fails. In order to make sense of the rather
arbitrary looking rules for computing the signature parameters
r
and
s
as well as the
verification, it is helpful to study the following proof.
r
r
s
In short, the verifier accepts a signature (
r
,
s
) only if the relation
β
·
≡
α
Proof.
We'll prove the correctness of the Elgamal signature scheme. More specif-
ically, we show that the verification process yields a “true” statement if the verifier
uses the correct public key and the correct message, and if the signature parameters
(
r
,
s
) were chosen as specified. We start with the verification equation:
r
r
s
d
)
r
(
k
E
)
s
β
·
≡
(
α
α
mod
p
dr
+
k
E
s
≡
α
mod
p
.
x
:
We require that the signature is considered valid if this expression is identical to
α
x
dr
+
k
E
s
α
≡
α
mod
p
.
(10.1)
According to Fermat's Little Theorem, the relationship (10.1) holds if the exponents
on both sides of the expression are identical modulo
p
−
1:
x
≡
dr
+
k
E
s
mod
p
−
1
from which the construction rule of the signature parameters
s
follows:
r
)
k
−
1
E
s
≡
(
x
−
d
·
mod
p
−
1
.
The condition that gcd(
k
E
,
p
−
1)=1 is required since we have to invert the
ephemeral key modulo
p
1 when computing
s
.
Let's look at an example with small numbers.
−
Example 10.2.
Again, Bob wants to send a message to Alice. This time, it should
be signed with the Elgamal digital signature scheme. The signature and verification
process is as follows:
