.PH ""
.S 11
.EQ
delim $$
gsize 11
define vv % v under %
define ddelta % delta under %
define ww % w under %
define xx % x under %
define yy % y under %
.EN
.nr Pt 1
.nr Au 0
.ds HP 11 11 11 11 11 11 11
.am DE
.sp
.ls 2
..
.ce 99
.B
Cryptanalytic attacks on the multiplicative knapsack cryptosystem and on
Shamir's fast signature scheme
.sp .5
.I
A. M. Odlyzko
.sp .5
.R
AT&T Bell Laboratories
Murray Hill, New Jersey 07974
.sp
.I
ABSTRACT
.ce 0
.R
.sp
.P
The basic Merkle-Hellman additive trapdoor
knapsack public-key cryptosystem was recently
shown to be insecure, and attacks have also
been developed on stronger variants of it,
such as the Graham-Shamir system
and the iterated knapsack cryptosystem.
This paper shows that some simple variants of
another Merkle-Hellman system, the
multiplicative knapsack cryptosystem, are
insecure.
It is also shown that the Shamir
fast signature scheme
can be broken quickly.
Similar attacks can also be used to
break the Scho\*:bi-Massey authentication scheme.
These attacks have not been rigorously
proved to succeed, but heuristic
arguments and empirical evidence
indicate that they work on systems
of practical size.
.bp
.ce 99
.B
Cryptanalytic attacks on the multiplicative knapsack cryptosystem and on
Shamir's fast signature scheme
.sp .5
.I
A. M. Odlyzko
.sp .5
.R
AT&T Bell Laboratories
Murray Hill, New Jersey 07974
.sp
.ce 0
.ls 2
.H 1 Introduction
One of the best-known public-key cryptosystems,
the basic Merkle-Hellman additive trapdoor
knapsack system [18], was recently shown to be
easy to break by Shamir [25].
.PH "''- \\\\nP -''"
.nr P 1
Subsequently, Adleman [2] proposed
attacks on the Graham-Shamir scheme
and on the multiply iterated Merkle-Hellman
system.
Adleman's attack on the general multiply-iterated
knapsack systems does not seem to succeed [3,7],
but other attacks on the doubly iterated
knapsack schemes have been proposed by
Adleman and Lagarias (see [7,14]).
Furthermore, Brickell [6] and Lagarias
and the author [15] have developed attacks
on low-density knapsack cryptosystems.
This paper develops attacks on several other public-key
cryptosystems.
We show that it is easy to break the Shamir fast signature public-key
scheme [24], which is related to the Merkle-Hellman
additive knapsack system, but is designed for
authentication.
Another scheme we show how to break, but only under certain
circumstances, is the Merkle-Hellman multiplicative
knapsack public-key cryptosystem [18].
Both of these schemes are described in detail below.
We also indicate briefly how to adapt
our methods to attack the Scho\*:bi-Massey
knapsack-based signature scheme.
.P
Both the multiplicative and the additive knapsack
systems as well as the Shamir signature scheme
relied for their presumed security on the difficulty
of the general knapsack problem:
.br
.in 4
Given $n+2$ integers $a sub 1 , "..." ,~a sub n$,
$M$, and $m$, find a solution
$c sub 1 , "..." ,~c sub n$ (if it exists) for the
modular equation
.DS 2
.EQ
m~==~sum from j=1 to n~c sub j a sub j ~~~~~ ( roman mod~M)~,
.EN
.DE
in which each $c sub j$ is an integer in the range
$0~<=~c sub j~<=~1$ (or else in the range
$0~<=~c sub j~<=~log~M$).
.in 0
.P
This problem is known to be NP-complete [24] and so is
presumed to be hard, at least in the worst case.
(There is some empirical evidence, backed by
heuristics and in some cases by theoretical analyses, which indicates that many instances of this
problem may be solvable in polynomial time [6,15].)
In order to have a usable cryptosystem, however, it
is necessary that the intended user should be able
to utilize it, which means that he must be able to rapidly decode
messages or sign them (in a signature scheme).
In order to make this possible, the designers of the
systems mentioned above have built into them \f2trapdoors\f1,
which enable the intended user to transform a seemingly
very hard general knapsack problem into a very easy one.
For instance, in the basic Merkle-Hellman additive
knapsack system, the designer publishes $n$ keys,
$a sub 1 , "..." , a sub n$, which are all large
integers of about $2n$ bits each, and anyone
wishing to send him a message $( epsilon sub 1 , "..." , epsilon sub n )$,
$epsilon sub i~=~0$ or 1, computes the integer
.DS 2
.EQ
m~=~sum from i=1 to n~epsilon sub i a sub i
.EN
.DE
and transmits it over a regular communication
channel.
An eavesdropper faces the apparently intractable
problem of determining the $epsilon sub i$ knowing
only the $a sub i$ and $m$.
The recipient, however, possesses secret keys
$W$ and $M$ such that the sequence $W a sub 1 , "..." , W a sub n$,
when reduced modulo $M$, becomes a superincreasing sequence [18],
and the transformed knapsack problem is thus very easy to solve.
In other variations of this scheme, the recipient might have to
perform several such modular multiplications using several sets
of secret keys.
In all cases, however, there is some (secret) trapdoor which
allows the recipient to transform the seemingly hard knapsack
problem into a very tractable one.
It is this presence of trapdoors which makes some of the attacks on the additive
knapsack cryptosystems feasible [2,25].
In those attacks the
cryptanalyst carries out an
initial polynomial-time but
relatively long precomputation
which with high probability
finds some trapdoor (usually not
the one built into the system)
which then enables him to decrypt
each cyphertext about as rapidly
as the intended recipient can do it.
Other attacks, such as those of
[15] and to some extent of [6], do
not depend on the existence of
specific trapdoors, but on the
public knapsack of the cryptosystem
being sparse.
In those attacks, decrypting each
message is still a polynomial-time
process for the cryptanalyst, but
takes substantially longer than for
the possessor of the secret keys (typically
on the order of $n sup 4$ operations
versus $n sup 3$ in the case of [15]).
.P
The trapdoor present in the Merkle-Hellman
multiplicative knapsack public-key cryptosystem makes that system vulnerable
to our attack.
This system's design was motivated by the presumed difficulty
of both the general knapsack problem and the discrete logarithm
problem.
Here the designer chooses $n$ relatively prime numbers
$p sub 1 , "..." , p sub n$ (which would usually be the first
$n$ primes, or else random $n$-bit primes) and a prime $q$
such that
.DS 2
.EQ (1.1)
q~>~
prod from i=1 to n~p sub i~,
.EN
.DE
together with a primitive root $b$ modulo $q$.
He then finds integers $a sub i$ (the discrete
logarithms of the $p sub i$ to base $b$),
$1~<=~a sub i~<=~q-1$,
such that
.DS 2
.EQ (1.2)
p sub i~==~b sup {a sub i} ~~~~~( roman mod~q)~,
.EN
.DE
and publishes $a sub 1 , "..." , a sub n$, keeping
$b$ and $q$ secret.
Anyone wishing to send him a message $( epsilon sub 1 , "..." , epsilon sub n )$,
$epsilon sub i~=~0$ or 1, computes the integer
.DS 2
.EQ (1.3)
k~=~sum from i=1 to n~epsilon sub i a sub i
.EN
.DE
and transmits it.
The intended receipient, knowing $b$ and $q$,
then computes $m~==~b sup k$ (modulo $q$),
$1~<=~m~<=~q-1$.
Since
.DS 2
.EQ
b sup k~=~prod from i=1 to n~ ( b sup {a sub i } ) sup {epsilon sub i}~==~
prod from i=1 to n~p sub i sup {epsilon sub i}~~~~~
( roman mod~q)~,
.EN
.DE
and $q$ satisfies (1.1), we have
.DS 2
.EQ
m~=~prod from i=1 to n~p sub i sup {epsilon sub i}~,
.EN
.DE
and therefore $epsilon sub i~=~1$ if and only if
$p sub i ~|~ m$.
Thus the message is easy to recover for
the intended recipient.
The cryptanalyst, on the other hand, faces the
task of either trying to solve for the $epsilon sub i$
knowing only the $k$ in (1.3) and the $a sub i$, or
else of trying to discover the trapdoor keys $b$
and $q$.
The first of these attacks (which applies to any
knapsack system) is discussed in [15].
Based on actual tests and heuristics, it appears to
work in many cases.
Its disadvantage is that it requires a separate run
of the lattice reduction algorithm (which takes at
least on the order of $n sup 4$ operations) to attack
each $n$-bit message.
Here we discuss an attack that is likely to discover the secret
keys $b$ and $q$ in polynomial time with high probability, provided that
the $p sub i$ (or at least a large subset of them) are
known to the cryptanalyst,
and are not too large, so that $q$ is $O( n~log~n)$ bits long.
This attack does not apply if the $p sub i$
are not known, or even when they are known
but their order is given by a permutation
unknown to the cryptanalyst.
.P
A typical value for $n$ might be 100.
In that case, if the $p sub i$ are the initial
$n$ primes, (1.1) forces $q$ to be on the
order of 730 bits in length.
If the $p sub i$ are random 100-bit primes,
(1.1) forces $q$ to be on the order of 10,000
bits in length, which might be regarded as prohibitive,
both from the standpoint of waste of transmission facilities
and because of the difficulty of computing $m$.
Thus the temptation might be to use only small primes $p sub i$,
and for ease of implementation perhaps fixed primes all the time,
which would make the system vulnerable to our attack.
.P
The multiplicative knapsack system has another weakness which
the attack presented here does not exploit.
This comes from the fact that the system designer must be
able to compute the discrete logarithms $a sub i$ in (1.2).
The discrete logarithm problem modulo a prime $q$ is widely
thought to be very hard, and the best general algorithm that is known for it,
due to Western and Miller [28] (see also [19])
and analyzed by Adleman [1],
has running time of about
.DS 2
.EQ
exp ( O ( ( log~ q ) sup half~ ( log~log~ q ) sup half ) )~.
.EN
.DE
However, relatively efficient algorithms are known when $q-1$
is divisible only by relatively small primes [20].
Hence in the multiplicative knapsack system, $q$ is chosen
to have this property.
This fact provides additional information to the cryptanalyst,
which might make it possible to break the system even when
the $p sub i$ are not known.
.P
The Shamir fast signature scheme [24] is similar in many
ways to the basic Merkle-Hellman additive knapsack system.
It was designed to make up for a significant disadvantage
of the additive knapsack, namely that it could not be used
for authentication.
In many applications, what is required is not the
ability for $A$ to transmit to $B$ without anyone
else reading the message, but rather a way for $A$
to send a message to $B$ in such a way that $B$
can be sure the message comes from $A$ and not from
anyone else.
The RSA system [22] is very effective in this role,
whereas the additive and multiplicative knapsack
schemes are not very suitable, because only a very
small fraction of the messages that can be transmitted
are actually valid cyphertext messages.
The Shamir scheme [24] overcomes this difficulty, and has
the additional very desirable feature that it is very
fast, even when implemented in software.
.P
In the Shamir scheme with parameter $n$
($n~=~100$ is suggested in [24]), Party A, who
wishes to provide electronic signatures, publishes
a prime $p$ of about $n$ bits and $2n$ integers
$a sub 1 , "..." , a sub 2n$, each of about $n$ bits.
Then, in order to certify that an $n$-bit message
$( delta sub 1 , "..." , delta sub n )$ comes from
$A$, $A$ provides a signature consisting of $2n$
integers $ epsilon sub 1 , "..." , epsilon sub 2n $,
$0~<=~epsilon sub i~<=~n$ for all $i$,
which he computes using his secret trapdoor information,
such that
.DS 2
.EQ (1.4)
sum from i=1 to n~
delta sub i 2 sup i-1~==~
sum from j=1 to 2n~epsilon sub j a sub j~~~~~( roman mod ~p)~.
.EN
.DE
Any recipient of $A$'s message can easily
check whether (1.4) holds.
The presumed security of this scheme stemmed from the fact
that solving (1.4) for the $epsilon sub j$ seemed hard
without $A$'s secret information.
This information consists of a 0-1 matrix $E~=~( e sub ij )$
of size $n$ by $2n$, such that
for $1~<=~i~<=~n$,
.DS 2
.EQ (1.5)
2 sup i-1~==~ sum from j=1 to 2n~e sub ij a sub j~~~~~
( roman mod ~ p )~.
.EN
.DE
This matrix is constructed by choosing the $e sub ij$
independently to be 0 or 1 with equal probability.
Then, with very high probability, the leading $n times n$
submatrix of $E$ will be nonsingular modulo the randomly
chosen prime $p$.
(One can even choose $p$ after one chooses the
matrix $E$ so that $p$ will not divide the determinant
of the leading $n times n$ submatrix of $E$.)
Next, $a sub n+1 , "..." , a sub 2n$ are chosen to be
random $n$-bit integers, and the system (1.5),
$1~<=~i~<=~n$, is solved to obtain $a sub 1 , "..." , a sub n$.
.P
The simplest way to form the signature
$( epsilon sub 1 , "..." , epsilon sub 2n )$ for an $n$-bit
message $( delta sub 1 , "..." , delta sub n )$ is to take
.DS 2
.EQ
epsilon sub j~=~
sum from i=1 to n~e sub ij delta sub i~,
.EN
.DE
which by (1.5) will satisfy (1.4), and will have $0~<=~epsilon sub j~<=~n$.
This procedure, however, is very insecure, because every message
yields $2n$ linear equations for the $e sub ij$, so that after about $n$
messages, an eavesdropper can discover the matrix $E$ and thus can break the scheme.
To circumvent this problem, Shamir proposed that to sign
$( delta sub 1 , "..." , delta sub n )$, $A$ should first choose
a random subset $a sub {i sub 1} , "..." , a sub {i sub k}$ of the
$a sub i$, form the signature $( epsilon sub 1 sup prime , "..." , epsilon sub 2n sup prime )$ for the message
.DS 2
.EQ
sum from i=1 to n~
delta sub i 2 sup i-1~-~
sum from j=1 to k~a sub i sub j
.EN
.DE
as above, and then form the signature
$( epsilon sub 1 , "..." , epsilon sub 2n )$
by taking
$epsilon sub {i sub j}~=~epsilon sub {i sub j} sup prime +1$,
$1~<=~j~<=~k$, and
$epsilon sub i~=~epsilon sub i sup prime$
if $i~!=~i sub j$ for any $j$.
This appears to sufficiently randomize the linear
equations so as to make a linear algebra attack
on this scheme unlikely to succeed.
However, Section 4 shows that the difficulties
can be overcome by using recently developed
tools of diophantine
approximation.
We do not reconstruct the secret matrix $E$.
Instead, using on the order of $O ( n sup 4 )$ bit operations we
construct a different matrix which then allows
us to sign a message using only $O( n sup 3 )$
operations.
As a comparison, we note that the secret matrix $E$
takes on the order of $n sup 5$ bit operations to compute
(using Gaussian elimination and ordinary arithmetic schemes,
which are the only practical ones in the ranges of interest)
even if we don't count the cost of computing random numbers,
and each signature takes on the order of $n sup 2$ bit operations
to generate once $E$ is known.
.P
The attack we describe depends
on the matrix $E$ being essentially
a random $0-1$ matrix so that a
signature $( epsilon sub 1 , "..." , epsilon sub 2n )$
is recognized as valid whenever it satisfies
the congruence (1.4) and has
$0~<=~epsilon sub i~<=~n$,
$1~<=~i~<=~2n$.
However, it is possible to restrict
attention to matrices $E$ in which all column
sums are $<=~m$ for some $m~<~n$, so that
valid signatures have
$0~<=~epsilon sub i~<=~m$.
(Shamir suggested in his original proposed [24]
that for $n~=~100$, it might be best for
technical reasons to take $m~=~63$, for example.)
If $m$ is taken to be very small, say
$m~<~sqrt n$, then the attack we describe here
is expected to fail.
However, such a system would still be vulnerable
to an attack similar to the one described here,
but directed at each message individually.
In addition, each signature would then reveal
a lot of information about the matrix $E$, which
might be sufficient for the cryptanalyst to recover
$E$.
We do not pursue these approaches here,
since our purpose is just to point out
some of the basic weaknesses of these
systems, which should be sufficient
to discourage people from using them.
.P
Recently Shamir and Tulpan [26] have
developed another attack on the Shamir
signature scheme.
Unlike the attack prescribed here, it
can be proved to succeed with high
probability, but its running time is
exponential in $n$.
For $n$ not too large,
though, the running time is not very high.
The case of $n~=~100$ was tested successfully
in [26], and the authors extrapolated that
even $n~=~500$ might be doable.
.P
Scho\*:bi and Massey [23]
have proposed a knapsack-based
signature scheme different from
the Shamir one.
Its advantage is that it can be
used both for transmission of
information and authentication.
Its disadvantage is that the secret
key is very large, and it is much
slower than Shamir's.
In Section 5 we briefly indicate how
it can be attacked by methods similar
to those used for breaking the
multiplicative knapsack system and
the Shamir scheme.
.P
As is the case with the other attacks [2,6,15,25] on the additive
knapsack schemes, we cannot prove that our attacks always
succeed.
In fact, while attacks on the basic Merkle-Hellman additive
knapsack cryptosystem can be shown to succeed most of the
time [14,25], we cannot prove even that for our attacks.
The main reason is that we rely on the Lenstra, Lenstra, and
Lova\*'sz lattice basis reduction algorithm [17] satisfying certain
conditions (at least on average) which it has not been
proved to possess.
However, extensive numerical experiments by Brickell [8] and the
author show that the algorithm often does satisfy those
conditions (which are discussed in Section 2).
Extrapolation from these numerical
experiments indicate that our
attack on the Shamir scheme,
for example, ought to be successful
for $n$ up to at least 1000.
.P
In Section 2, we discuss briefly the lattice basis reduction
algorithm which is the basic tool of our attacks,
as well as other algorithms that could possibly
be used in its place.
Sections 3 and 4 present the cryptanalysis of the
multiplicative knapsack system and the Shamir fast
signature scheme, respectively.
Section 4 also describes successful attempts to break
the Shamir scheme using the approach presented there.
Finally, in Section 5 we briefly
discuss attacks on the Scho\*:bi-Massey
scheme.
.H 1 "Lattice basis reduction algorithm"
The initial attack on the additive knapsack cryptosystems
by Shamir relied on H. W. Lenstra's polynomial time algorithm for
the integer programming problem when the number of variables
is fixed [16].
Since then, this algorithm has been largely superseded
in cryptographic applications by the Lenstra, Lenstra,
and Lova\*'sz lattice reduction algorithm [17],
(which we will refer to as the $roman L sup 3$ algoritm),
which is easy to program and whose running time is polynomial
in the total size of the problem.
It was first applied in cryptography
by Adleman [2].
.P
Given $n$ vectors $vv sub 1 , "..." , vv sub n~member~Z sup n$,
the lattice $L$ spanned by them is the collection of all integer
linear combinations
.DS 2
.EQ
sum from i=1 to n~c sub i vv sub i ~,~~~~~c sub i~member~Z~.
.EN
.DE
Many problems in computational complexity, number theory,
and cryptography can be reduced to the problem of
finding the shortest vector in a lattice.
In many cases, it suffices just to find
some short vector in a lattice.
The $roman L sup 3$ algorithm [17] does find
a fairly short vector.
To be precise, given a basis $vv sub 1 , "..." , vv sub n$
for a lattice $L$, the algorithm produces another
basis $ww sub 1 , "..." , ww sub n$ for $L$ that
Lenstra, Lenstra, and Lova\*'sz call \f2reduced\f1.
We do not need the precise definition, but it can be
shown [17] that the shortest vector in the reduced
basis is relatively short:
.DS 2
.EQ (2.1)
min from i~|| ww sub i || sup 2~<=~
2 sup n-1 min from { vv member L prime}~
|| vv || sup 2~,
.EN
.DE
where
$L prime~=~L \e "{" ( 0, "..." , 0) "}"$, and
.DS 2
.EQ
|| ( u sub 1 , "..." , u sub n ) || sup 2~=~left (
sum from i=1 to n~u sub i sup 2 right ) sup half
.EN
.DE
is the euclidean norm of a vector.
Furthermore, the other vectors of the reduced
lattice basis tend to be short also.
The running time of the original algorithm was shown to be
$O( n sup 6 ( log~B) sup 3 )$, where $B$ is
an upper bound for the coordinates of the
initial basis
$vv sub 1 , "..." , vv sub n$, and slightly
faster variants have been proposed [12].
.P
What is perhaps most striking about the $roman L sup 3$
algorithm is that it performs much better
in practice than it is guaranteed to.
Very extensive tests by Brickell [8] and independently by the
author
(up to dimension 102)
show that in most cases the reduced basis
vectors are very short, in fact much shorter
than the worst case bound (2.1) guarantees.
Some of the computational results are
described in greater detail in [15].
The assumption underlying our
attacks is that when the $roman L sup 3$
algorithm is applied to the
lattices that arise in our
problems (which are of a
somewhat special nature),
it will in a substantial
fraction of the cases find
reduced bases in which
the shortest vector is at
most a constant factor longer
than the shortest vector in
the lattice, and that the
next few shortest vectors in
the reduced basis are
also short.
This assumption is fully supported
by the experiments that have been
carried out so far,
in dimensions up to around 100.
This is sufficient for our attack
on the Shamir scheme, for example,
with parameter $n~<wig~500$.
.P
There are some indications that in higher
dimensions the performance of the $roman L sup 3$
algorithm might deteriorate.
For example, the numerical
evidence seems to imply that
the ratio of the product of the
lengths of the vectors in a reduced
basis produced by the $roman L sup 3$
algorithm to the determinant of the
lattice grows roughly like
$exp ~ ( cn sup 2 )$ for some small
constant $c$.
Except for the value of $c$,
this is similar to the worst
case bound of [17].
On the other hand, by reasoning
in analogy with the reduction
theory of quadratic forms
[9; pp. 259-263] we might expect
that for most lattices there would
be some reduced basis for which the
above ratio grows only as
$exp~ ( c prime ~ n~log~n)$.
Thus it is quite possible that our
attacks might fail in very high
dimension, say on the order of several hundred.
Such high dimensions, though, would be
required in the case of the Shamir
signature scheme (for example) only
when the parameter size $n$ in that
scheme (which is about $2~log sub 2 ~n$
times larger than the dimension of
the lattice that is used in the cryptanalysis)
is on the order of several thousand, which
makes that scheme impractical.
Furthermore, as new diophantine
approximation algorithms are
developed, the range of applicability
of our attacks can be expected to increase.
.P
It is possible to significantly
speed up the $roman L sup 3$ algorithm by performing some  of
the crucial multiprecision operations in floating
point arithmetic.
The rigorous analysis of [17] then no longer applies,
but since all operations on basis elements
are still carried out in integers, at the end
of the computation it is easy to check that
the basis is in fact reduced.
The running time of this modified algorithm,
assuming that roundoff errors do not cause it
to make incorrect decisions, can be shown to
be $O(n sup 4 ( log~B) sup 3 )$.
In practice, the running time seems to be much
shorter, perhaps on the order of
$n~  ( log~B) sup 3$ or so.
Present computational experience
with lattices in dimensions up to 102 
indicates that even a relatively inefficient high-level
language
implementation of the modified algorithm on
a high-speed machine such as the CRAY-1 can find
a reduced basis for a typical 50-dimensional lattice given
in terms of 100-bit coordinates
in a few minutes.
.P
We use the $roman L sup 3$ algorithm primarily because
its basic version is the only one in
this area which is guaranteed to produce
reasonably short vectors in a lattice in
polynomial time.
It is quite possible that other algorithms,
such as those of [4,5,10,11,21,27], or modifications
of them, could perform just as well or
better in practice on typical lattices.
Therefore the running time bounds
that we quote
should be regarded as provisional, and capable
of substantial improvement.
.H 1 "Multiplicative knapsack"
In this section we present an attack on the multiplicative knapsack
cryptosystem.
We assume that integers $a sub 1 , "..." , a sub n$ are known and
at least some of the primes (or relatively prime numbers)
$p sub 1 , "..." , p sub n$ are known, and we try to find the
unknown integer $b$ and prime $q$ such that
.DS 2
.EQ (3.1)
b sup {a sub i}~==~p sub i ~~~~~( roman mod~q)~.
.EN
.DE
We assume that $b$, $q$, and the $a sub i$ are of about
$m$ bits; if the $p sub i$ are the first $n$ primes, then
$m~wig~n~log sub 2~n$, and if the $p sub i$ are $n$-bit
primes, then $m~>wig~n sup 2$, since we must have $q~>wig~prod p sub i$.
Our attack will take polynomial time only if
$m~=~O ( n~log~n)$.
.P
The basic idea behind the attack is to find a collection of vectors
$ddelta~=~( delta sub 1 , "..." , delta sub n )$ such that
.DS 2
.EQ (3.2)
0~=~
sum from i=1 to n~delta sub i a sub i ~,
.EN
.DE
and such that the $delta sub i$ are not too large.
(If not all the $p sub i$ are known, then we also
require that $delta sub i~=~0$ for those $i$
for which $p sub i$ is not known.)
By (3.1), each such vector $ddelta$ gives a congruence
of the form
.DS 2
.EQ (3.3)
1~==~
{u ( ddelta )} over {v ( ddelta )} ~~~~~( roman mod~q)~,
.EN
.DE
where
.DS 2
.EQ (3.4)
u ( ddelta )~=~prod from {size 8 i from size 8 {delta sub i > 0}}~
p sub i sup {delta sub i} ~,~~~~~
v( ddelta )~=~ prod from {size 8 i from size 8 {delta sub i < 0}}~
p sub i sup {- delta sub i}~.
.EN
.DE
But then
.DS 2
.EQ
q | u ( ddelta ) ~-~ v ( ddelta )~.
.EN
.DE
If we compute several of the
$u ( ddelta )~-~v ( ddelta )$, then
their greatest common divisor is likely to be $q$.
Once we have found $q$, it is easy us to compute $b$.
We find a solution $ddelta$ to
.DS 2
.EQ (3.5)
1~=~sum from i=1 to n~delta sub i  a sub i
.EN
.DE
(with $delta sub i~=~0$ for those $i$
for which $p sub i$ is not known, again)
and then compute
.DS 2
.EQ
b~==~
PI p sub i sup delta sub i ~~~ ( roman mod~ q)~.
.EN
.DE
Since $q$ is already known, we do not require
the $delta sub i$ in (3.5) to be small in
order to compute $b$ efficiently.
In some cases it may be impossible to find
a solution to (3.5), but that can happen
only if $gcd ( a sub 1 , "..." , a sub n )~=~d > 1$,
in which case we might as well work with
$b sup d$ and
$a sub 1 / d , "..." , a sub n /d$.
In most cases, however, even the first
few of the $a sub i$ should be relatively
prime, so there will be no difficulty.
.P
We now consider this approach in detail.
Vectors $ddelta$ that satisfy (3.2) are
easy to find in general.
The difficulty is in finding $ddelta$ that satisfy (3.2)
with small $delta sub i$.
There are several ways to use the $roman L sup 3$ algorithm
to find solutions to (3.2) with small $delta sub i$.
We pick a subset of $k$ $a sub i$'s for which the
$p sub i$ are known.
By renumbering the $a sub i$ and $p sub i$, we can
assume that we are dealing with $a sub 1 , "..." , a sub k$
and $p sub 1 , "..." , p sub k$.
We next apply the $roman L sup 3$ algorithm to the lattice $L$ spanned
by the $k+1$ vectors in $Z sup k+1$ given by
.DS 3
.EQ
ww sub 1~mark =~
(1, 0, 0 , "..." , 0 , 2 sup m a sub 1 )~,
.EN
.sp
.EQ
ww sub 2~lineup =~(0,1,0, "..." , 0, 2 sup m a sub 2 )~,
.EN
.sp
.EQ (3.6)
lineup 3dot
.EN
.sp
.EQ
ww sub k~lineup =~
( 0, 0 , "..." , 0 , 1 , 2 sup m a sub k  )~,
.EN
.sp
.EQ
ww sub k+1~lineup =~
(0,0, "..." , 0,0, 2 sup 4m )~.
.EN
.DE
(In actual implementations one would replace $2 sup m$
by a smaller power of 2, but we will not worry about such details
here.)
Note that any vector in $L$ is given by
.DS 2
.EQ (3.7)
left ( delta sub 1 , delta sub 2 , "..." , delta sub k ,~
2 sup m left {
sum from i=1 to k ~delta sub i
a sub i  right } + d ^ 2 sup 4m   right )
.EN
.DE
for some $delta sub 1 , "..." , delta sub k$,
$d ~member~Z$.
For a vector to be short, its last coordinate
has to be zero, and the $delta sub i$ should all
be small.
This can only happen if $d~=~0$ and
$sum delta sub i a sub i~=~0$, since
if $d~!=~0$, some of the $delta sub i$
would have to be very large, which
would make the vector long.
.P
To determine how short the vectors in the reduced basis
might be, we apply the pigeon-hole principle.
Consider the integers
.DS 2
.EQ
sum from i=1 to k~x sub i a sub i ~,~~~~~0~<=~x sub i~<=~B~.
.EN
.DE
They are all $<wig~kB2 sup m$ in absolute magnitude,
and so if their total number, $(B+1) sup k$,
exceeds $kB2 sup m$ (which occurs for $B~approx~2 sup m/(k-1)$),
two of them will have to be equal,
and so we obtain an equation of
the form
.DS 2
.EQ
sum from i=1 to k~
x sub i a sub i~=~
sum from i=1 to k~
x sub i sup prime a sub i~,~~~~~
0~<=~x sub i ,~ x sub i sup prime~<=~B~,
.EN
.DE
which gives, for $y sub i~=~x sub i - x sub i sup prime$,
.DS 2
.EQ
sum from i=1 to k~y sub i a sub i~=~0 ~,~~~~~
| y sub i |~<=~B~.
.EN
.DE
In fact, it is easy to show that many such
equations have to be satisfied.
Therefore we
can expect that there are many vectors in our lattice
of length $<wig~sqrt k~ 2 sup m/(k-1)$.
The basic unproved assumption underlying our attack is that
the $roman L sup 3$ algorithm will find such vectors.
.P
We next consider the running time of the algorithm.
The $roman L sup 3$ algorithm takes about $O( k m sup 3 )$
bit operations (somewhat more if we use the original
rigorously analyzed form of it).
The integers $u( ddelta )$ and $v( ddelta )$ will
each have on the order of $km~2 sup m/(k-1)$ bits,
and so will the $u( ddelta )~-~v( ddelta )$.
Hence computing the $u( ddelta )~-~v( ddelta )$ and
their greatest common divisors, which will give $q$,
takes on the order of $k sup 2 m sup 2 ~4 sup m/(k-1)$
bit operations.
Finally, computing $b$ takes
$O(m sup 3 )$ operations.
Hence our estimate for the total work involved is on
the order of
.DS 2
.EQ
k  m sup 3 ~+~
k sup 2 m sup 2 2 sup 2m/(k-1)
.EN
.DE
bit operations.
If $m~wig~n~log sub 2 ~n$ (when the $p sub i$
are the initial $n$ primes, for example), and
if we choose $k~=~n$, this results in about
$n sup 6$
bit operations.
However, if the $p sub i$ are $n$-bit primes,
$m~wig~n sup 2$, and the algorithm is exponential.
.H 1 "Shamir's fast signature scheme"
The cryptanalysis of the Shamir fast signature
scheme is in some ways similar to the attack
on the multiplicative knapsack system.
Suppose that the prime $p$ of about $n$ bits
and the $n$-bit numbers $a sub 1 , "..." , a sub 2n$
are the public keys.
To be able to sign a message, we only need to be
able to find, for each integer $m$ in the
range $0~<=~m~<=~p-1$, some integers $epsilon sub 1 , "..." , epsilon sub 2n$
such that
.DS 2
.EQ (4.1)
m~==~
sum from i=1 to 2n~
epsilon sub i a sub i ~~~~~( roman mod~ p )~,
.EN
.DE
and such that $0~<=~epsilon sub i~<=~n$.
We will find a way to do this fast
without discovering the secret matrix $E~=~( e sub ij )$.
.P
We first find solutions to
.DS 2
.EQ (4.2)
sum from i=1 to 2n~epsilon sub i a sub i~==~0~~~~~( roman mod~p)~,
.EN
.DE
where the $epsilon sub i$ are to be small but not
identically zero.
Initially, we work with
only a subset of the $a sub i$, which without
loss of generality we may take to be $a sub 1 , "..." , a sub k$.
.P
By the pigeon-hole principle, a solution to
.DS 2
.EQ (4.3)
sum from i=1 to k~epsilon sub i a sub i~=~0
.EN
.DE
with $| epsilon sub i |~<=~B$ is guaranteed to exist approximately when
$B~>wig~2 sup n/(k-1)$.
Each such solution will of course give a solution to
.DS 2
.EQ (4.4)
sum from i=1 to k~
epsilon sub i a sub i~==~0~~~~~( roman mod~p)~.
.EN
.DE
To find solutions to (4.4), we consider the lattice $L$ spanned
by
.DS 3
.EQ
ww sub 1~mark =~
( 2 sup r a sub 1 , 1, 0 , "..." , 0 )~,
.EN
.sp
.EQ
ww sub 2~lineup =~ ( 2 sup r a sub 2 , 0,1, "..." , 0)~,
.EN
.sp
.EQ (4.5)
lineup 3dot
.EN
.sp
.EQ
ww sub k~lineup =~
(2 sup r a sub k , 0,0, "..." , 1 )~,
.EN
.sp
.EQ
ww sub k+1~lineup =~
(2 sup r p , 0,0, "..." , 0 )~,
.EN
.DE
where $r~approx~4n/k$, say.
A vector in $L$ is of the form
.DS 2
.EQ
ww ~=~( 2 sup r
left ( sum from i=1 to k~epsilon sub i a sub i - dp right ) , ~
epsilon sub 1 , epsilon sub 2 , "..." , epsilon sub k )~,
.EN
.DE
and so is short only when the $epsilon sub i$ are small and
.DS 2
.EQ
sum from i=1 to k~epsilon sub i a sub i~=~dp~,
.EN
.DE
that is, when we have a solution to (4.4).
Our assumption, supported by empirical evidence, is that
when the LLL algorithm is applied to a basis of the form
(4.5), it will find a reduced basis
$ww sub 1 sup star , "..." , w sub k+1 sup star$ such that
the first coordinate of each of $ww sub 1 sup star , "..." , ww sub k sup star$
is equal to 0, and the other coordinates are
$<wig ~ 2 sup n/(k-1)$ in absolute magnitude.
.P
Once the reduced basis
$ww sub 1 sup star , "..." , ww sub k+1 sup star$ has been
found with the above properties, vectors $vv sub i$,
$1~<=~i~<=~k$, are formed by deleting the first coordinate of $ww sub i sup *$.
The $vv sub i$ generate a $k$-dimensional lattice of solutions
to (4.4).
We then form the matrix whose rows are the $vv sub i$,
and compute its inverse.
This completes the basic stage of our attack.
.P
Once the steps outlined above have been completed, we can
easily generate solutions to (4.1), which give the desired
forged signatures.
Suppose that $m$ is given.
We choose $d sub 1 , "..." , d sub 2n$ to be integers in
the range $0~<=~d sub i~<=~n$, subject to the constraint
that $d sub 1 , "..." , d sub k$ should be close to $n/2.$
We next select $x~member~Z$ such that
.DS 2
.EQ (4.6)
xa sub 1~==~
m~-~sum from i=1 to 2n~d sub i a sub i~~~~~
( roman mod~p)~.
.EN
.DE
Using the precomputed inverse of the matrix of the $vv sub i$,
we express
.DS 2
.EQ
( x , 0 , "..." , 0)~=~
sum from i=1 to k~c sub i vv sub i ~,~~~~~c sub i~member~R~.
.EN
.DE
(Since we only need to know the $c sub i$ to within $+- ^1/10$,
say, the inverse of the matrix can be computed in floating point
arithmetic.)
We then form
.DS 2
.EQ
yy~=~( y sub 1 , "..." , y sub k )~=~( x, 0 , "..." , 0 )~-~
sum from i=1 to k~ ( ( c sub i ) ) vv sub i~=~
sum from i=1 to k ~
"{" c sub i - (( c sub i )) "}" vv sub i~,
.EN
.DE
where $((t))$ denotes the integer nearest to $t$.
We expect the $c sub i - (( c sub i ))$ to behave like
independent random variables distributed uniformly
on $[- 1/2, 1/2]$, and so we expect the coordinates
of $yy$ on average to be about
$<wig ~B( k/12) sup half$ in absolute magnitude.
Hence we can expect that the $y sub i + d sub i$,
$1~<=~i~<=~k$, will all be in the range $[0,n]$
if $Bk sup half$ is sufficiently much smaller
than $n$, and we will have
.DS 2
.EQ
sum from i=1 to k~ ( y sub i + d sub i ) a sub i~+~
sum from i=k+1 to 2n ~d sub i a sub i~==~m~~~~~( roman mod~p )~,
.EN
.DE
which gives the desired signature.
.P
The computational complexity of this attack and the allowable
choices for $k$ are easy to evaluate.
The LLL algorithm takes on the order of
$k sup 4 n sup 3$ bit operations.
We are constrained by the fact that we
need to have $B sqrt k~<wig~n$ (actually,
$<wig~n( log~n ) sup {- half}$), where
$B~approx~2 sup n/(k-1)$.
If we choose $k$ slightly larger than
$2n/( log sub 2~n )$, the constraints
will be satisfied, and the running time
of the initial preprocessing stage will
be on the order of $n sup 4$.
Once the initial stage is completed, any
signature takes about $n sup 3$ bit
operations to generate.
.P
The above attack might occasionally fail
because some coefficient $y sub i + d sub i$
is either $<~0$ or $>~n$.
In that case, we can either try to correct
this problem by adding some combination
of the $vv sub i$, or else can try again
with a different set of $d sub i$'s.
In any case, this problem is unlikely
to arise,
at least in the basic Shamir signature
scheme described here.
If the matrix $E$ is chosen
so that its column sums are
all $<=~m~<~n$, so that valid
signatures have $0~<=~epsilon sub i ~<=~m$,
it might be necessary to choose $k$
larger than $2n/( log sub 2 n )$, since
we need $Bk sup 1/2 m sup -1$ to be
quite small.
.P
The attack presented above on the basic Shamir scheme was
implemented using the Vaxima symbolic
manipulation system.
It was tested on about half a dozen sets of keys that were generated using $n~=~30$ and $p~=~2 sup 31 - 1$.
The basic stage was carried out using
$k~=~12$ and $r~=~10$.
In about 200 examples, the absolute values of
coordinates of the $yy$ vector were always
$<=~7$, and were $<=~5$ most of the time.
Several sets of keys with $n~=~50$ and
$p~=~669369903482281$ were also tested
using $k~=~16$ and $r~=~14$.
In over 50 examples, the absolute values
of the coordinates of the $yy$ vector
were usually $<=~7$, although once a
coefficient of 14 appeared.
.H 1 "The Schobi-Massey scheme"
This scheme [23] is a modification
of the iterated Merkle-Hellman
additive knapsack cryptosystem.
The designer publishes keys
$a sub 1 , "..." , ~ a sub n$,
derived from the usual iterated system,
which can be used to transmit
$n$-bit messages to him (or her).
To sign a message $m$ (which we can
again regard as an integer in the
range $0~<=~m~<=~ sum from 1 to n~a sub i )$,
the designer provides a set of
integers $x sub i$ such that
.DS 2
.EQ (5.1)
m~=~sum from i=1 to n~x sub i a sub i~,
.EN
.DE
and the $x sub i$ are not too large in
absolute value.
The construction of the $x sub i$ is
quite complicated, and we will not
present it here.
In their paper, Scho\*:bi and Massey [23]
suggest the use of a triply
iterated knapsack with $n~=~200$, in
which case the $x sub i$ might satisfy
$| x sub i |~<=~100$, say.
.P
Our attack on the Scho\*:bi-Massey signature
scheme is very similar to those on the
multiplicative knapsack and
on Shamir's scheme, so we only
briefly sketch it.
Given a message $m$,
to forge a signature we select
$x sub k+1 , "..." ,~ x sub n$
at random in the allowed range, and
attempt to compute
$x sub 1 , "..." ,~ x sub k$ so that
the $x sub i$ are small and (5.1)
is satisfied.
(The size of $k$ would depend on $n$,
the sizes of the $a sub i$, and the
desired sizes of the $x sub i$.)
We form the lattice
(cf. [15])
.DS 3
.EQ
ww sub 1 ~mark =~
( 1, ~ 0 ,  "..." ,~ 0,~ a sub 1 )~,
.EN
.sp
.EQ
ww sub 2 ~lineup =~
(0,~ 1 , "..." ,~ 0,~ a sub 2 )~,
.EN
.sp
.EQ
lineup 3dot
.EN
.sp
.EQ
ww sub k~lineup =~
( 0,~ 0 , "..." ,~ 1, ~ a sub k )~,
.EN
.sp
.EQ
ww sub k+1~lineup =~
( 0, ~ 0 , "..." ,~ 0,~ b )~,
.EN
.DE
where
.DS 2
.EQ
b~=~ m~-~
sum from i=k+1 to n~ x sub i a sub i~.
.EN
.DE
If $x sub k+1 , "..." ,~ x sub n$
were chosen so that $b$ is large
(as will happen for most random
choices), then vectors
.DS 2
.EQ
x sub 1 ww sub 1 ~+~
x sub 2 ww sub 2 ~+~ "..." ~+~
x sub k ww sub k ~-~
ww sub k+1
.EN
.DE
corresponding to solutions of (5.1)
with small $x sub 1 , "..." ,~ x sub k$
will be short, and we expect that
the $roman L sup 3$ algorithm will find them.
.HU "Acknowledgement"
The author thanks A. E. Brouwer, J. C. Lagarias,
and H. W. Lenstra, Jr., for their comments.
.bp
.ce
.B
References
.R
.AL
.LI
L. M. Adleman, A subexponential algorithm for the
discrete logarithm problem with applications to
cryptography, pp. 55-60 in Proc. 20-th IEEE Symp.
Found. Computer Sci. (1979).
.LI
L. M. Adleman, On breaking the iterated Merkle-Hellman
public key cryptosystem,
pp. 303-308 in \f2Advances in Cryptology:
Proceedings of Crypto 82\f1,
D. Chaum, R. L. Rivest, and A. T. Sherman,
eds., Plenum Press, 1983.
.LI
L. M. Adleman, E. F. Brickell,
J. C. Lagarias, and A. M. Odlyzko,
paper in preparation.
.LI
L. Afflerbach,
Minkowskische Reduktionsbedingungen fu\*:r
positiv definite quadratische Formen in 5
Variabeln, Monatsh. Math. \f294\f1 (1982), 1-8.
.LI
A. J. Brentjes,
.ul
Multi-dimensional Continued Fraction Algorithms,
Ph.D. dissertation, Leiden, 1981.
.LI
E. F. Brickell,
Solving low density knapsacks,
to appear in Proceedings of Crypto 83,
to be published by Plenum Press.
.LI
E. F. Brickell, J. C. Lagarias,
and A. M. Odlyzko, Evaluation
of the Adleman attack on multiply
iterated knapsack cryptosystems,
extended abstract to appear in Proceedings
of Crypto 83, to be published by Plenum
Press.
.LI
E. F. Brickell and G. J. Simmons, A status
report on knapsack based public key cryptosystems,
Congressus Numerantum,
\f237\f1 (1983), 3-72.
.LI
J. W. S. Cassels,
.ul
Rational Quadratic Forms,
Academic Press, 1978.
.LI
U. Dieter, How to calculate shortest vectors
in a lattice, Math. Comp. \f229\f1 (1975), 827-833.
.LI
H. R. P. Ferguson and R. W. Forcade,
Multidimensional Euclidean algorithms,
J. reine angew. Math. \f2344\f1 (1982), 171-181.
.LI
E. Kaltofen, On the complexity of finding short
vectors in integer lattices,
pp. 236-244 in
.ul
Computer Algebra,
J. A. van Hulzen, ed.,
Proceedings of EUROCAL '83,
Lecture Notes in Computer Science #162, Springer-Verlag, 1983.
.LI
J. C. Lagarias, The computational complexity of
simultaneous diophantine approximation problems,
pp. 32-39 in Proc. 23-rd IEEE Symp. Found. Comp.
Sci. (1982).
Revised version to appear in SIAM J. Comp.
.LI
J. C. Lagarias, Knapsack-type public key cryptosystems
and diophantine approximation,
extended
abstract to appear in Proceedings of Crypto 83,
to be published by Plenum Press.
(Full manuscript in preparation.)
.LI
J. C. Lagarias
and A. M. Odlyzko, Solving
low-density subset sum problems,
pp. 1-10 in Proc. 24-th IEEE
Symposium on Foundations of
Computer Science (1983).
Revised version to be published.
.LI
H. W. Lenstra, Jr., Integer programming with a fixed
number of variables, Math. of Operations Research, to appear.
.LI
A. K. Lenstra, H. W. Lenstra, Jr., and L. Lova\*'sz,
Factoring polynomials with rational coefficients,
Math. Annalen,
\f2261\f1 (1982), 515-534.
.LI
R. C. Merkle and M. E. Hellman, Hiding information
and signatures in trapdoor knapsacks, IEEE Trans.
Inform. Theory, IT-24 (1978), 525-530.
.LI
J. C. P. Miller, On factorization, with a suggested
new approach, Math. Comp., \f229\f1 (1975),
155-172.
.LI
S. C. Pohlig and M. E. Hellman, An improved algorithm
for computing logarithms over $GF( p)$ and its
cryptographic significance, IEEE Trans. Inform. Theory,
IT-24 (1978), 106-110.
.LI
M. Pohst, On the computation of lattice
vectors of minimal length, successive
minima and reduced bases with applications,
ACM SIGSAM Bulletin \f215\f1 (1981), 37-44.
.LI
R. L. Rivest, A. Shamir, and L. Adleman, A method
for obtaining digital signatures and public-key
cryptosystems, Comm. ACM, \f221\f1 (1978), 120-126.
.LI
P. Scho\*:bi and J. L. Massey,
Fast authentication in a trapdoor-knapsack
public key cryptosystem,
pp. 289-306 in
.ul
Cryptography,
T. Beth, ed., Lecture Notes in
Computer Science #149,
Springer-Verlag, 1983.
.LI
A. Shamir, A fast signature scheme, MIT Laboratory
for Computer Science report, 1978.
.LI
A. Shamir, A polynomial time algorithm for breaking
the basic Merkle-Hellman cryptosystem, pp. 145-152
in Proc. 23-rd IEEE Symp. Found. Computer Sci. (1982).
.LI
A. Shamir and Y. Tulpan,
Fast cryptanalysis of a fast
signature scheme, in preparation.
.LI
G. Szekeres,
Multidimensional continued fractions,
Ann. Univ. Sci. Budapest,
Sect. Math., \f213\f1 (1970), 113-140.
.LI
A. E. Western and J. C. P. Miller,
.ul
Tables of Indices and Primitive Roots,
Royal Soc. Math. Tables, Vol. 9, Cambridge
Univ. Press 1968.
.LE