Cryptography Reference
In-Depth Information
14.2.2.4
Security Analysis
A major advantage of the Rabin asymmetric encryption system is that it is based
on the Square family and that the problem of inverting a trapdoor permutation from
this family can be shown to be computationally equivalent to solving the IFP. This
is expressed in Theorem 14.1.
Theorem 14.1
Breaking the Rabin asymmetric encryption system is computation-
ally equivalent to solving the IFP.
Proof.
To prove the theorem, one must show (a) that somebody who can solve the
IFP can also break the Rabin asymmetric encryption system (by inverting a trapdoor
permutation), and (b) that somebody who can break the Rabin system can also solve
the IFP.
Direction (a) is obvious—that is, somebody who can solve the IFP for
n
can
easily break the Rabin system by factorizing
n
and (mis)using the private key (
p, q
)
to find square roots for a given ciphertext
c
∈
Z
n
.
Direction (b) is less obvious. For this directon, we must show that somebody
who can break the Rabin system by inverting the trapdoor permutation (i.e., comput-
ing square roots) can also factorize
n
and solve the IFP, accordingly. We assume an
adversary who has a Rabin oracle
O
Rabin
that takes as input a ciphertext
c
and that
returns as output a possible plaintext
m
(that represents a square root of
c
modulo
n
). The adversary can use this oracle to solve the IFP, and to factorize
n
.Heorshe
therefore selects
x
=1, then the adversary has already found
a prime factor of
n
and is done. Otherwise (if
gcd
(
x, n
)=1), then the adversary
computes
∈
R
Z
n
.If
gcd
(
x, n
)
x
2
(mod
n
)
c
≡
and
m
=
O
Rabin
(
c
)
.
Note that
m
must be one of the four square roots of
c
. Also note that
m
and
x
may be different, but that they must at least fulfill one of the following pairs of
congruences:
1.
m
≡
x
(mod
p
) and
m
≡
x
(mod
q
): In this case,
m
=
x
and
gcd
(
m
−
x, n
)=
gcd
(0
,n
)=
n
, and this is not useful to find a prime factor of
n
.
