Some Cryptographic Techniques
`
`For Secure Data Communication
`
`Vijayaraghavan Varadharajan
`
`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 Polytechnic
`
`August 1984
`
`Collaboration:
`
`British Telecom Research Labs.,
`
`Martlesham
`
`
`
`Page A
`
`——4
`
`PMC Exhibit 2117
`PMC Exhibit 2117
`Apple v. PMC
`Apple v. PMC
`IPR2016-00753
`IPR2016-00753
`Page 1
`Page 1
`
`

`

`PLYMOUTH OCCT MES
`
`Page i
`
`PMC Exhibit 2117
`PMC Exhibit 2117
`Apple v. PMC
`Apple v. PMC
`IPR2016-00753
`IPR2016-00753
`Page 2
`Page 2
`
`

`

`DECLARATION
`
`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: Vijaya
`
`van VawadLar, uw
`
`-ii-
`
`Pageit
`
`PMC Exhibit 2117
`PMC Exhibit 2117
`Apple v. PMC
`Apple v. PMC
`IPR2016-00753
`IPR2016-00753
`Page 3
`Page 3
`
`

`

`anes
`
`Acknowledgements
`
`I wish to express my grateful thanks to Dr C T Stockel,
`
`Director of Studies,
`
`(Dept of Mathematics, Statistics and Computing,
`
`Plymouth Polytechnic) and to my supervisors Mr P W Sanders, (Dept of
`
`Communication Engineering, Plymouth Polytechnic) and Dr R WK 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 Comminication 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
`
`Comminication Engineering, ETH, Zurich) and Prof W Ledermann (Dept
`
`of Mathematics, Sussex University) who 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 Polytechnic.
`
`I am grateful to the members 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 Mrs 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.
`
`- iii -
`
`Page tii
`
`PMC Exhibit 2117
`PMC Exhibit 2117
`Apple v. PMC
`Apple v. PMC
`IPR2016-00753
`IPR2016-00753
`Page 4
`Page 4
`
`

`

`eeee
`
`CONTENTS
`
`Abstract
`
`CHAPTER 1 = INTRODUCTION
`
`1.1
`1.2
`
`General
`Thesis Organization
`
`CHAPTER 2 = CRYPTOGRAPHIC CONCEPTS
`
`2.1
`2.2
`
`2.3
`
`,
`
`Cryptographic Systems
`Cryptosystem Security and Complexity
`Theory
`Cryptographic Techniques
`
`2.3.1
`2.3.2
`
`Block Cipher
`Stream Cipher
`
`CHAPTER 3 = DATA ENCRYPTION ALGORITHMS
`
`3.1
`
`General
`
`,
`
`3.2
`
`—
`
`Transposition Cipher
`3B.1l.t
`Substitution Cipher
`3.1.2
`Product Cipher
`3.1.3
`Data Encryption Standard
`3.2.1
`DES Algorithm - An Overview
`3.2.2
`The Key Schedule Procedure
`3.2.3
`DES Encryption and Decryption
`
`3.3
`
`Software DES Implementation
`
`3.3.1
`
`A Possible Advantage of DES
`Software
`
`3.4
`
`_
`
`3.5
`
`Some Characteristics of DES Algorithm
`3.4.1
`Avalanche Effect
`3.4.2
`Complementary Property
`Design Criteria
`
`3.5.1
`3.562
`3.5.3
`
`S_Boxes
`Initial and Final Permitations
`P=jPermutation
`
`3.6
`
`Criticism and Weaknesses of DES
`
`326.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
`
`Page
`
`xii
`
`1
`
`1
`2
`
`4
`
`4
`7
`
`10
`
`19
`12
`
`16
`
`16
`
`16
`16
`17
`18
`18
`22
`24
`
`27
`
`28
`
`30
`30
`31
`38
`
`38
`39
`39
`
`40
`
`49
`41
`42
`42
`
`oo
`
`Page i
`
`- iv =
`
`PMC Exhibit 2117
`PMC Exhibit 2117
`Apple v. PMC
`Apple v. PMC
`IPR2016-00753
`IPR2016-00753
`Page 5
`Page 5
`
`

`

`
`
`
`
`Contents continued....
`
`Page
`
`3.7 .
`
`3.8
`
`Cryptanalysis of DES
`Discussion
`
`CHAPTER 4 — DESIGN OF ENCRYPTION SYSTEM: SYSTEM HARDWARE
`
`4.1
`
`System Requirements
`
`4.1.1
`4.1.2
`4.1.3
`
`Security Requirements
`Operator Requirements
`Technical Requirements
`
`General System Description
`
`4.261
`4.2.2
`4.2.3
`
`Apple Microcomputer
`Encryption Interface Unit
`Modem
`
`CHAPTER 5 — POINT TO POINT COMMUNICATION SYSTEM: SYSTEM
`SOFTWARE (1)
`
`5.1
`
`General
`
`5-2
`
`5.3
`
`5.1.1
`5.1.2
`5.1.3
`
`Polling Technique
`Interrupt Driven Technique
`Point—to=Point Communication
`
`Block Encryption Mode
`
`5.2.1
`5.2.2
`5.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.2
`5.4.3
`
`Implementation
`Results and Discussion
`
`Cipher Block Chaining with Plaintext
`Feedback
`
`.
`
`5-5el
`55.2
`5-5-3
`
`Principle
`Implementation
`Results and Discussion
`
`5.6
`
`Stream Cipher Feedback with Vector
`Feedback
`
`5.6.1
`5.6.2
`5. 6.3
`
`Principle
`Implementation
`Results and Discussion
`
`43
`
`45
`
`47
`
`47
`
`47
`48
`48
`
`49
`
`51
`52
`70
`
`72
`
`72
`
`72
`72
`73
`
`74
`
`74
`74
`81
`
`86
`
`Bo
`89
`90
`
`94
`
`94
`97
`98
`
`101
`
`1O1
`195
`105
`
`199
`
`109
`1l2
`112
`
`Page v
`
`PMC Exhibit 2117
`PMC Exhibit 2117
`Apple v. PMC
`Apple v. PMC
`IPR2016-00753
`IPR2016-00753
`Page 6
`Page 6
`
`

`

`Contents condinued...
`
`Page
`
`CHAPTER 6 - STATISTICAL TESTS ON DES OUTPUT SEQUENCES
`
`6.1
`
`6.2
`
`6.3
`
`6.4
`
`General
`
`Statistical Tests For Randomess
`
`6e201
`6.2.2
`6.2.3
`6.2.4
`
`: The Frequency Test
`Test 1
`Test 2 : The Serial Test
`Test 3 : The Runs Test
`Test 4 : The Autocorrelation
`Test
`
`Results and Discussion
`
`Other Statistical Tests
`
`6.401
`6.4.2
`
`Cross-—Correlation Test
`-Test to Detect Dependence
`Between Output and Input
`
`CHAPTER 7
`
`- LOCAL FILE SECURITY: SYSTEM SOFTWARE (2)
`
`7.1
`
`7.2
`
`7.3
`
`General
`Chdice of DES Mode
`
`Implementation
`
`CHAPTER 8
`
`~- SECURITY IN PRESTEL VIEWDATA SYSTEM: SYSTEM
`
`SOFTWARE (3)
`
`8.1
`
`8.2
`
`8.3
`
`General
`
`.
`
`Brief Review of Prestel Viewdata System
`Encryption/Decryption in Prestel System
`
`CHAPTER 9
`
`- KEY DISTRIBUTION AND PUBLIC KEY CRYPTOGRAPHY
`
`9.1
`
`9.2
`
`9.3
`
`9.4
`
`9.5
`
`General
`
`Key Management Using Key Centre
`
`Communication Security
`
`File Security
`
`Key Distribution for Groups of Users
`9.5.1
`Method i
`
`Public Key Systems
`
`9.6.1
`
`9.6.2
`
`Merkle-Hellman Trapdoor
`Knapsack Public Key Cryptosystem
`Rivest-Shamir-Adleman (RSA)
`Public Key Cryptosystem
`
`116
`
`116
`
`116
`
`117
`118
`118
`120
`
`124
`
`126
`
`126
`127
`
`130
`
`130
`
`130
`
`131
`
`134
`
`134
`
`134
`
`134
`
`144
`
`144
`
`146
`
`147
`
`150
`
`151
`
`152
`
`153
`
`158
`
`
`
`- vi =
`
`Page vi
`
`PMC Exhibit 2117
`PMC Exhibit 2117
`Apple v. PMC
`Apple v. PMC
`IPR2016-00753
`IPR2016-00753
`Page 7
`Page 7
`
`

`

`
`
`Contents continued...
`
`9.7
`
`9.8
`
`9.6.3
`
`Diffie-Hellman Public Key
`Distribution System
`
`Key Distribution Using Public Key for
`Groups of Users
`9.7.1
`Method 2
`9.7.2
`Method 3
`9.7.3
`Method 4
`
`Key Distribution for Prestel Encryption
`System
`
`CHAPTER 10 = EXTENSIONS OF THE RSA CRYPTOSYSTEM
`
`10.1
`
`10.2
`
`10,3
`
`General
`
`Some 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
`Computation of Z(m) Without
`Factorization of m
`Determining d Without Factoring
`m or Computing %(m)
`
`10.3.3.
`
`10.4
`
`Extension of RSA System to Matrix Rings
`
`Page
`
`161
`
`162
`
`163
`163
`164
`
`165
`
`167
`
`167
`
`167
`
`169
`170
`
`171
`171
`172
`
`172
`
`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-singular Matrices over
`2/mzZ
`Orthogonal Matrices over
`Z/mZ
`Upper Triangular Matrices over 2/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
`
`10.5
`
`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
`
`10.6
`
`Extension of RSA System to Matrix Rings
`with Polynomial Elements
`
`" 200
`
`200
`201
`
`:
`
`209
`
`216
`
`217
`
`- vii -
`
`Pagevii
`
`PMC Exhibit 2117
`PMC Exhibit 2117
`Apple v. PMC
`Apple v. PMC
`IPR2016-00753
`IPR2016-00753
`Page 8
`Page 8
`
`

`

`
`
`Contents continued...
`
`10.6.1
`
`10.6.2
`
`Non-singular Matrices
`over R = Z[xj/(m,f(x))
`Upper Triangular Matrices
`over R= Z[x}/(m,f(x))
`
`10.7
`
`Discussion
`
`CHAPTER 11 =— FACTORIZATION TRAPDOOR FROM IDEAL POINT OF VIEW
`
`11.1
`
`11.2
`
`General
`
`Basic Concepts
`11.2.1
`Ideal
`
`11.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
`
`11.3
`
`11.4
`
`11.5
`
`Ring of Integers
`
`Polynomial Rings
`
`Matrix Rings
`
`11.5.1
`11.5.2
`
`Approach (a)
`Approach (b}
`
`CHAPTER 12 — FACTORIZATION TRAPDOOR IN ALGEBRAIC NUMBER FIELDS
`
`12.1
`
`12.2
`
`12.3
`
`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
`2[i]
`Representation of Messages
`and System Operation
`
`Factorization Trapdoor System in other
`Quadratic Fields
`12.3.1
`Quadratic Fields R (VD)
`12.3.2
`Desiqn of Trapdoor Coding
`System: Complex Euclidean
`Quadratic Fields
`Security of the System in
`R (4D)
`Representation of Messages
`and System Operation
`Real Quadratic Fields _
`
`12.3.3
`
`12.3.4
`
`12.3.5.
`
`230
`
`230
`
`230
`
`230
`230
`230
`231
`231
`231
`231
`
`233
`
`234
`
`235
`
`236
`242
`
`244
`
`244
`
`244
`
`244
`246
`
`254
`
`254
`
`264
`
`264
`266
`
`269
`
`269
`
`270
`
`- viii -
`
`
`
`Pageviii
`
`PMC Exhibit 2117
`PMC Exhibit 2117
`Apple v. PMC
`Apple v. PMC
`IPR2016-00753
`IPR2016-00753
`Page 9
`Page 9
`
`

`

`Contents continued...
`
`12.4
`
`Discussion
`
`CHAPTER 13 — CONVENTIONAL CRYPTOSYSTEM WITH PUBLIC KEY
`DISTRIBUTION
`
`13.1
`
`13.2
`13.3
`13.4
`
`13-5
`
`13.6
`
`13.7
`
`13.8
`13.9
`
`General
`
`Logarithms over Finite Fields
`Public Key Distribution in GF(2”)
`Short Cycling Attack
`
`DES/PKD Hybrid System
`
`Central Public Key File
`13.5.1
`Local Public Key File
`13.5.2
`No Public Key File
`13.5.3
`Exponentiation in GF(2")
`13.6.1
`Method 1
`(13.6.2
`Method 2
`Hardyare Design of an Exponentiator in
`GF (2°
`}
`:
`Normal Basis Generators in GFr(2!@7y
`Extension of Diffie-Hellman System to
`Matrix Rings
`
`13.9.1
`13.9.2
`13.9.3
`
`Design of Base Matrix
`Example
`Use of Upper Triangular Matrices
`over Z2/pZ
`
`CHAPTER 14 = PERMUTATION POLYNOMIALS IN THE DESIGN OF PUBLIC
`KEY SYSTENS
`
`14.1
`14.2
`14.3
`14,4
`
`14.5
`
`14.6
`
`14.7
`
`General
`Polynomial y = x" (mod m)
`Polynomial y = axct+b (mod m)
`Linear Fractional Substitution
`
`Rédei Rational Functions
`
`‘Dickson Polynomial based Public Key
`System
`Discussion
`
`CHAPTER 15 = CHAINING TECHNIQUES AND BROADCASTING WITH PUBLIC
`KEY SYSTEMS
`
`15.1
`
`General
`
`Page
`
`271
`
`274
`
`274
`
`274
`277
`280
`
`284
`
`288
`289
`289
`290
`290
`293
`300
`
`303
`306
`
`306
`308
`309
`
`310
`
`310
`310
`312
`313
`
`314
`
`316
`
`318
`
`321
`
`321
`
`~
`
`-ix-
`
`.
`Page 1x
`
`PMC Exhibit 2117
`PMC Exhibit 2117
`Apple v. PMC
`Apple v. PMC
`IPR2016-00753
`IPR2016-00753
`Page 10
`Page 10
`
`

`

`Contents continued...
`
`15.2
`
`Chaining Techniques
`15.2.1
`Method 1
`15.2.2
`Method 2
`
`15.3
`
`Broadcasting of Messages
`
`CHAPTER 16 — CONCLUSIONS
`
`REFERENCES
`
`APPENDICES:
`
`1.
`
`2.
`;
`3.
`4.
`5.
`
`6.
`
`7.
`
`8.
`
`9.
`10.
`ll.
`12.
`
`13.
`
`14.
`
`15.
`
`14.
`
`17.
`
`18.
`
`19,
`
`20.
`
`21.
`22.
`
`Data Encryption Standard : A Software
`Design
`Point-to-Point Communication : Block
`Encryption Program (ECB)
`Extended Character Set
`Graphics Display Program (RESTRY.F77)
`Point-to-Point Commimication: 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 (CBC)
`PRESTEL Editing Keyboard
`Chinese Remainder Theorem
`Euclid's Algorithm
`Determinant of a Matrix over GF(2)
`Program (DETMOD.F77 )
`Matrix Exponentiation Program
`(MATEXP. FIN)
`Polynomial Exponentiation Program
`( POLYEXT.F77 )
`.
`Cycle Length Calculation Program
`in GF(2**7 )(CYCLE.F77)
`Short Cycling Attack in FKD System
`over GF(2**7){ RANDCYCLE.F77)
`‘
`Results of Cycling in PKD System
`over GF(2**7)
`Public Key Distribution Program
`Listing
`Determination of A Normal Basis
`Generator in GF(2**127)
`Normal Basis Exponentiator - Circuit
`Diagram
`Multiplier Matrix Program (M-MATRIX.F77}
`Multiplier Implementation Using T-Matrix
`Approach (T-Matrix.F77 )
`
`Page
`
`321
`324
`325
`
`326
`
`328
`
`332
`
`A-1
`
`A-5
`
`Am24
`A=-25
`A-28
`
`A-41
`
`A-52
`
`A=69
`
`A-83
`A-B4
`A-85
`A-88
`
`A-90
`
`A-92
`
`A-94
`
`A~98
`
`A-102
`
`4-114
`
`A-123
`
`A=-125
`
`A-129
`A-134
`
`Page x
`
`PMC Exhibit 2117
`PMC Exhibit 2117
`Apple v. PMC
`Apple v. PMC
`IPR2016-00753
`IPR2016-00753
`Page 11
`Page 11
`
`

`

`coer
`
`Contents continued...
`
`23.
`
`24.
`
`25
`
`26.
`
`Exclusive-or Gate Count Program
`(EXOR NO. F77)
`Inverse Matrix over GF(2) Program
`(INVMOD. F77)
`Matrix based Public Key Distribution
`Program (PKDEXT. F77)
`Dickson Polynomials Based PK System
`Program (DPOLY. F77)
`
`Page
`
`A-137
`
`A-139
`
`A-142
`
`Awl 43
`
`Papers Published/Submitted
`
`Page xi
`
`PMC Exhibit 2117
`PMC Exhibit 2117
`Apple v. PMC
`Apple v. PMC
`IPR2016-00753
`IPR2016-00753
`Page 12
`Page 12
`
`

`

`core
`
`Some Cryptographic Techniques For Secure Data Communication
`
`V Varadharajan
`
`Abstract
`
`This thesis investigates conventional and public key
`cryptographic techniques for secure data commmication.
`
`Block and stream cipher methods to provide secure
`commmication 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 commmication and file
`security. 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 randomness 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
`commmnication network poses problems with regard to key distribution
`since the keys used need to be distributed to the users over 4a Secure,
`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 trapdoor property.
`The security of
`such systems again relies on the difficulty of factorizing a large
`integer.
`
`An extension of the Diffie-Hellman public key distribution
`system to matrix rings is proposed. Short cycling attacks against
`the exponentiation system in GF(2 ) have been analysed and are shown
`to be equivalent to a randomsearch procedure.
`A hybrid system
`using exponentiation in GF(2" ) for key distribution and the DES for
`data security has been implemented and the advantage of normal basis
`representation in the computation of the exponentiation in GF(2 ) is
`examined,
`
`The role of perimtation polynomials in the design of public
`key systems has also been investigated.
`In particular, it is show
`that secure public key systems can be designed using Dickson
`permitation polynomials and Rédei rational functions. Further the
`complexity of public key systems can be increased by combining the
`permitation polynomials under the law of composition.
`
`- xii +
`
`Page xi1
`
`PMC Exhibit 2117
`PMC Exhibit 2117
`Apple v. PMC
`Apple v. PMC
`IPR2016-00753
`IPR2016-00753
`Page 13
`Page 13
`
`

`

`oree
`
`CHAPTER 1
`
`INTRODUCTION
`
`1,1
`
`General
`
`;
`Fhe concept of data security is becoming increasingly
`significant owing to the expanding role of distributed computation,
`distributed data bases and telecommmications 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 computer data security not only in the military and
`political areas but also in the field of commerce, where a. single
`transaction may involve millions of pounds. This has motivated
`research particularly in the art of cryptography, which forms the
`centraltechnique of commmnication security.
`Cryptography is the science and study of secret writing Cad.
`Cryptography can be defined as the transformation of a message of a
`data stream by means of an algorithm so that anyone observing the
`transformed data cannot deduce the hidden information.
`Such
`
`transformations provide solutions to two major problemsof data
`security namely the privacy problem and the authentication problem (2),
`In some environments the message can be transmitted in clear text as
`
`A common example where the
`long as its integrity is safeguarded.
`problem of authentication predominates is in telephone communication
`where the called party cannot determine who is calling. Other
`environments may require that the contents of the message 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 commmication system by illegitimate users,
`
`-l1l--
`
`Page 1
`
`PMC Exhibit 2117
`PMC Exhibit 2117
`Apple v. PMC
`Apple v. PMC
`IPR2016-00753
`IPR2016-00753
`Page 14
`Page 14
`
`

`

`This thesis is mainly concerned with the data privacy problem.
`
`the easy availability of enormous computer
`On one hand,
`power enables the cryptographer to design complicated algorithms.
`But on the other hand,
`the computer 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 design 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 design of
`
`public key cryptosystems with a particular emphasis on the extensions
`of the Rivest-Shamir-Adleman (RSA)
`(12] type factorization trapdoor
`systems.
`
`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 randomess
`
`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
`
`Page 2
`
`
`PMC Exhibit 2117
`PMC Exhibit 2117
`Apple v. PMC
`Apple v. PMC
`IPR2016-00753
`IPR2016-00753
`Page 15
`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
`
`microcomputer and the Prestel 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 ofpublic 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 Rédei 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 mist be taken when the
`
`RSA system or its extensiors are used in a broadcasting type situation
`are described.
`
`Chapter 16 contains the main conclusions.
`
`Page 3
`
`
`PMC Exhibit 2117
`PMC Exhibit 2117
`Apple v. PMC
`Apple v. PMC
`IPR2016-00753
`IPR2016-00753
`Page 16
`Page 16
`
`

`

`CHAPTER 2
`
`CRYPTOGRAPHIC CONCEPTS
`
`2.1
`
`Cryptographic Systems
`
`Detailed treatment of cryptographic principles can be found
`in C2, 3, 4a].
`A basic cryptographic privacy system is shown in figure
`2.1. The transmitter or the sender generates a plaintext message M
`which is to be communicated 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 cryptogram or ciphertext, C = T(M).
`When the legitimate receiver obtains C, it is deciphered with the
`inverse transformation to obtain the plaintext message, M = tlie).
`The transformation T 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 individual transformation to be employed is
`called the key. Note that there may be more than one key involved.
`Assuming that the same key is used in both encryption and decryption,
`then C = T,
`(M) and M = T,) (C)-
`Thus a general cryptosystem consists of the following
`components:
`
`1.
`
`2.
`
`3.
`4.
`
`5.
`
`A plaintext message space M ;
`
`A ciphertext message space C ;
`
`A key space K;
`A family of encryption transformations EL.
`ke K,
`
`: M+C where
`
`A family of decryption transformations
`ke K.
`
`dD.
`
`: C+ M where
`
`The encryption and decryption transformations E. and Q. 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 (s)
`result in totally different transformations of plaintexts 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
`PMC Exhibit 2117
`Apple v. PMC
`Apple v. PMC
`IPR2016-00753
`IPR2016-00753
`Page 17
`Page 17
`
`

`

`_ SECURE, CHANNEL
`
`RECEIVER
`
`Fig. 2.1 - Basic Cryptographic Privacy Systen
`
`
`
`EAVESDROPPER
`
`
`
`ENCRYPTION
`DECRYPTION
`
`
`
` __ SECURE CHANNEL
`
`
`Fig. 2.2 - Basic Cryptographic Authentication Systen
`
`-5-
`
`Page 5
`
`PMC Exhibit 2117
`PMC Exhibit 2117
`Apple v. PMC
`Apple v. PMC
`IPR2016-00753
`IPR2016-00753
`Page 18
`Page 18
`
`

`

`compromising the security of the system. Only the key(s) needs to be
`
`kept secret. This satisfies one of the general requirements of a
`
`¢ryptosystem that the security mist not depend on the secrecy of
`
`something like a cryptographic algorithmwhich cannot be easily changed
`
`if it is compromised.
`
`In addition, a publicly known system is necessary
`
`for standardization among commercial 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 E. and Dd. are also easily derived from
`each other. Thus if both E. and Dd. are protected both secrecy and
`authenticity are achieved. However secrecy cannot be separated from
`authenticity because making either E. or DL 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
`
`In this case, the opponent not only sees all
`authentication problem.
`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 those encrypted with the correct key.
`In asymmetric cryptosystems,
`the enciphering and deciphering
`keys differ in such a way that at least one key is computationally
`infeasible to determine from the other... Thus one of the transformations
`E.
`_ or dD. can be revealed without endangering the other.
`Secrecy and
`authenticity are provided by protecting the separate transformations
`namely D. for secrecy and EB. for authenticity.
`Such asymmetric systems
`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 algorithm over a secure
`
`channel among the comminicators. 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 cf dispute that may arise between the sender and. the receiver
`
`a
`
`over the actual message sent in an authentication system.
`
`The
`
`~e-
`
`Page 6
`
`PMC Exhibit 2117
`PMC Exhibit 2117
`Apple v. PMC
`Apple v. PMC
`IPR2016-00753
`IPR2016-00753
`Page 19
`Page 19
`
`

`

`inability. of the symmetric system to deal with this type of problem
`
`limits its application. This can be seen as. follows.
`
`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 mist be able to procuce 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, however,
`
`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
`solution to this signature problem.
`If user A wishes to send a
`signed message M to user B, he signs the message by producing
`$= Dd, (M). When user B receives S, he can recover M by operating on
`S with Ey» that is, M= E, (S).
`B keeps S as the proof that user A
`has sent him the particular message M as only the user A could have
`generated S because he is the only one who knows Dy To obtain
`secrecy of communication as well as authentication, user A sends
`E, (S) instead of S to user B. As only B knows D_, he is the only
`B
`one who can recover S and hence M.
`
`2.2
`
`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
`key is’called cryptanalysis [2].
`If cryptanalysis is impossible so
`that a cryptanalyst cannot deduce M from C or C”
`from:M” without prior
`knowledge of the key,
`the cryptographic system can be
`said to be secure.
`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) Atciphertext 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-
`
`.
`
`Page 7
`
`PMC Exhibit 2117
`PMC Exhibit 2117
`Apple v. PMC
`Apple v. PMC
`IPR2016-00753
`IPR2016-00753
`Page 20
`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 eryptanalyst uses each of
`
`these facts to determine which message was most likely
`sent.
`
`(b) Under a ‘known plaintext' attack, the cryptanalyst . is
`assumed to have a substantial amount of corresponding
`
`message — cryptogram pairs and tries to determine the
`
`key used in the algorithm. This 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 common 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.
`
`(c) A ‘chosen text' attack generally occurs less frequently
`than a known plaintext attack.
`In this case,
`the
`
`is assumed to choose messages to be
`cryptanalyst
`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 more formidable cryptanalytical threats. 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
`
`~ 8 =
`
`Page 8
`
`PMC Exhibit 2117
`PMC Exhibit 2117
`Apple v. PMC
`Apple v. PMC
`IPR2016-00753
`IPR2016-00753
`Page 21
`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 be the computing power the
`cryptanalyst has at his disposal [7] . As an example, 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 t