It is not necessary to provide an efficient algorithm guaranteed to crack all instances of a cryptosystem to call its security into question, and our analysis is only an indication that the simple system of the previous section can often be broken.

Suppose we are given the sequence :

generated using an unknown multiplier (correponding to 1000 in the previous example), an unknown modulus , and an unknown super-increasing sequence . Let . Then there are non-negative such that .

must be larger than all the , hence it must be significantly
larger than the earliest members of the sequence.

The decryption method begins by guessing which
of the known correspond to a few of the early members of the sequence.
A trial-and-error approach is considered feasible for practical size
problems.

Suppose we have guessed that 2464, 611, and 2456 correspond to
the first three , and further that 2464 corresponds to .

may be eliminated from pairs of equations to obtain:

Since is large compared to this implies

must be small-- about the size of (positive or negative). In other words, and must both be close to 0 or to 2464 mod 2464.

It is plausible that restrictions of this kind give a lot of
information about . As we look at all possible values of ,
mod 2464 is evenly distributed through the entire range
from 0 to 2463. If we require, for example, that the number is
either or , we would expect that only about
of the values for satisfy this. It seems plausible that the
distribution of is independent of the distribution of
, so a similar restriction on the second number reduces
the possible values of by .

In our example,
implies
and
. We look at the values of
for something which makes mod 2464 small. Part of the
results:

The multiples of are clearly the most likely candidates. We try , which gives .

[The published algorithm recommends guessing more than 3 of the
lowest and determining from an integer program:

using a special algorithm which is polynomial-time for a fixed number of constraints.]

Since
implies is close to , we
try using , on the , which gives:

This is

The were generated using , ,
. Comparison of the
with the ``almost'' super-increasing
sequence obtained above shows that, except for the first few terms,
the ratio of terms from the two sequences is nearly constant. Since
a multiple of a super-increasing sequence is super-increasing,
this explains why we would expect to obtain a useful sequence.

- ...
^{4} - Calculations in this section were done using the Calc program based on the emacs editor. Both programs are available free as part of the GNU system.

2002-12-14