Cryptography Reference
In-Depth Information
Ms.
A
now has the problem of deciding which of the four roots
M
i
represents
the original plain text
M
. If prior to encoding the message
B
adds some redundant
material, say a repetition of the last
r
bits, and informs
A
of this, then
A
will have
no trouble in choosing the right text, since the probability that one of the other
texts will have the same identifier is very slight.
Furthermore, redundancy prevents the following attack strategy against the
Rabin procedure: If an attacker
X
chooses at random a number
R ∈
Z
n
A
and is
able to obtain from
A
oneoftheroots
R
i
of
X
:=
R
2
mod
n
A
(no matter how
he or she may motivate
A
to cooperate), then
R
i
≡±R
mod
n
A
will hold with
probability
2
.
From
n
A
=
p · q
|
R
i
− R
2
=(
R
i
− R
)(
R
i
+
R
)
=0
, however, one
would have
1
, and
X
would have broken the code
with the factorization of
n
A
(cf. [Bres], Section 5.2). On the other hand, if the
plain text is provided with redundancy, then
A
can always recognize which root
represents a valid plain text. Then
A
would at most reveal
R
(on the assumption
that
R
had the right format), which for Mr. or Ms.
X
, however, would be useless.
The avoidance of deliberate or accidental access to the roots of a pretended
cipher text is a necessary condition for the use of the procedure in the real world.
The following example of the cryptographic application of quadratic residues
deals with an identification schema published in 1986 by Amos Fiat and Adi
Shamir. The procedure, conceived especially for use in connection with smart
cards, uses the following aid: Let
I
be a sequence of characters with information
for identifying an individual
A
,let
m
be the product of two large primes
p
and
q
, and let
f
(
Z, n
)
→
Z
m
be a random function that maps arbitrary finite
sequences of characters
Z
and natural numbers
n
in some unpredictable fashion
to elements of the residue class ring
= gcd (
R
−
R
i
,n
A
)
∈{
p, q
}
Z
m
. The prime factors
p
and
q
of the modulus
m
are known to a central authority, but are otherwise kept secret. For the identity
represented by
I
and a yet to be determined
k ∈
N
the central authority has now
the task of producing key components as follows.
Algorithm for key generation in the Fiat-Shamir procedure
1.
Compute numbers
v
i
=
f
(
I,i
)
∈
Z
m
for some
i
≥
k
∈
N
.
2.
Choose
k
different quadratic residues
v
i
1
,...,v
i
k
from among the
v
i
and
compute the smallest square roots
s
i
1
,...,s
i
k
of
v
−
1
,...,v
−
1
i
k
Z
m
.
in
i
1
3.
Store the values
I
and
s
i
1
,...,s
i
k
securely against unauthorized access
(such as in a smart card).
For generating keys
s
i
j
we can use our functions
jacobi_l()
and
root_l()
;
the function
f
can be constructed from one of the
hash functions
from Chapter
17, such as RIPEMD-160. As Adi Shamir once said at a conference, “Any crazy
function will do.”
