Codes The Guide to Secrecy from Ancient to Modern Times DISCRETE MATHEMATICS and ITS APPLICATIONS Series Editor Kenneth H. Rosen, Ph.D. Juergen Bierbrauer, Introduction to Coding Theory Kun-Mao Chao and Bang Ye Wu, Spanning Trees and Optimization Problems Charalambos A. Charalambides, Enumerative Combinatorics Charles J. Colbourn and Jeffrey H. Dinitz, The CRC Handbook of Combinatorial Designs Steven Furino, Ying Miao, and Jianxing Yin, Frames and Resolvable Designs: Uses, Constructions, and Existence Randy Goldberg and Lance Riek, A Practical Handbook of Speech Coders Jacob E. Goodman and Joseph O’Rourke, Handbook of Discrete and Computational Geometry, Second Edition Jonathan Gross and Jay Yellen, Graph Theory and Its Applications Jonathan Gross and Jay Yellen, Handbook of Graph Theory Darrel R. Hankerson, Greg A. Harris, and Peter D. Johnson, Introduction to Information Theory and Data Compression, Second Edition Daryl D. Harms, Miroslav Kraetzl, Charles J. Colbourn, and John S. Devitt, Network Reliability: Experiments with a Symbolic Algebra Environment Derek F. Holt with Bettina Eick and Eamonn A. O’Brien, Handbook of Computational Group Theory David M. Jackson and Terry I. Visentin, An Atlas of Smaller Maps in Orientable and Nonorientable Surfaces Richard E. Klima, Ernest Stitzinger, and Neil P. Sigmon, Abstract Algebra Applications with Maple Patrick Knupp and Kambiz Salari, Verification of Computer Codes in Computational Science and Engineering William Kocay and Donald L. Kreher, Graphs, Algorithms, and Optimization Donald L. Kreher and Douglas R. Stinson, Combinatorial Algorithms: Generation Enumeration and Search Charles C. Lindner and Christopher A. Rodgers, Design Theory Alfred J. Menezes, Paul C. van Oorschot, and Scott A. Vanstone, Handbook of Applied Cryptography Continued Titles Richard A. Mollin, Algebraic Number Theory Richard A. Mollin, Codes: The Guide to Secrecy from Ancient to Modern Times Richard A. Mollin, Fundamental Number Theory with Applications Richard A. Mollin, An Introduction to Cryptography Richard A. Mollin, Quadratics Richard A. Mollin, RSA and Public-Key Cryptography Kenneth H. Rosen, Handbook of Discrete and Combinatorial Mathematics Douglas R. Shier and K.T. Wallenius, Applied Mathematical Modeling: A Multidisciplinary Approach Jörn Steuding, Diophantine Analysis Douglas R. Stinson, Cryptography: Theory and Practice, Second Edition Roberto Togneri and Christopher J. deSilva, Fundamentals of Information Theory and Coding Design Lawrence C. Washington, Elliptic Curves: Number Theory and Cryptography DISCRETE MATHEMATICS AND ITS APPLICATIONS Series Editor KENNETH H. ROSEN Codes The Guide to Secrecy from Ancient to Modern Times Richard A. Mollin Boca Raton London New York Singapore C4703_Discl.fm Page 1 Friday, April 8, 2005 1:36 PM Published in 2005 by Chapman & Hall/CRC Taylor & Francis Group 6000 Broken Sound Parkway NW, Suite 300 Boca Raton, FL 33487-2742 © 2005 by Taylor & Francis Group, LLC Chapman & Hall/CRC is an imprint of Taylor & Francis Group No claim to original U.S. Government works Printed in the United States of America on acid-free paper 10 9 8 7 6 5 4 3 2 1 International Standard Book Number-10: 1-58488-470-3 (Hardcover) International Standard Book Number-13: 978-1-58488-470-5 (Hardcover) Library of Congress Card Number 2005041403 This book contains information obtained from authentic and highly regarded sources. Reprinted material is quoted with permission, and sources are indicated. A wide variety of references are listed. Reasonable efforts have been made to publish reliable data and information, but the author and the publisher cannot assume responsibility for the validity of all materials or for the consequences of their use. No part of this book may be reprinted, reproduced, transmitted, or utilized in any form by any electronic, mechanical, or other means, now known or hereafter invented, including photocopying, microfilming, and recording, or in any information storage or retrieval system, without written permission from the publishers. For permission to photocopy or use material electronically from this work, please access www.copyright.com (http://www.copyright.com/) or contact the Copyright Clearance Center, Inc. (CCC) 222 Rosewood Drive, Danvers, MA 01923, 978-750-8400. CCC is a not-for-profit organization that provides licenses and registration for a variety of users. For organizations that have been granted a photocopy license by the CCC, a separate system of payment has been arranged. Trademark Notice: Product or corporate names may be trademarks or registered trademarks, and are used only for identification and explanation without intent to infringe. Library of Congress Cataloging-in-Publication Data Mollin, Richard A., 1947- Codes: the guide to secrecy from ancient to modern times / Richard A. Mollin. p. cm. Includes bibliographical references and index. ISBN 1-58488-470-3 (alk. paper) 1. Computer security. 2. Data encryption (Computer science) I. Title. QA76.9.A25M67 2005 005.8'2--dc22 2005041403 Visit the Taylor & Francis Web site at http://www.taylorandfrancis.com Taylor & Francis Group and the CRC Press Web site at is the Academic Division of T&F Informa plc. http://www.crcpress.com Preface Thisbookhasbeenwrittenwithabroadspectrumofreadersinmind,which includes anyone interested in secrecy and related issues. Thus, this is a tome for the merely curious, as well as history-minded readers, amateur mathemati- cians, engineers, bankers, academics, students, those practitioners working in cryptography, specialists in the field, and instructors wanting to use the book for a text in a course on a variety of topics related to codes. We will look at thistopicfromallaspectsincludingnotonlythoserelatedtocryptography(the study of methods for sending messages in secret), but also the notion of codes as removal of noise from telephone channels, satellite signals, CDs and the like. The uninitiated reader may consider the following. Imagine a world where you can send a secret message to someone, and describe to anyone listening in precise detail how you disguised the message. Yet that person could not remove the disguise from that message no matter how much time or how many resources are available. Well, that world exists in the here and now, and the methodology is called public-key cryptography. It permeates our lives, from the use of a bank card at an automated teller machine ATM to the buying of items or bank transactions over the Internet. You can even purchase items over the Internet and do so anonymously, as you would using hard cash. In this book, you will find out how this is done. Doyoueverwonderhowsecureyourprivateconversationisoveracellphone? In general, they are not secure at all. In this book, you will find out how they can be made secure. And those transactions over the Internet, just how secure are they? Can these methods be trusted? In this text, you will learn which methodologies are secure and which are not. Here is an excerpt from the end of Chapter 2 that is apt. “What made all of the above not just possible, but rather a necessity — that good old mother of invention — was the advent of the Internet. While information secrecy, as we have seen throughout history, was strictly the purview of governments and their agents, the Internet, and its associated e-mail and e-commerce activities, demanded a mechanism for the ordinarycitizentohavetheir privacyconcernsaddressed. ... Fewofusactually understand the mechanisms behind all of these protocols that we use every day (although this book will foster that understanding), yet cryptography has becomeeverybody’sbusiness,henceeverybody’sconcern. Thereforeitisalmost a personal duty that each of us learn as much as possible about the underlying mechanisms that affect our security, our privacy, and therefore our well-being.” What are smart cards and how do they affect your life? This book reveals the answers. What are biometrics and how do they affect you? Several of your identitycharacteristicssuchasfingerprints,retinaldata,voiceprints,andfacial geometry, to mention a few, can be embedded in smart cards to identify you to a bank, for instance. Perhaps you have allergies to some medicines, such as penicillin, and this information can be embedded in a medical smart card so that in the event of an accident, appropriate measures can be taken that may save your life. Read this book to find out how this is done. vii viii How did all this begin and where is it headed? Read Chapter 1 to learn about the rumblings of the art of secrecy carved in stone almost four millennia ago and how it evolved to the present where it permeates nearly every aspect of your life. (cid:2) Features of This Text • The text is accessible to virtually anyone who wishes to learn the issues surrounding secrecy. To this end, Appendix A contains all necessary mathe- matical facts for the novice, or as a fingertip reference for the initiated. Other appendices, such as Appendix E, contain the requisite probability theory for background needed to understand Information and Coding Theory in Chapter 11, for instance. Moreover, the main text is geared to gently introduce the necessary concepts as they arise. The more difficult or advanced topics are marked with the pointing hand symbol (cid:3) for the more advanced (or adventur- ous) reader. • There are nearly 200 examples, diagrams, figures, and tables throughout the text to illustrate the history and concepts presented. •Morethan200 footnotes pepperthetextasfurtherroutesforinformation- gathering. Think of these as analogues of hyperlinks in the Internet (see page 328), where you can click on a highlighted portion to get further information about a given topic, or ignore it if you already have this knowledge or are not interested. These links provide avenues to pursue information about related topics that might be of separate interest to a wide variety of readers. • There are more than 80 mini bibliographies throughout the text of those whohelpedtodeveloptheconceptssurroundingcodes,aswellashistoricaldata in general to provide the human side of the concepts introduced. •Therearejustunder300references forfurtherreadinginthebibliography. This provides further pointers for the reader interested in pursuing topics of interestrelatedtowhatispresentedherein. Moreover,itprovidesthefoundation for the facts presented. • The index has nearly 5000 entries, and has been devised in such a way to ensure that there is maximum ease in getting information from the text. • To the instructor who wishes to give a course from this text: There are morethan370exercisesinAppendixG separatedaccordingtochapterandeven the appendices A–F. (Some are marked with a ✰ symbol for those particularly challenging problems.) The wealth of material in this book allows for more than one course to be given on various aspects of secrecy and even a mini- course in coding and information theory (see Chapter 11). With nearly 50 Theorems, Propositions, and related material, and more than 60 equations, the background is amply covered. Moreover, this text is self-contained so that no other reference is needed since the aforementioned appendices have all possible background and advanced material covered in detail (see the Table of Contents for the information covered in each appendix). • The webpage cited below will contain a file for updates. Furthermore, comments via the e-mail address below are also welcome. ix (cid:2) Acknowledgments: The author is grateful to various people for their timeinproofreadingvariousaspectsofthisproject. ThanksgotoProfessorJohn Brillhart, who received portions pertaining to his expertise, and as a pioneer in computational number theory with his seminal work in primality testing and factoring, it is an honour to have had him on board. I am grateful to my American colleague Jacek Fabrykowski, a mathematician who devoted his time to looking at the material. A special thanks to my former student (now working cryptographer), Thomas Zaplachinski, whose invaluable expertise in the field helped to keep the material current and accurate. A nonspecialist, Michael Kozielec, assisted greatly in giving me the valuable perspective of the uninitiated for this project which was highly beneficial in setting the proper tone for the book. Thanks go to Ken Rosen, the series editor, who always works diligently to promote the books in the series, and another special thanks to Bob Stern, my senior editor, who makes the transition from copy to finished product a seamless task. For specific information, especially on fine-tuning of details on MULTICS, and related information, thanks go to Brian Kernighan for providing background data. Richard Mollin, Calgary website: http://www.math.ucalgary.ca/˜ramollin/ e-mail: [email protected]