Cryptography Reference
In-Depth Information
an adversary wants to generate a valid signature. In this case, the adversary first
generates
4
h
(
m
)
h
(
m
)
−
1
(mod (
p
u
≡
−
1))
and then computes
s
≡
su
(mod (
p
−
1))
and
r
that satisfies the following system of two equivalences:
r
≡
ru
(mod (
p
−
1))
r
≡
r
(mod
p
)
Obviously, the CRT and the CRA can be used to compute
r
(see Section
3.3.3). The pair (
r
,s
) then represents the ElGamal signature for
m
(or
h
(
m
),
respectively). In fact, one can show that
y
r
(
r
)
s
y
ru
r
su
(mod
p
)
≡
g
u
(
xr
+
ks
)
(mod
p
)
≡
g
h
(
m
)
(mod
p
)
.
≡
On the other hand, one can show that then
r
≥
p
, and hence 1
≤
r
≤
p
−
1
does not apply.
In either case, it is necessary to use a cryptographic hash function
h
and not
to directly sign a message
m
.If
m
were signed directly (i.e., without first hashing
it), then it would be possible to existentially forge a digital signature. In fact, if
m
is
signed directly, then the signature verification equivalence is
g
m
y
r
r
s
(mod
p
).
In this case, it is possible to select
r
,
s
,and
m
in a way that the equivalence is
satisfied. More specifically, one can randomly select two integers
u
and
v
with
gcd
(
v, p
≡
−
1) = 1, and compute
r
,
s
,and
m
as follows:
g
u
y
v
(mod
p
)
r
≡
rv
−
1
(mod (
p
s
≡−
−
1))
m
≡
su
(mod(
p
−
1))
4
Note that it is required that there exists a multiplicative inverse of
h
(
m
) modulo
p −
1.
