Cryptography Reference
In-Depth Information
Key Generation for Elgamal Digital Signature
1. Choose a large prime
p
.
2. Choose a primitive element
Z
p
or a subgroup of
Z
p
.
α
of
3. Choose a random integer
d
∈{
2
,
3
,...,
p
−
2
}
.
d
4. Compute
β
=
α
mod
p
.
The public key is now formed by
k
pub
=(
p
,
α
,
β
), and the private key by
k
pr
=
d
.
Signature and Verification
Using the private key and the parameters of the public key, the signature
sig
k
pr
(
x
,
k
E
)=(
r
,
s
)
for a message
x
is computed during the signing process. Note that the signature
consists of two integers
r
and
s
. The signing consists of two main steps: choosing a
random value
k
E
, which forms an ephemeral private key, and computing the actual
signature of
x
.
Elgamal Signature Generation
1. Choose a random ephemeral key
k
E
∈{
0
,
1
,
2
,...,
p
−
2
}
such that
1)=1.
2. Compute the signature parameters:
gcd(
k
E
,
p
−
k
E
r
≡
α
mod
p
,
r
)
k
−
1
E
s
≡
(
x
−
d
·
mod
p
−
1
.
On the receiving side, the signature is verified as ver
k
pub
(
x
,
(
r
,
s
)) using the public
key, the signature and the message.
Elgamal Signature Verification
1. Compute the value
r
r
s
t
≡
β
·
mod
p
2. The verification follows from:
t
≡
α
x
mod
p
=
⇒
valid signature
x
≡
α
mod
p
=
⇒
invalid signature
