Abstract
In this paper new methods, generalizing those of Shamir, are presented for attacking generalizations of the basic system. It is shown how these methods may be applied to the Graham-Shamir public-key crypto-system [2], and the iterated Merkle-Hellman public-key cryptosystem. We are unable to present a rigorous proof that the attacks presented here are effective. However, in the case of the Graham-Shamir system, the methods have been implemented and have performed well in tests. The method of attack uses recent results of Lenstra, Lenstra, and Lovasz [5]. The cryptanalytic problem is treated as a lattice problem rather than a linear programming one as in Shamir's result.