Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10 5/26/83; site ihldt.UUCP
Path: utzoo!linus!decvax!harpo!gummo!whuxlb!pyuxll!eisx!npoiv!npois!hogpc!houxm!ihnp4!ihldt!stewart
From: stewart@ihldt.UUCP
Newsgroups: net.crypt,net.math
Subject: Re: Cracking public - key encryption schemes such as RSA
Message-ID: <1905@ihldt.UUCP>
Date: Thu, 25-Aug-83 10:05:32 EDT
Article-I.D.: ihldt.1905
Posted: Thu Aug 25 10:05:32 1983
Date-Received: Thu, 25-Aug-83 21:42:05 EDT
References: <737@hou5e.UUCP>
Organization: BTL Naperville, Il.
Lines: 15

The knapsack public key cryptosystem (R. Merkle & M. Hellman, 1978) will
not make a very good substitute for the RSA cryptosystem, since it has
been broken by A. Shamir (the S of RSA).  It turns out that while the
knapsack problem is NP-complete, the special case of the problem used in
the cryptosystem is not.  Shamir found a way to transform the cyphertext
into a simpler problem that can be solved without the secret key.

It is still possible to further scramble the system so that Shamir's
method does not work, but breaking the basic version casts doubts on
variations.

I don't have references (sorry about that).  This was told to me by
Marty Hellman, and I don't have much other information.

Bob Stewart