Public key cryptography and the zero-one knapsack problem

Creator: 

Cobb, Simon, 1950-

Date: 

1983

Abstract: 

This paper reviews several popular symmetric cryptosystems, monoalphabetic and polyalphabetic. Their susceptibility to cryptanalysis is examined. Asymmetric cryptosystems are introduced through public key  cryptography. The Rivest-Shamir-Adelman cryptosystem is explained. Then the Merkle-Hellman system based on the zero-one knapsack problem is presented. Standard attacks on the zero-one knapsack problem are rejected as too time-consuming. Herlestam's proposed attack is discussed in detail. The results of theoretical examination and computer tests show that it is not quick, as claimed. The recent polynomial time algorithm of A. Shamir solving most instances of the Merkle-Hellman system is studied in detail.

Subject: 

Cryptography
Computers -- Access Control

Language: 

English

Publisher: 

Carleton University

Thesis Degree Name: 

Master of Science: 
M.Sc.

Thesis Degree Level: 

Master's

Thesis Degree Discipline: 

Information and Systems Science

Parent Collection: 

Theses and Dissertations

Items in CURVE are protected by copyright, with all rights reserved, unless otherwise indicated. They are made available with permission from the author(s).