Modern Cryptography AppliMeadt hematfiocErsn cryption andI nformaSteicounr ity ChucEka sttom III N<!wYork Chic�gos,o, n F'M>iscco AthensLo ndon MadridM exi<:Coi ty Mil"" NewOitlhi Sing"pOrSey dneyT oronto Copyright © 2016 by McGraw-Hill Education. All rights reserved. Except as permitted under the United States Copyright Act of 1976, no part of this publication may be reproduced or distributed in any form or by any means, or stored in a data base or retrieval system, without the prior written permission of the publisher. ISBN: 978-1-25-958809-9 MHID: 1-25-958809-2 The material in this eBook also appears in the print version of this title: ISBN: 978-1-25- 958808-2, MHID: 1-25-958808-4. eBook conversion by codeMantra Version 1.0 All trademarks are trademarks of their respective owners. Rather than put a trademark symbol after every occurrence of a trademarked name, we use names in an editorial fashion only, and to the benefit of the trademark owner, with no intention of infringement of the trademark. Where such designations appear in this book, they have been printed with initial caps. McGraw-Hill Education eBooks are available at special quantity discounts to use as premiums and sales promotions or for use in corporate training programs. To contact a representative, please visit the Contact Us page at www.mhprofessional.com. Information has been obtained by McGraw-Hill Education from sources believed to be reliable. However, because of the possibility of human or mechanical error by our sources, McGraw-Hill Education, or others, McGraw-Hill Education does not guarantee the accuracy, adequacy, or completeness of any information and is not responsible for any errors or omissions or the results obtained from the use of such information. TERMS OF USE This is a copyrighted work and McGraw-Hill Education and its licensors reserve all rights in and to the work. Use of this work is subject to these terms. Except as permitted under the Copyright Act of 1976 and the right to store and retrieve one copy of the work, you may not decompile, disassemble, reverse engineer, reproduce, modify, create derivative works based upon, transmit, distribute, disseminate, sell, publish or sublicense the work or any part of it without McGraw-Hill Education’s prior consent. You may use the work for your own noncommercial and personal use; any other use of the work is strictly prohibited. Your right to use the work may be terminated if you fail to comply with these terms. THE WORK IS PROVIDED “AS IS.” McGRAW-HILL EDUCATION AND ITS LICENSORS MAKE NO GUARANTEES OR WARRANTIES AS TO THE ACCURACY, ADEQUACY OR COMPLETENESS OF OR RESULTS TO BE OBTAINED FROM USING THE WORK, INCLUDING ANY INFORMATION THAT CAN BE ACCESSED THROUGH THE WORK VIA HYPERLINK OR OTHERWISE, AND EXPRESSLY DISCLAIM ANY WARRANTY, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO IMPLIED WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. McGraw-Hill Education and its licensors do not warrant or guarantee that the functions contained in the work will meet your requirements or that its operation will be uninterrupted or error free. Neither McGraw-Hill Education nor its licensors shall be liable to you or anyone else for any inaccuracy, error or omission, regardless of cause, in the work or for any damages resulting therefrom. McGraw-Hill Education has no responsibility for the content of any information accessed through the work. Under no circumstances shall McGraw-Hill Education and/or its licensors be liable for any indirect, incidental, special, punitive, consequential or similar damages that result from the use of or inability to use the work, even if any of them has been advised of the possibility of such damages. This limitation of liability shall apply to any claim or cause whatsoever whether such claim or cause arises in contract, tort or otherwise. This book is dedicated to the men and women working in military and intelligence agencies who implement cryptography, work with cryptanalysis, and apply cryptography to computer security. About the Author Chuck Easttom has more than 20 years of experience working in various aspects of the computer industry. For the past 15 years, he has focused primarily on computer security. He has wide experience in security, penetration testing, and forensics, but his favorite security topic is cryptography. Easttom has taught cryptography to U.S. government personnel, Department of Defense–related personnel, and friendly foreign governments. Of his six computer science patents, one is a method of distributed steganography. He has published papers on cryptography, and his various computer security books always include chapters on cryptography. He is a frequent speaker on cryptographic topics including RSA encryption, cryptographic backdoors, and cryptanalysis. Easttom’s security-related background includes 30 industry certifications, work with various vendors in the creation or revision of their certification tests, years of hands-on direct experience, and extensive teaching experience. Contents at a Glance PART I Foundations CHAPTER 1 History of Cryptography to the 1800s CHAPTER 2 History of Cryptography from the 1800s CHAPTER 3 Basic Information Theory CHAPTER 4 Essential Number Theory and Discrete Math CHAPTER 5 Essential Algebra PART II Symmetric Ciphers and Hashes CHAPTER 6 Feistel Networks CHAPTER 7 Substitution-Permutation Networks CHAPTER 8 S-Box Design CHAPTER 9 Cryptographic Hashes PART III Asymmetric Ciphers CHAPTER 10 Common Algorithms CHAPTER 11 Elliptic Curve Cryptography PART IV Applications CHAPTER 12 Random Number Generators CHAPTER 13 Secure Sockets Layer/Transport Layer Security Protocol CHAPTER 14 Virtual Private Networks CHAPTER 15 Military Applications CHAPTER 16 Steganography CHAPTER 17 Cryptanalysis CHAPTER 18 Cryptographic Backdoors CHAPTER 19 The Future of Cryptography APPENDIX Implementing Cryptography Index Contents Acknowledgments Introduction PART I Foundations CHAPTER 1 History of Cryptography to the 1800s Why Study Cryptography? What Is Cryptography? Substitution Ciphers The Caesar Cipher Atbash Cipher Affine Ciphers Homophonic Substitution Polybius Cipher Null Cipher Multi-Alphabet Substitution Devices Book Ciphers Transposition Ciphers Reverse Order Rail Fence Cipher Geometric Shape Cipher Columnar Cipher Combinations Conclusions Test Your Knowledge Answers Endnotes CHAPTER 2 History of Cryptography from the 1800s Cryptography Marches On Playfair Cipher Two-Square Cipher Four-Square Cipher Hill Cipher ADFGX and ADFGVX Ciphers Bifid Cipher Gronsfeld Cipher Vernam Cipher Cryptography Comes of Age Enigma SIGABA Lorenz Cipher IFF Systems The NSA: The Early Years Conclusions Test Your Knowledge Answers Endnotes CHAPTER 3 Basic Information Theory The Information Age Claude Shannon Theorem 1: Shannon’s Source Coding Theorem Theorem 2: Noisy Channel Theorem Core Concepts of Cryptography Information Entropy Quantifying Information Confusion and Diffusion Avalanche Hamming Distance Hamming Weight Kerckhoffs’s Principle/Shannon’s Maxim Scientific and Mathematical Theories What Is a Mathematical Theory? The Scientific Process A Scientific Theory Binary Math Converting Binary Operations Conclusions Test Your Knowledge Answers Endnotes CHAPTER 4 Essential Number Theory and Discrete Math Number Systems Natural Numbers Negative Numbers Rational and Irrational Numbers Real Numbers Imaginary Numbers Prime Numbers Finding Prime Numbers Relatively Prime, or Co-prime, Numbers Important Operations Divisibility Theorems Summation Logarithms Modulus Operations Famous Number Theorists and Their Contributions Fibonacci Fermat Euler Goldbach Discrete Mathematics Set Theory Logic