Cryptography Reference
In-Depth Information
is then called
square function
. It is bijective, and hence the inverse function
Sqrt
n
:
QR
n
−→
QR
n
x
1
/
2
x
−→
exists and is called the
square root function
. Either function maps an element of
QR
n
to another element of
QR
n
. The function represents a permutation.
To turn the square function into a one-way function (or one-way permutation,
respectively), we must have an index set
I
. Taking into account that
n
must be a
Blum integer, the index set can be defined as follows:
I
:=
{
n
|
n
=
pq
;
p, q
∈
P
;
p
=
q
;
|
p
|
=
|
q
|
;
p, q
≡
3(mod4)
}
Using this index set, we can define the following family of square functions:
x
2
Square :=
{
Square
n
:
QR
n
−→
QR
n
,x
−→
}
n∈I
This family is called the
Square family
, and the family of inverse functions can
be defined as follows:
x
1
/
2
{
Sqrt
n
:
QR
n
−→
QR
n
,x
−→
}
n∈I
Sqrt :=
It is called the
Sqrt family
. The Square family of trapdoor permutations is
used by several public key cryptosystems, including, for example, the Rabin public
key cryptosystem (see Section 14.2.2). For every
n
I
, the prime factors
p
and
q
represent a trapdoor. Hence, if we can solve the IFP, then we can trivially invert the
Square family. We look at algorithms to solve the IFP next.
∈
7.3
INTEGER FACTORIZATION ALGORITHMS
Many algorithms can be used to solve the IFP.
4
They can be divided into two broad
categories:
4
http://mathworld.wolfram.com/PrimeFactorizationAlgorithms.html
