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.