Cryptography Reference
In-Depth Information
the Jacobi symbol can be computed efficiently (without knowledge of the factorization
of the modulus) does
not
seem to yield an
efficient
algorithm for determining whether or
not a given residue is a square modulo a given composite (of unknown factorization). In
fact, it is believed that determining whether or not a given integer is a quadratic residue
modulo a given composite (of unknown factorization) is infeasible. Goldwasser and
Micali [123] have suggested use of the conjectured intractability of this problem toward
the construction of cryptographic schemes, and that suggestion has been followed in
numerous works.
A.2.4. Blum Integers and Their Quadratic-Residue Structure
We call
N
=
P
·
Q
, where
P
and
Q
are primes, a
Blum integer
if
P
≡
Q
≡
3
(mod 4).
For such
P
(resp.,
Q
), the integer
−
1 is not a quadratic residue mod
P
(resp., mod
Q
),
and it follows that
−
1 is not a quadratic residue modulo
N
and that
−
1 has Jacobi
symbol 1 mod
N
.
By earlier discussion, each quadratic residue
s
modulo
N
has four square roots,
denoted
. The important fact about Blum
Integers is that exactly one of these square roots is a quadratic residue itself.
9
Conse-
quently,
x
→
x
2
±
x
and
±
y
, so that
GCD
(
N
,
x
±
y
)
∈{
P
,
Q
}
mod
N
induces a
permutation
on the set of quadratic residues mod-
ulo
N
.
(We comment that some sources use a more general definition of Blum integers,
but the preceding special case suffices for our purposes. The term “Blum integers” is
commonly used in honor of Manuel Blum, who advocated the use of squaring modulo
such numbers as a one-way
permutation
.)
We mention that in case
P
≡
Q
(mod 8), the Jacobi symbol of 4 modulo
N
=
P
·
Q
is
−
1. In this case, obtaining a square root of 4 mod
N
that is a quadratic residue
itself allows us to factor
N
(since such a residue
r
satisfies
r
≡ ±
2
(mod
N
) and
(
r
−
2)
·
(
r
+
2)
≡
0
(mod
N
)).
9
Let
a
and
b
be such that
a
2
(mod
P
) and
b
2
≡
s
(mod
Q
). Then, either
a
or
−
a
(but not both) is a
quadratic residue mod
P
, and similarly for
b
. Suppose, without loss of generality, that
a
(resp.,
b
) is a quadratic
residue mod
P
(resp., mod
Q
). The
x
satisfying
x
≡
a
(mod
P
) and
x
≡
b
(mod
Q
) is a square root of
s
modulo
N
that is a quadratic residue itself. The other square roots of
s
modulo
N
(i.e.,
−
x
and
±
y
, such that
y
≡
a
≡
s
(mod
P
) and
y
≡−
b
(mod
Q
) are not quadratic residues mod
N
.
