throbber
some Cryptographic Techniques
`
`For Secure 'Data Communication
`
`Vi jayaraghavan Varadharaj an
`
`This thesis is submitted to the Council
`
`for National Academic Awards in partial
`
`fulfilment of the requirements for the
`
`degree of Doctor of Philosophy
`
`‘Department of Communication Engineering
`
`Plymouth Fblytechnic
`
`August 1984
`
`Collaboration;
`
`British Telecom Research Labs.,
`
`Martlesham
`
`Amazon Ex. 1023
`
`IPR Petition - USP 7,805,749
`
`PMC Exhibit 2117
`Apple v. PMC
`IPR2016-00755
`Page 1
`
`

`
`PL‘(MG'-.ITH P‘ ' ""_*-'7:-‘"2-3
`
`ssemcnrsié
`- -‘H
`mg is - 005- 82 I/HR‘
`
`xFmo53<43:z
`
`PMC Exhibit 2117
`Apple v. PMC
`IPR2016-00755
`Page 2
`
`

`
`I hereby declare that while registered as a candidate for
`
`the degree of Doctor of Philosophy with the Council for National
`
`Academic Awards I have not been a registered candidate for another
`
`award of the CNAA or other academic or professional institution.
`
`signed; Vguaa
`
`van vamlleam aim
`
`PMC Exhibit 2117
`Apple v. PMC
`IPR2016-00755
`Page 3
`
`

`
`Acknowledgements
`
`I wish to express my grateful thanks to Dr C T Stockel,
`
`Director of Studies,
`
`(Dept of Mathematics. Statistics and Computing,
`
`Plymouth Rolytechnic) and to my supervisors Mr P W Sanders/(Dept of
`
`Comunication Engineering, Plymouth Polytechnic) and Dr R W K Odoni
`(Dept of Mathematics. Exeter University) for their valuable guidance
`and advice at all stages of this research project.
`My thanks are
`
`also due to Dr G Wade (Dept of Commnication Engineering, Plymouth
`
`Polytechnic) who was previously the Director of Studies.
`
`I would
`
`like to mention in particular that Mr Sanders had always been a source
`
`of encouragement.
`
`A special word of thanks should go to Dr Odoni
`
`for readily accepting to be one of the supervisors having acted as
`
`an advisor in the early stages of the_project.
`
`I am greatly indebted
`
`to him for the long hours of useful discussions we had on numerous
`occasions.
`
`My sincere thanks should also go to Prof S D Cohen (Dept
`
`of Mathematics, Glasgow University), Prof J Massey (Institute of
`
`Communication Engineering, ETH, Zurich) and Prof W Ledermann (Dept
`
`of Mathematics, Sussex University) wh had unhesitatingly spared
`their time and offered valuable suggestions and advice in the course
`
`of the project.
`
`I take this opportunity to acknowledge with thanks the
`
`various facilities made available to me by the Plymouth Fblytechnic.
`
`I am grateful to the mmbers of staff and technicians,
`
`in particular
`
`to Mr A Santillo and L Roberts, of the Dept of Communication Engineering
`
`for their kind co—operation and technical assistance as well as to the
`
`Library staff members.
`
`I should also like to express my gratitude to the Devon
`
`County Council and the British Telecom Research Labs, Martlesham
`
`for the financial support and facilities provided for the project.
`
`I have pleasure in thanking Ms W Happer for her accurate
`
`and neat typing of the thesis.
`
`Finally I shall be failing in my duty if I do not mention
`
`the encouragement and support received from my parents at every
`
`stage of the accomplishment of my task.
`
`PMC Exhibit 2117
`Apple v. PMC
`IPR2016-00755
`Page 4
`
`

`
`CONTENTS
`
`Abstract
`
`CHAPTER 1 - INTRODUCTION
`
`1.1
`1.2
`
`General
`
`Thesis Organization
`
`CHAPTER 2 - CRYPICGRAPHIC CONCEPTS
`
`2.1
`2.2
`
`2.3
`
`Cryptographic Systems
`Cxyptosystem Security and Complexity
`Theory
`Cryptographic Techniques
`
`2 . 3. 1
`2. 3. 2
`
`Block Cipher
`Stream Cipher
`
`- DATA ENGRYPIION AILXDRITHMS
`
`3.1
`
`General
`
`3. 1 . 1
`3. 1 . 2
`3. 1 . 3
`
`Transposition Cipher
`Substitution Cipher
`Product Cipher
`
`Data Encryption Standard
`
`3.2.1
`3.2.2
`3.2.3
`
`DES Algorithm - An Overview
`The Key Schedule Procedure
`DES Encryption and Decryption
`
`Software DES Implementation
`
`3.3.1
`
`A Fbssible Advantage of DES
`Software
`
`Some Characteristics of DES Algorithm
`3.4.1.
`Avalanche Effect
`
`3.4.2
`
`Complementary Property
`
`Design Criteria
`3.5.1
`&Boxes
`3.5.2
`Initial and" Final Permutations
`3.5.3
`P-Permutation
`
`Criticism and Weaknesses of DES
`
`3.6.1
`3 6 2
`3.6.3
`
`3 6 4
`
`The Key Length
`Unpublished Design Principles
`Number of Rounds
`
`Key Schedule Algorithm-
`weak and Semiweak Keys
`
`PMC Exhibit 2117
`Apple v. PMC
`IPR2016-00755
`Page 5
`
`

`
`Contents continued. . . .
`
`3.7 ‘
`3.8
`
`Cryptanalysis of DES
`Discussion
`
`CHAPTER 4 - DESIGN OF ENCRYPTION SYSTEM: SYSTEM HARD.-IARE
`
`4. 1
`
`System Requirement 5
`
`4.1.1
`4.1.2
`4.1.3
`
`Security Requirements
`Operator Requirements
`Teclmical Requirements
`
`General System Description
`
`4.2.1
`4.2.2
`4.2.3
`
`Apple Microcomputer
`Encryption Interface Unit
`Nodem
`
`— FUINT TO POIN1‘ COMMUNICATION SYSTEM: svsrsm
`
`so1=1'wAR_5 (1;
`
`5.1
`
`General
`
`5.1.1
`5 . 1 . 2
`5. 1 .3
`
`Polling Technique
`Interrupt Dr iven Technique
`Point—to—Fbint Communication
`
`lock Encryption Nbde
`2 1
`
`2.2
`2 3
`
`Principle
`Implementation
`Results and Discussion
`
`Cipher Block Chaining Mode
`
`5.3.1
`5.3.2
`5. 3.3
`
`Principle
`Implementation
`Results and Discussion
`
`Stream Cipher Feedback
`
`5.4.1
`5.4.2
`5 . 4. 3
`
`Principle
`Implementation
`Results and Discussion
`
`Cipher Block Giaining with Plaintext
`Feedback
`
`'
`
`5 1
`5.2
`5 3
`
`Principle
`Implementation
`Results and Discussion
`
`Stream Cipher Feedback with Vector
`
`Implementation
`Results and Discussion
`
`PMC Exhibit 2117
`Apple v. PMC
`IPR2016-00755
`Page 6
`
`

`
`Contents condinued. . .
`
`CHAPTER 6 - SI‘AI‘IS'I‘IGM_ TESTS ON DES OUTPUT SEQUENCES
`
`6.1
`
`6.2
`
`General
`
`Statistical Tests For Randomness
`
`6.2.1
`6.
`.
`6.
`6.
`
`.
`
`Test
`Test
`Test
`Test
`Test
`
`The Frequency Test
`The Serial Test
`The Runs Test
`The Autocorrelation
`
`Results and Discussion
`
`Other Statistical Tests
`
`6.4.1
`6.4.2
`
`C ass.-Correlation Test
`-Test to Detect Dependence
`Between Output and Input
`
`- LOCAL FILE SECURITY: SYSTEM SOFTWARE (2)
`
`7.1
`7.2
`
`7.3
`
`General
`Choice of DES Node
`
`Implementation
`
`- SECURIIY IN PRESTE1. VIEAIDDATA SYSTEM: SYSTEM
`SOFTWARE (3)
`
`8.1
`
`8.2
`
`8.3
`
`General
`
`.
`
`Brief Review of Prestel Viewdata System
`
`Encryption/Decryption in Prestel System
`
`- KEY DISTRIEJTION AND PUBLIC KEY CRYPTCXERAFI-IY
`
`9.1
`
`9.2
`
`9.3
`
`9.4
`
`9.5
`
`General
`
`Key Management Using Key Centre
`
`Conmnmication Security
`
`File Security
`
`Key Distribution for Groups of Users
`9.5.1
`Method 1
`
`9.6
`
`Public Key Systems
`
`9 . 6. 1
`
`9.6.2
`
`Merkle-Hellman Trapdoor
`Knapsack Public Key Cryptosystem
`Rivest-Shamir—Ad1eman (RSA)
`Public Key Cryptosystem
`
`PMC Exhibit 2117
`Apple v. PMC
`IPR2016-00755
`Page 7
`
`

`
`Contents continued. . .
`
`9.6.3
`
`Diffie—He11man Hlblic Key
`Distribution System
`
`Key Distribution Using Public Key for
`Groups of Users
`9.7.]
`Method 2
`9.7.2
`Method 3
`9.7.3
`Method 4
`
`Key Distribution for Prestel Fmcryption
`System
`
`CHAPTER 10 — DCIENSIONS OF THE RSA CRYPIOSYSTBVI
`
`10.1
`
`10.2
`
`General
`
`801119 Design Aspects of RSA Cryptosystem
`
`10.2.1
`10.2.2
`
`Primality Tests
`Choice of Coding Exponents
`
`_
`
`Cryptanalysis of RSA System
`10.3.1
`Factorization of m
`
`10.3.2
`
`10.3.3.
`
`Computation of ¢(m) Without
`Factorization of m
`
`Determining d without Factoring
`m or Computing ¢(m)
`
`167
`
`167
`
`167
`
`169
`170
`
`171
`171
`
`172
`
`172
`
`Extension of RSA System to Matrix Rings
`
`172
`
`10. 4.1
`10.4.2
`
`10.4.3
`
`10.4.4
`10.4.5
`10.4.6
`
`10.4.7
`10.4.8
`10.4.9
`
`.
`
`Trapdoor .Rings
`Non—singu1ar Matrices over
`Z/mZ
`Orthogonal Matrices over
`Z/mZ
`Upper Triangular Matrices over Z/mZ185
`Linear Fractional Group
`189
`- Proportion of Non-singular
`191
`Matrices over 2/mz
`System Design and Operation
`System Implementation
`Discussion
`
`172
`174
`
`183
`
`192
`195
`198
`
`Extension of RSA System to Polynomial
`Rings
`
`10.5.1
`10.5.2
`
`10.5.3
`
`10.5.4
`
`Concept of Galois Field
`A Polynomial Based RSA
`System
`An Improved Polynomial Based
`RSA System
`Discussion
`
`Extension of RSA System to Matrix Rings
`with Polynomial Elements
`
`‘ 200
`
`200
`
`PMC Exhibit 2117
`Apple v. PMC
`IPR2016-00755
`Page 8
`
`

`
`Contents continued...
`
`10.6.1
`
`10.6.2
`
`Non—singu1ar Matrices
`over‘ R = Z[x]/(m,f(x))
`Upper Triangular Matrices
`over R = Z[x]/(m,f(x))
`
`Discussion
`
`CHAPTER 11 - FACFORIZATION TRAPIIIDR FROM IDEAL POINT OF VIEN
`
`1 1 . 1
`
`11 . 2
`
`General
`
`Basic Concepts
`11.2.1
`Ideal
`
`1 1 . 2. 2
`11.2.3
`11.2.4
`11.2.5
`
`11.2.6
`11.2.7
`
`Congruence
`Principal Ideal
`Prime Ideal
`Product of Ideals
`
`Unique Factorization of Ideals
`Factorization Trapdoor
`
`Ring of Integers
`
`Polynomial Rings
`
`Matrix Rings
`
`11.5.1
`1 1 .5.2
`
`Approach (a)
`Approach (b)
`
`CHAPTER 12 — FACTORIZATION TRAPIIDR IN ALGEBRAIC NUMBER FIE.DS
`
`1 2 . 1
`
`12.2
`
`General
`
`Factorization Trapdoor System in Gaussian
`Integers
`
`12.2.1
`12.2.2
`
`12.2.3
`
`12.2.4
`
`Ring of Gaussian Integers
`Design of Trapdoor Coding
`System in Z[i]
`Security of the System in
`Z[i]
`.
`Representation of Dvbssages
`and System Operation
`
`Factorization Trapdoor System in other
`Qxadratic Fields
`
`12.3.1
`12.3.2
`
`Quadratic Fields R NB)
`Design of Trapdoor Coding
`System: Complex Euclidean
`Quadratic Fields
`Security of the System in
`R (J6)
`Representation of Messages
`and System Operation
`Rea1_ Qiadratic __ Fields _ __
`
`— viii —
`
`Page viii
`
`PMC Exhibit 2117
`Apple v. PMC
`IPR2016-00755
`Page 9
`
`

`
`Contents continued...
`
`12.4
`
`Discussion
`
`CHAPTER 13 - coNv1~:NrIcȢAL CRYFTOSYSTEM WITH PUE.IC KEY
`DISTRIBUTION
`
`13.1
`
`13.2
`
`13.3
`
`13.4
`
`13.5
`
`General
`
`Logarithms over Finite Fields
`
`Public Key Distribution in Gr-*(2”)
`
`Short cycling Attack
`
`mas/ncn Hybrid System
`
`13.5.1
`13.5.2
`13.5.3
`
`Central Public Key File
`Local Public Key File
`No Public Key File
`
`Exponentiation in GF(2n)
`13.6.1
`Method 1
`
`_13.6.2
`
`Method 2
`
`Hardyare Desig of an Exponentiator in
`GF'(2 )
`>-
`
`Normal Basis Generators in GF12127)
`Extension of Diffie—He1lman System to
`Matrix Rings
`13.9.1
`Design of Base Matrix
`13.9.2
`Example
`13.9.3
`Use of Upper Triangular Matrices
`over z/pz
`
`CHAPTER 14 - PERMJTATION FTLYNOMIALS IN THE DESIGN OF PUE.IC
`KEY SYSTEMS
`
`14.1
`
`14.2
`
`14.3
`14.4
`
`14.5
`
`14.6
`
`14.7
`
`General
`
`Fblynomial y
`
`x" (mod n)
`
`Polynomial y E ax-+b (mod :11)
`Linear Fractional Substitution
`
`Rédei Rational Functions
`
`[Dickson Polynomial based Public Key
`System
`Discussion
`
`CHAPTER 15 - CHAINDIG TECHNHXJES AND BROAIIZASTIING WITH PUE.IC
`KEY SYSTEMS
`
`'1S.1
`
`General
`
`PMC Exhibit 2117
`Apple v. PMC
`IPR2016-00755
`Page 10
`
`

`
`Contents continued. . .
`
`1 5. 2
`
`Chaining Techniques
`15.2.1
`Method 1
`15.2.2
`Method 2
`
`Broadcasting of Messages
`
`CHAPTER 16 — @NG..USIONS
`
`REFERENCES
`
`Data Encryption Standard 2 A Software
`Design
`Fbint—to-Point Communication : Block
`
`Encryption Program (ECB)
`Extended Character Set
`
`Graphics Display Program (RES‘1‘RY.F‘77)
`Point—to—Fbint Conmnmication: Cipher
`Block Chaining Program (CBC)
`Point—to-Point Communication : Stream
`
`Cipher Feedback Program (CFB)
`Results of some Statistical Tests on
`
`DES Output Sequences
`File Security : Cipher Block Chaining
`Program (CR2)
`PRESTH. Editing Keyboard
`Ofinese Remainder Theorem
`
`Euclid's Algorithm
`Determinant of a Matrix over GF(2)
`Program (DE'l'1\DD.F77)
`Matrix Exponentiation Program
`(MA‘IExP.1-'m)
`Polynomial Exponentiation Program
`(PQ.YE<'l".F77)
`.
`Qrcle Length Calculation Program
`in G!-‘(2*‘*7)(CYG.E.F77)
`Short Oycling Attack in H(D System
`over GF(2**7)( RANIIIYCLEJ-'77)
`'
`Results of Cycling in PKD System
`over GI-‘(2'**7)
`Public Key Distribution Program
`Listing
`Determination of A Normal Basis
`Generator in GI-‘(2**127)
`Normal Basis Exponentiator — Circuit
`Diagram
`‘
`Multiplier Matrix Program (M—MA‘.l'RIX.F77)
`Multiplier Implementation Using T—Matrix
`Approach (l‘—Matrix.F’/7)
`
`PMC Exhibit 2117
`Apple v. PMC
`IPR2016-00755
`Page 11
`
`

`
`Contents continued. . .
`
`23.
`
`24.
`
`25.
`
`26.
`
`Exclusive-or Gate Count Program
`(ED<DR N-O. P77)
`Inverse Matrix over GF‘(2) Program
`(Im/Moo. F7?)
`Matrix based Public Key Distribution
`Program (PKDE(T. F77)
`Dickson Polynomials Based PK System
`Program (DPCLY. F77)
`
`Paper 5 Publ i shed/Submitted
`
`PMC Exhibit 2117
`Apple v. PMC
`IPR2016-00755
`Page 12
`
`

`
`Some gryptographic Iechigges For Secure Data Commnication
`
`V Varadharajan
`
`Abstract
`
`This thesis investigates conventional and public key
`cryptographic techiques for secure data communication.
`
`Block and stream cipher mthods to provide secure
`communication over an insecure channel are discussed with particular
`reference to the Data Encryption Standard (DES) algorithm.
`A
`microprocessor based data encryption interface unit has been designed
`and constructed using the DES to provide both communication and file
`secdrity. Several chaining techniques using the system have also
`been investigated enabling a study of their error characteristics.
`speed of operation, level of security and their ability to overcome
`difficulties due to data redundancy and structure.
`A statistical
`analysis of the randoness of the output sequences in each of these
`techniques has been made. Furthermore ,the developed system can be
`used on the Prestel public network allowing storage and retrieval of
`completely and partly encrypted frames of information on the Prestel
`database.
`
`The use of such a DES based encryption system in a
`communication network poses problems with regard to key distribution
`since the keys used need to be distributed to the users over asecure,
`separate channel. Several methods of key distribution including the
`use of public key systems are discussed.
`
`Extensions of the Rivest—Shamir—Adleman (RSA) public key
`scheme to matrix rings, polynomial rings and algebraic number fields
`have been proposed. These extensions indicate that rings other than
`the ring of rational integers can be used to construct public key
`systems with the factorization trapoor property. The security of
`such systems again relies on the difficulty of factorizing a large
`integer.
`
`An extension of the Diffie—He1lman public key distribution
`system to matrix rings is proposeg. Short cycling attacks against
`the exponentiation system in GF(2 ) have been analysed and are shown
`to be equivalent to a randomnsearch procedure.
`A hybrid system
`using exponentiation in GF(2 ) for key distribtion and the DES for
`data security has been imlemented and the advantage of normal Rasis
`representation in the comutation of the exponentiation in GF(2 ) is
`examined.
`
`The role of permtation polynomials in the design of public
`key systems has also been investigated.
`In particular, it is shown
`that secure public key systems can be desiged using Dickson
`permutation polynomials and Redei rational functions. Further the
`complexity of pblic key systems can be increased by combining the
`permutation polynomials under the law of composition.
`
`PMC Exhibit 2117
`Apple v. PMC
`IPR2016-00755
`Page 13
`
`

`
`CHAPTER
`
`IN'l‘ROl11C1'I('.N
`
`General
`
`The concept of data security is becoming increasingly
`
`significant owing to the expanding role of distributed computation,
`
`distribted data bases and telecommunications applications such as
`
`electronic mail and electronic funds transfer.
`
`The computer and
`
`communications technologies have resulted in a dramatic increase
`
`in the volume and speed of information-collection, distribution and
`
`storage. Greater information transfer and storage in turn imply
`
`greater risk of exposure of sensitive or confidential information to
`
`unauthorised users due to the ready availability of inexpensive
`
`miniature intercepting devices. These have resulted in an increased
`
`interest in comuter data security not only in the military and
`
`political areas but also in the field of commerce, where a.sing1e
`
`transaction may involve millions of pounds. This has motivated
`
`research particularly in the art of cryptography, which forms the
`
`centralltechnique of comunication security.
`
`cryptography is the science and study of secret writing [1].
`‘Cryptography can be defined as the transformation of a message or a
`
`data stream by means of an algorithm so that anyone observing the
`transfored data cannot deduce the hidden information.
`Such
`
`transformations provide solutions to two major problems-of data
`
`security namely the privacy problem and the authentication problem [2].
`In some environments the message can be transmitted in clear text as
`
`long as its integrity is safeguarded.
`
`A common example where the
`
`problem of authentication predominates is in telephone comunication
`
`where the called party cannot determine who is calling. Other
`
`environments may require that the contents of the essage be concealed
`
`during transmission from unauthorised observation and this is a privacy
`
`problem. The problems of privacy and authentication are closely
`
`related and techniques for solving one can frequently be applied to
`
`the other. Data encryption is recognised [3] as the most reliable
`
`method for not only protecting vital information from eavesdroppers
`
`but also a technique of message authentication preventing injection of
`
`false information into a communication system by illegitimate users,
`
`_]__
`
`Pagel
`
`PMC Exhibit 2117
`Apple v. PMC
`IPR2016-00755
`Page 14
`
`

`
`This thesis is mainly concerned with the data privacy problem.
`
`On one hand.
`the easy availability of enornnus computer
`power enables the cryptographer to design complicated alorithms.
`But on the other hand,
`the compter technology also helps the code
`
`breakers to be more effective in cracking the system.
`
`So it is a
`
`never ending struggle between code makers and code breakers.
`
`Recent developments in encryption techniques for computer
`
`communication network security including the Data Encryption Standard
`
`(DES)
`
`[11] and the evolution of public key cryptosystems provided
`
`the major thrust of the present research work. Essentially the thesis
`
`can be divided into two parts.
`
`In the first part (Chapters 2 to 9).
`
`the use of encryption and decryption techniques in communication
`
`systems is investigated. The desig and operation of an encryption
`
`interface unit incorporating the DES to provide communication and file
`
`security and different key distribution schemes are discussed. The
`
`second part (Chapters 10 to 15) is mainly concerned with the desig of
`
`public key cryptosystems with a particular emphasis on the extensions
`
`of the Rivest-Shamir-Adleman (RSA)
`systems.
`
`[12] type factorization trapdoor
`
`1.2
`
`Thesis Organization
`
`In Chapter 2, basic concepts of symmetric and asymmetric
`
`cryptosystems and major cryptographic techniques are briefly reviewed.
`
`An analysis of the DES is presented in Chapter 3 which
`
`includes a software implementation of the Standard, its possible
`
`weaknesses, some of its underlying design criteria and its crypto-
`
`graphic strength.
`
`The design of a microprocessor based
`
`data encryption
`
`interface unit using the DES is described in Chapter 4.
`
`The operation of the interface unit to provide a two—way
`
`secure data transfer in a two—node Apple microcomputer network is the
`
`subject of Chapter 5.
`
`Four different stream and block chaining
`
`techniques of the DES have been investigated using the developed
`interface unit.
`
`In Chapter 6, a statistical analysis of the randomness
`
`characteristic of the output sequences produced by the DES under
`
`different modes has been carried out.
`
`The use of the developed encryption interface unit has been
`
`- 2 _
`
`PMC Exhibit 2117
`Apple v. PMC
`IPR2016-00755
`Page 15
`
`

`
`extended in Chapter 7 to allow file security in Apple disk systems.
`
`Chapter 8 is concerned with the incorporation of DES based
`
`encryption system in Prestel Viewdata network. This enables transfer
`
`and storage of encrypted as well as plain data between an Apple
`
`microcomuter and the Frestel database.
`
`Different methods of key distribution for communication and
`
`file security are investigated in Chapter 9.
`
`It includes a brief
`
`review of the RSA and the Knapsack public key cryptosystems.
`
`In Chapter 10, the prototype RSA system over rational
`
`integers has been extended to matrix and polynomial rings.
`
`Chapter 11 discusses the notion of ideal theory and considers
`
`the RSA type factorization trapdoor systems from an ideal point of
`view.
`
`The factorization trapdoor concept in some quadratic
`
`algebraic number fields and the design of public key systems in such
`
`fields are investigated in Chapter 12.
`
`The implementation of a hybrid system using the DES and the
`
`Diffie-Hellman public key distribution [35] system is investigated in
`
`Chapter 13. An extension of the Diffie—Hellman system to matrix
`
`rings is.proposed.
`
`The role of permutation polynomials in the design of public
`
`key systems forms the subject of Chapter 14.
`
`In particular, the use
`
`of Dickson permutation polynomials and certain Redei functions in the
`
`construction of public key systems is discussed.
`
`In Chapter 15, the use of chaining techniques in the matrix
`
`public key system and some precautions which mst be taken when the
`
`RSA system or its extensionsare used in a broadcasting type situation
`are described.
`
`Chapter 16 contains the main conclusions.
`
`PMC Exhibit 2117
`Apple v. PMC
`IPR2016-00755
`Page 16
`
`

`
`CHAPTER 2
`
`cmn7rosnA1=H1c CONCEPTS
`
`Cfltggraphic Systems
`
`Detailed treatment of cryptographic principles can be found
`
`in [2, 3, 4].
`
`A basic cryptographic privacy system is shown in figure
`
`2.1. The transmitter or the sender generates a Elaintext message M
`
`which is to be comnnmicated to a legitimate receiver over an insecure
`
`channel monitored by an eavesdropper.
`
`To prevent the eavesdropper from
`
`learning the contents of M.
`
`the sender encrypts M, with an invertible
`
`transformation to produce the cfltgram or ciphertext. C = T(M).
`
`when the legitimate receiver obtains C, it is deciphered with the
`inverse transformation to obtain the plaintext message. M = 'l"1(C).
`
`The transformation 1‘ applied at the sending and receiving
`
`ends is a key dependent mapping from a set of messages in the plaintext
`
`to a set of ciphertext messages and vice versa. The particular
`
`transformation used is chosen from a family of transformations. The
`
`parameter that selects the individal transformation to be employed is
`
`called the IE. Note that there may be more than one key involved.
`
`Assuming that the same key is used in both encryption and decryption,
`then c = rk (M) and M = ‘r;1(C)-
`Thus a general cryptosystem consists of the following
`components:
`
`1.
`
`2.
`
`3.
`
`4.
`
`S.
`
`A plaintext message space M ;
`
`A ciphertext message space C ;
`
`A key space K;
`
`A family of encryption transformations Ek : M-* C where
`kt-2 K.
`
`A family of decryption transformations
`kc K.
`
`Dk : C-> M where
`
`The encryption and decryption transformations E1‘ and Dk are defined by
`the encrypting and decrypting algorithms E. and D which may be a set of
`
`instructions. a piece of hardware or a computer program and is common
`
`to every transformation in the family. Different values of the key (5.)
`
`result in totally different transformations of plaintex-ts and cipher-
`
`texts. This implies that the family of transformations, that is, the
`general cryptographic system, can be made public information without
`
`Page 4
`
`PMC Exhibit 2117
`Apple v. PMC
`IPR2016-00755
`Page 17
`
`

`
`EAVESDROPPER
`
`oscnvpnou 7"
`
`RECEIVER
`
`__ -.—__...-.-.—-.—-_.—-__
`SECURE CHANNEL
`
`Fig. 2.1 - Basic Cryptographic Privacy System
`
`EAVESDROPPER
`
`ENCRYPTION
`
`DECRYPTION
`
`SECURE CHANNEL
`
`Fig. 2.2 - Basic Cryptographic Authentication System
`
`PMC Exhibit 2117
`Apple v. PMC
`IPR2016-00755
`Page 18
`
`

`
`compromising the security of the system. Only the key(s) needs to be
`
`kept secret. This satisfies one of the general requiremnts of a
`
`cryptosystem that the security must not depend on the secrecy of
`
`something like a cryptographic algorithmsflfich cannot be easily changed
`
`if it is compromised.
`In addition, a publicly known system is necessary
`for standardization among commrcial users.
`Even though the opponent
`
`knows the set of all possible keys, that is, the key space, he may
`
`still be unable to discover the correct set of keys required if the
`
`key space is large.
`
`Simmons
`[5] classifies cryptosystems as symmetric (one-key)
`and asymmetric (two key).
`In symmetric cryptosystems, the enciphering
`and deciphering keys are the same or easily determined from each other.
`
`Because the general method of encryption and decryption is known, this
`
`means that the transformations Ek and Ch are also easily derived from
`each other. Thus if both ER and Dk are protected both secrecy and
`authenticity are achieved. However secrecy cannot be separated from
`
`authenticity because making either Ek or {k available. exposes the
`other. Thus for secure communication. such a system requires the key
`
`to be transmitted to the receiver via some secure channel. Figure 2.2
`
`illustrates how such a cryptographic system can be used to solve the
`
`authentication problem.
`
`In this case, the opponent not only sees all
`
`ciphertexts flowing on the channel but can alter them at will. The
`
`-legitimate receiver protects himself from being deceived by an altered
`or injected message, by decrypting all the messages he receives and
`
`accepting only thse encrypted with the correct key.
`
`In asymmetric cryptosystems, the enciphering and deciphering
`
`keys differ in such a way that at least oe key is comutationally
`
`infeasible to determine from the other_.
`
`Thus one of the transformations
`
`Secrecy and
`Ek _or Eh can be revealed without endangering the other.
`authenticity are provided by protecting the separate transformations
`
`Such asymmetric systems
`namely Dk for secrecy and Ek for authenticity.
`are often referred to as public key systems as in addition to E and D,
`
`the encryption key is made public. Only the decrypting key is kept
`
`secret by the receiver. The use of such systems thus avoid the
`
`necessity to transmit the key used in the algcrithm over a secure
`
`channel among the communicators. Moreover such systems can be used to
`
`transmit the secret key required for conventional symmetric systems.
`
`Such asymmetric systems are also able to deal with the
`
`problem of dispute that ay arise between the sender and the receiver
`
`over the actual message sent in an authentication system.
`
`The
`
`- 6 '
`
`Page6
`
`PMC Exhibit 2117
`Apple v. PMC
`IPR2016-00755
`Page 19
`
`

`
`inabi1ity_of the symtric system to deal with this type of problem
`
`limits its application. This can be seen as_fo11ow5.
`
`The validity of contracts and agreements is usually
`
`guaranteed by signatures.
`
`The essence of a signature is that only one
`
`person can produce it but anybody can recognize it.
`
`For this, each
`
`user must be able to produce messages whose authenticity can be checked
`
`by anyone, but which could not have been produced by anyone else
`
`especially the intended recipient.
`
`In a symmetric system, the receiver
`
`authenticates any message that he receives from the sender by
`
`deciphering it with the key which the two hold in common. Because this
`
`key is held in common, owever,
`
`the receiver has the ability to produce
`
`any ciphertext that could have been produced by the sender and hence
`
`the receiver cannot prove that it is the sender who actually sent him
`
`the disputed message. The asymmetric system provides a direct elegant
`
`solutio to this signature problem.
`
`If user A wishes to send a
`
`Signed message M to user B, he sigs the message by producing
`
`S = DA (M). when user B receives 5, he can recover M by operating on
`S with EA, that is. M = EA (5).
`B keeps S as the proof that user A
`has sent him the particular message M as only the user A could have
`
`to obtain
`generated 5 because he is the only one who knows QA.
`secrecy of comnication as well as authentication, user A sends
`
`B
`E3 (5) instead of S to user B. As only B knows D 5 he is the only
`one wh can recover S and hence M.
`
`Cryptosystem Security and Complexity Theory
`
`Any attempt by the eavesdropper either to decrypt a
`
`cryptogram C to get the plaintext M or to encrypt an inauthentic plain-
`
`text M’ to get an acceptable cryptogram C’ without prior knowledge of the
`
`If cryptanalysis is impossible so
`key is called cgygtanalysis [2].
`that a cryptanalyst cannot deduce M from C or C7 from“Pf without prior
`
`said to be secure.
`the cryptographic system can be
`knowledge of the key.
`[In order to measure the security of a cryptosystem, Diffie and
`Hellman [2]
`have defined at least three types of attack which the
`
`system should withstand when being subjected.
`(a) A'ciphertext only‘ attack is the weakest form of attack
`
`which the cryptographic system mst withstand.
`
`In this
`
`attack,
`
`the cryptanalyst
`
`attempts to decipher the
`
`cryptogram using only the statistical properties of the
`
`-7-
`
`_:_
`
`PMC Exhibit 2117
`Apple v. PMC
`IPR2016-00755
`Page 20
`
`

`
`message source. As an example, consider a letter
`
`written in English. Not all characters or words occur
`
`equally often; for instance, the letter ‘E’ occurs
`
`approximately 13% of the time [6]
`
`.
`
`Such non-
`
`uniformities in the frequency distribution of the
`
`alphabet are used to give clues about the message. There
`
`is also probably a heading which contains a date and
`
`address and a closing such as ‘sincerely’ . with the aid
`
`of statistical tables, the cryptanalyst
`
`uses each of
`
`these facts to determine which message was mst likely
`sent.
`
`Under a ‘known plaintext' attack, the cryptanalyst . is
`
`assumed to have a substantial amonmt of corresponding
`
`message - cryptogram pairs and tries to determine the
`
`key used in the algorithm.
`
`‘mis form of attack is a
`
`significant threat as frequently messages are enciphered
`
`under the same key. Hence if a system cannot withstand
`
`such an attack, all messages which have been encrypted
`
`under a common key needs to be kept secret as long as
`any of the messages is to be kept secret.
`Such an
`
`attack is quite conmnn in practice.
`
`For instance. a
`
`typical example is when information may be transmitted
`
`in secrecy which is intended for public release at a
`later date.
`
`A 'chosen text‘ attack generally occurs less frequently
`
`than a known plaintext attack.
`
`In this case,
`
`the
`
`cryptanalyst
`
`is assumed to choose messages to be
`
`enciphered or ciphertexts to be deciphered in an attempt
`to determine the key.
`
`For the purpose of certifying systems as secure, it is
`
`necessary to consider mre formidable cryptana1ytica_1 flu-eats. These not
`only give more realistic models of the working invironment of a
`
`cryptographic system but also make the assessment of the system's
`strength easier.
`
`There are two fundamentally different ways in which crypto-
`graphic systems may be considered secure.
`
`A cryptosystem is said to be unconditionally secure under a
`
`PMC Exhibit 2117
`Apple v. PMC
`IPR2016-00755
`Page 21
`
`

`
`given form of attack if the amount of information available to the
`cryptanalyst is actually insufficient to determine the solution, which
`
`may be the key or the plaintext, whatever he the computing power the
`
`cryptanalyst has at his disposal [7] . As an examle. consider a‘
`
`cryptosystem where a message—cryptogram pair uniquely determines the
`
`key. This system is not unconditionally secure under a chosen text
`
`attack or a known plaintext attack. However if the information content
`
`of the message plus the information content of the key is greater than
`
`the maximum possible amount of information in the cryptogram.
`
`then this
`
`system is unconditionally secure under a ciphertext only attack.
`
`The
`
`cryptanalyst cannot determine the complete message and key from the
`
`cryptogram alone, since he would obtain more information than that
`provided by the cryptogram.
`
`Unfortunately, unconditionally secure systems require either
`
`perfect source coding or a key whose length grows linearly with respect
`
`to the sum of the lengths of all messages enciphered [7]
`
`. This
`
`requirement is not practical in most applications. Thus computationally
`
`secure systems are usually used in cryptography.
`
`A system is said to
`
`be computationally secure under a given form of attack if the amount
`
`of computation required to compute the solutio exceeds the cryptanalyst's
`
`abilities or the economic value of the message to him.
`
`A measure
`
`called the work factor is often associated with a cryptosystem which
`
`gives an expression of the minimum amount of work necessary for a
`
`successful attack.
`
`In practice,
`
`there is no universally accepted
`
`fixed set of paramters used to express the work factor. Frequently,
`
`however. it is measured in one or more of the following ways:
`
`cryptanalyst hurs, number of mathematical or logical operations,
`
`comuting resources such as data storage and processbng requirements,
`
`special hardware and calender time or more generally the cost in some
`
`nnney units such as dollars. This idea of computationally secure
`
`system is also related to the concept of one—way functions and
`
`complexity theory.
`
`Algorithmic complexity theory is concerned with the comp-
`
`utational requirements (both time and space) as a function of the size
`
`of the problem solved by a particular algorithm. Complexity theory is
`
`essentially a collection of results in computer science that attempts
`
`to quantify the statement ‘Problem A is 'harder'
`
`than problem B’ [6]
`
`.
`
`There is a class of problems called NP problems [8] and in particular
`
`a distinguished subclass of NP called the class of NP—comPlete problems
`
`-9-
`
`IIIiiiiiiiiiiiiiEEEEEEsEEEEIlIEEEI!!!!!!!!!!!!!!!!IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII
`
`PMC Exhibit 2117
`Apple v. PMC
`IPR2016-00755
`Page 22
`
`

`
`which are regarded to be the 'hardest' problems.

This document is available on Docket Alarm but you must sign up to view it.


Or .

Accessing this document will incur an additional charge of $.

After purchase, you can access this document again without charge.

Accept $ Charge
throbber

Still Working On It

This document is taking longer than usual to download. This can happen if we need to contact the court directly to obtain the document and their servers are running slowly.

Give it another minute or two to complete, and then try the refresh button.

throbber

A few More Minutes ... Still Working

It can take up to 5 minutes for us to download a document if the court servers are running slowly.

Thank you for your continued patience.

This document could not be displayed.

We could not find this document within its docket. Please go back to the docket page and check the link. If that does not work, go back to the docket and refresh it to pull the newest information.

Your account does not support viewing this document.

You need a Paid Account to view this document. Click here to change your account type.

Your account does not support viewing this document.

Set your membership status to view this document.

With a Docket Alarm membership, you'll get a whole lot more, including:

  • Up-to-date information for this case.
  • Email alerts whenever there is an update.
  • Full text search for other cases.
  • Get email alerts whenever a new case matches your search.

Become a Member

One Moment Please

The filing “” is large (MB) and is being downloaded.

Please refresh this page in a few minutes to see if the filing has been downloaded. The filing will also be emailed to you when the download completes.

Your document is on its way!

If you do not receive the document in five minutes, contact support at support@docketalarm.com.

Sealed Document

We are unable to display this document, it may be under a court ordered seal.

If you have proper credentials to access the file, you may proceed directly to the court's system using your government issued username and password.


Access Government Site

We are redirecting you
to a mobile optimized page.





Document Unreadable or Corrupt

Refresh this Document
Go to the Docket

We are unable to display this document.

Refresh this Document
Go to the Docket