HANDBOOK of
`
`APPLIED
`
`CRYPTOGRAPHY
`
`Alfred J. Menezes
`
`Paul C. van Oorschot
`
`Scott A. Vanstone
`
`Apple 1 135
`
`Apple V. USR
`IPR2018-00809
`
`Apple 1135
`Apple v. USR
`IPR2018-00809
`
`

`

`Foreword
`
`by R.L. Rivest
`
`As we draw near to closing out the twentieth century, we see quite clearly that the
`information-processing and telecommunications revolutions now underway will
`continue vigorously into the twenty-first. We interact and transact by directing flocks
`of digital packets towards each other through cyberspace, carrying love notes, digital
`cash, and secret corporate documents. Our personal and economic lives rely more and
`more on our ability to let such ethereal carrier pigeons mediate at a distance what we
`used to do with face-to-face meetings, paper documents, and a firm handshake.
`Unfortunately, the technical wizardry enabling remote collaborations is founded on
`broadcasting everything as sequences of zeros and ones that one's own dog wouldn't
`recognize. What is to distinguish a digital dollar when it is as easily reproducible as the
`spoken word? How do we converse privately when every syllable is bounced off a
`satellite and smeared over an entire continent? How should a bank know that it really is
`Bill Gates requesting fiom his laptop in Fiji a transfer of $10,000,000,000 to another
`bank? Fortunately, the magical mathematics of cryptography can help. Cryptography
`provides techniques for keeping information secret, for determining that information
`has not been tampered with, and for determining who authored pieces of information.
`
`Cryptography is fascinating because of the close ties it forges between theory and
`practice, and because today's practical applications of cryptography are pervasive and
`critical components of our information-based society. Inforrnation—protection protocols
`designed on theoretical foundations one year appear in products and standards
`documents the next. Conversely, new theoretical developments sometimes mean that
`last year's proposal has a previously unsuspected weakness. While the theory is
`advancing vigorously, there are as yet few true guarantees; the security of many
`proposals depends on unproven (if plausible) assumptions. The theoretical work refines
`and improves the practice, while the practice challenges and inspires the theoretical
`work. When a system is "broken," our knowledge improves, and next year's system is
`improved to repair the defect. (One is reminded of the long and intriguing battle
`between the designers of bank vaults and their opponents.)
`
`Cryptography is also fascinating because of its game-like adversarial nature. A good
`cryptographer rapidly changes sides back and forth in his or her thinking, from attacker
`to defender and back. Just as in a game of chess, sequences of moves and counter-
`moves must be considered until the current situation is understood. Unlike chess
`
`players, cryptographers must also consider all the ways an adversary might try to gain
`by breaking the rules or violating expectations. (Does it matter if she measures how
`long I am computing? Does it matter if her "random" number isn't one?)
`
`The current volume is a major contribution to the field of cryptography. It is a rigorous
`encyclopedia of known techniques, with an emphasis on those that are both (believed to
`be) secure and practically useful. It presents in a coherent manner most of the important
`cryptographic tools one needs to implement secure cryptographic systems, and explains
`many of the cryptographic principles and protocols of existing systems. The topics
`covered range fiom low-level considerations such as random-number generation and
`efficient modular exponentiation algorithms and medium-level items such as public-
`key signature techniques, to higher-level topics such as zero-knowledge protocols. This
`
`ii
`
`

`

`book's excellent organization and style allow it to serve well as both a self-contained
`tutorial and an indispensable desk reference.
`
`In documenting the state of a fast-moving field, the authors have done incredibly well
`at providing error-free comprehensive content that is up-to-date. Indeed, many of the
`chapters, such as those on hash fiJnctions or key-establishment protocols, break new
`ground in both their content and their unified presentations. In the trade-off between
`comprehensive coverage and exhaustive treatment of individual items, the authors have
`chosen to write simply and directly, and thus eff1ciently, allowing each element to be
`explained together with their important details, caveats, and comparisons.
`
`While motivated by practical applications, the authors have clearly written a book that
`will be of as much interest to researchers and students as it is to practitioners, by
`including ample discussion of the underlying mathematics and associated theoretical
`considerations. The essential mathematical techniques and requisite notions are
`presented crisply and clearly, with illustrative examples. The insightfill historical notes
`and extensive bibliography make this book a superb stepping-stone to the literature. (I
`was very pleasantly surprised to find an appendix with complete programs for the
`CRYPTO and EUROCRYPT conferences!)
`
`It is a pleasure to have been asked to provide the foreword for this book. I am happy to
`congratulate the authors on their accomplishment, and to inform the reader that he/she
`is looking at a landmark in the development of the field.
`
`Ronald L. Rivest
`
`Webster Professor of Electrical Engineering and Computer Science
`Massachusetts Institute of Technology
`June 1996
`
`iii
`
`

`

`Preface
`
`This book is intended as a reference for professional cryptographers, presenting the
`techniques and algorithms of greatest interest to the current practitioner, along with the sup-
`
`porting motivation and background material. It also provides a comprehensive source from
`which to learn cryptography, serving both students and instructors. In addition, the rigor-
`
`ous treatment, breadth, and extensive bibliographic material should make it an important
`reference for research professionals.
`Our goal was to assimilate the existing cryptographic knowledge of industrial interest
`
`into one consistent, self—contained volume accessible to engineers in practice, to computer
`scientists and mathematicians in academia, and to motivated non-specialists with a strong
`
`desire to learn cryptography. Such a task is beyond the scope of each of the following: re—
`search papers, which by nature focus on narrow topics using very specialized (and often
`
`non-standard) terminology; survey papers, which typically address, at most, a small num-
`ber of major topics at a high level; and (regretably also) most books, due to the fact that
`many book authors lack either practical experience or familiarity with the research litera-
`ture or both. Our intent was to provide a detailed presentation of those areas of cryptogra-
`phy which we have found to be of greatest practical utility in our own industrial experience,
`
`while maintaining a sufliciently formal approach to be suitable both as a trustworthy refer—
`ence for those whose primary interest is further research, and to provide a solid foundation
`
`for students and others first learning the subject.
`Throughout each chapter, we emphasize the relationship between various aspects of
`
`cryptography. Background sections commence most chapters, providing a framework and
`perspective for the techniques which follow. Computer source code (e. g. C code) for algo—
`
`rithms has been intentionally omitted, in favor of algorithms specified in suflicient detail to
`allow direct implementation without consulting secondary references. We believe this style
`ofpresentation allows a better understanding of how algorithms actually work, while at the
`
`same time avoiding low—level implementation-specific constructs (which some readers will
`invariably be unfamiliar with) of various currently-popular programming languages.
`
`The presentation also strongly delineates what has been established as fact (by math-
`ematical arguments) from what is simply current conjecture. To avoid obscuring the very
`
`applied nature of the subject, rigorous proofs ofcorrectness are in most cases omitted; how—
`ever, references given in the Notes section at the end of each chapter indicate the original
`
`or recommended sources for these results. The trailing Notes sections also provide infor—
`mation (quite detailed in places) on various additional techniques not addressed in the main
`text, and provide a survey of research activities and theoretical results; references again in-
`
`dicate where readers may pursue particular aspects in greater depth. Needless to say, many
`results, and indeed some entire research areas, have been given far less attention than they
`
`warrant, or have been omitted entirely due to lack of space; we apologize in advance for
`such major omissions, and hope that the most significant of these are brought to our atten-
`tion.
`
`To provide an integrated treatment of cryptography spanning foundational motivation
`through concrete implementation, it is useful to consider a hierarchy of thought ranging
`
`from conceptual ideas and end—user services, down to the tools necessary to complete ac—
`tual implementations. Table 1 depicts the hierarchical structure around which this book is
`
`organized. Corresponding to this, Figure 1 illustrates how these hierarchical levels map
`
`xxiii
`
`

`

`XXiv
`
`Preface
`
`
`Information Security Objectives
`
`Confidentiality
`Data integrity
`Authentication (entity and data origin)
`Non—repudiation
`
`Cryptographic functions
`
`Chapters 6, 7, 8
`Encryption
`Message authentication and data integrity techniques Chapter 9
`Identification/entity authentication techniques
`Chapter 10
`Digital signatures
`Chapter 11
`
`Cryptographic building blocks
`
`Chapter 6
`Stream ciphers
`Chapter 7
`Block ciphers (symmetric—key)
`Chapter 8
`Public—key encryption
`Chapter 9
`One—way hash functions (unkeyed)
`Message authentication codes
`Chapter 9
`
`Signature schemes (public—key, symmetric—key)
`Chapter 11
`Utilities
`
`
`
`
`
`Chapter 4
`Public—key parameter generation
`Chapter 5
`Pseudorandom bit generation
`Eflicient algorithms for discrete arithmetic
`Chapter 14
`
`Foundations
`
`Chapter 1
`Introduction to cryptography
`Mathematical background
`Chapter 2
`
`Complexity and analysis of underlying problems
`Chapter 3
`
`Infrastructure techniques and commercial aspects
`Key establishment protocols
`Chapter 12
`Key installation and key management
`Chapter 13
`Cryptographic patents
`Chapter 15
`
`Cryptographic standards
`Chapter 15
`
`Table 1: Hierarchical levels ofapplied cryptography.
`
`onto the various chapters, and their inter—dependence.
`Table 2 lists the chapters of the book, along with the primary author(s) of each who
`should be contacted by readers with comments on specific chapters. Each chapter was writ-
`ten to provide a self-contained treatment of one major topic. Collectively, however, the
`chapters have been designed and carefully integrated to be entirely complementary with
`
`respect to definitions, terminology, and notation. Furthermore, there is essentially no du-
`plication of material across chapters; instead, appropriate cross—chapter references are pro—
`vided where relevant.
`
`While it is not intended that this book be read linearly from front to back, the material
`has been arranged so that doing so has some merit. Two primary goals motivated by the
`
`“handbook” nature ofthis project were to allow easy access to stand—alone results, and to al—
`low results and algorithms to be easily referenced (e. g., for discussion or subsequent cross—
`
`reference). To facilitate the ease of accessing and referencing results, items have been cate—
`gorized and numbered to a large extent, with the following classes ofitems j ointly numbered
`
`consecutively in each chapter: Definitions, Examples, Facts, Notes, Remarks, Algorithms,
`Protocols, and Mechanisms. In more traditional treatments, Facts are usually identified as
`
`propositions, lemmas, or theorems. We use numbered Notes for additional technical points,
`
`

`

`Preface
`
`XXV
`
`2.5925
`
`fl5926
`
`gmxéEmEEivA>mx.o__n:&3965333:3$3.232:2.5925a3:725a3:725w.5925bhot—«:0oSEED
`
`
`
`
`>Emzcmbccoo
`8:88.55ENEvcm3:98
`
`wcozwvcze328$cozficoeoaé
`
`5:233E283
`
`9.39303EmEmmmcmE>3wEmucmfi
`
`Nhot—«:02.59302hot—«:0
`
`cozmfisaeéo:
`
`cozmozcmfism
`
`£595Emu
`
`
`
`MMEOHQNSOOMEOHQNSO
`
`aE926a59:6
`
`
`
`mQEmcgmcozmoEEoEcozmozcmfism
`55632$me
`
`£395Emu
`
`moscEcoE
`
`cozabocm
`
`as.ȣ2.35
`
`
`
`mohamcgwwoSficQw
`
`
`
`wcozocacwm;
`
`
`
`wcozocacwm;
`
`83380
`
`20:20x83
`
`gmxéEmEEiv
`
`
`
`9936Emwbm
`
`
`
`$57233Eoucmh
`
`.6382:
`
`mhwwwESma|cozmhwcwm
`
`v5.55m5.35
`
`mhot—«:0N“SEE—U
`
`w>ox68$8Ewecgafiwo
`
`Ehot—«:0
`
`Figure 1
`
`Roadmap ofthe book.
`
`

`

`xxvi
`
`Preface
`
`
`Chapter
`Primary Author
`
`AJM PVO SAV
`
`1. Overview of Cryptography
`
`2. Mathematical Background
`3. Number—Theoretic Reference Problems
`
`4.
`5.
`
`Public-Key Parameters
`Pseudorandom Bits and Sequences
`
`Stream Ciphers
`6.
`7. Block Ciphers
`
`Public—Key Encryption
`8.
`9. Hash Functions and Data Integrity
`10.
`Identification and Entity Authentication
`
`*
`
`*
`*
`
`*
`*
`
`*
`
`*
`
`1 1. Digital Signatures
`12. Key Establishment Protocols
`
`13. Key Management Techniques
`14.
`Efficient Implementation
`15.
`Patents and Standards
`
`*
`
`*
`
`*
`
`*
`
`*
`
`*
`
`*
`
`*
`
`*
`
`*
`
`*
`
`— Overall organization
`
`*
`
`Table 2: Primary authors ofeach chapter.
`
`while numbered Remarks identify non—technical (ofien non—rigorous) comments, observa—
`tions, and opinions. Algorithms, Protocols and Mechanisms refer to techniques involving
`
`a series of steps. Examples, Notes, and Remarks generally begin with parenthetical sum-
`mary titles to allow faster access, by indicating the nature of the content so that the entire
`
`item itself need not be read in order to determine this. The use of a large number of small
`subsections is also intended to enhance the handbook nature and accessibility to results.
`Regarding the partitioning of subject areas into chapters, we have used what we call a
`functional organization (based on functions of interest to end—users). For example, all items
`
`related to entity authentication are addressed in one chapter. An alternative would have been
`what may be called an academic organization, under which perhaps, all protocols based on
`
`zero—knowledge concepts (including both a subset of entity authentication protocols and
`signature schemes) might be covered in one chapter. We believe that a functional organi-
`zation is more convenient to the practitioner, who is more likely to be interested in options
`
`available for an entity authentication protocol (Chapter 10) or a signature scheme (Chapter
`11), than to be seeking a zero—knowledge protocol with unspecified end—purpose.
`
`In the front matter, a top-level Table of Contents (giving chapter numbers and titles
`only) is provided, as well as a detailed Table of Contents (down to the level of subsections,
`e. g., §5.1.1). This is followed by a List of Figures, and a List of Tables. At the start of each
`chapter, a brief Table of Contents (specifying section number and titles only, e. g., §5. 1, §5 .2)
`
`is also given for convenience.
`At the end ofthe book, we have included a list ofpapers presented at each of the Crypto,
`Eurocrypt, Asiacrypt/Auscrypt and Fast Software Encryption conferences to date, as well
`as a list of all papers published in the Journal of Cryptology up to Volume 9. These are
`in addition to the References section, each entry of which is cited at least once in the body
`of the handbook. Almost all of these references have been verified for correctness in their
`
`exact titles, volume and page numbers, etc. Finally, an extensive Index prepared by the
`
`authors is included. The Index begins with a List of Symbols.
`Our intention was not to introduce a collection of new techniques and protocols, but
`
`

`

`Preface
`
`XXVii
`
`rather to selectively present techniques from those currently available in the public domain.
`Such a consolidation of the literature is necessary from time to time. The fact that many
`
`good books in this field include essentially no more than what is covered here in Chapters
`7, 8 and 11 (indeed, these might serve as an introductory course along with Chapter 1) illus—
`
`trates that the field has grown tremendously in the past 15 years. The mathematical foun-
`dation presented in Chapters 2 and 3 is hard to find in one volume, and missing from most
`cryptography texts. The material in Chapter 4 on generation of public-key parameters, and
`
`in Chapter 14 on eflicient implementations, while well-known to a small body of specialists
`and available in the scattered literature, has previously not been available in general texts.
`
`The material in Chapters 5 and 6 on pseudorandom number generation and stream ciphers
`is also ofien absent (many texts focus entirely on block ciphers), or approached only from
`a theoretical viewpoint. Hash functions (Chapter 9) and identification protocols (Chapter
`10) have only recently been studied in depth as specialized topics on their own, and along
`
`with Chapter 12 on key establishment protocols, it is hard to find consolidated treatments
`of these now-mainstream topics. Key management techniques as presented in Chapter 13
`have traditionally not been given much attention by cryptographers, but are of great impor-
`
`tance in practice. A focused treatment of cryptographic patents and a concise summary of
`cryptographic standards, as presented in Chapter 15, are also long overdue.
`
`In most cases (with some historical exceptions), where algorithms are known to be in-
`secure, we have chosen to leave out specification of their details, because most such tech-
`
`niques are of little practical interest. Essentially all of the algorithms included have been
`verified for correctness by independent implementation, confirming the test vectors speci—
`fied.
`
`Acknowledgements
`
`This project would not have been possible without the tremendous efforts put forth by our
`peers who have taken the time to read endless drafis and provide us with technical correc—
`tions, constructive feedback, and countless suggestions. In particular, the advice of our Ad—
`
`visory Editors has been invaluable, and it is impossible to attribute individual credit for their
`many suggestions throughout this book. Among our Advisory Editors, we would particu—
`
`larly like to thank:
`
`Mihir Bellare
`
`Don Coppersmith
`
`Dorothy Denning Walter Fumy
`
`Burt Kaliski
`Chris Mitchell
`
`Peter Landrock
`Tatsuaki Okamoto
`
`Arj en Lenstra
`Bart Preneel
`
`Ueli Maurer
`Ron Rivest
`
`Gus Simmons
`Yacov Yacobi
`
`Miles Smid
`
`Jacques Stem
`
`Mike Wiener
`
`In addition, we gratefully acknowledge the exceptionally large number of additional indi-
`viduals who have helped improve the quality of this volume, by providing highly appreci-
`ated feedback and guidance on various matters. These individuals include:
`
`Carlisle Adams
`Simon Blackburn
`
`Colin Boyd
`
`Ed Dawson
`Whit Diffie
`
`Luis Encinas
`Shuhong Gao
`
`Jovan Golié
`
`Rich Ankney
`Ian Blake
`
`Jorgen Brandt
`
`Peter de Rooij
`Hans Dobbertin
`
`Warwick Ford
`Will Gilbert
`
`Tom Berson
`Antoon Bosselaers
`
`Mike Burmester
`
`Yvo Desmedt
`Carl Ellison
`
`Amparo Fuster
`Marc Girault
`
`Dieter Gollmann
`
`Li Gong
`
`

`

`xxviii
`
`Preface
`
`Carrie Grant
`Darrel Hankerson
`
`Mike Just
`Neal Koblitz
`
`Evangelos Kranakis
`Xuejia Lai
`S. Mike Matyas
`
`Mike Mosca
`Volker Mueller
`
`Kaisa Nyberg
`Walter Penzhorn
`Leon Pintsov
`Matt Robshaw
`
`Rainer Rueppel
`Jeff Shallit
`
`Andrea Vanstone
`Jerry Veeh
`Robert Zuccherato
`
`Blake Greenlee
`Anwar Hasan
`
`Andy Klapper
`Cetin Koc
`
`David Kravitz
`Charles Lam
`Willi Meier
`
`Tim Moses
`David Naccache
`
`Andrew Odlyzko
`Birgit Pfitzmann
`Fred Piper
`Peter Rodney
`
`Mahmoud Salmasizadeh
`Jon Sorenson
`
`Serge Vaudenay
`Fausto Vitini
`
`Helen Gustafson
`Don Johnson
`
`Lars Knudsen
`Judy Koeller
`
`Hugo Krawczyk
`Alan Ling
`Peter Montgomery
`
`Serge Mister
`James Nechvatal
`
`Richard Outerbridge
`Kevin Phelps
`Carl Pomerance
`Phil Rogaway
`
`Roger Schlafly
`Doug Stinson
`
`Klaus Vedder
`Lisa Yin
`
`We apologize to those whose names have inadvertently escaped this list. Special thanks are
`due to Carrie Grant, Darrel Hankerson, Judy Koeller, Charles Lam, and Andrea Vanstone.
`Their hard work contributed greatly to the quality of this book, and it was truly a pleasure
`working with them. Thanks also to the folks at CRC Press, including Tia Atchison, Gary
`
`Bennett, Susie Carlisle, Nora Konopka, Mary Kugler, Amy Morrell, Tim Pletscher, Bob
`Stern, and Wayne Yuhasz. The second author would like to thank his colleagues past and
`present at Nortel Secure Networks (Bell-Northem Research), many ofwhom are mentioned
`
`above, for their contributions on this project, and in particular Brian O’Higgins for his en-
`couragement and support; all views expressed, however, are entirely that of the author. The
`
`third author would also like to acknowledge the support of the Natural Sciences and Engi-
`neering Research Council.
`
`Any errors that remain are, of course, entirely our own. We would be grateful ifreaders
`who spot errors, missing references or credits, or incorrectly attributed results would contact
`us with details. It is our hope that this volume facilitates further advancement of the field,
`
`and that we have helped play a small part in this.
`
`Alfred J. Menezes
`
`Paul C. van Oorschot
`Scott A. Vanstone
`
`August, 1996
`
`

`

`Table of Contents
`
`List of Tables
`
`List of Figures
`
`Foreword by KL. Rivest
`Preface
`
`XV
`
`xix
`
`xxi
`xxiii
`
`Overview of Cryptography
`1.1
`Introduction ................................
`
`1
`
`1.2
`1.3
`
`1.4
`
`1.5
`
`2
`Information security and cryptography ..................
`6
`Background on functions .........................
`6
`1.3.1 Functions (1-1, one-way, trapdoor one-way) ............
`1.3.2 Permutations ............................ 10
`
`1.3.3
`
`Involutions ............................. 10
`
`Basic terminology and concepts ...................... 11
`
`Symmetric-key encryption ........................ 15
`1.5.1 Overview of block ciphers and stream ciphers ........... 15
`1.5.2 Substitution ciphers and transposition ciphers ........... 17
`
`1.5.3 Composition of ciphers ...................... 19
`1.5.4 Stream ciphers ........................... 20
`
`1.5.5 The key space ........................... 21
`1.6 Digital signatures ............................. 22
`1.7 Authentication and identification ..................... 24
`
`1.7.1
`
`Identification ............................ 24
`
`1.8
`
`1.7.2 Data origin authentication ..................... 25
`Public-key cryptography ......................... 25
`1.8.1 Public-key encryption ....................... 25
`1.8.2 The necessity of authentication in public—key systems ....... 27
`1.8.3 Digital signatures from reversible public-key encryption ...... 28
`
`1.8.4 Symmetric—key vs. public-key cryptography ............ 31
`1.9 Hash functions .............................. 33
`
`1.10 Protocols and mechanisms ......................... 33
`
`1.11 Key establishment, management, and certification ............. 35
`1.11.1 Key management through symmetric-key techniques ....... 36
`
`1.11.2 Key management through public-key techniques .......... 37
`1.11.3 Trusted third parties and public-key certificates .......... 39
`
`1.12 Pseudorandom numbers and sequences .................. 39
`1.13 Classes of attacks and security models .................. 41
`1.13.1 Attacks on encryption schemes .................. 41
`1.13.2 Attacks on protocols ........................ 42
`
`1.13.3 Models for evaluating security ................... 42
`1.13.4 Perspective for computational security ............... 44
`1.14 Notes and further references ........................ 45
`
`

`

`vi
`
`Table of Contents
`
`2 Mathematical Background
`49
`2.1
`Probability theory ............................. 50
`2.1.1 Basic definitions .......................... 50
`
`2.1 .2 Conditional probability ...................... 5 1
`2.1.3 Random variables ......................... 51
`
`2.1 .4 Binomial distribution ....................... 52
`
`2.1.5 Birthday attacks .......................... 53
`
`2.1.6 Random mappings ......................... 54
`Information theory ............................ 56
`
`2.2. 1 Entropy .............................. 56
`2.2.2 Mutual information ........................ 57
`
`Complexity theory ............................. 57
`2.3.1 Basic definitions .......................... 57
`
`2.2
`
`2.3
`
`2.3.2 Asymptotic notation ........................ 58
`2.3.3 Complexity classes ......................... 59
`2.3.4 Randomized algorithms ...................... 62
`
`2.4 Number theory .............................. 63
`2.4.1 The integers ............................ 63
`
`2.4.2 Algorithms in Z .......................... 66
`2.4.3 The integers modulo n ....................... 67
`
`2.4.4 Algorithms in Zn ......................... 71
`2.4.5 The Legendre and Jacobi symbols ................. 72
`2.4.6 Blum integers ........................... 74
`
`2.5 Abstract algebra .............................. 75
`2.5.1 Groups ............................... 75
`
`2.5.2 Rings ............................... 76
`2.5.3 Fields ............................... 77
`
`2.5.4 Polynomial rings .......................... 78
`2.5.5 Vector spaces ........................... 79
`Finite fields ................................ 80
`
`2.6
`
`2.6.1 Basic properties .......................... 80
`
`2.6.2 The Euclidean algorithm for polynomials ............. 81
`2.6.3 Arithmetic of polynomials ..................... 83
`2.7 Notes and further references ........................ 85
`
`3 Number-Theoretic Reference Problems
`
`87
`
`3.1
`
`3.2
`
`Introduction and overview ......................... 87
`
`The integer factorization problem ..................... 89
`3 .2. 1 Trial division ............................ 90
`
`3.2.2 Pollard’s rho factoring algorithm .................. 91
`3.2.3 Pollard’s p — 1 factoring algorithm ................ 92
`
`3.2.4 Elliptic curve factoring ....................... 94
`3.2.5 Random square factoring methods ................. 94
`
`3.2.6 Quadratic sieve factoring ...................... 95
`3.2.7 Number field sieve factoring .................... 98
`
`3.3
`3.4
`3.5
`
`The RSA problem ............................. 98
`The quadratic residuosity problem ..................... 99
`Computing square roots in Zn ....................... 99
`
`3.5.1 Case (i): n prime .......................... 100
`3.5.2 Case (ii): n composite ....................... 101
`
`

`

`Table of Contents
`
`vii
`
`3.6
`
`The discrete logarithm problem ...................... 103
`3.6.1 Exhaustive search ......................... 104
`
`3.6.2 Baby-step giant-step algorithm ................... 104
`3.6.3 Pollard’s rho algorithm for logarithms ............... 106
`
`3.6.4 Pohlig-Hellman algorithm ..................... 107
`3.6.5
`Index-calculus algorithm ...................... 109
`3.6.6 Discrete logarithm problem in subgroups of 2; .......... 113
`The Diflie-Hellman problem ....................... 113
`Composite moduli ............................. 114
`
`Computing individual bits ......................... 114
`3.9.1 The discrete logarithm problem in Z; — individual bits ...... 116
`3.9.2 The RSA problem — individual bits ................ 1 16
`3.9.3 The Rabin problem — individual bits ............... 117
`
`3.7
`3.8
`
`3.9
`
`3.10 The subset sum problem .......................... 117
`3.10.1 The L3-lattice basis reduction algorithm .............. 118
`3.10.2 Solving subset sum problems of low density ............ 120
`
`3.10.3 Simultaneous diophantine approximation ............. 121
`3.11 Factoring polynomials over finite fields .................. 122
`
`3.11.1 Square-free factorization ...................... 123
`3.11.2 Berlekamp’s Q-matrix algorithm .................. 124
`3.12 Notes and further references ........................ 125
`
`133
`4 Public-Key Parameters
`4.1
`Introduction ................................ 133
`
`4.1.1 Generating large prime numbers naively .............. 134
`
`4.2
`
`4.1 .2 Distribution of prime numbers ................... 134
`Probabilistic primality tests ........................ 135
`4.2.1 Fermat’s test ............................ 136
`
`4.2.2 Solovay-Strassen test ....................... 137
`4.2.3 Miller-Rabin test .......................... 138
`
`4.2.4 Comparison: Fermat, Solovay-Strassen, and Miller-Rabin ..... 140
`(True) Primality tests ........................... 142
`
`4.3
`
`4.3.1 Testing Mersenne numbers ..................... 142
`4.3.2 Primality testing using the factorization of n — 1 ......... 143
`4.3.3
`Jacobi sum test ........................... 144
`
`4.4
`
`4.5
`
`4.3.4 Tests using elliptic curves ..................... 145
`Prime number generation ......................... 145
`4.4.1 Random search for probable primes ................ 145
`
`4.4.2 Strong primes ........................... 149
`4.4.3 NIST method for generating DSA primes ............. 150
`4.4.4 Constructive techniques for provable primes ............ 152
`Irreducible polynomials over 21, ...................... 154
`4.5. 1
`Irreducible polynomials ...................... 154
`4.5.2 Irreducible trinomials ....................... 157
`
`4.5.3 Primitive polynomials ....................... 15 7
`
`4.6 Generators and elements of high order .................. 160
`4.6.1 Selecting a prime p and generator of Z; .............. 164
`4.7 Notes and further references ........................ 165
`
`

`

`viii
`
`Table of Contents
`
`169
`5 Pseudorandom Bits and Sequences
`5.1
`Introduction ................................ 169
`
`5.1.1 Background and Classification ................... 170
`Random bit generation .......................... 171
`
`Pseudorandom bit generation ....................... 173
`5.3.1 ANSI X9.17 generator ....................... 173
`5.3.2 FIPS 186 generator ......................... 174
`Statistical tests ............................... 175
`
`5 .2
`
`5 .3
`
`5.4
`
`5.4.1 The normal and chi-square distributions .............. 176
`
`5.4.2 Hypothesis testing ......................... 179
`5.4.3 Golomb’s randomness postulates .................. 180
`5.4.4 Five basic tests ........................... 181
`
`5.4.5 Maurer’s universal statistical test ................. 183
`
`5.5
`
`Cryptographically secure pseudorandom bit generation .......... 185
`5.5.1 RSA pseudorandom bit generator ................. 185
`5 .5 .2 Blum—Blum— Shub pseudorandom bit generator ........... 186
`5.6 Notes and further references ........................ 187
`
`191
`6 Stream Ciphers
`6. 1
`Introduction ................................ 1 9 1
`6.1 . 1 Classification ........................... 192
`
`6.2
`
`Feedback shift registers .......................... 195
`6.2.1 Linear feedback shift registers ................... 195
`
`6.2.2 Linear complexity ......................... 198
`6.2.3 Berlekamp-Massey algorithm ................... 200
`
`6.2.4 Nonlinear feedback shifi registers ................. 202
`Stream ciphers based on LFSRs ...................... 203
`
`6.3
`
`6.3.1 Nonlinear combination generators ................. 205
`6.3.2 Nonlinear filter generators ..................... 208
`
`6.3.3 Clock—controlled generators .................... 209
`6.4 Other stream ciphers ............................ 212
`6 .4. 1 SEAL ............................... 2 1 3
`
`6.5 Notes and further references ........................ 216
`
`223
`7 Block Ciphers
`7.1
`Introduction and overview ......................... 223
`
`7.2
`
`Background and general concepts ..................... 224
`7.2.1
`Introduction to block ciphers .................... 224
`7.2.2 Modes of operation ........................ 228
`
`7.2.3 Exhaustive key search and multiple encryption .......... 233
`Classical ciphers and historical development ............... 237
`
`7.3
`
`7.3.1 Transposition ciphers (background) ................ 238
`7.3.2 Substitution ciphers (background) ................. 238
`
`. 241
`.
`7.3.3 Polyalphabetic substitutions and Vigenere ciphers (historical) .
`7.3.4 Polyalphabetic cipher machines and rotors (historical) ....... 242
`7.3.5 Cryptanalysis of classical ciphers (historical) ........... 245
`7.4 DES .................................... 250
`
`7.4.1 Product ciphers and Feistel ciphers ................. 250
`
`7.4.2 DES algorithm ........................... 252
`7.4.3 DES properties and strength .................... 256
`
`

`

`Table of Contents
`
`ix
`
`7.5
`
`7.6
`
`7.7
`
`FEAL ................................... 259
`
`IDEA ................................... 263
`
`SAFER, RC5, and other block ciphers ................... 266
`7.7.1 SAFER .............................. 266
`
`7.7.2 RC5 ................................ 269
`
`7.7.3 Other block ciphers ........................ 270
`7.8 Notes and further references ........................ 271
`
`283
`8 Public-Key Encryption
`8.1
`Introduction ................................ 283
`
`8.2
`
`8.3
`
`8.4
`
`8.1.1 Basic principles .......................... 284
`
`RSA public-key encryption ........................ 285
`8 .2. 1 Description ............................. 286
`8.2.2 Security of RSA .......................... 287
`
`8.2.3 RSA encryption in practice .................... 290
`Rabin public-key encryption ........................ 292
`
`ElGamal public-key encryption ...................... 294
`8.4.1 B