Cryptography Reference
In-Depth Information
for all
k
≥
k
0
.
If we accept the IFA, then the
integer factoring problem
(IFP) captured in
Definition 7.11 is intractable.
Definition 7.11 (Integer factoring problem)
Let
n
be a positive integer (i.e.,
n
∈
N
). The IFP is to determine the prime factors of
n
(i.e., to determine
p
1
,...,p
k
∈
P
and
e
1
,...,e
k
∈
N
) such that
n
=
p
e
1
···
p
e
k
.
The IFP is well defined, because every positive integer can be factored
uniquely up to a permutation of its prime factors (see Theorem 3.5). Note that the
IFP must not always be intractable, but that it must be possible to easily find an
instance of the IFP that is intractable.
Again using complexity-theoretic arguments, one can show that RSAP
≤
P
IFP (i.e., the RSAP polytime reduces to the IFP). This means that one can invert
the RSA function if one can solve the IFP. The converse, however, is not known
to be true (i.e., it is not known whether there exists a simpler way to invert the
RSA function than to solve the IFP). In order to better understand the RSAP and the
underlying RSA assumption, it is worthwhile to have a look at the currently available
integer factorization algorithms. This is done in Section 7.3.
7.2.3
Modular Square Function
Similar to the exponentiation function, the square function can be computed and
inverted efficiently in the real numbers, but it is not known how to invert it efficiently
in a cyclic group. If, for example, we consider
Z
n
, then modular squares can be
computed efficiently, but modular square roots can only be computed efficiently
if the prime factorization of
n
is known. In fact, it can be shown that computing
square roots in
Z
n
and factoring
n
are computationally equivalent. Consequently,
the modular square function looks like a candidate one-way function. Unfortunately,
the modular square function (in its general form) is neither injective nor surjective.
It can, however, be made injective and surjective (and hence bijective) if the domain
and range are both restricted to
QR
n
(i.e., the set of quadratic residues or squares
modulo
n
), with
n
being a Blum integer (see Definition 3.33). The function
Square
n
:
QR
n
−→
QR
n
x
2
x
−→
