PoineyRAPHY
`
`IPR2016-01404
`
`Protocols, Algorithms,
`and Source Code in C
`
`Exhibit 2002
`
`Pelaalse
`
`Le — aaagl91ea a |
`
`f|
`
`Exhibit 2002
`IPR2016-01404
`
`

`

`OURCE CODE IN C
`
`PROTOCOLS, ALGOR
`
`
`
`New York
`
`John Wiley & Sons,Inc.
`© Chichester
`Brisbane
`Toronto
`
`© Singapore
`
`
`
`

`

`Publisher: Katherine Schowalter
`Editor: Phil Sutherland
`Assistant Editor: Allison Roarty
`Managing Editor: Robert Aronds-
`Text Design & Composition: North Market Street Graphics
`Designations used by companies to distinguish their products are often claimed as trademarks. in all
`instances where John Wiley & Sons, Inc. is aware of a claim, the product namesappearin initial capital
`or all capital letters. Readers, however, should contact the appropriate companies for more complete
`information regarding trademarks and registration.
`This text is printed on acid-free paper.
`Copyright © 1996 by Bruce Schneier
`Published by John Wiley & Sons, Inc.
`
`All rights reserved. Published simultaneously in Canada.
`This publication is designed to provide accurate and authoritative information in regard to the subject
`matter covered. It is sold with the understanding that the publisher is not engaged in rendering legal,
`accounting, or other professional service.If legal advice or other expert assistance is required, the services
`of a competent professional person should be sought.
`tn no event will the publisher or author beliable for any consequential, incidental, or indirect damages
`(including damages for loss of business profits, business interruption, loss of business information, and
`the like) arising from the useor inability to use the protocols and algorithmsin this book, even if the pub-
`lisher or author has been advised of the possibility of such damages.
`Some of the protocols and algorithms in this book are protected by patents and copyrights. It is the
`responsibility of the reader to obtain ali necessary patent and copyright licenses before implementingin
`software any protocol or algorithm in this book. This book does not contain an exhaustivelist of all appli-
`cable patents and copyrighis.
`Some of the protocols and algorithmsin this book are regulated under the United States Department of
`State International Traffic in Arms Regulations.It is the responsibility of the reader to obtain all neces-
`sary export licenses before implementing in software for export any protocol or algorithm in this book.
`Reproduction or translation of any part of this work beyond that permitted by section 107 or 108 of the
`1976 United States Copyright Act without the permission of the copyright owneris unlawful. Requests
`for permission or further information should be addressed to the Permissions Department, John Wiley &
`Sons, Inc.
`
`Library of Congress Cataloging-in-Publication Data:
`Schneier, Bruce
`Applied Cryptography Second Edition: protocols, algorithms, and source code in C
`/ Bruce Schneier.
`p.
`cm.
`Includes bibliographical references(p. 675).
`ISBN 0-471-12845-7 (cloth : acid-free paper). — ISBN
`0-471-11709-9 (paper : acid-free paper]
`1. Computersecurity.
`2. Telecommunication—Security measures,
`3. Cryptography.
`1. Title.
`QA76.9.A25835
`1996
`005.8'2—dc30
`
`95-13398
`CIP
`
`Printed in the United States of America
`10987654
`
`

`

`CHAPTER‘
`
`Foundations
`
`1.1 TERMINOLOGY
`
`Sender and Receiver
`Suppose a sender wants to send a message to a receiver. Moreover, this sender
`wants to send the message securely: She wants to make sure an eavesdropper can-
`not read the message.
`
`Messages and Encryption
`A message is plaintext (sometimes called cleartext). The process of disguising a
`message in such a wayasto hide its substance is encryption. An encrypted message
`is ciphertext. The process of turning ciphertext back into plaintext is decryption.
`This is all shown in Figure 1.1.
`(if you want to follow the ISO 7498-2 standard, use the terms “encipher” and
`“decipher.” It seems that some cultures find the terms “encrypt” and “decrypt”
`offensive, as they refer to dead bodies.)
`Theart and science of keeping messages secureis cryptography, andit is practiced
`by cryptographers. Cryptanalysts are practitioners of cryptanalysis, the art andsci-
`ence of breaking ciphertext; that is, seeing through the disguise. The branch of
`mathematics encompassing both cryptography and cryptanalysis is cryptology and
`its practitioners are eryptologists. Modern cryptologists are generally trained in the-
`oretical mathematics—they haveto be.
`
`
`
`Plaintext
`
`Encryption
`
`Ciphertext
`
`Decryption
`
`Original
`Plaintext
`
`
`
`Figure 1.1 Encryption and Decryption.
`
`_ eg
`
`
`
`

`

` CHAPTER 1 Foundations
`
`Plaintext is denoted by M, for message, or P, for plaintext. it can be a stream of
`bits, a text file, a bitmap, a stream of digitized voice, a digital video image .. . what-
`ever. As far as a computer is concerned, M is simply binary data. (After this chapter,
`this book concernsitself with binary data and computer cryptography.} Theplain-
`text can be intendedfor either transmissionorstorage. In any case, M is the message
`to be encrypted.
`Ciphertext is denoted by C.It is also binary data: sometimes the samesize as M,
`sometimes larger. (By combining encryption with compression, C may be smaller
`than M. However, encryption does not accomplish this.) The encryption function E,
`operates on M to produce C. Or, in mathematical notation:
`
`E(M)=C
`Tn the reverse process, the decryption function D operates on C to produce M:
`D(C)=M
`Since the whole point of encrypting and then decrypting a message is to recover
`the original plaintext, the following identity must hold true:
`D(E(M)) = M
`
`Authentication, Integrity, and Nonrepudiation
`In addition to providing confidentiality, cryptography is often asked to do other
`jobs:
`
`— Authentication. It should be possible for the receiver of a message to
`ascertain its origin; an intruder should not be able to masquerade as
`someoneelse.
`— Integrity. It should be possible for the receiver of a message to verify
`that it has not been modified in transit; an intruder should not be able
`to substitute a false messagefor a legitimate one.
`— Nonrepudiation. A sender should notbe ableto falsely deny later that
`he sent a message.
`
`These are vital requirements for social interaction on computers, and are analo-
`gous to face-to-face interactions. That someone is who hesays heis .
`.
`. that some-
`one’s credentials—whether a driver’s license, a medical degree, or a passport—are
`valid .
`.
`. that a documentpurporting to come from a person actually came from that
`person... . These are the things that authentication, integrity, and nonrepudiation
`provide.
`
`Algorithms and Keys
`A cryptographic algorithm, also called a cipher, is the mathematical function used
`for encryption and decryption. (Generally, there are two related functions: one for
`encryption and the other for decryption.}
`
`ee
`
`

`

`1.1 Terminology
`
`
`
`If the security of an algorithm is based on keeping the way that algorithm works
`A secret, it is a restricted algorithm. Restricted algorithms have historical interest,
`put are woefully inadequate by today’s standards. A large or changing group of users
`cannot use them, because every time a user leaves the group everyone else must
`switch to a different algorithm.If someone accidentally reveals the secret, everyone
`must change their algorithm.
`Even more damning, restricted algorithms allow no quality control or standard-
`ization. Every group of users must have their own uniquealgorithm. Such a group
`can't use off-the-shelf hardware or software products; an eavesdropper can buy the
`same product and learn the algorithm. They have to write their own algorithms and
`implementations. If no one in the group is a good cryptographer, then they won't
`know if they have a secure algorithm.
`Despite these major drawbacks,restricted algorithms are enormously popular for
`low-security applications. Users either don’t realize or don’t care about the security
`problems inherent in their system.
`Modern cryptography solves this problem with a key, denoted by K. This key might
`be any one of a large numberof values. The range of possible values of the key is called
`the keyspace. Both the encryption and decryption operations use this key {i.e., they
`are dependent on the key andthis fact is denoted by the K subscript}, so the functions
`now become:
`
`E,{M)=C
`D,C)=M
`Those functions have the property that (see Figure 1.2):
`
`D,\Ex(M)) = M
`
`Some algorithms use a different encryption key and decryption key (see Figure
`1.3}. That is, the encryption key, Kj, is different from the corresponding decryption
`key, K,. In this case:
`Ex,(M) a G
`Dx,\C} — NM
`Dx,lEx, (M)) = M
`All of the security in these algorithms is based in the key (or keys}; none is based
`in the details of the algorithm. This means that the algorithm can be published and
`analyzed. Products using the algorithm can be mass-produced.
`it doesn’t matterif an
`
` |
`
`Key
`
`Key
`
`|
`
`Plaintext
`
`+ Ciphertext
`Encryption |
`
`Original
`= Plaintext
`
`-[ Decryption
`
`|
`
`Figure 1.2 Encryption and decryption with a key.
`
`
`
`

`

` CHAPTER 1 Foundations
`
`
`
`
`
`Decryption
`Encryption
`Key
`Key
`Original
`|
`|
`Ciphertext
`Plaintext
`Encryption $$ Decryption -——>
`
`
`
`Plaintext
`
`Figure 1.3 Encryption and decryption with two different keys.
`
`eavesdropper knows your algorithm; if she doesn’t know your particular key, she
`can’t read your messages.
`A cryptosystem is an algorithm,plusall possible plaintexts, ciphertexts, and keys.
`
`Symmetric Algorithms
`There are two general types of key-based algorithms: symmetric and public-key.
`Symmetric algorithms, sometimes called conventional algorithms, are algorithms
`where the encryption key can be calculated from the decryption key andvice versa.
`In most symmetric algorithms, the encryption key and the decryption key are the
`same. These algorithms, also called secret-key algorithms, single-key algorithms, or
`one-key algorithms, require that the sender and receiver agree on a key before they
`can communicate securely. The security of a symmetric algorithm rests in the key;
`divulging the key means that anyone could encrypt and decrypt messages. As long
`as the communication needs to remain secret, the key must remain secret.
`Encryption and decryption with a symmetric algorithm are denoted by:
`
`EM) = C
`D,(C)=M
`
`Symmetric algorithms can be divided into two categories. Some operate on the
`plaintext a single bit (or sometimes byte} at a time; these are called stream algo-
`rithms or stream ciphers. Others operate on the plaintext in groups of bits. The
`groups of bits are called blocks, and the algorithmsare called block algorithms or
`block ciphers. For modern computer algorithms, a typical block size is 64 bits—
`large enough to preclude analysis and small enough to be workable. (Before com-
`puters, algorithms generally operated on plaintext one character at a time. You can
`thinkof this as a stream algorithm operating on a stream of characters.)
`
`Public-Key Algorithms
`Public-key algorithms (also called asymmetric algorithms) are designed so that
`the key used for encryption is different from the key used for decryption. Further-
`more, the decryption key cannot(at least in any reasonable amountof time} be cal-
`culated from the encryption key. The algorithms are called “public-key” because
`the encryption key can be made public: A complete stranger can use the encryption
`key to encrypt a message, but only a specific person with the corresponding decryp-
`
`

`

`
`
`tion key can decrypt the message. In these systems, the encryption key is often
`called the public key, and the decryption keyis often called the private key. Thepri-
`yate key is sometimesalso called the secret key, but to avoid confusion with sym-
`metric algorithms, that tag won’t be used here.
`Encryption using public key K is denoted by:
`E,{M)} = C
`
`Even though the public key and private key are different, decryption with the cor-
`responding private key is denoted by:
`D,(C)=M
`
`Sometimes, messages will be encrypted with the private key and decrypted with
`the public key; this is used in digital signatures (see Section 2.6). Despite the possi-
`ble confusion, these operations are denotedby, respectively:
`
`D(C} a M
`
`Cryptanalysis
`The whole point of cryptography is to keep the plaintext (or the key, or both)
`secret from eavesdroppers (also called adversaries, attackers, interceptors, interlop-
`ers, intruders, opponents, or simply the enemy}. Eavesdroppers are assumed to have
`complete access to the communications between the sender and receiver.
`Cryptanalysis is the science of recovering the plaintext of a message without
`access to the key. Successful cryptanalysis may recover the plaintext or the key.It
`also may find weaknesses in a cryptosystem that eventually lead to the previous
`results. (The loss of a key through noncryptanalytic meansis called a compromise.|}
`An attempted cryptanalysis is called an attack. A fundamental assumption in
`cryptanalysis, first enunciated by the Dutchman A. Kerckhoffs in the nineteenth
`century,
`is that the secrecy must reside entirely in the key [794]. Kerckhoffs
`assumes that the cryptanalyst has complete details of the cryptographic algorithm
`and implementation. (Of course, one would assume that the CIA does not make a
`habit of telling Mossad about its cryptographic algorithms, but Mossad probably
`finds out anyway.) While real-world cryptanalysts don’t always have such detailed
`information, it’s a good assumption to make. If others can’t break an algorithm,
`even with knowledge of how it works, then they certainly won’t be able to breakit
`without that knowledge.
`There are four general types of cryptanalytic attacks. Of course, each of them
`assumes that the cryptanalyst has complete knowledge of the encryption algo-
`rithm used:
`
`1. Ciphertext-only attack. The cryptanalyst has the ciphertext of several
`messages, all of which have been encrypted using the same encryption
`algorithm. The cryptanalyst’s job is to recover the plaintext of as many
`messages as possible, or better yet to deduce the key (or keys) used to
`
`
`
`

`

`aN CHAPTER | Foundations
`
`encrypt the messages, in order to decrypt other messages encrypted with
`the same keys.
`
`Given: Cy aa E,{P,), Cy ad E,{ Pa), ees C; a E,(P;)
`Deduce: Either P,, P), ... P; k; or an algorithm
`to infer Pi, 1 from Cis I = FE,(Pi. 1)
`
`. Known-plaintext attack. The cryptanalyst has access not only to the
`ciphertext of several messages, but also to the plaintext of those messages.
`His job is to deduce the key (or keys) used to encrypt the messages or an
`algorithm to decrypt any new messages encrypted with the same key (or
`keys}.
`
`Given: Pi, C, = EP), Py, Cy = E,{Pa),
`Deduce: Either k, or an algorithm
`to infer P;,, from C;,, = E,{P;,,)
`
`| oh P,, C; = E,{P,)
`
`. Chosen-plaintext attack. The cryptanalyst not only has access to the
`ciphertext and associated plaintext for several messages, but he also
`chooses the plaintext that gets encrypted. This is more powerful than a
`known-plaintext attack, because the cryptanalyst can choose specific
`plaintext blocks to encrypt, ones that might yield more information about
`the key. His job is to deduce the key (or keys] used to encrypt the messages
`or an algorithm to decrypt any new messages encrypted with the same key
`(or keys).
`
`Given: P,, C; = E,(P,), Po, Cy = Ex(P2), .. . Py C= Ex(P,},
`where the cryptanalyst gets to choose P;, P,, .. . P,
`Deduce: Either k, or an algorithm to infer P;,, from C;,, = Ex{P, , J
`. Adaptive-chosen-plaintext attack. This is a special case of a chosen-
`plaintext attack. Not only can the cryptanalyst choose the plaintext that is
`encrypted, but he can also modify his choice based on the results of previ-
`ous encryption. In a chosen-plaintext attack, a cryptanalyst might just be
`able to choose onelarge block of plaintext to be encrypted; in an adaptive-
`chosen-plaintext attack he can choose a smaller block of plaintext and
`then choose another based on theresultsof thefirst, and so forth.
`
`Thereare at least three other types of cryptanalytic attack.
`
`pt Chosen-ciphertext attack. The cryptanalyst can choose different cipher-
`texts to be decrypted and has access to the decrypted plaintext. For exam-
`ple, the cryptanalyst has access to a tamperproof box that does automatic
`decryption. His job is to deduce the key.
`Given: C,, P, = DAC}, Cy, P, = D,(Cy), i fle Cs P; = D,(C;)
`Deduce: k
`
`

`

`|
`
`|
`
` 1.1 Terminology a
`This attack is primarily applicable to public-key algorithms and will be
`
`discussed in Section 19.3. A chosen-ciphertext attack is sometimes effec-
`tive against a symmetric algorithm as well. (Sometimes a chosen-plaintext
`attack and a chosen-ciphertext attack are together known as achosen-text
`attack.}
`6. Chosen-key attack. This attack doesn’t mean that the cryptanalyst can
`choose the key; it means that he has some knowledge about the relation-
`ship between different keys. It’s strange and obscure, not very practical,
`and discussed in Section 12.4.
`
`7. Rubber-hose cryptanalysis. The cryptanalyst threatens, blackmails, or tor-
`tures someone until they give him the key. Bribery is sometimesreferred
`to as a purchase-key attack. These are all very powerful attacks and often
`the best way to break an algorithm.
`
`Known-plaintext attacks and chosen-plaintext attacks are more common than
`you might think. .t is not unheard-of for a cryptanalyst to get a plaintext message
`that has been encrypted or to bribe someone to encrypt a chosen message. You may
`not even have to bribe someone; if you give a message to an ambassador, you will
`probably find that it gets encrypted and sent back to his country for consideration.
`Many messages have standard beginnings and endings that might be known to the
`cryptanalyst. Encrypted source code is especially vulnerable because of the regular
`appearance of keywords: #define, struct, else, return. Encrypted executable code has
`the same kinds of problems: functions, loop structures, and so on. Known-plaintext
`attacks (and even chosen-plaintext attacks] were successfully used against both the
`Germans and the Japanese during World War I. David Kahn’s books [794,795,796]
`have historical examples of these kinds of attacks.
`And don’t forget Kerckhoffs’s assumption:If the strength of your new cryptosys-
`tem relies on the fact that the attacker does not know thealgorithm’s inner work-
`ings, you’re sunk.
`If you believe that keeping the algorithm’s insides secret
`improves the security of your cryptosystem morethan letting the academic com-
`munity analyze it, you’re wrong. And if you think that someone won’t disassemble
`your source code and reverse-engineer your algorithm, you’re naive. (In 1994 this
`happened with the RC4 algorithm—see Section 17.1.) The best algorithms we have
`are the ones that have been made public, have been attacked by the world’s best
`cryptographers for years, and are still unbreakable. (The National Security Agency
`keeps their algorithms secret from outsiders, but they have the best cryptographers~
`in the world working within their walls—you don’t. Additionally, they discuss
`their algorithms with one another, relying on peer review to uncover any weak-
`nesses in their work.}
`Cryptanalysts don’t always have access to the algorithms, as when the United
`States broke the Japanese diplomatic code PURPLE during World WarIf [794]—but
`they often do. If the algorithm is being used in a commercial security program,it is
`simply a matter of time and moneyto disassemble the program andrecoverthealgo-
`rithm. If the algorithm is being used in a military communications system,it is sim-
`
`$l
`
`

`

`
`
`CHAPTER | Foundations
`
`
`Pom lie Ine
`
`ply a matter of time and moneyto buy(or steal) the equipment and reverse-engineer
`1 ate OU ER ree bee met. ene
`the algorithm.
`namin nan Bian en ners
`
`

`

` 1.2 Steganography
`
`1. Data complexity. The amountof data neededas inputto the attack.
`9. Processing complexity. The time needed to perform the attack. This is
`often called the work factor.
`3. Storage requirements. The amount of memory neededto do theattack.
`
`As a rule of thumb, the complexity of an attack is taken to be the maximum of
`these three factors. Someattacks involve tradingoff the three complexities: A faster
`attack might bepossible at the expenseof a greater storage requirement.
`Complexities are expressed as orders of magnitude. If an algorithm has a process-
`ing complexity of 2, then 2° operations are required to break the algorithm.
`(These operations may be complex and time-consuming.) Still, if you assume that
`you have enough computing speedto perform a million operations every second and
`you set a million parallel processors againstthetask,it will still take over 10”years
`to recover the key. That’s a billion times the age of the universe.
`While the complexity of an attack is constant (until some cryptanalyst finds a bet-
`ter attack, of course), computing poweris anything but. There have been phenome-
`nal advances in computing powerduring the last half-century and there is no reason
`to think this trend won’t continue. Many cryptanalytic attacks are perfect for paral-
`lel machines: The task can be broken downintobillions of tiny pieces and noneof
`the processors need to interact with each other. Pronouncing an algorithm secure
`simply because it is infeasible to break, given current technology, is dicey at best.
`Good cryptosystems are designed to be infeasible to break with the computing
`powerthat is expected to evolve many years in the future.
`
`Historical Terms
`Historically, a code refers to a cryptosystem that deals with linguistic units:
`words, phrases, sentences, and so forth. For example, the word “OCELOT”might be
`the ciphertext for the entire phrase “TURN LEFT 90 DEGREES,” the word “LOL-
`LIPOP” might be the ciphertext for “TURN RIGHT 90 DEGREES,” and the words
`“BENT EAR” might be the ciphertext for “HOWITZER.” Codesof this type are not
`discussed in this book; see [794,795]. Codes are only useful for specialized circum-
`stances. Ciphers are useful for any circumstance. If your code has no entry for
`“ANTEATERS,” then you can’t say it. You can say anything with a cipher.
`
`1.2 STEGANOGRAPHY
`
`Steganography serves to hide secret messages in other messages, such that the
`secret’s very existence is concealed. Generally the sender writes an innocuous mes-
`sage and then conceals a secret message on the samepieceof paper. Historical tricks
`include invisible inks, tiny pin punctures on selected characters, minute differences
`between handwritten characters, pencil marks on typewritten characters, grilles
`which cover most of the message except for a few characters, and so on.
`
`
`
`

`

` CHAPTER | Foundations
`
`More recently, people are hiding secret messages in graphic images. Replace the
`least significant bit of the image with a message. The graphical image won't change
`appreciably—most graphics standards specify more gradations of color than the
`human eye can notice—and the message can be stripped out at the receiving end.
`You can store a 64-kilobyte message in a 1024 x 1024 grey-scale picture this way.
`Several public-domain programsdothis sort of thing.
`Peter Wayner’s mimic functions obfuscate messages. These functions modify a
`message so that its statistical profile resembles that of something else: the classi-
`fieds section of The New York Times, a play by Shakespeare, or a newsgroup on the
`Internet [1584,1585]. This type of steganography won't fool a person, but it might
`fool some big computers scanning the Internet for interesting messages.
`
`1.3.
`
`SUBSTITUTION CIPHERS AND TRANSPOSITION CIPHERS
`
`Before computers, cryptography consisted of character-based algorithms. Different
`cryptographic algorithmseither substituted characters for one another or transposed
`characters with one another. The better algorithms did both, many times each.
`Things are more complex these days, but the philosophy remains the same. The
`primary change is that algorithms work on bits instead of characters. This is actu-
`ally just a changein the alphabetsize: from 26 elements to two elements. Most good
`cryptographic algorithmsstill combine elements of substitution and transposition.
`Substitution Ciphers
`A substitution cipher is one in which each character in the plaintext is substi-
`tuted for another character in the ciphertext. The receiver inverts the substitution
`on the ciphertext to recover the plaintext.
`In classical cryptography, there are four types of substitution ciphers:
`
`— A simple substitution cipher, or monoalphabetic cipher, is one in
`which each characterof the plaintext is replaced with a correspond-
`ing character of ciphertext. The cryptograms in newspapers are sim-
`ple substitution ciphers.
`— Ahomophonic substitution cipheris like a simple substitution cryp-
`tosystem, except a single characterof plaintext can map to oneof sev-
`eral characters of ciphertext. For example, “A” could correspond to
`either 5, 13, 25, or 56, “B” could correspondto either 7, 19, 31, or 42,
`and so on.
`— A polygram substitution cipher is one in which blocks of characters
`are encrypted in groups. For example, “ABA” could correspond to
`
`“RTQ,” “ABB” could correspond to “S_L,” and soon.
`— A polyalphabetic substitution cipher is made up of multiple simple
`substitution ciphers. For example, there might be five different sim-
`ple substitution ciphers used; the particular one used changes with
`the position of each character of the plaintext.
`
`

`

`
`
`1.3 Substitution Ciphers and Transposition Ciphers
`
`
`
`The famous Caesar Cipher, in which each plaintext character is replaced by the
`character three to the right modulo 26 (“A”is replaced by “D,” “B” is replaced by
`wp” HW"is replaced by “Z,”..., “X” is replaced by “A,” “Y” is replaced by “B,”
`and v7" is replaced by “C”} is a simple substitution cipher. It’s actually even sim-
`pler, because the ciphertext alphabetis a rotation of the plaintext alphabet and not
`an arbitrary permutation.
`ROT13 is a simple encryption program commonly found on UNIX systems;it is
`also a simple substitution cipher. In this cipher, “A” is replaced by “N,” “B”is
`replaced by “O,” and so on. Every letter is rotated 13 places.
`Encrypting a file twice with ROT13 restores theoriginalfile.
`P = ROT13 (ROT13 (P})
`
`
`
`ROT13 is not intended for security; it is often used in Usenet posts to hide poten-
`tially offensive text, to avoid giving away the solution to a puzzle, and soforth.
`Simple substitution ciphers can be easily broken because the cipher does not hide
`the underlying frequencies of the different letters of the plaintext. All it takes is
`about 25 English characters before a good cryptanalyst can reconstruct the plaintext
`[1434]. An algorithm for solving these sorts of ciphers can be found in [578,587,
`1600,78, 1475, 1236,880}. A good computer algorithm is [703].
`Homophonic substitution ciphers were used as early as 1401 by the Duchy of Man-
`tua [794]. They are much more complicated to break than simple substitution ciphers,
`but still do not obscure all of the statistical properties of the plaintext language. With
`a known-plaintext attack, the ciphers are trivial to break. A ciphertext-only attackis
`harder, but only takes a few seconds on a computer. Details are in [1261].
`Polygram substitution ciphers are ciphers in which groupsofletters are encrypted
`together. The Playfair cipher, invented in 1854, was used by the British during
`World War I [794]. It encrypts pairs of letters together. Its cryptanalysis is discussed
`in [587,1475,880]. The Hill cipher is another example of a polygram substitution
`cipher [732]. Sometimes you see Huffman coding usedasa cipher; this is an insecure
`polygram substitution cipher.
`Polyalphabetic substitution ciphers were invented by Leon Battista in 1568 [794].
`They were used by the Union army during the American Civil War. Despite the fact
`that they can be broken easily [819,577,587,794] (especially with the help of com-
`puters), many commercial computer security products use ciphers of this form
`[1387,1390,1502]. (Details on how to break this encryption scheme, as used in Word-
`Perfect, can be found in [135,139].) The Vigenére cipher, first published in 1586, and
`the Beaufort cipher are also examples of polyalphabetic substitution ciphers.
`Polyalphabetic substitution ciphers have multiple one-letter keys, each of which
`is used to encrypt oneletter of the plaintext. Thefirst key encrypts thefirst letter of
`the plaintext, the second key encrypts the secondletter of the plaintext, and so on.
`After all the keys are used, the keys are recycled. If there were 20 one-letter keys,
`then every twentieth letter would be encrypted with the same key. Thisis called the
`period of the cipher. In classical cryptography, ciphers with longer periods were sig-
`nificantly harder to break than ciphers with shortperiods. There are computer tech-
`niques that can easily break substitution ciphers with very long periods.
`
`

`

`
`
`CHAPTER | Foundations
`
`
`A running-key cipher—sometimes called a book cipher—in which onetext is
`used to encrypt anothertext, is another example of this sort of cipher. Even though
`this cipher has a periodthe length ofthe text, it can also be brokeneasily [576,794].
`Transposition Ciphers
`In a transposition cipher the plaintext remains the same, but the order of charac-
`ters is shuffled around. In a simple columnar transposition cipher, the plaintext is
`written horizontally onto a piece of graph paperoffixed width and the ciphertextis
`read off vertically (see Figure 1.4), Decryption is a matter of writing the ciphertext
`vertically onto a piece of graph paperof identical width and then readingtheplain-
`text off horizontally.
`Cryptanalysis of these ciphers is discussed in [587,1475]. Since the letters of the
`ciphertext are the sameas thoseof the plaintext, a frequency analysis on the cipher-
`text would reveal that each letter has approximately the same likelihood as in
`English. This gives a very good clue to a cryptanalyst, who can then use a variety of
`techniques to determine the right ordering of the letters to obtain the plaintext.
`Putting the ciphertext through a second transposition cipher greatly enhances secu-
`tity. There are even more complicated transposition ciphers, but computers can
`break almost all of them.
`The German ADFGVX cipher, used during World War I, is a transposition cipher
`combined with a simple substitution. It was a very complex algorithm for its day
`but was broken by Georges Painvin, a French cryptanalyst [794].
`Although many modern algorithms use transposition,it is troublesome becauseit
`requires a lot of memory and sometimes requires messages to be only certain
`lengths. Substitution is far more common.
`
`Rotor Machines
`In the 1920s, various mechanical encryption devices were invented to automate
`the process of encryption. Most were based on the conceptof a rotor, a mechanical
`wheel wired to perform a general substitution.
`A rotor machine has a keyboard anda series of rotors, and implementsa version
`of the Vigenére cipher. Each rotor is an arbitrary permutation of the alphabet, has 26
`positions, and performs a simple substitution. For example, a rotor might be wired
`
`
`Plaintext:compuTer GRAPHICS MAY BE SLOW BUTATLEASTIT’S EXPENSIVE,
`COMPUTERGR
`APHICSMAYB
`ESLOWBUTAT
`
`LEASTITSEX
`
`PENSIVE
`Ciphertext: cAELP OPSEE MHLAN PIOSS UCWTITSBIVEMUTE RATSG YAERB TX
`
`Figure 1.4 Columnar transposition cipher.
`
`
`
`|
`
`L
`
`

`

` 1.4 Simple XORet
`
`
`
`
`
`The German Enigma hadthree rotors, chosen fromasetof five, a plugboard that i
`
`substitute “F” for “A,” “U” for “B,” “L” for “C,” and so on. And the output pins
`i ne rotor are connected to the input pinsof the next.
`° - example, in a 4-rotor machinethefirst rotor might substitute “F” for “A,” the
`second might substitute “Y”for “F,” the third might substitute “E” for “Y,” and the
`fourth might substitute “C” for “E”; “C” would be the output ciphertext. Then
`some of the rotors shift, so next time the substitutions will be different.
`It is the combination of several rotors and the gears moving them that makes the
`machine secure. Because the rotors all move at different rates, the period for an n-
`rotor machine is 26". Some rotor machines can also have a different numberof posi-
`tions on eachrotor, further frustrating cryptanalysis.
`The best-known rotor device is the Enigma. The Enigma was used by the Ger-
`mans during World War I. The idea was invented by Arthur Scherbius and Arvid
`Cerhard Damm in Europe. It was patented in the United States by Arthur Scherbius
`[1383]. The Germans beefed up the basic design considerably for wartimeuse.
`
`slightly permuted theplaintext, and a reflecting rotor that caused eachrotor to oper-
`ate on each plaintext letter twice. As complicated as the Enigma was, it was broken
`during World War II. First, a team of Polish cryptographers broke the German
`Enigma and explained their attack to the British. The Germans modified their
`Enigma as the war progres