Computer Security and Cryptography

Gain the skills and knowledge needed to create effective data security systems This book updates readers with all the tools, techniques, and concepts needed to understand and implement data security systems. It presents a wide range of topics for a thorough understanding of the factors that affect the efficiency of secrecy, authentication, and digital signature schema. Most importantly, readers gain hands-on experience in cryptanalysis and learn how to create effective cryptographic systems. The author contributed to the design and analysis of the Data Encryption Standard (DES), a widely used symmetric-key encryption algorithm. His recommendations are based on firsthand experience of what does and does not work. Thorough in its coverage, the book starts with a discussion of the history of cryptography, including a description of the basic encryption systems and many of the cipher systems used in the twentieth century. The author then discusses the theory of symmetric- and public-key cryptography. Readers not only discover what cryptography can do to protect sensitive data, but also learn the practical limitations of the technology. The book ends with two chapters that explore a wide range of cryptography applications. Three basic types of chapters are featured to facilitate learning: Chapters that develop technical skills Chapters that describe a cryptosystem and present a method of analysis Chapters that describe a cryptosystem, present a method of analysis, and provide problems to test your grasp of the material and your ability to implement practical solutions With consumers becoming increasingly wary of identity theft and companies struggling to develop safe, secure systems, this book is essential reading for professionals in e-commerce and information technology. Written by a professor who teaches cryptography, it is also ideal for students. COMPUTER SECURITY AND CRYPTOGRAPHY CONTENTS FOREWORD PREFACE ACKNOWLEDGMENTS ABOUT THE AUTHOR CHAPTER 1 APERITIFS 1.1 The Lexicon of Cryptography 1.2 Cryptographic Systems 1.3 Cryptanalysis 1.4 Side Information 1.5 Thomas Jefferson and the M-94 1.6 Cryptography and History 1.7 Cryptography and Computers 1.8 The National Security Agency 1.9 The Giants 1.10 No Sex, Money, Crime or . . . Love 1.11 An Example of the Inference Process in Cryptanalysis 1.12 Warning! CHAPTER 2 COLUMNAR TRANSPOSITION 2.1 Shannon’s Classification of Secrecy Transformations 2.2 The Rules of Columnar Transposition Encipherment 2.3 Cribbing 2.4 Examples of Cribbing 2.5 Plaintext Language Models 2.6 Counting k-Grams 2.7 Deriving the Parameters of a Markov Model from Sliding Window Counts 2.8 Markov Scoring 2.9 The ADFGVX Transposition System 2.10 CODA 2.11 Columnar Transposition Problems CHAPTER 3 MONOALPHABETIC SUBSTITUTION 3.1 Monoalphabetic Substitution 3.2 Caesar’s Cipher 3.3 Cribbing Using Isomorphs 3.4 The x(2)-Test of a Hypothesis 3.5 Pruning from the Table of Isomorphs 3.6 Partial Maximum Likelihood Estimation of a Monoalphabetic Substitution 3.7 The Hidden Markov Model (HMM) 3.8 Hill Encipherment of ASCII N-Grams 3.9 Gaussian Elimination 3.10 Monoalphabetic Substitution Problems CHAPTER 4 POLYALPHABETIC SUBSTITUTION 4.1 Running Keys 4.2 Blaise de Vigenère 4.3 Gilbert S. Vernam 4.4 The One-Time Pad 4.5 Finding the Key of Vernam–Vigenère Ciphertext with Known Period by Correlation 4.6 Coincidence 4.7 Venona 4.8 Polyalphabetic Substitution Problems CHAPTER 5 STATISTICAL TESTS 5.1 Weaknesses in a Cryptosystem 5.2 The Kolmogorov–Smirnov Test 5.3 NIST’s Proposed Statistical Tests 5.4 Diagnosis 5.5 Statistical Tests Problems CHAPTER 6 THE EMERGENCE OF CIPHER MACHINES 6.1 The Rotor 6.2 Rotor Systems 6.3 Rotor Patents 6.4 A Characteristic Property of Conjugacy 6.5 Analysis of a 1-Rotor System: Ciphertext Only 6.6 The Displacement Sequence of a Permutation 6.7 Arthur Scherbius 6.8 Enigma Key Distribution Protocol 6.9 Cryptanalysis of the Enigma 6.10 Cribbing Enigma Ciphertext 6.11 The Lorenz Schlüsselzusatz 6.12 The SZ40 Pin Wheels 6.13 SZ40 Cryptanalysis Problems 6.14 Cribbing SZ40 Ciphertext CHAPTER 7 THE JAPANESE CIPHER MACHINES 7.1 Japanese Signaling Conventions 7.2 Half-Rotors 7.3 Components of the RED Machine 7.4 Cribbing RED Ciphertext 7.5 Generalized Vowels and Consonants 7.6 “Climb Mount Itaka” – War! 7.7 Components of the PURPLE Machine 7.8 The PURPLE Keys 7.9 Cribbing PURPLE: Finding the V-Stepper 7.10 Cribbing PURPLE: Finding the C-Steppers CHAPTER 8 STREAM CIPHERS 8.1 Stream Ciphers 8.2 Feedback Shift Registers 8.3 The Algebra of Polynomials over Z(2) 8.4 The Characteristic Polynomial of a Linear Feedback Shift Register 8.5 Properties of Maximal Length LFSR Sequences 8.6 Linear Equivalence 8.7 Combining Multiple Linear Feedback Shift Registers 8.8 Matrix Representation of the LFSR 8.9 Cribbing of Stream Enciphered ASCII Plaintext 8.10 Nonlinear Feedback Shift Registers 8.11 Nonlinear Key Stream Generation 8.12 Irregular Clocking 8.13 RC4 8.14 Stream Encipherment Problems CHAPTER 9 BLOCK-CIPHERS: LUCIFER, DES, AND AES 9.1 LUCIFER 9.2 DES 9.3 The DES S-Boxes, P-Box, and Initial Permutation (IP) 9.4 DES Key Schedule 9.5 Sample DES Encipherment 9.6 Chaining 9.7 Is DES a Random Mapping? 9.8 DES in the Output-Feedback Mode (OFB) 9.9 Cryptanalysis of DES 9.10 Differential Cryptanalysis 9.11 The EFS DES-Cracker 9.12 What Now? 9.13 The Future Advanced Data Encryption Standard 9.14 And the Winner Is! 9.15 The Rijndael Operations 9.16 The Rijndael Cipher 9.17 Rijndael’s Strength: Propagation of Patterns 9.18 When is a Product Block-Cipher Secure? 9.19 Generating the Symmetric Group 9.20 A Class of Block Ciphers 9.21 The IDEA Block Cipher CHAPTER 10 THE PARADIGM OF PUBLIC KEY CRYPTOGRAPHY 10.1 In the Beginning. . . 10.2 Key Distribution 10.3 E-Commerce 10.4 Public-Key Cryptosystems: Easy and Hard Computational Problems 10.5 Do PKCS Solve the Problem of Key Distribution? 10.6 P.S. CHAPTER 11 THE KNAPSACK CRYPTOSYSTEM 11.1 Subset Sum and Knapsack Problems 11.2 Modular Arithmetic and the Euclidean Algorithm 11.3 A Modular Arithmetic Knapsack Problem 11.4 Trap-Door Knapsacks 11.5 Knapsack Encipherment and Decipherment of ASCII-Plaintext 11.6 Cryptanalysis of the Merkle–Hellman Knapsack System (Modular Mapping) 11.7 Diophantine Approximation 11.8 Short Vectors in a Lattice 11.9 Knapsack-Like Cryptosystems 11.10 Knapsack Cryptosystem Problems CHAPTER 12 THE RSA CRYPTOSYSTEM 12.1 A Short Number-Theoretic Digression 12.2 RSA 12.3 The RSA Encipherment and Decipherment of ASCII-Plaintext 12.4 Attack on RSA 12.5 Williams Variation of RSA 12.6 Multiprecision Modular Arithmetic CHAPTER 13 PRIME NUMBERS AND FACTORIZATION 13.1 Number Theory and Cryptography 13.2 Prime Numbers and the Sieve of Eratosthenes 13.3 Pollard’s p – 1 Method 13.4 Pollard’s r-Algorithm 13.5 Quadratic Residues 13.6 Random Factorization 13.7 The Quadratic Sieve (QS) 13.8 Testing if an Integer is a Prime 13.9 The RSA Challenge 13.10 Perfect Numbers and the Mersenne Primes 13.11 Multiprecision Arithmetic 13.12 Prime Number Testing and Factorization Problems CHAPTER 14 THE DISCRETE LOGARITHM PROBLEM 14.1 The Discrete Logarithm Problem Modulo p 14.2 Solution of the DLP Modulo p Given a Factorization of p – 1 14.3 Adelman’s Subexponential Algorithm for the Discrete Logarithm Problem 14.4 The Baby-Step, Giant-Step Algorithm 14.5 The Index-Calculus Method 14.6 Pollard’s r-Algorithm 14.7 Extension Fields 14.8 The Current State of Discrete Logarithm Research CHAPTER 15 ELLIPTIC CURVE CRYPTOGRAPHY 15.1 Elliptic Curves 15.2 The Elliptic Group over the Reals 15.3 Lenstra’s Factorization Algorithm 15.4 The Elliptic Group over Z(p) ( p > 3) 15.5 Elliptic Groups over the Field Z(m,2) 15.6 Computations in the Elliptic Group E(Z(m,2))(a, b) 15.7 Supersingular Elliptic Curves 15.8 Diffie–Hellman Key Exchange Using an Elliptic Curve 15.9 The Menezes–Vanstone Elliptic Curve Cryptosystem 15.10 The Elliptic Curve Digital Signature Algorithm 15.11 The Certicom Challenge 15.12 NSA and Elliptic Curve Cryptography CHAPTER 16 KEY EXCHANGE IN A NETWORK 16.1 Key Distribution in a Network 16.2 U.S. Patent ’770 16.3 Spoofing 16.4 El Gamal’s Extension of Diffie–Hellman 16.5 Shamir’s Autonomous Key Exchange 16.6 X9.17 Key Exchange Architecture 16.7 The Needham–Schroeder Key Distribution Protocol CHAPTER 17 DIGITAL SIGNATURES AND AUTHENTICATION 17.1 The Need for Signatures 17.2 Threats to Network Transactions 17.3 Secrecy, Digital Signatures, and Authentication 17.4 The Desiderata of a Digital Signature 17.5 Public-Key Cryptography and Signature Systems 17.6 Rabin’s Quadratic Residue Signature Protocol 17.7 Hash Functions 17.8 MD5 17.9 The Secure Hash Algorithm 17.10 NIST’s Digital Signature Algorithm 17.11 El Gamal’s Signature Protocol 17.12 The Fiat–Shamir Identification and Signature Schema 17.13 The Oblivious Transfer CHAPTER 18 APPLICATIONS OF CRYPTOGRAPHY 18.1 UNIX Password Encipherment 18.2 Magnetic Stripe Technology 18.3 Protecting ATM Transactions 18.4 Keyed-Access Cards 18.5 Smart Cards 18.6 Who Can You Trust?: Kohnfelder’s Certificates 18.7 X.509 Certificates 18.8 The Secure Socket Layer (SSL) 18.9 Making a Secure Credit Card Payment on the Web CHAPTER 19 CRYPTOGRAPHIC PATENTS 19.1 What is a Patent? 19.2 Patentability of Ideas 19.3 The Format of a Patent 19.4 Patentable versus Nonpatentable Subjects 19.5 Infringement 19.6 The Role of Patents in Cryptography 19.7 U.S. Patent 3,543,904 19.8 U.S. Patent 4,200,770 19.9 U.S. Patent 4,218,582 19.10 U.S. Patent 4,405,829 19.11 PKS/RSADSI Litigation 19.12 Leon Stambler INDEX

Gain the skills and knowledge needed to create effective data security systems

This book updates readers with all the tools, techniques, and concepts needed to understand and implement data security systems. It presents a wide range of topics for a thorough understanding of the factors that affect the efficiency of secrecy, authentication, and digital signature schema. Most importantly, readers gain hands-on experience in cryptanalysis and learn how to create effective cryptographic systems.

The author contributed to the design and analysis of the Data Encryption Standard (DES), a widely used symmetric-key encryption algorithm. His recommendations are based on firsthand experience of what does and does not work.

Thorough in its coverage, the book starts with a discussion of the history of cryptography, including a description of the basic encryption systems and many of the cipher systems used in the twentieth century. The author then discusses the theory of symmetric- and public-key cryptography. Readers not only discover what cryptography can do to protect sensitive data, but also learn the practical limitations of the technology. The book ends with two chapters that explore a wide range of cryptography applications.

Three basic types of chapters are featured to facilitate learning:

• Chapters that develop technical skills
• Chapters that describe a cryptosystem and present a method of analysis
• Chapters that describe a cryptosystem, present a method of analysis, and provide problems to test your grasp of the material and your ability to implement practical solutions

With consumers becoming increasingly wary of identity theft and companies struggling to develop safe, secure systems, this book is essential reading for professionals in e-commerce and information technology. Written by a professor who teaches cryptography, it is also ideal for students.