Cryptography Reference
In-Depth Information
With the help of the information stored by the central authority on the smart
card Ms.
A
can now authenticate herself to a communication partner Mr.
B
.
Protocol for authentication à la Fiat-Shamir
1.
A
sends
I
and the numbers
i
j
,
j
=1
,...,k
,to
B
.
2.
B
generates
v
i
j
=
f
(
I,i
j
)
∈
Z
m
for
j
=1
,...,k
. The following steps 3-6
are repeated for
τ
=1
,...,t
(for a value
t
∈
N
yet to be determined):
3.
A
chooses a random number
r
τ
∈
Z
m
and sends
x
τ
=
r
τ
to
B
.
4.
B
sends a binary vector
(
e
τ
1
,...,e
τ
k
)
to
A
.
5.
A
sends numbers
y
τ
:=
r
τ
e
τ
i
=1
s
i
∈
Z
m
to
B
.
6.
B
verifies that
x
τ
=
y
τ
e
τ
i
=1
v
i
.
If
A
truly possesses the values
s
i
1
,...,s
i
k
, then in step 6
y
τ
e
τ
i
=1
v
i
=
r
τ
e
τ
i
=1
v
i
=
r
τ
e
τ
i
=1
s
i
v
−
1
i
v
i
=
r
τ
·
e
τ
i
=1
Z
m
), and
A
thereby has proved her identity to
B
.An
attacker who wishes to assume the identity of
A
can with probability
2
−
kt
guess
the vectors
(
e
τ
1
,...,e
τ
k
)
that
B
will send in step 4, and as a precaution in step 3
holds (all calculations are in
send the values
x
τ
=
r
τ
e
τ
i
=1
v
i
to
B
;for
k
=
t
=1
, for example, this would
give the attacker an average hit number of
2
. Thus the values of
k
and
t
should be
chosen such that an attacker has no realistic probability of success and such that
furthermore—depending on the application—suitable values result for
•
the size of the secret key;
•
the set of data to be exchanged between
A
and
B
;
•
the required computer time, measured as the number of multiplications.
Such parameters are given in [Fiat] for various values of
k
and
t
with
kt
=72
.
All in all, the security of the procedure depends on the secure storage of the
values
s
i
j
, on the choice of
k
and
t
, and on the factorization problem: Anyone
who can factor the modulus
m
into the factors
p
and
q
can compute the secret
key components
s
i
j
, and the procedure has been broken. It is a matter, then, of
choosing the modulus in such a way that it is not easily factorable. In this regard
the reader is again referred to Chapter 17, where we discuss the generation of RSA
moduli, subject to the same requirements.
A further security property of the procedure of Fiat and Shamir is that
A
can repeat the process of authentication as often as she wishes without thereby
giving away any information about the secret key values. Algorithms with
such properties are called
zero knowledge processes
(see, for example, [Schn],
Section 32.11).
