  Given positive integers $a_1,..., a_n, t$, the fixed weight subset sum
problem is to find a subset of the $a_i$ that sum to $t$, where the subset has
a prescribed number of elements. It is this problem that underlies the security
of modern knapsack cryptosystems, and solving the problem results directly in a
message attack. We present new exponential algorithms that do not rely on
lattices, and hence will be applicable when lattice basis reduction algorithms
fail. These algorithms rely on a generalization of the notion of splitting
system given by Stinson. In particular, if the problem has length $n$ and
weight $\ell$ then for constant $k$ a power of two less than $n$ we apply a
$k$-set birthday algorithm to the splitting system of the problem. This
randomized algorithm has time and space complexity that satisfies $T \cdot
S^{\log{k}} = O({n \choose \ell})$ (where the constant depends uniformly on
$k$). In addition to using space efficiently, the algorithm is highly
parallelizable.
