Cryptography Reference
In-Depth Information
Verification Stage
: Bob does each of the following:
∈
F
p
and reject if not.
1. Using Alice's public key (
p, α, y
) verify that
β
y
β
β
γ
(mod
p
), and
σ
α
m
(mod
p
).
2. Compute
δ
≡
≡
3. ver
k
(
m,
(
β,γ
)) = 1 if and only if
σ
≡
δ
(mod
p
). Otherwise reject.
Example 4.8
Let
p
= 5531
, with primitive root
α
=10
.Alice selects
a
= 351
as her private key and computes
α
a
10
351
y
(mod 5531)
.Thus, her
public key is
(
p, α, y
) = (5531
,
10
,
3122)
.If
m
= 1129
, and she chooses
r
= 151
,
then she computes
β
≡
≡
3122
≡
≡
10
151
≡
1257 (mod 5531)
.Then she computes
aβ
)
r
−
1
151
−
1
γ
≡
(
m
−
≡
(1129
−
351
·
1257)
·
≡
52 (mod 5530)
,
and sends
sig
k
(1129
,
151) = (
β,γ
) = (1257
,
52)
to Bob.First Bob verifies that
β
)
∗
, then computes,
∈
(
Z
/p
Z
y
β
β
γ
3122
1257
1257
52
10
1129
α
m
(mod 5531)
,
δ
≡
≡
≡
3865
≡
≡
so Bob accepts the signature as valid.
Analysis
Suppose that Mallory tries to forge Alice's signature on
m
by choosing a
random
r
1
∈
)
∗
and computing
β
≡
α
r
1
(mod
p
). Mallory is now in
(
Z
/
(
p
−
1)
Z
the position of having to compute
γ
≡
aβ
)
r
−
1
1
(
m
−
(mod
p
−
1)
.
However, if the DLP in
F
p
is intractable, then this computation is infeasible so
only a guess at the value of
γ
is possible with a probability of success being
1
/p
. For large
p
, this is insignificant.
As noted prior to the description of the ElGamal scheme, we purposely did
not hash the message. However, one
must
hash the message or else Mallory can
forge a signature on a random message. Here is how he does it.
Suppose that Mallory selects
r
1
,r
2
∈
Z
−
Z
)
∗
. He then computes
(
/
(
p
1)
α
r
1
y
r
2
(mod
p
)
β
1
r
−
1
β
1
≡
and
γ
1
≡−
(mod
p
−
1)
.
2
Now we show that (
β
1
,γ
1
) is a valid signature for the message
m
1
≡
γ
1
r
1
(mod
p
−
1)
.
We have,
y
β
1
β
γ
1
1
α
aβ
1
α
(
r
1
+
ar
2
)(
−
β
1
r
−
2
)
α
aβ
1
α
(
r
1
+
ar
2
)
γ
1
≡
≡
≡
α
aβ
1
α
−
β
1
r
1
r
−
1
α
−
β
1
r
1
r
−
1
−
β
1
a
α
γ
1
r
1
α
m
1
(mod
p
)
.
≡
≡
≡
2
2
Search WWH ::
Custom Search