~
`
`t ~
`
`1
`
`~ O
`
`h
`3J ':
`[µ
`'
`~i ry`` t~
`:~' ~
`{
`l f ?.i~
`.i ?'i _.
`
`S
`
`~alfi~ed . ~ Ie~leze
`Paul ~1 ~~a~10or~~cllot
`Scott ~a, ~ anstorle
`
`Facebook's Exhibit No. 1005
`0001
`
`MOBILEIRON, INC. - EXHIBIT 1011
`Page 001
`
`

`

`Computer Sciences
`Applied Mathematics
`Engio~eering
`H.1\DBOOI~ o~~
`
`Gr~~pto~raph~: in particular public-kc~- cr~~pto~raplry, has eme~~~ed in tl~e
`last 20 ~e~u~s as an iml~or~~ant d~isciplia~e that is not onl~~ the subject of an
`ruorn~o~~s ~unount of research. but pro~~ides the i'oundation for information
`secu~~iri~ in mama a~~plicatioils. Sta►~~dards are emel,~ia~~ to meet thi° demands
`Eor crypto raphic prot~cction in most areas of data communications. Public-
`ke~~ cr~-ptograpliir tecl»~iqu~~•~ arr no~~~~ in ~~~idespr~ad usr in industry:
`c~peciall~~ in the financial ser~~ices indu~u~~~. in the public sector. and b~
`indi~~id~~al~s fir their per~o»al ~»-i~~ac}~. .;~~ch a~ iii electronic nail. 'I~his
`H~uidbook ~~~~ill ser~~c ;~~ a ~~alusll>l~~ r~~fe~•ci~ce for tl~e no~~i~e as ~~~c11 as for
`the expert ~~~ho nec~ls a «~idi•r scope of co~~erage within the area o(~
`crypt~ograph~~. It is a necess~u~~ and timc~l~ wide for prolessio~ials ~~~~ho
`practice the art of~ crvptoyraph~.
`Tl~e Handbook of Applied Cryptography pr~~~ides a treatment that
`iti multifunctional:
`• It ser~-e~ as an introduction to tl~~: more practical aspects of
`both com~eutional and public-ke~~ cry-l~to;rapli}
`• l~ i~ a ~~aluable source of the latest tc~cha~iyues and algorithms
`COI' l~ll' ~C170L15 (]T~lCl1U011('1'
`• It prop°ides an integrated treatment of the field, ~~~hile still
`prrs~~ntin each majo~~ topic as a .~clf-contained ~~nit
`• It pro~~ides a mathen~~atic~l u~ratinent to accompan~~
`practical discussions
`• It contains ~ nou~h ah~,u~~iction to be a ~~a~luable relerencc for
`th~~oreticiv~s ~~~hilc ro~~<<~iuing enou~l~ det~iil to aceu~tll~~ allo~~
`implcmeiitation of the al ~~ri~hms dis~~u.~~ed
`This is th~~ deliniti~~e c~~pt~~,raph~~ rcicrcncc that no~iee as ~~~f~ll as r:~perienced
`~I~~~~~°toper,. cl~~~i~ n~~r._ rc,~•a~nc~rs. cn~~inrc~rs. ro~l~put~°r sci~•nti,t,. and
`~~Iathrmatici~uls alike sill find indispens~il~lc~.
`
`Facebook's Exhibit No. 1005
`0002
`
`MOBILEIRON, INC. - EXHIBIT 1011
`Page 002
`
`

`

`Facebook's Exhibit No. 1005
`0003
`
`MOBILEIRON, INC. - EXHIBIT 1011
`Page 003
`
`

`

`HANDBOOK of
`
`..{ ~,
`
`~ S:.r
`
`a
`
`~ ~~.,
`'P,, ' ''+. y..
`
`~.r.~
`
`Facebook's Exhibit No. 1005
`0004
`
`MOBILEIRON, INC. - EXHIBIT 1011
`Page 004
`
`

`

`The CRC Press Series on
`
`1
`
`Series Editor
`Kenneth H. Rosen, Ph.D.
`AT&T Bell Laboratories
`
`Charles J. Colbourn and Jeffery H. Dinitz, The CRC
`Handbook of Combinatorial Designs
`
`Steven Furino, Ying Miao, and Jianxing Yin,
`Frames and Resolvable Designs:
`Uses, Constructions, and Existence
`
`Daryl D. Harms, Miroslav Kraetzl, Charles J. Colbourn,
`and Stanley J. Devitt, Network Reliability:
`Experiments with A Symbolic Algebra Environment
`Richard A. Mollie, Quadratics
`
`Douglas R. Stinson, Cryptography: Theory and Practice
`
`Facebook's Exhibit No. 1005
`0005
`
`MOBILEIRON, INC. - EXHIBIT 1011
`Page 005
`
`

`

`H~ND~OOK of
`
`A1fredJ. Menezes
`Paul C, van Oorschot
`ScottA. Vanstone
`
`~,C
`
`CRC Press
`Boca K~ton New York London Tokyo
`
`Facebook's Exhibit No. 1005
`0006
`
`MOBILEIRON, INC. - EXHIBIT 1011
`Page 006
`
`

`

`~~~ 6
`. ~
`~aJ ~~~ 3
`~ ~q~
`~ ~~
`
`NOV 1 9 1996
`RIGHT ~F~~ s
`
`Library of Congress Catalogin~•in-Publication Data
`
`Menezes, A. J. (Alfred J.), 1965—
`Handbook of applied cryptography /Alfred Menezes, Paul van Oorschot,
`Scott Vanstone.
`p,
`cm. -- (CRC Press series on discrete mathematics and its
`applications)
`Includes bibliographical references and index.
`ISBN 0-8493-8523-7 (alk. paper)
`1. Computers--Access control--Handbooks, manuals, etc.
`2. Cryptography--Handbooks, manuals, etc. I. Van Oorschot, Paul C.
`II. Vanstone, Scott A. III. Title. IV. Series: Discrete
`mathematics and its applications.
`QA76.9.A25M463 1996
`005.8'2--dc20
`
`96-27609
`CIP
`This book contains informarion obtained from authentic and highly regarded sources. Reprinted material is quoted with
`pernussion, and sources aze indicated. A wide variety of references are listed. Reasonable efforts have been made to publish
`reliable data and information, but the author and the publisher cannot assume responsibility for the validity of all materials
`or for the consequences of their use.
`Neither this book nor any part may be reproduced or transmitted in any form or by any means, electronic or mechanical,
`including photocopying, microfilming, and recording, or by any information storage or retrieval system, without prior
`pernussion in writing from the publisher.
`The consent of CRC Press does not extend to copying for general distribution, for promotion, for creating new works,
`or for resale. Specific permission must be obtained in writing from CRC Press for such copying.
`Direct all inquiries to CRC Press, Inc., 2000 Corporate Blvd., N.W., Boca Raton, Florida 33431.
`D 1997 by CRC Press, Inc.
`
`No claim to original U.S. Government works
`dnternational Standard Book Number 0-8493-8523-7
`Library of Congress Card Number 96-27609
`Prineed in the [Jnited States of America 1 2 3 4 5 6 7 8 9 0
`Printed on acid-free paper
`
`Facebook's Exhibit No. 1005
`0007
`
`MOBILEIRON, INC. - EXHIBIT 1011
`Page 007
`
`

`

`To Archie and Lida Menezes
`
`To Cornelis Henricus van Oorschot
`and Maria Anna Buys van Vugt
`
`To Margret and Gordon Vanstone
`
`Facebook's Exhibit No. 1005
`0008
`
`MOBILEIRON, INC. - EXHIBIT 1011
`Page 008
`
`

`

`Contents in Brief
`
`Table of Contents ... . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . .. . . . . . . . .....v
`List of Tables ...... . . . . . . . . . . . . . . . . . . . . . . . . .. . .. . . . . . . . . . . . . . . . ...xv
`List of Figures ...... . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xix
`Foreword ........ . . . . . . . . . . . . . . . . . . . . . . . .. . .. . . . . . . . . . . . . . . . . ... .xxi
`Preface .................. . . .. . .. . . . . .. . . .. . . . . . . . . . . . . . . . . ... . . xxiii
`Overview of Cryptography ........ . ........ . .....:........ .. . . ......1
`Mathematical Background .. ......... . ............................ . 49
`Number-Theoretic Reference Problems ... .... . ........ . .... . . . . . .... 87
`Public-Key Parameters ....... ........................... .........133
`Pseudorandom Bits and Sequences ..... . . ......... ......... ...... . 169
`Stream Ciphers ..................................................191
`Block Ciphers ......................... ..........................223
`Public-Key Encryption ...........................................283
`Hash Functions and Data Integrity ......................... .. ......321
`Identification and Entity Authentication ..................... .......385
`Digital Signatures ................................................425
`Key Establishment Protocols ............ . ................. ........489
`Key Management Techniques ......... .......................:..543
`EfficientImplementadon .......... . ................ . . ........ . ... 591
`Patents and Standards ... .........................................635
`Bibliography of Papers from Selected Cryptographic Forums .........663
`References ............ ............................ . ........ . ....703
`Index ................. . ................ ........... . ........ . ....755
`
`1 2 3 4 5 6 7 8 9
`
`10
`11
`12
`13
`14
`15
`A
`
`iv
`
`Facebook's Exhibit No. 1005
`0009
`
`MOBILEIRON, INC. - EXHIBIT 1011
`Page 009
`
`

`

`Tale of Contents
`
`i,
`
`List of Tables
`List of Figures
`Foreword by R.L. Rivest
`Preface
`
`.. .
`
`. .
`. '.
`
`1 Overview of Cryptography
`Introduction
`1.1
`Information security and cryptography
`1.2
`Background on functions
`1.3
`1.3.1 Functions (1-1, one-way, trapdoor one-way)
`1.3.2 Permutations .
`1.3.3 Involutions .
`Basic terminology and concepts .
`Symmetric-key encryption
`1.5.1 Overview of block ciphers and stream ciphers
`1.5.2 Substitution ciphers and transposition ciphers
`1.5.3 Composition of ciphers
`1.5.4 Stream ciphers
`1.5.5 The key space
`1.6 Digital signatures
`Authentication and identification
`1.7
`1..7.1 Identification .
`1.72 Data origin authentication
`Public-key cryptography
`. ~.
`1.8.1 Public-key encryption
`1.8.2 The necessity of authentication in public-key systems
`1.8.3 Digital signatures from reversible public-key encryption .
`1.8.4 Symmetric-key vs. public-key cryptography .
`1.9 Hash functions
`1.10 Protocols and mechanisms .
`1.11 Key establishment, management, and certification .
`1.11.1 Key management through symmetric-key techniques
`1.11.2 Key management through public-key techniques .
`1.11.3 Trusted third parties and public-key certificates
`1.12 Pseudorandom numbers and sequences
`1.13 Classes of attacks and security models
`1.13.1 Attacks on encryption schemes
`1.13.2 Attacks on protocols
`1.13.3 Models for evaluating security
`1.13.4 Perspective for computational security .
`1.14 Notes and further references .
`
`1.4
`1.5
`
`1.8
`
`v
`
`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
`
`.. .
`
`Facebook's Exhibit No. 1005
`0010
`
`MOBILEIRON, INC. - EXHIBIT 1011
`Page 010
`
`

`

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

`

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

`

`viii
`
`Table of Contents
`
`5.4
`
`5 Pseudorandom Bits and Sequences
`5.1
`Introduction
`5.1.1 Background and Classification .
`5.2 Random bit generation
`Pseudorandom bit generation
`5.3
`5.3.1 ANSI X9.17 generator
`5.3.2 FIPS 186 generator .
`. ~.
`Statistical tests .
`5.4.1 The normal and chi-square distributions
`5.4.2 Hypothesis testing
`5.4.3 Golomb's randomness postulates .
`5.4.4 Five basic tests .
`5.4.5 Maurer's universal statistical test
`5.5 Cryptographically secure pseudorandom bit generation
`5.5.1 RSA pseudorandom bit generator
`5.5.2 Blum-Blum-Shub pseudorandom bit generator .
`5.6 Notes and further references .
`
`• 169
`169
`. 170
`. 171
`. 173
`. 173
`. 174
`175
`. 176
`. 179
`. 180
`181
`. 183
`. 185
`. 185
`. 186
`. 187
`
`6.2
`
`6 Stream Ciphers
`191
`6.1 Introduction
`191
`6.1.1 Classification
`. 192
`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
`62.4 Nonlinear feedback shift registers
`. 202
`Stream ciphers based on LFSRs
`.203
`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
`. . . . . . . . . . . . . . . . . . . . . . . . . . . .213
`6.5 Notes and further references .
`.216
`
`6.3
`
`7 Block Ciphers
`223
`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
`7.3 ~ Classical ciphers and historical development
`.237
`7.3.1 Transposition ciphers (background)
`_ 238
`7.3.2 Substitution ciphers (background)
`.238
`7.3.3 Polyalphabetic substitutions and Vigen~re ciphers (historical)
`. 241
`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
`
`Facebook's Exhibit No. 1005
`0013
`
`MOBILEIRON, INC. - EXHIBIT 1011
`Page 013
`
`

`

`Table of Contents
`
`7.5 FEAL
`IDEA
`7.6
`SAFER; RCS, and other block ciphers .
`7.7
`7.7.1 SAFER
`7.7.2 RCS
`7.7.3 Other block ciphers
`7.8 Notes and further references .
`
`~
`
`~ 8 Public-Key Encryption
`8.1 Introduction
`8.1.1 Basic principles
`8.2 RSA public-key encryption
`8.2.1 Description .
`8.2.2 Security of RSA
`8.23 RSA encryption in practice
`8.3 Rabin public-key encryption .
`8.4 ElGamal public-key encryption
`8.4.1 Basic ElGamal encryption
`8.4.2 Generalized E1Gama1 encryption .
`8.5 McEliece public-key encryption .
`8.6
`Knapsack public-key encryption .
`8.6.1 Merkle-Hellman knapsack encryption
`8.6.2 Chor-Rivest knapsack encryption
`Probabilistic public-key encryption
`8.7.1 Goldwasser-Micali probabilistic encryption
`8.7.2 Blum-Goldwasser probabilistic encryption .
`8.73 Plaintext-aware encryption .
`8.8 Notes and further references .
`
`8.7
`
`. ~ .
`
`9 Hash Functions and Data Integrity
`Introduction
`9.1
`9.2 Classification and framework
`9.2.1 General classification
`9.2.2 Basic properties and definitions
`9.2.3 Hash properties required for specific applications
`9.2.4 One-way functions and compression functions .
`9.2.5 Relationships between properties
`9.2.6 Other hash function properties and applications
`Basic constructions and general results
`9.3.1 General model for iterated hash functions
`9.3.2 General constructions and extensions
`9.3,3 Formatting and initialization details
`9.3.4 Security objectives and basic attacks .
`9.3.5 Bitsizes required for practical security
`9.4 Unkeyed hash functions (MDCs)
`9.4.1 Hash functions based on block ciphers .
`9.4.2 Customized hash functions based on NID4 .
`9.4.3 Hash functions based on modular arithmetic .
`Keyed hash functions (MACs)
`9.5.1 MACs based on block ciphers
`
`9.3
`
`9.5
`
`ix
`
`. 259
`. 263
`. 266
`. . 266
`. 269
`. 270
`. 271
`
`283
`. 283
`. 284
`. 285
`. 286
`. 287
`..290
`. 292
`. 294
`. 294
`. 297
`. 298
`. 300
`. 300
`. 302
`. 306
`. 307
`. 308
`. 311
`. 312
`
`321
`. 321
`. 322
`. 322
`. 323
`. "327
`. . 327
`. 329
`. 330
`. 332
`. 332
`. 333
`. 334
`. 335
`. 337
`. 338
`. 338
`. 343
`. 351
`. 352
`. 353
`
`Facebook's Exhibit No. 1005
`0014
`
`MOBILEIRON, INC. - EXHIBIT 1011
`Page 014
`
`

`

`x
`
`Table of Contents
`
`9.5.2 Constructing MACs from MDCs .
`9.5.3 Customized MACs .
`9.5.4 MACS for stream ciphers
`9.6 Data integrity and message authentication .
`9.6.1 Background and definitions
`9.6.2 Non-malicious vs. malicious threats to data integrity .
`9.6.3 Data integrity using a MAC alone
`9.6.4 Data integrity using an MDC and an authentic channel
`9.6.5 Data integrity combined with encryption .
`Advanced attacks on hash functions .
`9.7.1 Birthday attacks
`9.7.2 Pseudo-collisions and compression function attacks
`9.7.3 Chaining attacks
`9.7.4 Attacks based on properties of underlying cipher
`9.8 Notes and further references .
`
`9.7
`
`.. .
`
`10 Identification and Entity Authentication
`10.1 Introduction
`10.1.1 Identification objectives and applications
`10.12 Properties of identification protocols .
`10.2 Passwords (weak authentication)
`10.2.1 Fixed password schemes: techniques
`10.2.2 Fixed password schemes: attacks
`10.2.3 Case study - iJIVIX passwords . . .
`10.2.4 PINs and passkeys
`10.2.5 One-time passwords (towards strong authentication) .
`10.3 Challenge-response identification (strong authentication)
`10.3.1 Background on time-variant parameters
`10.3.2 Challenge-response by symmetric-key techniques
`10.3.3 Challenge-response by public-key techniques
`10.4 Customized and'zero-knowledge identification protocols
`10.4.1 Overview of zero-knowledge concepts :
`10.4.2. Feige-Fiat-Shamir identification protocol
`10.4.3 GQ identification protocol
`10.4.4 Schnorr identification protocol .
`10.4.5 Comparison: Fiat-Shamir, GQ, and Schnorr '.
`10.5 Attacks on identification protocols
`10.6 Notes and further references .
`
`11 Digital Signatures
`11.1 Introduction
`11.2 A framework for digital signature mechanisms
`11.2.1 Basic definitions
`11.2.2 Digital signature schemes with appendix .
`11.2.3 Digital signature schemes with message recovery
`11.2.4 Types of attacks on signature schemes
`11.3 RSA and related signature schemes
`1.1.3.1 The RSA signature scheme
`11.3.2 Possible attacks on RSA signatures
`11.3.3 RSA signatures in practice .
`
`. 354
`. 356
`. 358
`. 359
`. 359
`. 362
`. 364
`. 364
`. 364
`. 368
`. 369
`. 371
`. 373
`. 375
`. 376
`
`385
`. 385
`. 386
`. 387
`. 388
`. 389
`. 391
`. 393
`. 394
`. 395
`. 397
`. 397
`. 400
`.403
`.405
`.405
`.410
`. 412
`. 414
`. 416
`. 417'
`. 420
`
`425
`.425
`.426
`.426
`.428
`. 430
`. 432
`.433
`.433
`.434
`.435
`
`+
`
`~
`
`'.
`
`h
`
`Facebook's Exhibit No. 1005
`0015
`
`MOBILEIRON, INC. - EXHIBIT 1011
`Page 015
`
`

`

`Table of Contents
`
`'
`
`11.3.4 The Rabin public-key signature scheme
`11.3.5 ISO/IEC 9796 formatting
`11.3.6 PKCS #1 formatting
`i 11.4 Fiat-Shamir signature schemes
`11.4.1 Feige-Fiat-Shamir signature scheme
`11.4.2 GQ signature scheme
`11.5 The DSA and related signature schemes .
`11.5.1 The Digital Signature Algorithm (DSA)
`11.5.2 The ElGamal signature scheme
`11.5.3 The Schnorr signature scheme
`11.5.4 The E1Gama1 signature scheme with message recovery
`11.6 One-time digital signatures
`11.6.1 The Rabin one-time signature scheme
`11.6.2 The Merkle one-time signature scheme
`11.6.3 Authentication trees and one-time signatures .
`11.6.4 The GMR one-time signature scheme
`11.7 Other signature schemes .
`11.7.1 Arbitrated digital signatures
`11.7.2 ESIGN .
`11.8 Signatures with additional functionality
`11.8.1 Blind signature schemes
`11.8.2 Undeniable signature schemes
`11.8.3 Fail-stop signature schemes
`11.9 Notes and further references .
`
`12 Key Establishment Protocols
`12.1 Introduction
`12.2 Classification and framework
`12.2.1 General classification and fundamental concepts .
`'.
`12.2.2 Objectives and properties
`12.2.3 Assumptions and adversaries in key establishment protocols .
`12.3 Key transport based on symmetric encryption .
`12.3.1 Symmetric key transport and derivation without a server
`12.3.2 Kerberos and related server-based protocols
`12.4 Key agreement based on symmetric techniques
`12.5 Key transport based on public-key encryption .
`12.5.1 Key~transport using PK encryption without signatures .
`12.5.2 Protocols combining PK encryption and signatures
`12.5.3 Hybrid key transport protocols using PK encryption .
`12.6 Key agreement based on asymmetric techniques
`12.6.1 Diffie-Hellman and related key agreement protocols .
`12.6.2 Implicitly-certified public keys .
`12.6.3 Diffie-Hellman protocols using implicitly-certified keys .
`12.7 Secret sharing
`12.7.1 Simple shared control schemes .
`12.7.2 Threshold schemes .
`12.7.3 Generalized secret sharing
`. .
`12.8 Conference keying
`12.9 Analysis of key establishment protocols .
`12.9.1 Attack strategies and classic protocol flaws
`
`. ..
`
`XI
`
`.438
`. 442
`. 445
`. 447
`. 447
`. 450
`.451
`. 452
`.454
`. 459
`. 460
`. 462
`. 462
`. 464
`. 466
`. 468
`. 471
`. 472
`. . 473
`. 474
`. 475
`. .476
`.478 .
`.481
`
`489
`. 489
`.490
`. .490
`.493
`. 495
`. 497
`. 497
`. 500
`. 505
`. 506
`. 507
`. 509
`. 512
`. 515
`. 515
`. 520
`. 522
`. 524
`. 524
`. 525
`. 526
`. 528
`. 530
`. 530
`
`Facebook's Exhibit No. 1005
`0016
`
`MOBILEIRON, INC. - EXHIBIT 1011
`Page 016
`
`

`

`xii
`
`Table of Contents
`
`12.9.2 Analysis objectives and methods .
`12.10 Notes and further references .
`
`13 Key Management Techniques
`13.1 Introduction
`.13.2 Background and basic concepts
`1.3.2.1 Classifying keys by algorithm type and intended use .
`13.2.2 Key management objectives, threats, and policy
`13.2.3 Simple key establishment models
`13.2.4 Roles of third parties .
`13.2.5 Tradeoffs among key establishment protocols
`13.3 Techniques for distributing confidential keys
`13.3.1 Key layering and cryptoperiods
`13.3.2 Key translation centers and symmetric-key certificates .
`13.4 Techniques for distributing public keys
`13.4.1 Authentication trees
`13.4.2 Public-key certificates
`13.4.3 Identity-based systems .
`13.4.4 Implicitly-certified public keys .
`13.4.5 Comparison of techniques for distributing public keys .
`13.5 Techniques for controlling key usage
`13.5.1 Key separation and constraints on key usage .
`13.5.2 Techniques for controlling use of symmetric keys
`13.6 Key management involving multiple domains .
`13.6.1 Trust between two domains
`13.6.2 Trust models involving multiple certification authorities .
`13.6.3 Certificate distribution and revocation
`13.7 Key life cycle issues .
`13.7.1 Lifetime protection requirements .
`13.7.2 Key management life cycle
`13.8 Advanced trusted third party services
`13.8.1 Trusted timestamping service
`13.8.2 Non-repudiation and notarization of digital signatures
`13.8.3 Key escrow
`13.9 Notes and further references .
`
`. .
`
`. ..
`
`14 Efficient Implementation
`14.1 Introduction
`14:2 Multiple-precision integer arithmetic
`142.1 Radix representation .
`14.2.2 Addition and subtraction .
`14.2.3 Multiplication
`14.2.4 Squaring
`14.2.5 Division
`14.3 Multiple-precision modular arithmetic .
`14.3.1 Classical modular multiplication .
`14.3.2 Montgomery reduction .
`14.3.3 Barrett reduction .
`14.3.4 Reduction methods for moduli of special form .
`14.4 Greatest common divisor algorithms
`
`. 532
`. 534
`
`543
`. 543
`. 544
`. 544
`. 545
`. 546
`. 547
`. 550
`. 551
`. 551
`. 553
`. 555
`. 556
`. 559
`. 561
`. 562
`. 563
`. 567
`. 567
`. 568
`. 570
`. 570
`. 572
`. 576
`. 577
`. 578
`. 578
`. 581
`. 581
`. 582
`. 584
`. 586
`
`591
`. 591
`. 592
`. 592
`. 594
`. 595
`. 596
`. 598
`. 599
`. 600
`. 600
`. 603
`. 605
`. 606
`
`~
`
``,.
`''
`~;
`~` ~
`
`}
`
`Facebook's Exhibit No. 1005
`0017
`
`MOBILEIRON, INC. - EXHIBIT 1011
`Page 017
`
`

`

`Table of Contents
`
`14.4.1 Binary gcd algorithm .
`14.4.2 Lehmer's gcd algorithm
`14.4.3 Binary extended gcd algorithm .
`14.5 Chinese remainder theorem for integers
`14.5.1 Residue number systems .
`14.5.2 Garner's algorithm .
`14.6 Exponentiation
`14.6.1 Techniques for general exponentiation .
`14.6.2 Fixed-exponent exponentiation algorithms .
`14.6.3 Fixed-base exponentiation algorithms
`14.7 Exponent recoding
`14.7.1 Signed-digit representation .
`14.7.2 String-replacement representation
`14.8 Notes and further references .
`
`15 Patents and Standards
`15.1 Introduction
`15.2 Patents on cryptographic techniques .
`152.1 Five fundamental patents .
`15.2.2 Ten prominent patents
`15.2.3 Ten selected patents
`15.2.4.Orderingand acquiring patents .
`15.3 Cryptographic standards .
`. .
`15.3.1 International standards -cryptographic techniques .
`15.3.2 Banking security standards (ANSI, ISO) .
`15.3.3 International security architectures and frameworks
`15.3.4 U.S. government standards (FIPS)
`15.3.5 Internet standards and RFCs
`15.3.6 De facto standards
`15.3.7 Ordering and acquiring standards
`15.4 Notes and further references .
`
`A Bibliography of Papers from Selected Cryptographic Forums
`A.1 AsiacrypdAuscrypt Proceedings .
`A.2 Crypto Proceedings
`A3 Eurocrypt Proceedings
`A.4 Fast Software-Encryption Proceedings
`A.5 Journal of Cryptology papers
`
`References
`Index
`
`Xlll
`
`. 606
`. 607
`. 608
`. 610
`. 611
`.612
`.613
`. 614
`. 620
`. 623
`. 627
`. 627
`. 628
`. .630
`
`635
`. . 635
`. 635
`. 636
`. 638
`. 641
`. 645
`. .645
`. 645
`. 648
`. 653
`. 654
`. 655
`. 656
`. 656
`. 657
`
`663
`. 663
`. 667
`. 684
`. 698
`. 700
`
`703
`755
`
`Facebook's Exhibit No. 1005
`0018
`
`MOBILEIRON, INC. - EXHIBIT 1011
`Page 018
`
`

`

`List of Tables
`
`Some information security objectives
`Reference numbers comparing relative magnitudes .
`Prefixes used for various powers of 10
`
`Bit complexity of basic operations in 7L .
`Extended Euclidean algorithm (example) .
`Orders of elements in 7621 . .
`Computation of 55ss mod 1234
`. ".
`Bit complexity of basic operations in 7Gn
`Jacobi symbols of elements in 7L21 . .
`The subgroups of 7G19
`Complexity of basic operations in ]F'p~.
`The powers of x modulo f (x) = x4 -I- x + 1 .
`
`. .
`
`Some computational problems of cryptographic relevance
`Pollard's rho algorithm (example)
`Running time estimates for numbers factored with QS
`
`3
`44
`45
`
`66
`67
`. . 69
`72
`72
`. . 74
`76
`84
`86
`
`88
`. 107
`. 127
`
`. 140
`Smallest strong pseudoprimes
`. 143
`Known Mersenne primes .
`147
`Upper bounds on plot for sample values of k and t
`Number of Miller-Rabin iterations required so that p~,t < (2 )$0
`148
`149
`Upper bounds on the error probability of incremental search .
`Irreducible trinomials of degree ~n over 7G2, 1 < m < 722 .
`158
`Irreducible trinomials of degree ~ over 7G2, 723 < rrL < 1478 .
`. 159
`. 161
`Primitive polynomials over 7L2 . .
`Primitive polynomials of degree 7n ouer 7G2, 2""' - 1 a Mersenne prime . 162
`
`1.1
`1.2
`1.3
`
`2.1
`2.2
`2.3
`2.4
`2.5
`2.6
`2.7
`2.8
`2.9
`
`3.1
`3.2
`3.3
`
`4.1
`4.2
`4.3
`4.4
`4.5
`4.6
`4.7
`4.8
`4.9
`
`5.1
`5.2
`5.3
`
`6.1
`
`Selected percentiles of the standard normal distribution
`Selected percentiles of the x2 (chi-square} distribution .
`Mean and variance of Xu for Maurer's universal statistical test
`
`Berlekamp-Massey algorithm (example)
`
`Estimated roughness constant rip for various languages
`7.1
`DES initial permutation and inverse (IP and IP-1)
`7.2
`DES per-round functions: expansion E and permutation P
`73
`DES key schedule bit selections (PC 1 and PC2)
`7.4
`DES weak keys .
`7.5
`DES-pairs of semi-weak keys .
`7.6
`DES strength against various attacks
`7.7
`7.8
`DES S-boxes
`7.9
`FEAL functions f, fK
`7.10 FEAL strength against various attacks
`IDEA decryption subkeys derived from encryption subkeys
`7.11
`IDEA encryption sample: round subkeys and ciphertext
`7.12
`
`. .
`
`xv
`
`. 177
`. 178
`. 184
`
`.202
`
`. 250
`.253
`. 253
`. 256
`.258
`.258
`. 259
`. 260
`. 261
`. 262
`. 265
`. 265
`
`Facebook's Exhibit No. 1005
`0019
`
`MOBILEIRON, INC. - EXHIBIT 1011
`Page 019
`
`

`

`XVI
`
`List of Tables
`
`8.1
`
`. 266
`. 270
`
`. 392
`. 392
`. 418
`
`. 427
`. 440
`.442
`.445
`.457
`.459
`.463
`.467
`. 467
`
`7.13
`IDEA decryption sample: round subkeys and variables
`7.14 RCS magic constants .
`Public-key encryption schemes and related computational problems
`.284
`Resistance properties required for specified data integrity applications . . 327
`9.1
`Design objectives for n-bit hash functions (t-bit MAC key)
`9.2
`. 335
`Upper bounds on strength of selected hash functions .
`9.3
`. 339
`9.4
`Summary of selected hash functions based on n-bit block ciphers
`. 340
`9.5
`Summary of selected hash functions based on MD4
`. 345
`9.6
`Test vectors for selected hash functions
`. 345
`9.7
`Notation for MD4-family algorithms .
`. 345
`9.8
`RIPEMD-160 round function definitions
`. 349
`9.9
`RIPEMD-160 word-access orders and rotate counts
`. 351
`9.10 Properties of various types of authentication
`. 362
`9.11 Definition of preimage and collision attacks
`. 372
`10.1 Bitsize of password space for various character combinations
`10.2 Time required to search entire password space
`10.3
`Identification protocol attacks and counter-measures
`11.1 Notation for digital signature mechanisms
`11.2 Definition of sets and functions for modified-Rabin signatures
`11.3
`ISO/IEC 9796 notation
`11.4 PKCS #1 notation
`11.5
`Variations of the E1Gama1 signing equation
`11.6
`The elements of 1F25 as powers of a generator
`11.7 Notation for the Rabin one-time signature scheme
`11.8
`Parameters and signatures for Merkle's one-time signature scheme
`11.9
`Parameters and signatures for Merkle's one-time signature scheme
`12.1 Authentication summary -various terms and related concepts
`12.2 Key transport protocols based on symmetric encryption
`12.3 Selected key transport protocols based on public-key encryption .
`12.4 Selected key agreement protocols
`12.5 Selected MTI key agreement protocols .
`13.1 Private, public, symmetric, and secret keys .
`13.2 Types of algorithms commonly used to meet specified objectives
`13.3 Key protection requirements: symmetric-key vs. public-key systems .
`14.1 Signed-magnitude and two's complement representations of integers
`14.2 Multiple-precision subtraction (example) .
`14.3 Multiple-precision multiplication (example)
`14.4 Multiple-precision squaring (example)
`14.5 Multiple-precision division (example)
`14.6 Multiple-precision division after normalization (example)
`14.7 Montgomery reduction algorithm (example)
`14.8 Montgomery multiplication (example)
`14.9 Reduction modulo m = bt - c (example)
`14.10 Lehmer's gcd algorithm (example) .
`14.11 Single-precision computations in Lehmer's gcd algorithm (example)
`
`.492
`.497
`. 507
`. 516
`. 518
`
`. 544
`. 545
`. 551
`
`. 594
`. 595
`. 596
`. 597
`. 598
`. 599
`. 602
`. 603
`. 605
`. 609
`. 609
`
`. .
`
`Facebook's Exhibit No. 1005
`0020
`
`MOBILEIRON, INC. - EXHIBIT 1011
`Page 020
`
`

`

`List of Tables
`
`XVII
`
`. 610
`14.12 Binary extended gcd algorithm (example)
`14.13 Inverse computation using the binary extended gcd algorithm (example) . 611
`. 612
`14.14 Modular representations (example) .
`. 617
`14.15 Sliding-window exponentiation (example)
`14.16 Number of squarings and multiplications for exponentiation algorithms . 617
`14.17 Single-precision multiplications required by Montgomery exponentiation 620
`. 623
`14..18 Binary vector-addition chain exponentiation (example)
`14.19 Fixed-base Euclidean method for exponentiation (example)
`. 625
`. 628
`14.20 Signed-digit exponent recoding (example)
`
`15.1 Five fundamental U.S.. cryptographic patents .
`Ten prominent U.S. cryptographic patents
`15.2
`Ten selected U.S. cryptographic patents
`15.3
`ISO and ISO/IEC standards for generic cryptographic techniques
`15.4
`15.5 Characteristics of retail vs. wholesale banking transactions .
`15.6 ANSI encryption and banking security standards .
`ISO banking security standards . . .
`15.7
`ISO and ISO/IEC security architectures and frameworks .
`f 15.8
`Selected security-related U.S. FIPS Publications
`15.9
`15.10 Selected Internet RFCs
`15.11 PKCS specifications . .
`
`. 636
`. 638
`. 641
`. 646
`. 648
`. 649
`. 652
`. 653
`. 654
`. . 655
`. . 656
`
`Facebook's Exhibit No. 1005
`0021
`
`MOBILEIRON, INC. - EXHIBIT 1011
`Page 021
`
`

`

`List of Figures
`
`. .
`
`. :
`
`9
`
`4.1
`
`S.1
`5.2
`
`A taxonomy of cryptographic primitives
`1.1
`A function
`1.