Cryptography Reference
In-Depth Information
Dividing the two equivalences yields (
s
1
/s
2
)
e
y
c
1
−c
2
≡
(
x
c
1
−c
2
)
e
(mod
≡
x
c
1
−c
2
(mod
n
). Because
gcd
(
e, c
1
−
n
), and hence
s
1
/s
2
≡
c
2
)=1(note that
e
is prime), the attacker can use the Euclid extended algorithm to compute
u
and
v
with
u
(
c
1
−
c
2
)+
ve
=1. He or she can then compute A's private key
x
as follows:
(
s
1
/s
2
)
u
y
v
x
u
(
c
1
−c
2
)
x
ve
≡
≡
x
(mod
n
)
Consequently, if an attacker knew to prepare himself or herself for at least two
challenges, he or she could extract
e
th
roots without knowing the group order
φ
(
n
).
Against this background, it is reasonable to assume that the attacker can prepare
himself or herself for one challenge at most, and hence the success probability is
1
/e
.If
e
is sufficiently large, this probability can be made sufficiently small.
17.3.4
Schnorr
The Fiat-Shamir and Guillou-Quisquater protocols are based on the difficulty of
computing
e
th
roots in a finite group of unknown order (
e
=2in the case of Fiat-
Shamir). There are other protocols that are based on the discrete logarithm problem
(e.g., [26, 27]). In such a protocol, the prover shows that he or she knows the discrete
logarithm of his or her public key.
In this section, we briefly look at Claus P. Schnorr's proposal [27]. Unfortu-
nately, the Schnorr protocol cannot be shown to have the zero-knowledge property in
a mathematically strong sense (i.e., it is currently not known how to build a simulator
that can generate (
t, c, s
)).
Protocol 17.3
A round in the Schnorr authentication protocol.
A
B
(
p, g, x
)
(
p, g, y
)
r ∈
R
Z
p
t
=
g
r
(mod
p
)
t
−
c
←−
∈
R
{
0
,...,
2
k
c
−
1
}
s
−→
s ≡ r
+
cx
(mod
p −
1)
g
s
≡ ty
c
(mod
p
)
(
accept
or
reject
)
In the Schnorr authentication protocol, it is assumed that there is a trusted
party that acts as key authentication center (KAC). The KAC publishes a large prime
p
that represents the modulus and a generator
g
of
Z
p
. The prover A receives a
