Hamming Codes and the McEliece Cryptosystem
Loading...
Authors
Dill, Ben
Date of Issue
2011-04-01
Type
thesis
Language
Subject Keywords
Algorithm , Binary system (Mathematics) , Coding theory , Data transmission systems -- Design and construction , Redundancy (Engineering) -- Data processing
Other Titles
Abstract
In this paper, we seek to understand some basic principles of coding theory. Specifically, we define and explore binary codes, Hamming codes, and a special application of coding theory known as the McEliece cryptosystem. We describe the meaning and usage of generator matrices and parity check matrices and present bounds on the number of codewords in codes of a given minimum distance and length. We present and prove several known results about Hamming codes, including the fact that they are necessarily perfect codes. We show how to construct a cryptosystem using any linear code and discuss the strength of the McEliece cryptosystem in a future where quantum computers are a reality. Finally, we present one program which automatically decodes strings encoded with a Hamming code and another which encrypts and decrypts messages using the McEliece cryptosystem.