B.S.T.J. Briefs: Fast Decryption Algorithm for the Knapsack Cryptographic System

Public-key cryptosystems offer a degree of flexibility not available with conventional (private-key) systems.1,2 In particular, the key required for decryption in a public-key system can be changed at will, even in the middle of a message. This makes the task of the eavesdropper very difficult indeed. A frequently cited disadvantage of public-key systems is their relative slowness (typically a few kilobit/s) caused by the large amount of number-crunching they require.3 4 This has led to the development of hybrid cryptosystems in which a key, exchanged via a slow public-key system, is subsequently used in a fast conventional system, such as the Data Encryption Standard (DES).5 In this paper we present a fast algorithm for executing the knapsack cipher (a public-key cryptosystem).6 When implemented with TTL integrated circuitry, this algorithm should permit data rates in the neighborhood of 10 Mbit/s. This speed is sufficient to provide security for a wide range of voice, data, and narrowband video traffic without the need for a hybrid cryptosystem. Section II presents an elementary example of the knapsack cipher to show how it operates. In Section III we describe the fast algorithm, and in Section IV we discuss a more sophisticated knapsack cipher.