Cryptography, Information Theory, and Error-Correction E-Book

Aiden A. Bruen

• Herausgeber: John Wiley & Sons
• Kategorie: Wissenschaft und neue Technologien
• Sprache: Englisch

Seitenzahl: 1054

Veröffentlichungsjahr: 2021

Beschreibung

CRYPTOGRAPHY, INFORMATION THEORY, AND ERROR-CORRECTION A rich examination of the technologies supporting secure digital information transfers from respected leaders in the field As technology continues to evolve Cryptography, Information Theory, and Error-Correction: A Handbook for the 21ST Century is an indispensable resource for anyone interested in the secure exchange of financial information. Identity theft, cybercrime, and other security issues have taken center stage as information becomes easier to access. Three disciplines offer solutions to these digital challenges: cryptography, information theory, and error-correction, all of which are addressed in this book. This book is geared toward a broad audience. It is an excellent reference for both graduate and undergraduate students of mathematics, computer science, cybersecurity, and engineering. It is also an authoritative overview for professionals working at financial institutions, law firms, and governments who need up-to-date information to make critical decisions. The book's discussions will be of interest to those involved in blockchains as well as those working in companies developing and applying security for new products, like self-driving cars. With its reader-friendly style and interdisciplinary emphasis this book serves as both an ideal teaching text and a tool for self-learning for IT professionals, statisticians, mathematicians, computer scientists, electrical engineers, and entrepreneurs. Six new chapters cover current topics like Internet of Things security, new identities in information theory, blockchains, cryptocurrency, compression, cloud computing and storage. Increased security and applicable research in elliptic curve cryptography are also featured. The book also: * Shares vital, new research in the field of information theory * Provides quantum cryptography updates * Includes over 350 worked examples and problems for greater understanding of ideas. Cryptography, Information Theory, and Error-Correction guides readers in their understanding of reliable tools that can be used to store or transmit digital information safely.

Leseprobe

SERIES PAGE TITLE

A complete list of titles in this series appears at the end of this volume.

WILEY SERIES IN DISCRETE MATHEMATICS AND OPTIMIZATION

AARTS AND KORST

Simulated Annealing and Boltzmann Machines: A Stochastic Approach to Combinatorial Optimization and Neural Computing

AARTS AND LENSTRA

Local Search in Combinatorial Optimization

ALON AND SPENCER

The Probabilistic Method, Third Edition

ANDERSON AND NASH

Linear Programming in Infinite‐Dimensional Spaces: Theory and Application

ARLINGHAUS, ARLINGHAUS, AND HARARY

Graph Theory and Geography: An Interactive View E‐Book

AZENCOTT

Simulated Annealing: Parallelization Techniques

BARTHÉLEMY AND GUÉNOCHE

Trees and Proximity Representations

BAZARRA, JARVIS, AND SHERALI

Linear Programming and Network Flows

BRUEN AND FORCINITO

Cryptography, Information Theory, and Error‐Correction: A Handbook for the 21st Century

CHANDRU AND HOOKER

Optimization Methods for Logical Inference

CHONG AND Z.AK

An Introduction to Optimization, Fourth Edition

COFFMAN AND LUEKER

Probabilistic Analysis of Packing and Partitioning Algorithms

COOK, CUNNINGHAM, PULLEYBLANK, AND SCHRIJVER

Combinatorial Optimization

DASKIN

Network and Discrete Location: Modes, Algorithms and Applications

DINITZ AND STINSON

Contemporary Design Theory: A Collection of Surveys

DU AND KO

Theory of Computational Complexity, Second Edition

ERICKSON

Introduction to Combinatorics, Second Edition

GLOVER, KLINGHAM, AND PHILLIPS

Network Models in Optimization and Their Practical Problems

GOLSHTEIN AND TRETYAKOV

Modified Lagrangians and Monotone Maps in Optimization

GONDRAN AND MINOUX

Graphs and Algorithms (Translated by S. Vajda‐)

GRAHAM, ROTHSCHILD, AND SPENCER

Ramsey Theory, Second Edition

Cryptography, Information Theory and Error-Correction

A Handbook for the 21st Century

Second Edition

Aiden A. Bruen

Carleton UniversityOttawa, Canada

Mario A. Forcinito

AP Dynamics, Inc., andUniversity of CalgaryCalgary, Canada

James M. McQuillan

Western Illinois UniversityMacomb, United States

This second edition first published 2021

© 2021 John Wiley and Sons, Inc.

Edition History

John Wiley & Sons, Inc. (1e, 2005)

All rights reserved. No part of this publication may be reproduced, stored in a retrieval system, or transmitted, in any form or by any means, electronic, mechanical, photocopying, recording or otherwise, except as permitted by law. Advice on how to obtain permission to reuse material from this title is available at http://www.wiley.com/go/permissions.

The right of Aiden A. Bruen, Mario A. Forcinito, and James M. McQuillan to be identified as the authors of this work have been asserted in accordance with law.

Registered Office

John Wiley & Sons, Inc., 111 River Street, Hoboken, NJ 07030, USA

Editorial Office

111 River Street, Hoboken, NJ 07030, USA

For details of our global editorial offices, customer services, and more information about Wiley products visit us at www.wiley.com.

Wiley also publishes its books in a variety of electronic formats and by print‐on‐demand. Some content that appears in standard print versions of this book may not be available in other formats.

Limit of Liability/Disclaimer of Warranty

While the publisher and authors have used their best efforts in preparing this work, they make no representations or warranties with respect to the accuracy or completeness of the contents of this work and specifically disclaim all warranties, including without limitation any implied warranties of merchantability or fitness for a particular purpose. No warranty may be created or extended by sales representatives, written sales materials or promotional statements for this work. The fact that an organization, website, or product is referred to in this work as a citation and/or potential source of further information does not mean that the publisher and authors endorse the information or services the organization, website, or product may provide or recommendations it may make. This work is sold with the understanding that the publisher is not engaged in rendering professional services. The advice and strategies contained herein may not be suitable for your situation. You should consult with a specialist where appropriate. Further, readers should be aware that websites listed in this work may have changed or disappeared between when this work was written and when it is read. Neither the publisher nor authors shall be liable for any loss of profit or any other commercial damages, including but not limited to special, incidental, consequential, or other damages.

Library of Congress Cataloging‐in‐Publication Data is applied for

ISBN 978‐1‐119‐58242‐7 (hardback)

Cover Design: Wiley

Cover Image: © matejmo/iStock/Getty Images

Dedications

Dedicated to the memory of my late parents, Edward A. Bruen and Brid Bean de Brún and to the memory of my late sister Antoinette.

Dedicated also to my siblings Phil and Bernard, to my beloved wife Katri, and to our children Trevor, Robin, and Merike. (Aiden A. Bruen)

Also dedicated to my parents, Alberto Forcinito and Olga Swystun de Forcinito, my beloved wife Claudia, and our children Dante, Lucas, and Diego. (Mario A. Forcinito)

Also dedicated to my parents, Archie and Muriel McQuillan, my siblings Dan, Mary, and Ian, my beloved wife Joy, and our children Anna and Christopher. (James M. McQuillan)

Preface to the Second Edition

WELCOME, New Co‐author

It is a privilege to welcome back our readers, past, present, and future to this second edition. We are delighted to introduce a third author, Dr. James McQuillan from Western Illinois University. We now have as co‐authors a mathematician, a computer scientist, and an engineer which, we feel, provides a good balance.

Intended Readership, Connections Between the Areas

This new edition, like the first edition, is intended for a broad audience and our goals have not changed. Over the last 15 years, the three areas in the title have become more unified. For example, cryptographer A might exchange a key with B using public key cryptography. But in doing so, both would want to use error correction ensuring accuracy of transmission. Now that they have the common secret key they might use a symmetric‐key protocol such as DES or AES to exchange messages or even a one‐time pad. They need to know about security, and how it is measured, which brings in probability and entropy. This example is but the tip of the iceberg.

This book arose out of courses in cryptography and information theory at the University of Calgary. It is used as a text or a reference at universities in North America and Europe and of course can be used for self‐study. Parts of the material have also been presented at various industrial gatherings. Material related to some of the topics in the book has been patented and used in the energy sector.

Problems with Solutions

The second edition has well over 350 worked examples and problems with solutions.

Style

As with the first edition, we have made a considerable effort to ensure that the chapters are as accessible as possible. We wanted this new edition to also have both depth and breadth, to read with ease, and to explain the content clearly. We feel that the updates, the incorporation of new applications of basic principles, and the new examples and worked problems added to this edition greatly enhance and complete the book. We hope that it will be an excellent source for academics (including undergraduate and graduate students!) and practitioners that want to understand the mathematical principles and their real‐world consequences.

In a 2005 review of the first edition for the Mathematical Association of America, Dr. William Satzer states that the book is “lively and engaging, written with palpable enthusiasm.” He mentions the “… clearly communicated sense of interconnections among the [three] parts [of the book].” In a review for Mathematical Reviews (MR2131191), Dr. Andrea Sgarro from the University of Trieste, Italy, noted that the first edition “… is meant for a wide audience … and it can be used at various levels, both as a reference text and as a text for undergraduate and graduate courses; worked examples and problems are provided.”

Possible Courses

Each chapter covers a lot of ground so a course might only cover part of it. For a basic course in cryptography, one could start with Chapter 2 having taken a quick look at Chapter 1. Chapter 2 introduces basic ideas on keys and security. Some of the material relates to weaknesses due to letter frequencies and requires some sophisticated mathematics described more fully in Beutelspacher, [Beu94]. Chapter 3 covers public key cryptography algorithms such as RSA and key‐exchanges such as Diffie–Hellman, Elliptic curve cryptography and quantum cryptography are discussed in Chapter 6. Symmetric cryptography involving DES, AES, shift registers and perfect secrecy is discussed in Chapters 2, 4, 5, 15, 16 and 21. Various attacks are covered in Chapter 7 Part II of the book is devoted to information theory and Part III mainly deals with error-correction. However, along the way all these topics, i.e., cryptography, information theory and error-correction merge. The unity is beautifully illustrated in Chapters 24, 25 and 26.

Recent algorithms related to some in industry are discussed in Chapter 24. For applications to Bitcoin, there is Chapter 26. There are lots of options in the book for an undergraduate or graduate course for a term or a year in all three topics.

On the more applied side, the book can be used for courses in Cybersecurity Foundations, IT Systems, Data Security, and Cryptanalysis which might include topics such as HTTP, SSL/TLS, brute‐force, and birthday attacks.

What's New

We refer also to the preface of the first edition. Many new developments have taken place in this dynamic area since the first edition in 2005 and we have tried to cover them and to provide good references in this new edition. Chapters in the first edition have been updated. We have six new chapters dealing with Compression and Applications (Chapter 17), New Identities for the Shannon Function and an Application (Chapter 25), Blockchain and Bitcoin (Chapter 26), IoT, the Internet of Things (Chapter 27), In the Cloud (Chapter 28), and Review Problems and Solutions (Chapter 29). We touch only on a few of the changes and additions that have been made in various chapters, as follows:

Chapter 4

: homomorphic encryption is introduced, the discussion on quantum encryption is enlarged and post‐quantum cryptography is discussed.

Chapter 6

extends the usual algorithm for ECC and demonstrates corresponding new geometrical results.

Chapter 7

contains details of many new attacks.

Chapter 9

has a new extended discussion on entropy in weighing problems.

Chapter 11

has an improved treatment of source coding.

Chapter 12

now contains a full proof of the Fundamental Theorem of Information Theory.

Chapter 13

features a more user‐friendly approach to continuous signals and the Information Capacity Theorem for Band‐Limited channels.

The exposition for

Chapter 15

has been polished and simplified.

Chapter 16

includes background and full details of the Berlekamp–Massey algorithm.

Chapter 17

has details of the WKdm algorithms.

Chapter 18

outlines the proof by one of the authors on a long‐standing conjecture regarding the next‐to‐minimum weights of Reed–Muller codes.

Chapter 21

features a fresh approach to cyclic linear codes and culminates with a new user‐friendly proof of a powerful result on the periodicity of shift registers in Peterson and Weldon,

[PW72]

.

The study of MDS codes leads to a very interesting and basic “inverse” problem in linear algebra over any field. It could be discussed in a first year linear algebra class. See

Chapter 23

for the details.

Chapter 24

introduces a new hash function and improvements to the main algorithm in the chapter.

Chapter 25

brings readers of this book to the very forefront of research by exhibiting infinitely many new identities for the Shannon function.

Chapter 26

features a simple new proof of the security of Bitcoin in the matter of double spending, avoiding the assumptions of the approximation by a continuous random variable in the original paper by Nakamoto (

[Nak08]

).

Chapter 27

discusses privacy and security concerns relating to the Internet of Things (IoT). Important questions include: Who has access to the information that your smart device is collecting? Could someone remotely access your smart device?

Chapter 28

focuses on the availability of data stored in the cloud and on homomorphic encryption, which allows computations to be done on data while it is in an encrypted form.

Chapter 29

features another approach to MDS codes and, we hope, a very interesting discussion of the venerable topic of mutually orthogonal latin squares. There are also exercises in modular arithmetic, finite fields, linear algebra, and other topics to elucidate theoretical results in previous chapters, along with solutions.

Hardcover and eBook

The second edition will be available both as a hardcover book and as an eBook. The content will be the same in both. Besides traditional formatting for items in the bibliography, most of the items have accompanying URLs.

The eBook will have clickable links, including links to chapter and section numbers, to theorem numbers, from problems to their solutions, and to items in the bibliography. The URLs in the bibliography will also be clickable in the eBook.

Numbering of Definitions, Examples, Results.

When referring to a definition or result, we list the chapter number, a dot and then a number from an increasing counter for that chapter. For instance, Example 10.7 is the seventh numbered item in Chapter 10. Theorem 10.8 comes after Example 10.7 and is the eight such numbered item in Chapter 10.

Numbering of Problems, Solutions.

Most chapters have a section called Problems followed immediately by a corresponding section called Solutions at the end of the chapter. Problems and Solutions at the end of the chapter have their own counters. So, Problem 10.6 is the sixth problem in the Problems section (Section 10.15) of Chapter 10 and Solution 10.6 has the solution to that problem. It can be found in the subsequent section (Section 10.16).

Numbering of Equations.

Equation numbers follow their own counter for each chapter. For example, Equation (9.7) is the seventh equation in Chapter 9.

Acknowledgments for the Second Edition

The third author is extremely grateful to the first two authors for inviting him to be a co‐author on the second edition! Thank you so much!

We are extremely grateful to a few individuals for their help with the second edition. We thank Professor Dan McQuillan from the Department of Mathematics at Norwich University in Vermont for a careful reading and many improvements to many chapters in the second edition. We thank Joy McQuillan for a careful reading and improvements to several chapters. We are indebted to Professor Sumesh Philip from the School of Information Technology at Illinois State University in Illinois for many significant improvements to the new content in the second edition. We thank Professor David Wehlau of the Department of Mathematics and Computer Science at the Royal Military College of Canada and the Department of Mathematics and Statistics at Queen's University in Kingston, Canada for valuable comments. We also thank Dr. Valery Ipatov from Petersburg State Electrotechnical University in Russia for numerous corrections to the first edition, and Burt Wilsker for corrections to the first edition. These were incorporated into the second edition.

We thank the Wiley staff including Kimberly Monroe‐Hill, Kathleen Pagliaro, Blesy Regulas, Linda Christina E, Mindy Okura‐Marszycki, and Kathleen Santoloci for their help with the second edition. We also thank Wiley staff Gayathree Sekar, Becky Cowan, and Aileen Storry.

Book Website

The website for the book is

http://cryptohandbook.info

It will be a repository for additional information and updates.

We have done our best to correct the errors but, inevitably, some will remain. We invite our readers to submit errors to [email protected] . We will post them, with attribution, on the website along with other clarifications as they arise.

About the Authors

Aiden A. Bruen was born in Galway, Ireland. He read mathematics for his Undergraduate and Master's degree in Dublin and received his Doctorate at the University of Toronto, supervised by F.A. Sherk. At Toronto, he also worked with H.S.M. Coxeter, E. Ellers, and A. Lehman. Dr. Bruen is an Adjunct Research Professor at Carleton University and a Professor Emeritus at the University of Western Ontario.

Mario A. Forcinito was born in Buenos Aires, Argentina where he took his Bachelor's degree in Engineering. He obtained his doctorate in Engineering at the University of Calgary under the supervision of M. Epstein. Dr. Forcinito is the CTO of AP Dynamics, an engineering company in Calgary. He currently holds an Adjunct Professor position at the Schulich School of Engineering, University of Calgary and is an industrial engineering consultant in the energy area in Calgary.

James M. McQuillan grew up in Ottawa, Canada. He obtained his Undergraduate and Master's degrees from Carleton University in Ottawa and the University of Vermont and his doctorate from the University of Western Ontario (now Western University) in London, Canada. Dr. McQuillan is a Professor in the School of Computer Sciences at Western Illinois University.

Part IMainly Cryptography

Chapter 1Historical Introduction and the Life and Work of Claude E. Shannon

Goals, Discussion We present here an overview of historical aspects of classical cipher systems. Our objective is to give the reader a panoramic view of how the fundamental ideas and important developments fit together. This overview does not pretend to be exhaustive but gives a rough time line of development of the milestones leading to modern cryptographic techniques. The reader interested in a complete historical review is advised to consult the definitive treatise by Kahn [Kah67].

1.1 Historical Background

Cryptology is made up of two Greek words kryptos, meaning “hidden,” and lógos meaning “word.” It is defined [Bri19] as the science concerned with data communication and storage in secure and usually secret form. It encompasses both cryptography (from the Greek graphia meaning writing) and cryptanalysis or the art of extracting the meaning of a cryptogram.

Cryptography has a history that is almost as long as the history of the written word. Some four millennia ago (see [Kah67, p. 71]), an Egyptian scribe recorded in stone the first known hieroglyphic symbol substitution in the tomb of Khnumhotep II, a nobleman of the time. Although the intention in this case was to exalt the virtues of the person, rather than to send a secret message, the scribe used for the first time one of the fundamental elements used by cryptographers throughout the ages, namely substitution. He used unusual hieroglyphic symbols, known perhaps only to the elite, in place of the more common ones.

In substitution, the sender replaces each letter of a word in a message by a new letter (or sequence of letters or symbols) before sending the message. The recipient, knowing the formula used for the substitution – the secret key – is able to reconstruct the message from the scrambled text that was received. It is assumed that only the recipient and the sender know the secret key.

The other main cryptographic technique used is transposition (or permutation) in which the letters of the message are simply rearranged according to some prescribed formula which would be the secret key in that case.

The Greeks were the inventors of the first transposition cipher. The Spartans [Kah67] in the fifth century BCE, were the first recorded users of cryptography for correspondence. They used a secret device called a scytale consisting of a tapered baton around which was spirally wrapped either a strip of parchment or leather on which the message was written. When unwrapped, the letters were scrambled, and only when the strip was wrapped around an identically sized rod could the message be read.

Today, even with the advent of high‐speed computers, substitution and transposition form the fundamental building blocks of ciphers used in symmetric cryptography.

To put it in a historical perspective, asymmetric or public key cryptography was not invented until the 1970s. Exactly when it was invented, or who should take most of the credit, is an issue still in dispute. Both the NSA1 and the CESG2 have claimed priority in the invention of public key cryptography.

Cryptography has had several reincarnations in almost all cultures. Because of the necessity of keeping certain messages secret (i.e. totally unknown to potential enemies) governments, armies, ecclesiastics, and economic powers of all kinds have been associated throughout history with the development of cryptography. This trend continues today.

The Roman General Julius Caesar was the first attested user of substitution ciphers for military purposes [Kah67, p. 83]. Caesar himself recounted this incident in his Gallic Wars. Caesar found out that Cicero's station was besieged and realized that without help, he would not be able to hold out for long. Caesar had a volunteer ride ahead, with an encrypted message fastened to a spear which he hurled into the entrenchment. Basically, Cicero was told to keep up his courage and that Caesar and his legions were on their way.

In the cipher form used by Caesar, the first letter of the alphabet “A” was replaced by the fourth letter “D,” the second letter “B” by the fifth “E,” and so on. In other words, each original letter was replaced by one three steps further along in the alphabet. To this day, any cipher alphabet that consists of a standard sequence like Caesar's is called a Caesar alphabet even if the shift is different from three.

Not much mention is made of the coding abilities of Augustus Caesar, the first Emperor of Rome and nephew of Julius Caesar. His cipher involved a shift of only one letter so that for the plain text (that is the original text) A was enciphered as B.

Mention of cryptography abounds in early literature: Homer's Iliad refers to secret writing. The Kama‐sutra, the famous text book of erotics from the Indian subcontinent, lists secret writing as one of the 64 arts or yogas that women should know and practice [Kah67, p. 75]. One of the earliest descriptions of the substitution technique of encryption is given therein. One form involves the replacement of vowels by consonants and vice versa.

In Hebrew literature, there are also examples of letter substitution. The most prevalent is the atbash technique. Here the first and last, second and second last, and so on, letters of the Hebrew alphabet are interchanged. An example can be found in the Old Testament of the Bible. Kahn [Kah67, p. 77] cites Jeremiah 25: 26 and Jeremiah 51: 41, where the form “SHESHACH appears in place of Babel (Babylon).”

In Jeremiah 51: 41, the phrase with SHESHACH is immediately followed by one using “Babylon.” To quote:

How is SHESHACH taken!

And the praise of the whole earth seized!

How is Babylon become an astonishment

Among the nations!

Through Aramaic paraphrases of the Bible, it is clear that SHESHACH is the same as Babel. With the atbash technique, the second letter of the Hebrew alphabet “b” or beth becomes the repeated SH or SHIN, the next to last letter in the alphabet. Similarly, the “l” of lamed, becomes the hard ch, or kaph of SHESHACH. Since Babylon appears below, the use of atbash here was not to actually hide the word but perhaps just a way for the scribe to leave a trace of himself in the work he was copying.

The first people to clearly understand the principles of cryptography and to elucidate the beginnings of cryptanalysis were the Arabs [Kah67]. While Europe was in the Dark Ages, Arab arts and science flourished and scholars studied methods of cryptanalysis, the art of unscrambling secret messages without knowledge of the secret key. A complete description of this work, however, was not published until the appearance of the multivolume Subh al‐a'sha by about 1412.

European cryptology was being developed around this time in the Papal States and the Italian city‐states [Kah67]. The first European manual on cryptography (c1379) was a compilation of ciphers by Gabriele de Lavinde of Parma, who served Pope Clement VII. The Office of Cipher Secretary to the Pope was created in 1555. The first incumbent was Triphon Bencio de Assisi. But considerably before this in 1474, Cicco Simonetta wrote a manuscript that was entirely devoted to cryptanalysis.

Cryptanalysis was to have tragic consequences for Mary, Queen of Scots. It was the decipherment of a secret message to Anthony Babington supposedly planning an insurrection against Elizabeth I [Lea96] that resulted in her tragic end. Having obtained this evidence, Sir Francis Walshingham, the head of Queen Elizabeth's secret service, sent his agent back to Fotheringay Castle, to intercept and copy more of Mary's secret messages with the result that Mary and all her coconspirators were finally arrested. As a result of the trial, all were executed but only Mary was beheaded. Walshingham later claimed that his agents had found the keys to as many as 50 different ciphers in Mary's apartments. (There has long been a conjecture that Mary was actually innocent and that the evidence was planted to remove this inconvenient rival to the English throne.)

The architect, Leon Battista Alberti born in Florence in 1404, is known as “the Father of Western Cryptology.” In 1470, he published Trattati in Cifra, in which he described the first cipher disk. His technique led to a generalization of the Caesar cipher, using several shifted alphabets instead of just one alphabet. This gave rise to the so‐called Vigenère cipher discussed in Chapter 2. (This is actually a misattribution as de Vigenère worked on auto‐key systems).

In 1563, the Neapolitan, Giovanni Battista Porta published his De Furtivis Literarum Notis on cryptography, in which he formalized the division of ciphers into transposition and substitution.

Moving up several centuries, we find that cryptography was widely used in the American Civil War. The Federal Army [Bri97] made extensive use of transposition ciphers in which a key word indicated the order in which columns of the array were to be read and in which the elements were either plain text words or codeword replacements for plain text. Because they could not decipher them, the Confederacy, sometimes in desperation, published Union ciphers in newspapers appealing for readers to help with the cryptanalysis. To make matters worse for the Confederate Army, the Vigenère cipher which they themselves used was easily read by the Union Army.

Kahn reports [Kah67, p. 221] that a Vigenère tableau was found in the room of John Wilkes Booth after President Lincoln was shot. Because there was actually no testimony regarding any use of the cipher, could this have been a convenient method of linking Booth and the seven Southern sympathizers with the Confederate cause?

Lyon Playfair, Baron of St. Andrews, recommended a cipher invented in 1854 by his friend Charles Wheastone, to the British government and military. The cipher was based in a digraphic3 substitution table and was known as the Playfair Cipher. The main difference when compared with a simple substitution cipher is that characters are substituted two at a time. Substitution characters depend on the positions of the two plain text characters on a secret square table (the key) whose entries are the characters of the alphabet less the letter “J.”

In 1894, Captain Alfred Dreyfus of the French military was accused of treason and sent to Devil's Island, because his hand writing resembled that of an encrypted document that offered military information to Germany. To prove his innocence, the note had to be cryptanalyzed. To be certain that the decipherers' work was correct, an army liaison officer with the Foreign Ministry managed to elicit another similarly encrypted note in which the contents were known to him. The plain text then showed that Dreyfus had not written the encrypted document, but it took several more years before he was to “receive justice, re‐instatement and the Legion of Honour” [Kah67, p. 262].

Early in the twentieth century, Maugborne and Vernam put forth the basis for the cipher known as the one‐time pad. Although – as was proven later by Shannon – this cipher is effectively unbreakable, its use is somewhat restricted because, in practice, a random key that is as long as the message must be generated and transmitted securely from A to B. Soviet spies used this cipher, and it is said that the phone line between Washington and Moscow was protected with a one‐time pad during the Cold War era.

Edward Hugh Hebern [Bri97] of the United States invented the first electric contact rotor machine. In 1915, he experimented with mechanized encryption by linking two electric typewriters together using 26 wires to randomly pair the letters. In turn, this led to the idea of rotors which could not only mechanize substitution, but also alphabet shifts as well. The function of the rotor was to change the pairing of letters by physically changing the distribution of electric contacts between the two typewriters. By 1918, he had built an actual rotor‐based encryption machine.

At about the same time (1918–1919) three other inventors, the German Arthur Scherbius, the Dutchman Hugo Koch and the Swede Arvid Damm were filing patents of rotor‐based encryption machines. The Scherbius idea, which included multiple rotors, materialized in the first commercial models having four rotors, ENIGMA A and ENIGMA B in 1923. Ironically, Hebern only filed for patent protection in 1921, received one in 1924 and lost a patent interference case against International Business Machines in 1941. Later modifications to the Scherbius machine including a reflector rotor, and three interchangeable rotors were implemented by the Axis Forces during World War II.

Rotor‐based machines give the possibility to implement poly‐alphabetic substitution ciphers4 with very long keys or cycles in a practical way. With the advantage of mechanization, the ability of widespread deployment of cryptographic stations and widespread use became a reality. This translated into a larger volume of messages (potentially all messages) being encrypted. However, the increase in traffic gave more cipher text for cryptanalysts to analyze and the probability of operators making a deadly mistake in the management of keys was multiplied.

The timely breaking of the ENIGMA cipher by the Allies was due in part to inherent weaknesses in the encryption machine, mismanagement of keys by the operators and lots of mechanized, analytical work. The cipher was first broken, using only captured cipher text and a list of daily keys obtained through a spy, by the Polish mathematician Marian Rejewski. One of the important players in the mechanization of ensuing breaks was the English mathematician Alan Turing, who also contributed to the establishment of the basis for what is today called Computation Theory.

As a side note, after World War II, many of the ENIGMA machines captured by the Allies were sold to companies and governments in several countries.

Another very interesting cryptographic technique of a different kind was used by the US military in the Pacific campaign in World War II. Secret military messages were encrypted by translating them from English to the Navajo language. For decryption at the other end, of course, the Navajo was translated back into English. Some words describing military equipment did not exist in the original Navajo language, but substitutes were found. For example “tanks and planes” were described using the Navajo words for “turtles and birds.” To avoid the possibility of the enemy getting a handle of the code, the whole system was committed – by means of an intensive training program – to the memory of the translators or “Code Talkers.” This code was never broken.

Immediately after World War II, Shannon was publishing his seminal works on information theory. Almost simultaneously, thanks to the efforts of Ulam, von Neumann, Eckert, and Mauchly another key technological development was starting to make strident progress, the introduction of the newly invented digital computer as a mathematical tool [Coo87].

Figure 1.1 (a) Claude E. Shannon, Theseus, and the maze (see Section 1.4). (b) Claude E. Shannon.

Source: Reused with permission of Nokia Corporation and AT&T Archives.

Because of the importance of his contributions to the issues in this book, we present here a brief biography of Shannon, before finishing the chapter with a review of modern developments (Figure 1.1).

1.2 Brief Biography of Claude E. Shannon

Claude Shannon has been described as the “father of the information age.” His discoveries are everywhere. Waldrop [Wal01] gives an excellent example from the days, not so long ago, where most people listened to music on CDs, before streaming services became so popular.

Pick up a favorite CD. Now drop it on the floor. Smear it with your fingerprints. Then slide it into the slot on the player‐and listen as the music comes out just as crystal clear as the day you first opened the plastic case. Before moving on with the rest of your day, give a moment of thought to the man whose revolutionary ideas made this miracle possible: Claude Elwood Shannon.

Computers give us the power to process information. But Shannon gave us the capacity to understand and analyze information. Shannon demonstrated the unity of text, pictures, film, radio‐waves, and other types of electronic communication, and showed how to use these media to revolutionize technology and our way of thinking.

1.3 Career

Shannon was born in Petoskey, Michigan in 1916. His father was a business man who later became a judge, and his mother was a high schoolteacher. As a youngster he was interested in, and became adept at, handling all kinds of contraptions such as model airplanes and boats as well as learning the workings of the telegraph system. At the age of 20, he graduated with degrees in Mathematics and Electrical Engineering from the University of Michigan.

In the summer of 1936, Claude joined the MIT Electric Engineering department as a research assistant to work on an analog computer (as opposed to our modern digital computers) under the supervision of Vannevar Bush. Bush's analog computer, called a differential analyzer, was the most advanced calculator of the era and was used mainly for solving differential equations. A relay circuit associated with the analyzer used hundreds of relays and was a source of serious study by Shannon, then, and later.

During the summer of 1937, Shannon obtained an internship at Bell Laboratories and returned to MIT to work on a Master's thesis. In September 1938, he moved to the Mathematics Department of MIT and wrote a thesis in genetics with the title An Algebra for Theoretical Genetics graduating in 1940 with his PhD degree in Mathematics and the S.M. degree in Electrical Engineering.

Dr. Shannon spent the academic year of 1940–1941 at the Princeton Institute where he worked with Herman Weyl, the famous group‐theorist and geometer. Subsequently, he spent a productive 15 years at the Bell Laboratories in New Jersey returning to MIT in 1956, first as a visiting professor and then, in 1958, as Donner Professor of Science. This was a joint appointment between mathematics and electrical engineering. Here he did not teach ordinary courses but gave frequent seminars. According to Horgan and Claude [Hor90], he once gave an entire seminar course, with new results at each lecture!

He retired from MIT in 1978 but continued to work on many different problems including portfolio theory for the stock market, computer chess, juggling, and artificial intelligence. He died in 2001, at the age of 84 a few years after the onset of Alzheimer's Disease.

1.4 Personal – Professional

Dr. Shannon's Master's thesis [Sha40] and related publication in Transactions, American Institute of Electrical Engineers [Sha38] won him the Alfred Noble Prize along with fame and renown. The thesis has often been described as the greatest Master's thesis of all time; many feel that this may in fact understate the case.

At MIT, he was idolized by both the students and faculty. Golomb et al. [GBC+02], reports that Shannon was “somewhat inner‐directed and shy, but very easy to talk to after the initial connection had been made.”

In his spare time, Shannon built several items including Thrifty Roman numerical Backward‐looking Computer (THROBAC) which was actually a calculator that performed all the arithmetic operations in the Roman numerical system. He also built Theseus, a mechanical mouse in 1950. Controlled by a relay circuit, the mouse moved around a maze until it found the exit. Then, having been through the maze, the mouse, placed anywhere it had been before, would go directly to the exit. Placed in an unvisited locale, the mouse would search for a known position then proceed to the exit, adding the new knowledge to its memory.