Cryptography Reference
In-Depth Information
g
x
(mod
p
), and a public key certificate from
the KAC. He or she can use the Schnorr protocol to authenticate to the verifier B
in multiple rounds. A round of the Schnorr authentication protocol is illustrated in
Protocol 17.3. A randomly selects
r
private key
x
, the public key
y
≡
∈
R
Z
p
, computes
t
=
g
r
(mod
p
), and sends
this value to B. B, in turn, randomly selects
c
between 0 and 2
k
1 (
k
representing
the security parameter) and uses this value to challenge A. A must respond with
s
−
1), and B must verify that
g
s
ty
c
(mod
p
).
≡
r
+
cx
(mod
p
−
≡
The protocol is complete, because
g
s
g
r
g
cx
ty
c
(mod
p
)
.
≡
≡
The protocol is sound, because the adversary can either guess or prepare
himself or herself for one particular challenge. If the adversary were able to prepare
himself or herself for two challenges
c
1
and
c
2
, then he or she could also determine
the A's private key
x
.From
g
s
1
≡
ty
c
1
(mod
p
) and
g
s
2
≡
ty
c
2
(mod
p
),it
follows that
g
s
1
−s
2
≡
y
c
1
−c
2
≡
g
x·
(
c
1
−c
2
)
(mod
p
), and hence
x
≡
(
s
1
−
s
2
)
·
(
c
1
−
1). The success probability is 2
−k
. For any reasonably sized
k
(e.g., 20 to 70 bits), this probability is sufficiently small.
The efficiency of the Schnorr authentication protocol doesn't look impressive
at first sight. Note that computation of the commitment
t
is similar to the computa-
tion of an RSA digital signature (if
p
and
n
are equally sized). The major advantage
of the Schnorr authentication protocol, however, is related to the fact that the com-
putation of the commitment can be preprocessed, meaning that A can use offline
computing power to precompute many values for
t
that he or she can use later on.
The computation he or she has to do during the interaction with B is restricted to a
modular addition and a modular multiplication (both of them being efficient). This
is particularly advantageous for smart card implementations.
c
2
)
−
1
(mod
p
−
17.3.5
Turning Interactive Proofs of Knowledge into DSSs
Any (zero-knowledge) interactive proof of knowledge can be turned into a digital
signature system. In this case, there is no possibility for the verifier to challenge
the signatory. Instead, the challenge must be computed from the message
m
to be
signed. It must, however, be ensured that only
c
can be computed, once the signer
has committed to a specific value
t
. Consequently,
c
=
h
(
m, t
) with
h
being a
cryptographic hash function. In this setting,
m
is digitally signed with a pair (
t, s
),
and the digital signature can be verified similar to the protocol that implements the
interactive proof of knowledge. The resulting DSS is quite efficient.
