`
`IPR2016-01404
`
`Exhibit 2002
`IPR2016-01404
`
`
`
`URCE CODE IN C
`
`PROTOCOLS, 2- -
`
`
`
`New York
`
`Jchn Wiiey 8: Sons, inc.
`0 Chichesier
`Brfisbcme
`Tcronfro
`
`0 Singapore
`
`
`
`Publisher: Katherine Schowalter
`Editor: Phil Sutherland
`
`Assistant Editor: Mlison Roarty
`Managing Editor: Robert Aronds -
`Text Design & Composition: North Niarket Street Graphics
`
`Designations used by companies to distinguish their products are often claimed as trademarks. In all
`instances where Iohn Wiley & Sons, Inc. is aware of a claim, the product names appear in 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 S1 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.
`
`In no event will the publisher or author be liable 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 use or inability to use the protocols and algorithms in 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 all necessary patent and copyright licenses before implementing in
`software any protocol or algorithm in this book. This book does not contain an exhaustive list of all appli-
`cable patents and copyrights.
`
`Some of the protocols and algorithms in 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 owner is unlawful. Requests
`for permission or further information should be addressed to the Permissions Department, Iohn Wiley S1
`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. Computer security.
`2. Telecomrnunication——Security measures.
`3. Cryptography.
`I.
`QA76.9.A25S35
`
`1996
`
`0O5.8'2——dc2O
`
`Printed in the United States of America
`10 9 8 7 6 5 4
`
`95-12398
`Cll’
`
`
`
`CHAPTER
`
`‘I
`
`Foundafions
`
`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 Way as to 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.)
`The art and science of keeping messages secure is cryptography, and it is practiced
`by cryptographers. Cryptanalysts are praceitioners of cryptanalysis, the art and sci-
`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 cryptologists. Modern cryptologists are generally trained in the-
`oretical mathematics—they have to be.
`
`Piaintext
`
`Encryption
`
`Ciphertext
`
`_
`Decryption
`
`Original
`Plaintext
`
`Figure 1.1 Encryption and Decryption.
`
` ;——....j
`
`
`
` 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 concerns itself with binary data and computer cryptography.) The plain-
`text can be intended for either transmission or storage. In any case, M is the message
`to be encrypted.
`‘
`Ciphertext is denoted by C. It is also binary data: sometimes the same size 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
`
`In the reverse process, the decryption function D operates on C to produce M:
`
`U(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:
`
`Authentication, Integrity, and Nonrepudfatien
`
`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
`someone else.
`
`— 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 message for a legitimate one.
`
`—— Nonrepudiation. A sender should not be able to 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 he says he is .
`.
`. that some-
`one’s credentials——whether a driver's license, a medical degree, or a passport—are
`valid .
`.
`. that a document purporting 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 aigorithm, 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.)
`
`
`
`lI
`
`
`
`_
`
`
`
`1.1 Terminology
`
`
`
`If the security of an algorithm is based on keeping the way that algorithm works
`a S-écret, it is a restricted algorithm. Restricted algorithms have historical interest,
`but 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
`m st change their algorithm.
`Even more damning, restricted algorithms allow no quality control or standard-
`izatjon. very group of users must have their own unique algorithm. 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 number of 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 and this fact is denoted by the K subscript), so the functions
`now become:
`
`= M
`
`Those functions have the property that (see Figure 1.2):
`
`= M
`
`Some algorithms use a different encryption key and decryption key (see Figure
`1.3). That is, the encryption key, K1, is different from the corresponding decryption
`key, K2. in this case:
`
`EK1(M) = C
`DK2(C) =
`Dz<2(E;<1 (Ml) = 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.
`t doesn't matter if an
`
`)
`
`I
`
`Plaintext
`
`Key
`)
`
`Key
`
`I
`
`Ciphertext
`
`-
`
`Original
`Plaintext
`
`Figure 1.2 Encryption and decryption with a key.
`
`
`
`
`
`CHAPTER 1 Foundations
`
`1
`
`Encryption
`Key
`
`Decryption
`Key
`
`
`Original
`
`
`
`Plaintext
`Plaintext
`
`
`Ciphertext _
`
`
`
` Decption
`Encrypion
`
`
`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, plus all 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 irom the decryption key and vice 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:
`
`EK)M)= C
`
`DK(C)=1l/i
`
`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 algorithms are 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. (Beéore com-
`puters, algorithms generally operated on plaintext one character at a time. You can
`think of this as a stream algorithm operating on a stream or characters.)
`
`PubIic=~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 amount of 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-
`
`
`
`
`
`I.
`
`\
`
`1.1 Terminology
`
`. n key can decrypt the message. In these systems, the encryption key is often
`uclled the public key, and the decryption key is often called the private key. The pri-
`gite key is sometimes also 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:
`
`EK(M) = C
`
`Even though she public key and private key are different, decryption with the cor-
`responding private key is denoted by:
`
`DK(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 denoted by, respectively:
`
`= 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 means is 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 break it
`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. Ciphettext-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
`
`
`
`.
`
`.
`
`.
`
`I
`
`.
`
`CHAPTER 1 Foundations
`
`?
`‘mm
`
`I
`
`encrypt the messages, in order to decrypt other messages encrypted with
`the same keys.
`
`Given: C1 2 Ek(P1), C2 = Ek(P2),
`
`.
`
`.
`
`. C1-= Ek(Pj)
`
`. P,-; k; or an algorithm
`.
`.
`Deduce: Either P1, P2,
`to infer P1'+ 1 from C14. 1 =E}<(P1‘+ 1)
`
`2. 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: P1, C1: Eklpl), P2, C2 = Eklpzl, .
`Deduce: Either k, or an algorithm
`to infer P1-+1 from C1'+ 1 == .Ek(P1« ., 1)
`
`.
`
`. Pi, C1‘ =
`
`3. 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).
`
`. P1‘, C1‘ = Eklpi),
`.
`Cf:-lVeI1:1El31, C1: Eklpll, P1, C2 = Eklpgl, .
`Where the cryptanalyst gets to choose P1, P2,
`.
`.
`. P1
`Deduce: Either k, or an algorithm to infer P1» i 1 from C” 1 = Ek(P1- + 1)
`
`4. 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 one large 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 the results of the first, and so forth.
`
`There are at least three other types of cryptanalytie attack.
`
`5. 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.
`
`Gilvenz Cl; Pl :DklCll> C2; P2 : Dklczlz '
`Deduce: _k
`
`'
`
`' C13 Pi:
`
`
`
`1.1 Terminology
`
`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 a”chosen-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 Seetion 12.4.
`
`7. Rubber=h0se cryptanalysis. The cryptanalyst threatens, blackmails, or tor-
`tures someone until they give him the key. Bribery is sometimes referred
`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.
`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 Iapanese during World War II. 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 the algorithm’s inner work-
`ings, you're sunk.
`If you believe that keeping the algorithm’s insides secret
`improves the security of your cryptosystem more than 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 cryptographersl
`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 Iapanese diplomatic code PURPLE during World War II [794]—but
`they often do. If the algorithm is being used in a commercial security program, it is
`simply a matter of time and money to disassemble the program and recover the algo-
`rithm. If the algorithm is being used in a military communications system, it is sim-
`
`
`
`
`
`CHAPTER 1 Foundations
`
`,,,,,‘m.x-v;n,.n7
`
`ply a matter of time and money to buy (or steal) the equipment and reverse-engineer
`nunnwn u-r|I|I|.1/'I|IJI man/sun /un-
`the algorithm.
`m.,Vm.w ..,W..1M Wm, ,
`
`
`
`
`
`
`1.2 Steganography
`
`1. Data complexity. The amount of data needed as input to the attack.
`2, Processing complexity. The time needed to perfornr the attack. This is
`often called the work factor.
`
`3, Storage requirements. The amount of memory needed to do the attack.
`
`As 3 rule of thumb, the complexity of an attack is taken to be the maximum of
`these three factors. Some attacks involve trading off the three complexities: A faster
`attack might be possible at the expense of a greater storage requirement.
`complexities are expressed as orders of magnitude. If an algorithm has a process-
`ing complexity of 2128, then 2128 operations are required to break the algorithm.
`(These operations may be complex and time—consuming.) Still, if you assume that
`you have enough computing speed to perform a million operations every second and
`you set a million parallel processors against the task, it will still take over 1019 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 power is anything but. There have been phenome-
`nal advances in computing power during 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 down into billions of tiny pieces and none of
`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
`power that is expected to evolve many years in the future.
`
`Historical Terms
`
`Historically, a code refers to a cryptosystern 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 "I-IOWITZER.” Codes of 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
`”ANTE_ATERS,” 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 same piece of 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 1 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 programs do this 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 TRANsI>osmoN CIPHERS
`
`Before computers, cryptography consisted of character-based algorithms. Different
`cryptographic algorithms either 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 change in the alphabet size: from 26 elements to two elements. Most good
`cryptographic algorithms still 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 cr
`to ra h , there are four t
`S P Y
`
`VP
`
`VP
`
`es of substitution ci hers:
`13
`
`— A simple substitution cipher, or monoalphabetic cipher, is one in
`which each character of the plaintext is replaced with a correspond-
`ing character of ciphertext. The cryptograms in newspapers are sim-
`ple substitution ciphers.
`— A homophonic substitution cipher is like a simple substitution cryp-
`tosystem, except a single character of plaintext can map to one of sev-
`eral characters of ciphertext. For example, ”A” could correspond to
`either 5, 13, 25, or 56, ”B” could correspond to 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 ”SnL,” and so on.
`— 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.._...;;—
`
`
`
`
`
`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
`HE ,, “Wu is replacéd by ”Z,” .
`.
`.
`, ”X” is replaced by ”A,” ”Y” is replaced by ”B,”
`and ”Z” is replaced by ”C”) is a simple substitution cipher. It's actually “even sim-
`pler, because the ciphertext alphabet is a rotation of the plaintext alphabet and not
`an arbitrary permutation.
`RQT13 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 the original file.
`
`P = ROT13 (ROT13 (19))
`
`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 so forth.
`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 [5 78,58 7,
`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 attack is
`harder, but only takes a few seconds on a computer. Details are in [1261].
`Polygram substitution ciphers are ciphers in which groups of letters are encrypted
`together. The Playfair cipher, invented in 1854, was used by the British during
`World Wari [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 used as a cipher; this is an insecure
`polygram substitution cipher.
`Polyalphabetic substitution ciphers were invented by Leon Battista in 1568 [794j.
`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
`[138 7, 1390, 1502]. (Details on how to break this encryption scheme, as used in Word-
`Perfect, can be found in [135, 139].) The Vigenere 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 one letter of the plaintext. The first key encrypts the first letter of
`the plaintext, the second key encrypts the second letter 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. This is called the
`period of the cipher. 1n classical cryptography, ciphers with longer periods were sig-
`nificantly harder to break than ciphers with short periods. There are computer tech-
`niques that can easily break substitution ciphers with very long periods.
`
`
`
`CHAPTER 1 Foundations
`
`A running-=key cipher—sometimes called a book cipher——in which one text is
`used to encrypt another text, is another example of this sort of cipher. Even though
`this cipher has a period the length of the text, it can also be broken easily [5 76, 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 paper of fixed width and the ciphertext is
`read off vertically (see Figure 1.4). Decryption is a matter of writing the ciphertext
`vertically onto a piece of graph paper of identical Width and then reading the plain-
`text off horizontally.
`Cryptanalysis of these ciphers is discussed in [587,1475]. Since the letters of the
`ciphertext are the same as those of 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-
`rity. 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 because it
`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 concept of a rotor, a mechanical
`Wheel wired to perform a general substitution.
`A rotor machine has a keyboard and a series of rotors, and implements a version
`of the Vigenere 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
`
`Plalnl.'eXi§COMPUTEFiGRAPHICSMAYBESLOWBUTATLEASTlT’SEXPENSIVE.
`
`COMPUTERGR
`APHICSWAYB
`ESLOWBJTAT
`nEAST£TSEX
`
`l
`,
`
`PENSIVE
`l
`I Ciphertextt CAELP OPSEE MHLAN PIOSS ucwrn ‘rssu VEMUTE RATSG YAERB TX
`I.
`Figure 1.4 Coiuninar transposition cipher.
`
`I
`
`l
`
`
`
`1.4 Simple XOR %§\‘\\\
`
`ubstitute ”F” for ”A," ”U” for ”B,” ”L” for ”C,” and so on. And the output pins
`t? S e rotor are connected to the input pins of the next.
`0 F05; example, in a 4-rotor machine the first rotor might substitute ”F” for ”A, ” the
`second might substitute ”Y” for ”F, ” the third. might substitute ”E” for ”Yf” 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 neachines can also have a different number of posi-
`tions on each rotor, further frustrating cryptanalysis.
`The best-known rotor device is the Enigma. The Enigma was used by the Ger-
`mans during World War II. The idea was invented by Arthur Scherbius and Arvid
`Gerhard Damm in Europe. It was patented in the United States by Arthur Scherbius
`[1383]. The Germans beefed up the basic design considerably for wartime use.
`The German Enigma had three rotors, chosen from a set of five, a plugboard that
`slightly permuted the plaintext, and a reflecting rotor that caused each rotor to oper-
`ate on each plaintext letter twice. As complicated as the Enigma was, it was