Cryptography Reference
In-Depth Information
image of
c
under
BW
−
n
is the unique one of these four roots that is a quadratic residue
modulo both
p
and
q
, and it can be efficiently found by computing the Legendre
symbols by means of Algorithm 2.7.
Thus the algorithm that computes the four square roots in
Z
n
of
c
∈
QR
n
is:
Algorithm 8.2. Computation of the four square roots of a quadratic residue
modulo a Blum integer.
Input
:
(
p
,
q
)
(where
p
and
q
are distinct Blum primes with
n
=
pq
)and
c
∈
QR
n
.
Output
: The four square roots of
c
in
Z
n
.
c
(
p
+
1
)/
4
mod
q
.
2.
Compute
, using the extended Euclidean algorithm,
y
p
and
y
q
such that 1
c
(
p
+
1
)/
4
mod
p
and
m
q
1.
Compute
n
:=
pq
,
m
p
:=
:=
=
y
p
p
+
y
q
q
.
3.
Compute
r
:=
y
p
pm
q
+
y
q
qm
p
and
s
:=
y
p
pm
q
−
y
q
qm
p
.
4.
return
{
r
mod
n
,
s
mod
n
,
−
r
mod
n
,
−
s
mod
n
}
.
Let us see that this algorithm is correct and outputs the set of the four square roots
of
c
in
Z
p
and,
QR
n
. As we have remarked,
±
m
p
are the two square roots of
c
in
Z
q
. Thus the square roots of
c
in
Z
n
similarly,
±
m
q
are the two square roots of
c
in
are the solutions of the four systems of congruences:
x
≡±
m
p
(
mod
p
)
x
≡±
m
q
(
mod
q
)
which can be found by applying the Chinese remainder theorem. Looking at the
proof of Theorem 2.12 we see that the four roots are
±
r
mod
n
and
±
s
mod
n
,
where
r
y
q
qm
p
.
The algorithm that computes the inverse of the Blum-Williams function is the
same as the preceding one, except that it selects the unique square root of
c
that is a
quadratic residue modulo
n
and returns it as output:
:=
y
p
pm
q
+
y
q
qm
p
and
s
:=
y
p
pm
q
−
Algorithm 8.3. Computation of the inverse of the Blum-Williams function.
Input
:
(
p
,
q
)
(where
p
and
q
are distinct Blum primes with
n
=
pq
)and
c
∈
QR
n
.
Output
:
m
∈
QR
n
such that
m
2
mod
n
=
c
.
1.
Compute
n
:=
pq
,
m
p
:=
c
(
p
+
1
)/
4
mod
p
and
m
q
:=
c
(
p
+
1
)/
4
mod
q
.
2.
Compute
, using the extended Euclidean algorithm,
y
p
and
y
q
such that 1
=
y
p
p
+
y
q
q
.
3.
return
m
:=
(
y
p
pm
q
+
y
q
qm
p
)
mod
n
.
The algorithmproceeds asAlgorithm8.2 until the inverse
y
p
of
p
modulo
q
and the
inverse
y
q
of
q
modulo
p
are found. This gives the four square roots of
c
modulo
n
and
the one that belongs to
QR
n
can be found, for example, by computing the Legendre
symbols modulo
p
and
q
and checking that both are equal to
1. However, this com-
putation is not really necessary for we can directly see that the root
r
+
:=
(
y
p
pm
q
+
