Thư viện tri thức trực tuyến
Kho tài liệu với 50,000+ tài liệu học thuật
© 2023 Siêu thị PDF - Kho tài liệu học thuật hàng đầu Việt Nam
Computer security and cryptography
Nội dung xem thử
Mô tả chi tiết
COMPUTER SECURITY
AND CRYPTOGRAPHY
ALAN G. KONHEIM
COMPUTER SECURITY
AND CRYPTOGRAPHY
COMPUTER SECURITY
AND CRYPTOGRAPHY
ALAN G. KONHEIM
About the Cover: The term cipher alphabet is used when referring to a monoalphabetic substitution. When text
is written using the letters A, B, ... , Z, a cipher alphabet is a permutation or rearrangement of the 26 letters.
In the fifteenth century, cryptography became more sophisticated and cryptographers proposed using multiple
cipher alphabets, a process referred to as polyalphabetic substitution. Blaise de Vigene`re’s book A Treatise on
Secret Writing published in the sixteenth century contains the basic Vigene`re tableux, specifying the ciphertext
in polyalphabetic substitution. Rotor machines introduced in the 20th-century provided mechanical means for
implementing and speeding up polyalphabetic substitution.
The cover is a modified set of 17 cipher alphabets; the black background color is symbolic of the U.S. State
Department’s Black Chamber in which American cryptanalysis originated in the early part of the 20th-century.
It is technically defective in several aspects (i) fewer than 26 letters in each row are displayed and (ii) repeated
letters occur in the rows containing the word CRYPTOGRAPHY and my name.
Nevertheless, the cover hopefully projects the message to read Computer Security and Cryptography.
Copyright # 2007 by John Wiley & Sons, Inc. All rights reserved
Published by John Wiley & Sons, Inc., Hoboken, New Jersey
Published simultaneously in Canada
No part of this publication may be reproduced, stored in a retrieval system, or transmitted in any form
or by any means, electronic, mechanical, photocopying, recording, scanning, or otherwise, except as
permitted under Section 107 or 108 of the 1976 United States Copyright Act, without either the prior
written permission of the Publisher, or authorization through payment of the appropriate per-copy fee to the
Copyright Clearance Center, Inc., 222 Rosewood Drive, Danvers, MA 01923, (978) 750-8400, fax (978)
750-4470, or on the web at www.copyright.com. Requests to the Publisher for permission should be
addressed to the Permissions Department, John Wiley & Sons, Inc., 111 River Street, Hoboken, NJ 07030,
(201) 748-6011, fax (201) 748-6008, or online at http://www.wiley.com/go/permission.
Limit of Liability/Disclaimer of Warranty: While the publisher and author have used their best efforts in
preparing this book, they make no representations or warranties with respect to the accuracy or
completeness of the contents of this book and specifically disclaim any implied warranties of
merchantability or fitness for a particular purpose. No warranty may be created or extended by sales
representatives or written sales materials. The advice and strategies contained herein may not be suitable
for your situation. You should consult with a professional where appropriate. Neither the publisher nor
author shall be liable for any loss of profit or any other commercial damages, including but not limited to
special, incidental, consequential, or other damages.
For general information on our other products and services or for technical support, please contact our
Customer Care Department within the United States at (800) 762-2974, outside the United States at (317)
572-3993 or fax (317) 572-4002.
Wiley also publishes its books in a variety of electronic formats. Some content that appears in print may
not be available in electronic formats. For more information about Wiley products, visit our web site at
www.wiley.com.
Library of Congress Cataloging-in-Publication Data:
Konheim, Alan G., 1934–
Computer security & cryptography / by Alan G. Konheim.
p. cm.
Includes bibliographical references and index.
ISBN-13: 978-0-471-94783-7
ISBN-10: 0-471-94783-0
1. Computer security. 2. Cryptography. I. Title.
QA76.9.A25K638 2007
005.8--dc22 2006049338
Printed in the United States of America
10 9 8 7 6 5 4 3 2 1
CONTENTS
FOREWORD ix
PREFACE xi
ABOUT THE AUTHOR xvii
CHAPTER 1 APERITIFS
1.1 The Lexicon of Cryptography 1
1.2 Cryptographic Systems 4
1.3 Cryptanalysis 4
1.4 Side Information 6
1.5 Thomas Jefferson and the M-94 6
1.6 Cryptography and History 7
1.7 Cryptography and Computers 8
1.8 The National Security Agency 9
1.9 The Giants 10
1.10 No Sex, Money, Crime or ... Love 12
1.11 An Example of the Inference Process
in Cryptanalysis 13
1.12 Warning! 15
CHAPTER 2 COLUMNAR TRANSPOSITION
2.1 Shannon’s Classification of Secrecy
Transformations 18
2.2 The Rules of Columnar Transposition
Encipherment 18
2.3 Cribbing 21
2.4 Examples of Cribbing 25
2.5 Plaintext Language Models 30
2.6 Counting k-Grams 33
2.7 Deriving the Parameters of a Markov
Model from Sliding Window Counts 34
2.8 Markov Scoring 34
2.9 The ADFGVX Transposition System 47
2.10 CODA 49
2.11 Columnar Transposition Problems 50
CHAPTER 3 MONOALPHABETIC
SUBSTITUTION
3.1 Monoalphabetic Substitution 63
3.2 Caesar’s Cipher 65
3.3 Cribbing Using Isomorphs 66
3.4 The x2
-Test of a Hypothesis 67
3.5 Pruning from the Table of Isomorphs 68
3.6 Partial Maximum Likelihood Estimation
of a Monoalphabetic Substitution 73
3.7 The Hidden Markov Model (HMM) 78
3.8 Hill Encipherment of ASCII N-Grams 90
3.9 Gaussian Elimination 102
3.10 Monoalphabetic Substitution Problems 111
CHAPTER 4 POLYALPHABETIC
SUBSTITUTION
4.1 Running Keys 116
4.2 Blaise de Vigene`re 117
4.3 Gilbert S. Vernam 117
4.4 The One-Time Pad 119
4.5 Finding the Key of Vernam –Vigene`re
Ciphertext with Known Period by
Correlation 120
4.6 Coincidence 124
4.7 Venona 127
4.8 Polyalphabetic Substitution
Problems 132
CHAPTER 5 STATISTICAL TESTS
5.1 Weaknesses in a Cryptosystem 136
5.2 The Kolmogorov–Smirnov Test 136
5.3 NIST’s Proposed Statistical Tests 138
5.4 Diagnosis 139
5.5 Statistical Tests Problems 143
CHAPTER 6 THE EMERGENCE OF CIPHER
MACHINES
6.1 The Rotor 150
6.2 Rotor Systems 152
6.3 Rotor Patents 153
6.4 A Characteristic Property of Conjugacy 155
6.5 Analysis of a 1-Rotor System:
Ciphertext Only 156
6.6 The Displacement Sequence of a
Permutation 158
6.7 Arthur Scherbius 160
v
6.8 Enigma Key Distribution Protocol 163
6.9 Cryptanalysis of the Enigma 166
6.10 Cribbing Enigma Ciphertext 167
6.11 The Lorenz Schlu¨sselzusatz 170
6.12 The SZ40 Pin Wheels 171
6.13 SZ40 Cryptanalysis Problems 175
6.14 Cribbing SZ40 Ciphertext 176
CHAPTER 7 THE JAPANESE CIPHER
MACHINES
7.1 Japanese Signaling Conventions 191
7.2 Half-Rotors 191
7.3 Components of the RED Machine 193
7.4 Cribbing RED Ciphertext 200
7.5 Generalized Vowels and Consonants 209
7.6 “Climb Mount Itaka” – War! 210
7.7 Components of the PURPLE Machine 211
7.8 The PURPLE Keys 217
7.9 Cribbing PURPLE: Finding the V-Stepper 219
7.10 Cribbing PURPLE: Finding the
C-Steppers 238
CHAPTER 8 STREAM CIPHERS
8.1 Stream Ciphers 244
8.2 Feedback Shift Registers 244
8.3 The Algebra of Polynomials over Z2 247
8.4 The Characteristic Polynomial of a
Linear Feedback Shift Register 251
8.5 Properties of Maximal Length LFSR
Sequences 254
8.6 Linear Equivalence 258
8.7 Combining Multiple Linear Feedback
Shift Registers 259
8.8 Matrix Representation of the LFSR 260
8.9 Cribbing of Stream Enciphered ASCII
Plaintext 261
8.10 Nonlinear Feedback Shift Registers 271
8.11 Nonlinear Key Stream Generation 273
8.12 Irregular Clocking 275
8.13 RC4 278
8.14 Stream Encipherment Problems 281
CHAPTER 9 BLOCK-CIPHERS: LUCIFER,
DES, AND AES
9.1 LUCIFER 283
9.2 DES 288
9.3 The DES S-Boxes, P-Box, and Initial
Permutation (IP) 289
9.4 DES Key Schedule 292
9.5 Sample DES Encipherment 294
9.6 Chaining 295
9.7 Is DES a Random Mapping? 297
9.8 DES in the Output-Feedback Mode (OFB) 299
9.9 Cryptanalysis of DES 300
9.10 Differential Cryptanalysis 302
9.11 The EFS DES-Cracker 308
9.12 What Now? 311
9.13 The Future Advanced Data Encryption
Standard 312
9.14 And the Winner Is! 312
9.15 The Rijndael Operations 314
9.16 The Rijndael Cipher 323
9.17 Rijndael’s Strength: Propagation of
Patterns 323
9.18 When is a Product Block-Cipher Secure? 326
9.19 Generating the Symmetric Group 327
9.20 A Class of Block Ciphers 329
9.21 The IDEA Block Cipher 332
CHAPTER 10 THE PARADIGM OF
PUBLIC KEY CRYPTOGRAPHY
10.1 In the Beginning... 334
10.2 Key Distribution 335
10.3 E-Commerce 336
10.4 Public-Key Cryptosystems:
Easy and Hard Computational Problems 337
10.5 Do PKCS Solve the Problem
of Key Distribution? 341
10.6 P.S. 342
CHAPTER 11 THE KNAPSACK
CRYPTOSYSTEM
11.1 Subset Sum and Knapsack Problems 344
11.2 Modular Arithmetic and
the Euclidean Algorithm 346
11.3 A Modular Arithmetic
Knapsack Problem 350
11.4 Trap-Door Knapsacks 350
11.5 Knapsack Encipherment and
Decipherment of ASCII-Plaintext 355
11.6 Cryptanalysis of the Merkle–Hellman
Knapsack System (Modular Mapping) 358
11.7 Diophantine Approximation 364
11.8 Short Vectors in a Lattice 368
11.9 Knapsack-Like Cryptosystems 371
11.10 Knapsack Cryptosystem Problems 371
CHAPTER 12 THE RSA CRYPTOSYSTEM
12.1 A Short Number-Theoretic Digression 376
12.2 RSA 378
12.3 The RSA Encipherment and
Decipherment of ASCII-Plaintext 379
vi CONTENTS
12.4 Attack on RSA 382
12.5 Williams Variation of RSA 383
12.6 Multiprecision Modular Arithmetic 387
CHAPTER 13 PRIME NUMBERS AND
FACTORIZATION
13.1 Number Theory and Cryptography 390
13.2 Prime Numbers and the Sieve of
Eratosthenes 390
13.3 Pollard’s p 2 1 Method 391
13.4 Pollard’s r-Algorithm 394
13.5 Quadratic Residues 396
13.6 Random Factorization 401
13.7 The Quadratic Sieve (QS) 403
13.8 Testing if an Integer is a Prime 405
13.9 The RSA Challenge 407
13.10 Perfect Numbers and the
Mersenne Primes 408
13.11 Multiprecision Arithmetic 409
13.12 Prime Number Testing and
Factorization Problems 410
CHAPTER 14 THE DISCRETE LOGARITHM
PROBLEM
14.1 The Discrete Logarithm Problem
Modulo p 414
14.2 Solution of the DLP Modulo p Given a
Factorization of p 2 1 415
14.3 Adelman’s Subexponential Algorithm
for the Discrete Logarithm Problem 419
14.4 The Baby-Step, Giant-Step
Algorithm 420
14.5 The Index-Calculus Method 420
14.6 Pollard’s r-Algorithm 424
14.7 Extension Fields 426
14.8 The Current State of Discrete
Logarithm Research 428
CHAPTER 15 ELLIPTIC CURVE CRYPTOGRAPHY
15.1 Elliptic Curves 429
15.2 The Elliptic Group over the Reals 431
15.3 Lenstra’s Factorization Algorithm 432
15.4 The Elliptic Group over Zp ( p . 3) 434
15.5 Elliptic Groups over the Field Zm,2 436
15.6 Computations in the Elliptic Group
EZm,2(a, b) 438
15.7 Supersingular Elliptic Curves 441
15.8 Diffie –Hellman Key Exchange Using
an Elliptic Curve 442
15.9 The Menezes –Vanstone Elliptic
Curve Cryptosystem 443
15.10 The Elliptic Curve Digital Signature
Algorithm 444
15.11 The Certicom Challenge 445
15.12 NSA and Elliptic Curve Cryptography 445
CHAPTER 16 KEY EXCHANGE IN A NETWORK
16.1 Key Distribution in a Network 447
16.2 U.S. Patent ’770 448
16.3 Spoofing 448
16.4 El Gamal’s Extension of
Diffie–Hellman 450
16.5 Shamir’s Autonomous Key Exchange 451
16.6 X9.17 Key Exchange Architecture 453
16.7 The Needham–Schroeder Key
Distribution Protocol 456
CHAPTER 17 DIGITAL SIGNATURES AND
AUTHENTICATION
17.1 The Need for Signatures 464
17.2 Threats to Network Transactions 465
17.3 Secrecy, Digital Signatures, and
Authentication 465
17.4 The Desiderata of a Digital
Signature 466
17.5 Public-Key Cryptography and
Signature Systems 467
17.6 Rabin’s Quadratic Residue
Signature Protocol 468
17.7 Hash Functions 470
17.8 MD5 471
17.9 The Secure Hash Algorithm 473
17.10 NIST’s Digital Signature
Algorithm 474
17.11 El Gamal’s Signature Protocol 475
17.12 The Fiat –Shamir Identification and
Signature Schema 476
17.13 The Oblivious Transfer 478
CHAPTER 18 APPLICATIONS OF
CRYPTOGRAPHY
18.1 UNIX Password Encipherment 480
18.2 Magnetic Stripe Technology 482
18.3 Protecting ATM Transactions 484
18.4 Keyed-Access Cards 491
18.5 Smart Cards 491
18.6 Who Can You Trust?: Kohnfelder’s
Certificates 495
18.7 X.509 Certificates 495
18.8 The Secure Socket Layer (SSL) 497
18.9 Making a Secure Credit Card
Payment on the Web 502
CONTENTS vii
CHAPTER 19 CRYPTOGRAPHIC
PATENTS
19.1 What is a Patent? 506
19.2 Patentability of Ideas 507
19.3 The Format of a Patent 507
19.4 Patentable versus Nonpatentable
Subjects 508
19.5 Infringement 509
19.6 The Role of Patents in
Cryptography 509
19.7 U.S. Patent 3,543,904 509
19.8 U.S. Patent 4,200,770 511
19.9 U.S. Patent 4,218,582 512
19.10 U.S. Patent 4,405,829 512
19.11 PKS/RSADSI Litigation 514
19.12 Leon Stambler 514
INDEX 516
viii CONTENTS
FOREWORD
It’s not easy being a writer on cryptology. Actually, it’s not easy being a writer. You
have to think about what subjects you want to cover. Then you have to decide in what
order you want to put them—not so simple, because the most logical progression isn’t
always the best for teaching. Then comes the worst part: You actually have to cover a
blank screen or sheet of paper with letters and figures that make sense.
Alan Konheim has sweated through it many times. He has written a number of technical articles, which demonstrates that he has mastered the technicalities of his subject.
And he has passed through the fire of book authorship once before, in his acclaimed Cryptography: A Primer. In the years that followed, he has learned what worked in that book
and what didn’t, and has applied those lessons in the present work. The result is a fine
amalgam of scholarship and pedagogy.
But if the elements of writing—clarity and concision—have remained the same,
cryptology has not. For centuries, it was axiomatic that both en- and decipherer had to
have the same key, though used inversely. The invention of public-key cryptography abolished that axiom. It has transformed and energized the practical applications of cryptography. Many of these remain grounded in the classical, or symmetric, systems of
cryptography. And the enormous expansion of communications has driven its child,
secret communications, into vast new fields. Once the exclusive domain of soldiers and diplomats and spies, cryptology has become almost ubiquitous. People use it without knowing
that they are doing so. Every time a person uses an automatic teller machine, his or her transaction is encrypted. So are online bank transactions. Whenever anyone sends his or her
credit card number securely to, say, E-bay or Amazon, he or she is using cryptography.
And the field has emerged from the shadows, The National Security Agency, once so
secret that it was referred to as “No Such Agency,” is now mentioned in movies and on the
evening news almost without any identification, just as the CIA and FBI are. The post-9/
11 flap over the Bush administration’s warrantless wiretapping has further brought cryptology, the NSA, and privacy into the open. The International Association for Cryptologic
Research publishes its Journal of Cryptology four times a year. The aura of mysticism that
long enshrouded it has been dispelled by the cold logic of mathematics that now dominates it.
Alan Konheim knows all about this because he worked for IBM when it was a leader
in the field of cryptology and because he has kept up with new developments, as his many
technical articles demonstrate. His experience in teaching tells him what questions
students are likely to ask and what problems in understanding they are likely to encounter.
His previous book has taught him how to explain complicated matters effectively.
The result is this excellent book, which joins the permanent qualities of its writing
to the immediacy of its coverage. Cryptologists—beginners and veterans alike—will
welcome it. As do I.
Long Island, NewYork DAVID KAHN
October 2006
ix
PREFACE
NATIONAL SECURITY AND COMPUTER SECURITY
On September 11, 2001, the word security moved into the foreground of our national consciousness, where it continues to reside today. The presidential election in 2004 was
largely decided on the basis of which candidate was perceived to best manage
security for the American people. Americans are puzzled about the hatred expressed by
certain ideologies and foreign governments about our way of life and culture. The
missions of the National Security Agency/Central Security Service (CSS) include
both the protection of U.S. communications and the production of foreign intelligence.
Although cryptography plays a role in both of these areas, this book is not about either.
This book is about the role of cryptography in our day-to-day lives. Today, there is
no activity that does not depend on computers. When there is a power outage in
Santa Barbara, I often cannot buy Twinkies at the supermarket, to my dismay and that
of the merchant, but to the delight of my endocrinologist. The use of traveler’s checks
has declined because of the convenience and availability of ATM machines. Vast
amounts of data are maintained by banks and credit card companies. Stories of their
mismanaging customer data appear regularly in the news. Identity theft is well on its
way to becoming a flourishing industry. Credit card companies now have the nerve to
advertise identity theft insurance to protect the information that they are legally obliged
to guard, but fail to do so.
Cryptography has a role to play in many areas. Like seat belts, it will not completely
protect us. In the chapters that follow, I will develop the basic ideas about cryptography
and then illustrate some of the ways it interacts with and protects us.
WHY STUDY CRYPTOGRAPHY?
There is a symbiotic relationship between cryptography and the development of highperformance computing systems. Modern-day computers were created at the behest of
twentieth-century cryptanalysts. As the complexity of cryptographic systems progressed
from mechanical to electronic systems, so did the need to develop more efficient
methods to cryptanalyze them.
Every cryptosystem, which has a finite number of keys, can usually be analyzed
by key trial, deciphering the ciphertext with all possible keys until some recognizable
text appears. In many “classical” cryptographic systems, the testing of keys could be
performed by hand. The stimulus for the development of computers was the need to be
able to test large sets of possible keys to decipher coded traffic. Modern cryptosystems
are such that the number of possible keys is generally so large as to make exhaustive
key trial infeasible. Even computers are limited, and some analysis must precede key
testing for the process to be successful.
xi
The marriage of computing and cryptography provides a marvelous real-life
application of mathematics, and develops the inference skills that are fundamental to
engineering and science. When a student first views the ciphertext
To-drijohrunurmanpmlgchd-ehapuotp,te-nmabsno-nitioippmbo-a-a
sTasm-h-op-ms-vye-m.ikndu-n-atscegnetoin-l-rs-v-e-u-ta-olati
s-t-sccw——eorrgdhgngP.r-stenvercenhnerhchoie-nun-sr-tois-rma
eaeeadadrssou-o-etat-iefeotifc-m-a——ergua-eiuo-oixeordalmyes
there may be confusion. Word fragments may be detected, but how can the text be recovered? After students learn to critically examine the ciphertext, they are often capable of
deciphering it. Cryptography teaches students how clever they can be. Of course, instructors should caution their students as the television commercials for ED advise; to wit, if
their efforts in cryptanalyzing some ciphertext “last more than four hours, they should
seek tutorial assistance.”
Although computer security is certainly a hot topic today, its public discussion is often
accompanied by a great deal of hype. People are impressed by cryptosystems with large key
spaces and the press releases make liberal use of the term unbreakable. The Kryha machine,
a mechanical ciphering machine invented in 1924, had more than 4.57 1050 keys, but it
did not offer much secrecy protection. Invoking the lore of large numbers to “prove” the
strength of an encipherment scheme often fails to measure the real strength.
This book will provide the tools for understanding the central issues in data security.
It will provide an instructor with a wide range of topics to train students to evaluate
critically the factors that affect the effectiveness of secrecy, authentication, and digital
signature schema, sensitize a student to some of the factors that determine the strength
of an algorithm and its protocol implementations, and provide hands-on experience to
the student with cryptanalysis.
The book’s goal is to explain the nature of secrecy and the “practical” limitations of
cryptography in providing secrecy and its derivatives (authentication and digital
signatures).
MY PRIOR ART
Parts of Computer Security and Cryptography have served as the text for CMPSC 178
(Introduction to Cryptography) at UCSB. It is an upper-division elective in the undergraduate program of the Computer Science Department of the University of California
(Santa Barbara) from 1983 to 2005. CMPSC 178 is ten-week four-unit course, meeting
75 minutes twice weekly. Class lectures are supplemented by a Discussion Section
conducted by a Teaching Assistant. CMPSC 178 is usually taken in the Junior or
Senior year by students from the Departments of Computer Science, Electrical and
Computer Engineering, and Mathematics. The prerequisites are CMPSC 10 (a Java
programming language course), and PSTAT 120A or 121A (an entry-level course in
probability and statistics).
Eight or nine homework assignments require students to write programs to carry out
the cryptanalysis of various cryptosystems and various exercises related to other cryptologic topics. Although in class I hand out a hard copy of the assignments containing the
ciphertext, the nature of ciphertext requires the students to copy the ciphertext files
from my Web page. The same procedure will be followed with Computer Security and
Cryptography; the ciphertext for the exercises may be downloaded from Wiley’s ftpsite at ftp://ftp.wiley.com/public/sci_tech_med/computer_security.
xii PREFACE