Chuck Easttom Modern Cryptography Applied Mathematics for Encryption and Information Security Second Edition Modern Cryptography Chuck Easttom Modern Cryptography Applied Mathematics for Encryption and Information Security Second Edition Chuck Easttom Georgetown University and Vanderbilt University Plano, USA ISBN 978-3-031-12303-0 ISBN 978-3-031-12304-7 (eBook) https://doi.org/10.1007/978-3-031-12304-7 © The Editor(s) (if applicable) and The Author(s), under exclusive license to Springer Nature Switzerland AG 2021, 2022 This work is subject to copyright. All rights are solely and exclusively licensed by the Publisher, whether the whole or part of the material is concerned, specifically the rights of translation, reprinting, reuse of illustrations, recitation, broadcasting, reproduction on microfilms or in any other physical way, and transmission or information storage and retrieval, electronic adaptation, computer software, or by similar or dissimilar methodology now known or hereafter developed. The use of general descriptive names, registered names, trademarks, service marks, etc. in this publication does not imply, even in the absence of a specific statement, that such names are exempt from the relevant protective laws and regulations and therefore free for general use. The publisher, the authors, and the editors are safe to assume that the advice and information in this book are believed to be true and accurate at the date of publication. Neither the publisher nor the authors or the editors give a warranty, expressed or implied, with respect to the material contained herein or for any errors or omissions that may have been made. The publisher remains neutral with regard to jurisdictional claims in published maps and institutional affiliations. This Springer imprint is published by the registered company Springer Nature Switzerland AG The registered company address is: Gewerbestrasse 11, 6330 Cham, Switzerland I dedicate this book to my wife Teresa who is always long suffering with my work and research, and who has always been amazingly supportive. I could not have done any of this without her support. A quote from one of my favorite movies describes how I feel about her and her support “What truly is logic? Who decides reason? My quest has taken me to the physical, the metaphysical, the delusional, and back. I have made the most important discovery of my career—the most important discovery of my life. It is only in the mysterious equations of love that any logic or reasons can be found. I am only here tonight because of you. You are the only reason I am. You are all my reasons. Introduction The book Modern Cryptography: Applied Mathematics for Encryption and Information Security was first published with McGraw Hill, then later revised and published with Springer. This is the second edition with Springer. What has changed you might wonder? Some chapters have had only very minor changes, for example, Chap. 12 has had only a few updates. Other chapters have had not only revisions but also new algorithms added. Chapter 10 now provides details on the YAK cipher. The mathematics of Chap. 5 has been expanded. Chapters 20 and 21 are entirely new and cover quantum-resistant cryptography algorithms. Along with that addition, Chap. 19 that provides a general overview of quantum computing has also been expanded. Chapter 13 now covers additional digital certificate types. Chapter 8 has also been substantially expanded. Most importantly, all chapters have been reviewed to make concepts clearer for the reader. As with the previous editions, this book is not meant for the mathematician or cryptographer to deep dive into the topic. It is meant for the programmer, cyber security professional, network administrator, or others who need to have a deeper understanding of cryptography. For that reason, mathematical proofs are not included in this book. Sufficient mathematics to generally understand the concepts is provided, but no more than is absolutely needed. Beginning with the first version of this book in 2015, the intent has been the same: to fill a gap in cryptography literature. There are some excellent books written for the mathematically sophisticated. These books provide so much rich detail on the algorithms and the “why” behind the math. However, these are largely inacces- sible to those with less rigorous mathematical backgrounds. Then there are cyberse- curity books which provide very little detail on cryptography, books that prepare one for cybersecurity certifications such as CompTIA Security+ and ISC2 CISSP. However, those books provide only the most cursory review of cryptogra- phy. This book is meant to be a bridge between those two worlds. When you finish this book, you will know far more than you do now, even assuming you hold several cybersecurity certifications. However, there is much more to learn. There are a few specific books I recommend after you have completed this one. Any of the follow- ing will take you deeper into the math behind the cryptography: vii viii Introduction Understanding Cryptography: A Textbook for Students and Practitioners by Christof Paar and Jan Pelzl. An Introduction to Mathematical Cryptography (Undergraduate Texts in Mathematics) Second Edition, 2014, by Hoffstien, Pipher, and Silverman. Introduction to Modern Cryptography (Chapman & Hall/CRC Cryptography and Network Security Series) Second Edition by Katz and Lindell. Now those books will skip over things like s-box design, quantum-resistant cryp- tography, and a few other issues. But they will dive much deeper into current sym- metric and asymmetric algorithms as well as cryptographic hashes. So, if you complete this current book, and wish to dive deeper, I recommend one or more of these. Contents 1 History of Cryptography to the 1800s . . . . . . . . . . . . . . . . . . . . . . . . . 1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 In This Chapter We Will Cover the Following . . . . . . . . . . . . . . . . . . . . 2 Why Study Cryptography? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 What Is Cryptography? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 Substitution Ciphers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 The Caesar Cipher . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 Atbash Cipher . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 Affine Ciphers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 Homophonic Substitution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 Polybius Cipher . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 Null Cipher . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 Multi-alphabet Substitution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 Devices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 Phaistos Disc . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 Phryctoriae . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 Book Ciphers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 Transposition Ciphers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 Reverse Order . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 Rail Fence Cipher . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 Geometric Shape Cipher . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 Columnar Cipher . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 Combinations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 D’Agapeyeff Cipher . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 Test Your Knowledge . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 2 History of Cryptography from the 1800s . . . . . . . . . . . . . . . . . . . . . . 29 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 In This Chapter We Will Cover the Following . . . . . . . . . . . . . . . . . . . . 29 ix x Contents Playfair . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 Two-Square Cipher . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 Four-Square Cipher . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 Hill Cipher . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 ADFGVX . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 Bifid. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 The Gronsfeld Cipher . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 The Vernam Cipher . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 Edgar Allan Poe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 Cryptography Comes of Age . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 Enigma . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 Kryha . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 SIGABA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 Lorenz Cipher . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 Navajo Code Talkers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 VIC Cipher . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 IFF Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 The NSA: The Early Years . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 Test Your Knowledge . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 3 Basic Information Theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 In This Chapter We Will Cover . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 The Information Age . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 Claude Shannon . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 Theorem 1: Shannon’s Source Coding Theorem . . . . . . . . . . . . . . . . 55 Theorem 2: Noisy Channel Theorem . . . . . . . . . . . . . . . . . . . . . . . . . 55 Concepts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 Information Entropy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 Quantifying Information . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 Confusion and Diffusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 Avalanche . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 Hamming Distance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61 Hamming Weight . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61 Kerckhoffs’s Principle/Shannon’s Maxim . . . . . . . . . . . . . . . . . . . . . 62 Information Diversity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 Scientific and Mathematical Theories . . . . . . . . . . . . . . . . . . . . . . . . . . . 64 What Is a Mathematical Theory? . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65 The Scientific Process . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66 A Scientific Theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66 Binary Math . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69 Converting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70 Binary Operations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70 Contents xi Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72 Test Your Knowledge . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73 4 Essential Number Theory and Discrete Math . . . . . . . . . . . . . . . . . . 75 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75 In This Chapter We Will Cover . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76 Number Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76 Natural Numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77 Integers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77 Rational Numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78 Irrational Numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78 Real Numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78 Complex Numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79 Transcendental Numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82 Prime Numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83 Finding Prime Numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83 Relatively Prime . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88 Important Operations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89 Divisibility Theorems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90 Summation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90 Logarithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91 Modulus Operations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92 Famous Number Theorists and Their Contributions . . . . . . . . . . . . . . . . 94 Fibonacci . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94 Fermat . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95 Euler . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95 Goldbach . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96 Discrete Mathematics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96 Set Theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97 Logic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99 Combinatorics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106 Test Your Knowledge . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107 5 Essential Algebra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109 In This Chapter We Will Cover . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110 Groups, Rings, and Fields . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110 Groups . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112 Rings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113 Fields . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114 Diophantine Equations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115 Linear Algebra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116 Matrix Addition and Multiplication . . . . . . . . . . . . . . . . . . . . . . . . . . 117