`
`HANDBOOK of
`
`
`
`
`
`
`
`
`
`
`Paul C. van Oorschot
`Scott A. Vanstone
`
`APPLIED
`CRYPTOGRAPHY
`
`
`
`
` Alfred J. Menezes
`
`
`
`
`
`
`
`
`
`
`TCL Exhibit 1009
`Page 1
`
`

`

`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 from 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. Information-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 from 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
`
`TCL Exhibit 1009
`Page 2
`
`

`

`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 functions 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 efficiently, 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 insightful 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
`
`
`
`TCL Exhibit 1009
`Page 3
`
`

`

`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 sufficiently 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 sufficient detail to
`allow direct implementation without consulting secondary references. We believe this style
`of presentation 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 of correctness 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
`
`TCL Exhibit 1009
`Page 4
`
`

`

`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
`
`Stream ciphers
`Block ciphers (symmetric-key)
`Public-key encryption
`One-way hash functions (unkeyed)
`Message authentication codes
`Signature schemes (public-key, symmetric-key)
`Utilities
`Public-key parameter generation
`Pseudorandom bit generation
`Efficient algorithms for discrete arithmetic
`Foundations
`
`Chapter 6
`Chapter 7
`Chapter 8
`Chapter 9
`Chapter 9
`Chapter 11
`
`Chapter 4
`Chapter 5
`Chapter 14
`
`Chapter 1
`Introduction to cryptography
`Chapter 2
`Mathematical background
`Chapter 3
`Complexity and analysis of underlying problems
`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 of applied 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 of this 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 followingclasses of items jointlynumbered
`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,
`
`TCL Exhibit 1009
`Page 5
`
`

`

`Preface
`
`xxv
`
`Chapter 1
`
`introduction
`
`Chapter 2
`background
`
`math
`
`Chapter 3
`
`security foundations
`
`public-key
`
`Chapter 13
`
`key management
`
`Chapter 12
`
`establishment of secret keys
`
`Chapter 15
`standards
`patents and
`
`Chapter 14
`implementation
`
`efficient
`
`Chapter 4
`parameters
`public-key
`
`Chapter 5
`generation
`number
`random
`
`Chapter 11
`(symmetric-key)
`
`signatures
`
`Chapter 11
`(public-key)
`signatures
`
`Chapter 9
`
`(keyed)
`
`hash functions
`
`Chapter 9
`(unkeyed)
`
`hash functions
`
`Chapter 8
`(public-key)
`encryption
`
`Chapter 7
`
`(symmetric-key)
`block ciphers
`
`Chapter 6
`stream ciphers
`
`Chapter 11
`signatures
`
`digital
`
`Chapter 10
`identification
`
`Chapter 9
`
`authentication
`
`message
`
`Chapter 9
`techniques
`data integrity
`
`Chapters 6,7,8
`encryption
`
`Figure 1: Roadmap of the book.
`
`non-repudiation
`
`authentication
`
`data integrity
`
`confidentiality
`
`TCL Exhibit 1009
`Page 6
`
`

`

`xxvi
`
`Preface
`
`Chapter
`
`1. Overview of Cryptography
`2. Mathematical Background
`3. Number-Theoretic Reference Problems
`4.
`Public-Key Parameters
`5.
`Pseudorandom Bits and Sequences
`6.
`Stream Ciphers
`7. Block Ciphers
`8.
`Public-Key Encryption
`9. Hash Functions and Data Integrity
`10.
`Identification and Entity Authentication
`11. Digital Signatures
`12. Key Establishment Protocols
`13. Key Management Techniques
`14. Efficient Implementation
`15.
`Patents and Standards
`— Overall organization
`
`Primary Author
`AJM PVO SAV
`*
`*
`*
`*
`*
`*
`*
`*
`
`*
`
`*
`
`*
`*
`
`*
`*
`
`*
`*
`
`*
`
`*
`
`*
`
`*
`
`Table 2: Primary authors of each chapter.
`
`while numbered Remarks identify non-technical (often 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., x5.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., x5.1, x5.2)
`is also given for convenience.
`At the end of the book, we have included a list of papers 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
`
`TCL Exhibit 1009
`Page 7
`
`

`

`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 efficient 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 often 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 drafts 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 individualcredit for their
`many suggestions throughout this book. Among our Advisory Editors, we would particu-
`larly like to thank:
`
`Mihir Bellare
`Burt Kaliski
`Chris Mitchell
`Gus Simmons
`Yacov Yacobi
`
`Don Coppersmith
`Peter Landrock
`Tatsuaki Okamoto
`Miles Smid
`
`Dorothy Denning Walter Fumy
`Arjen Lenstra
`Ueli Maurer
`Bart Preneel
`Ron Rivest
`Jacques Stern
`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´c
`
`Rich Ankney
`Ian Blake
`J¨orgen Brandt
`Peter de Rooij
`Hans Dobbertin
`Warwick Ford
`Will Gilbert
`Dieter Gollmann
`
`Tom Berson
`Antoon Bosselaers
`Mike Burmester
`Yvo Desmedt
`Carl Ellison
`Amparo Fuster
`Marc Girault
`Li Gong
`
`TCL Exhibit 1009
`Page 8
`
`

`

`xxviii
`
`Preface
`
`Carrie Grant
`Darrel Hankerson
`Mike Just
`Neal Koblitz
`Evangelos Kranakis
`Xuejia Lai
`S. Mike Matyas
`Mike Mosca
`Volker M¨ueller
`Kaisa Nyberg
`Walter Penzhorn
`Leon Pintsov
`Matt Robshaw
`Rainer Rueppel
`Jeff Shallit
`Andrea Vanstone
`Jerry Veeh
`Robert Zuccherato
`
`Blake Greenlee
`Anwar Hasan
`Andy Klapper
`C¸ etin 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-Northern Research), many of whom 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 if readers
`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
`
`TCL Exhibit 1009
`Page 9
`
`

`

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

`

`vi
`
`Table of Contents
`
`2.2
`
`2.3
`
`2 Mathematical Background
`2.1
`Probability theory (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1)
`2.1.1 Basic definitions (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1)
`2.1.2 Conditional probability (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1)
`2.1.3 Random variables (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1)
`2.1.4 Binomial distribution (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1)
`2.1.5 Birthday attacks (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1)
`2.1.6 Random mappings (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1)
`Information theory (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1)
`2.2.1 Entropy (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1)
`2.2.2 Mutual information (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1)
`Complexity theory (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1)
`2.3.1 Basic definitions (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1)
`2.3.2 Asymptotic notation (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1)
`2.3.3 Complexity classes (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1)
`2.3.4 Randomized algorithms (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1)
`2.4 Number theory (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1)
`2.4.1 The integers (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1)
`2.4.2 Algorithms in Z (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1)
`2.4.3