Secret History: The Story of Cryptology

Cover
Half Title
Series Page
Title Page
Copyright Page
Dedication
Contents
New and Improved
Note to the Reader
Introduction
Acknowledgments
PART I: CLASSICAL CRYPTOLOGY
	1. Monoalphabetic Substitution Ciphers, or MASCs: Disguises for Messages
		1.1. Caveman Crypto
		1.2. Greek Cryptography
			1.2.1. The Skytale Cipher
			1.2.2. The Polybius Cipher5
		1.3. Viking Cryptography
		1.4. Early Steganography
		1.5. Caesar Cipher
		1.6. Other MASC Systems
		1.7. Edgar Allan Poe
		1.8. Arthur Conan Doyle
		1.9. Frequency Analysis
		1.10. Biblical Cryptology
		1.11. More Frequencies and Pattern Words
		1.12. Vowel Recognition Algorithms
			1.12.1. Sukhotin’s Method
		1.13. More MASCs
		1.14. Cryptanalysis of a MASC
		1.15. Ciphers by a Killer and a Composer
		1.16. Affine Ciphers
		1.17. Morse Code and Huffman Coding
		1.18. MASC Miscellanea
		1.19. Nomenclators
		1.20. Cryptanalysis of Nomenclators
		1.21. Book Codes
		References and Further Reading
	2. Simple Progression to an Unbreakable Cipher
		2.1. The Vigenère Cipher
		2.2. History of the Vigenère Cipher
		2.3. Cryptanalysis of the Vigenère Cipher
		2.4. Kryptos
		2.5. Autokeys
		2.6. The Running Key Cipher and Its Cryptanalysis
		2.7. The One-Time Pad or Vernam Cipher
		2.8. Breaking the Unbreakable
		2.9. Faking Randomness
		2.10. An Unsolved Cipher from 1915.
		2.11. OTPs and the SOE
		2.12. History Rewritten!
		References and Further Reading
	3. Transposition Ciphers
		3.1. Simple Rearrangements and Columnar Transposition
			3.1.1. Rail-Fence Transposition
			3.1.2. Rectangular Transposition
			3.1.3. More Transposition Paths
		3.2. Cryptanalysis of Columnar Transposition
		3.3. Historic Uses
		3.4. Anagrams
		3.5. Double Transposition
		3.6. Word Transposition
			3.6.1. Civil War Reenactors
		3.7. Transposition Devices
		References and Further Reading
	4. Shakespeare, Jefferson, and JFK
		4.1. Shakespeare vs. Bacon
		4.2. Thomas Jefferson: President, Cryptographer
		4.3. Wheel Cipher Cryptanalysis
		4.4. The Playfair Cipher
		4.5. Playfair Cryptanalysis
			4.5.1. Computer Cryptanalysis
		4.6. Kerckhoffs’s Rules
		References and Further Reading
	5. World War I and Herbert O. Yardley
		5.1. The Zimmermann Telegram
		5.2. ADFGX: A New Kind of Cipher
		5.3. Cryptanalysis of ADFGX
		5.4. Herbert O. Yardley
		5.5. Peacetime Victory and a Tell-All Book
		5.6. The Case of the Seized Manuscript
		5.7. Cashing In, Again
		5.8. Herbert O. Yardley—Traitor?
		5.9. Censorship
		References and Further Reading
	6. Matrix Encryption
		6.1. Levine and Hill
		6.2. How Matrix Encryption Works
		6.3. Levine’s Attacks
		6.4. Bauer and Millward’s Attack
		6.5. More Stories Left to Tell
		References and Further Reading
	7. World War II: The Enigma of Germany
		7.1. Rise of the Machines
		7.2. How Enigma Works
		7.3. Calculating the Keyspace
		7.4. Cryptanalysis Part 1: Recovering the Rotor Wirings
		7.5. Cryptanalysis Part 2: Recovering the Daily Keys
		7.6. After the Break
		7.7. Alan Turing and Bletchley Park
		7.8. The Lorenz Cipher and Colossus
		7.9. What If Enigma Had Never Been Broken?
		7.10. Endings and New Beginnings
		References and Further Reading
	8. Cryptologic War against Japan
		8.1. Forewarning of Pearl Harbor?
		8.2. Friedman’s Team Assembles
		8.3. Cryptanalysis of Red, a Japanese Diplomatic Cipher
			8.3.1. Orange
		8.4. Purple—How It Works
		8.5. Purple Cryptanalysis
		8.6. Practical Magic
		8.7. Code Talkers
		8.8. Code Talkers in Hollywood
		8.9. Use of Languages as Oral Codes
		References and Further Reading
	9. SIGABA: World War II Defense
		9.1. The Mother of Invention
		9.2. Making the Rotors
		9.3. Anatomy of a Success
		9.4. SIGABA Production
		9.5. Keyspace and Modern Cryptanalysis
		9.6. Missing or Captured Machines?
		9.7. The End of SIGABA
		References and Further Reading
	10. Enciphering Speech
		10.1. Early Voice Encryption
		10.2. The Cost of Insecurity
		10.3. SIGSALY—A Solution from the Past Applied to Speech
		10.4. Plan B
		10.5. SIGSALY in Action
		10.6. SIGSALY Retires
		10.7. Voice vs. Text
		References and Further Reading
PART II: MODERN CRYPTOLOGY
	11. Claude Shannon
		11.1. About Claude Shannon
		11.2. Measuring Information
		11.3. One More Time…
		11.4. Unicity Points
		11.5. Dazed and Confused
		11.6. Entropy in Religion
		11.7. Entropy in Literature
		References and Further Reading
	12. National Security Agency
		12.1. Origins of NSA
		12.2. TEMPEST
		12.3. Size and Budget
		12.4. The Liberty and the Pueblo
		12.5. The Church Committee Investigations
		12.6. Post Cold War Downsizing
		12.7. The Crypto AG Connection
		12.8. 2000.. and Beyond
		12.9. Interviewing with NSA
		12.10. Another Betrayal
		12.11. NSA and the Media
		12.12. BRUSA, UKUSA, and Echelon
		References and Further Reading
	13. The Data Encryption Standard
		13.1. How DES Works
		13.2. Reactions to and Cryptanalysis of DES
			13.2.1. Objection 1: Key Size Matters
			13.2.2. Objection 2: S-Box Secrecy
			13.2.3. S-Boxes Revealed!
		13.3. EFF vs. DES
		13.4. A Second Chance
		13.5. An Interesting Feature
			13.5.1. Cryptologic Humor
		13.6. Modes of Encryption
			13.6.1. Levine’s Methods
			13.6.2. Modern Modes
				13.6.2.1. Electronic Code Book Mode
				13.6.2.2. Cipher Block Chaining Mode
				13.6.2.3. Cipher Feedback Mode
				13.6.2.4. Output Feedback Mode
				13.6.2.5. Counter Mode
				13.6.2.6. Offset Codebook Mode
		References and Further Reading
	14. The Birth of Public Key Cryptography
		14.1. A Revolutionary Cryptologist
		14.2. Diffie–Hellman Key Exchange
		14.3. RSA: A Solution from MIT
			14.3.1. Fermat’s Little Theorem (1640.)
			14.3.2. The Euclidean Algorithm
		14.4. Government Control of Cryptologic Research
		14.5. RSA Patented; Alice and Bob Born Free
		14.6. History Rewritten
		References and Further Reading
	15. Attacking RSA
		15.1. A Dozen Non-Factoring Attacks
			15.1.1. Attack 1. Common Modulus Attack
			15.1.2. Attack 2. Man-in-the-Middle
			15.1.3. Attack 3. Low Decryption Exponent
			15.1.4. Attack 4. Partial Knowledge of p or q7
			15.1.5. Attack 5. Partial Knowledge of d8
			15.1.6. Attack 6. Low Encryption Exponent Attack
			15.1.7. Attack 7. Common Enciphering Exponent Attack
				15.1.7.1. The Chinese Remainder Theorem
			15.1.8. Attack 8. Searching the Message Space
			15.1.9. Attack 9. Adaptive Chosen Ciphertext Attacks
			15.1.10. Attack 10. Timing Attack13
			15.1.11. Attack 11. Textbook RSA Attack14
			15.1.12. Attack 12. Ron Was Wrong, Whit Is Right Attack
		15.2. A Factoring Challenge
			15.2.1. An Old Problem
		15.3. Trial Division and the Sieve of Eratosthenes (c. 284–204.. BCE)
		15.4. Fermat’s Factorization Method
		15.5. Euler’s Factorization Method
		15.6. Pollard’s
		15.7. Dixon’s Algorithm24
			15.7.1. The Quadratic Sieve
		15.8. Pollard’s Number Field Sieve34
			15.8.1. Other Methods
			15.8.2. Cryptological Humor
		References and Further Reading
	16. Primality Testing and Complexity Theory
		16.1. Some Facts about Primes
		16.2. The Fermat Test
		16.3. The Miller–Rabin Test13
			16.3.1. Generating Primes
		16.4. Deterministic Tests for Primality
			16.4.1. The AKS Primality Test (2002.)
			16.4.2. GIMPS
		16.5. Complexity Classes, P vs. NP, and Probabilistic vs. Deterministic
			16.5.1. Cryptologic Humor
		16.6. Ralph Merkle’s Public Key Systems
		16.7. Knapsack Encryption
		16.8. Elgamal Encryption
		References and Further Reading
	17. Authenticity
		17.1. A Problem from World War II
		17.2. Digital Signatures (and Some Attacks)
			17.2.1. Attack 13. Chosen Ciphertext Attack
			17.2.2. Attack 14. Insider’s Factoring Attack on the Common Modulus
			17.2.3. Attack 15. Insider’s Nonfactoring Attack
			17.2.4. Elgamal Signatures
		17.3. Hash Functions: Speeding Things Up
			17.3.1. Rivest’s MD5 and NIST’s SHA-1, SHA-2, and SHA-3
			17.3.2. Hash Functions and Passwords
		17.4. The Digital Signature Algorithm
		References and Further Reading
	18. Pretty Good Privacy and Bad Politics
		18.1. The Best of Both Worlds
		18.2. The Birth of PGP
		18.3. In Zimmermann’s Own Words
		18.4. The Impact of PGP
		18.5. Password Issues
		18.6. History Repeats Itself
		18.7. A Terrorist and an iPhone
		18.8. Another Terrorist and Another iPhone
		18.9. Yet Another Attempt at Anti-Crypto Legislation
		References and Further Reading
	19. Stream Ciphers
		19.1. Congruential Generators
		19.2. Linear Feedback Shift Registers
		19.3. LFSR Attack
		19.4. Cell Phone Stream Cipher A5/1.
		19.5. RC4
		References and Further Reading
	20. Suite B All-Stars
		20.1. Elliptic Curve Cryptography
			20.1.1. Elgamal, ECC Style
		20.2. Personalities behind ECC
		20.3. The Advanced Encryption Standard (AES)
			20.3.1. SubBytes
			20.3.2. ShiftRows
			20.3.3. MixColumns
			20.3.4. AddRoundKey
			20.3.5. Putting It All Together: How AES-128. Works
		20.4. AES Attacks
		20.5. Security Guru Bruce Schneier
		References and Further Reading
	21. Toward Tomorrow
		21.1. Quantum Cryptography: How It Works
		21.2. Quantum Cryptography: Historical Background
		21.3. Quantum Computers and Quantum Distributed Key Networks
		21.4. NSA Weighs In
		21.5. NIST Responds
		21.6. Predictions
		21.7. DNA Computing
		References and Further Reading
Index