Cryptography Reference
In-Depth Information
So the question (most general-purpose integer factorization algorithms try to
answer) is how to find two integers
x
and
y
that satisfy equivalence (7.1).
The general approach is to choose a set of
t
relatively small primes
S
=
{
p
1
,p
2
,...,p
t
}
(the so-called factor base) and to proceed with the following two
steps:
a
i
(mo d
n
) for arbitrary
a
i
, and this value is
expressed as the product of powers of the primes in
S
. In this case,
b
i
can
be represented as a vector in a
t
-dimensional vector space. This step is called
the
relation collection stage
, and it is highly parallelizable.
•
First, one computes
b
i
≡
•
Second, if we have collected enough (e.g.,
t
+1) values for
b
i
, then a solution
of equivalence (7.1) can be found by performing the Gaussian elimination
on the matrix
B
=[
b
i
]. This step is called the
matrix step
and cannot be
parallelized. It works on a huge (sparse) matrix and eventually comes up with
a nontrivial factor of
n
.
Obviously, the choice of the number of primes of
S
is very important for the
performance of the QS. If it is too small, then the relation collection stage may take
very long (because a very small proportion of numbers factor over a small set of
primes). If, however, it is too large (and too many primes are put into
S
), then the
matrix may become too large to be reduced efficiently.
In either case, the QS has a subexponential running time of
L
n
[
2
,c
] for some
constant
c
. As mentioned later, a variation of the QS was used in 1994 when RSA-
129 was successfully factorized.
7.3.2.3
NFS
The NFS was developed and proposed in the 1990s (e.g., [7]). It is conceptually
similar to the QS and is currently the fastest general-purpose integer factorization
algorithm. It has a running time of
L
n
[
3
,c
] for
c
=1
.
923 and was used in 1999
to factorize RSA-155 (see the following section). Furthermore, there are several
variations of it, including, for example, the special number field sieve (SNFS) and
the general number field sieve (GNFS).
7.3.3
State of the Art
When the RSA public key cryptosystem was published, a famous challenge was
posted in the August 1977 issue of
Scientific American
[8]. In fact, US$100 were
offered to anyone who could decrypt a message that was encrypted using a 129-
digit integer acting as modulus. The number became known as RSA-129, and it was
