Some Cryptographic Techniques
`
`For 5ecure'Data Communication
`
`Vijayaraghavan Varadharaj an
`
`This thesis is submitted to the Council
`
`for National Academic Awards in partial
`
`fulfilment of the requirements for the
`
`degree of lbctor of Philosophy
`
`-Department of Communication Engineering
`
`Plytmuth Fblytechnic
`
`August 1984
`
`Collaboration;
`
`British Telecom Researgh Labs.,
`
`Martlesham
`
`Amazon Ex. 1023
`
`IPR Petition — USP 7,805,749
`
`PMC Exhibit 2117
`Apple v. PMC
`IPR2016-00753
`Page 1
`
`

`
`PLvw:o'-_:TH P’ ' "*_-'é;!-'*':-:
`
`- V sseomsbiél
`I’/‘Mg (3 — 005. 82 VAR
`
`x?1)o53%3:?_
`
`PMC Exhibit 2117
`Apple v. PMC
`IPR2016-00753
`Page 2
`
`

`
`DElCl.ARAT ION’
`
`I hereby declare that while registered as a candidate for
`
`the degree of Doctor of Fhilosophy 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 Varadf-flm C-UV»
`
`PMC Exhibit 2117
`Apple v. PMC
`IPR2016-00753
`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
`
`Communication Engineering, Plymouth Fblytechic) 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 Cbhen (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 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.
`
`PMC Exhibit 2117
`Apple v. PMC
`IPR2016-00753
`Page 4
`
`

`
`CONTENTS
`
`Abstract
`
`CHAPTER 1 - INTRODUCTION
`
`1.1
`1.2
`
`General
`
`Thesis Organization
`
`CHAPTER 2 - CRYF'I%RI'-XPHIC GJNCEPIS
`
`2 1
`2.2
`
`2.3
`
`Cryptographic Systems
`Ck-yptosystem Security and Complexity
`Theory
`Cryptographic Techniques
`
`2.3.).
`2.3.2
`
`Block Cipher
`Stream Cipher
`
`— DATA ENCRYPIION AL@RITl-IMS
`
`3.1
`
`General
`
`3. 1 . 1
`3. 1 . 2
`3. 1 . 3
`
`Transposition Cipher
`Subst itut ion 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 Possible Advantage of DES
`Software
`
`Some Characteristics of DES Algorithm
`3.4.1.
`Avalanche Effect
`
`Complementary Property
`3.4.2
`Design Criteria
`3.5.1
`S-Boxes
`3.5.2
`Initial a.nd'Fina1 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 Serniweak Keys
`
`PMC Exhibit 2117
`Apple v. PMC
`IPR2016-00753
`Page 5
`
`

`
`Contents continued. . . .
`
`3.7 4
`3.8
`
`Cryptanalysis of DES
`Discussion
`
`CHAPTER 4 - DESIGN OF ENCRYPIION SYSTEM: SYSTEM HARDNARE
`
`4. 1
`
`System Requirements
`
`4.1.1
`4.1.2
`4.1.3
`
`Security Requirements
`Operator Requirements
`Technical Requirements
`
`General System Description
`
`4.2.1
`4.2.2
`4.2.3
`
`Apple Microcomputer
`Encryption Interface Unit
`Nbdem
`
`— FDINT T0 POIN1‘ COMMJNICATION SYSTEM: svsram
`
`SOFTWARE (1)
`5.1
`General
`
`5.1.1
`5. 1 .2
`5.1 .3
`
`Polling Technique
`Interrupt Driven Technique
`Point—to—Point Communication
`
`lock Encryption Nbde
`2 l
`
`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.2
`5 . 4. 3
`
`Implementation
`Results and Discussion
`
`Cipher Block Chaining with Plaintext
`
`Principle
`Implementation
`Results and Discussion
`
`Implementation
`Results and Discussion
`
`PMC Exhibit 2117
`Apple v. PMC
`IPR2016-00753
`Page 6
`
`

`
`Contents condinued. . .
`
`CHAPTER 6 - SI'AI‘IS'I‘ICM_ TESTS ON DES OUTPUT SEQIENCES
`
`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.].
`6.4.2
`
`C oss—-Correlation Test
`—Test to Detect Dependence
`Between Output and Input
`
`- LOCAL FILE SEOJRITY: SYSTEM $F'I‘hb\RE (2)
`
`7.1
`7.2
`
`7.3
`
`General
`Choice of DES Vode
`
`Implementation
`
`- SEKJJRIIY IN PRESFEL VIEMDQTA SYSTEM: SYSI'FJ"i
`SOFTWARE (3)
`
`8.1
`
`8.2
`
`8.3
`
`General
`
`.
`
`Brief Review of Prestel Viewdata System
`
`Encryption/Decryption in Prestel System
`
`- KEY DISIRIEFFION AND PUBLIC KEY CRYFTCXSRAPHY
`
`9.1
`
`9.2
`
`9.3
`
`9.4
`
`9.5
`
`General
`
`Key Management Using Key Centre
`
`Connuunication Security
`
`File Security
`
`Key Distribution for Groups of Users
`9.5.1
`Method 1
`
`Public Key Systems
`
`9.6.1
`
`9.6.2
`
`Merkle-Hellman Trapdoor
`Knapsack Public Key Cryptosystem
`Rivest—Shamir-Adleman (RSA)
`Public Key Cryptosystem
`
`PMC Exhibit 2117
`Apple v. PMC
`IPR2016-00753
`Page 7
`
`

`
`Contents continued. . .
`
`9.6.3
`
`D'iffie—He11man Public Key
`Distribution System
`
`Key Distribution Using Public Key for
`Groups of Users
`Method 2
`9.7.1
`9.7.2
`Method 3
`9.7.3
`Method 4
`
`Key Distribution for Prestel Encryption
`System
`
`CHAPTER 10 — BCIENSIONS OF THE RSA CRYPIOSYSTEM
`
`10.1
`
`10.2
`
`General
`
`some Design Aspects of RSA Cryptosystem
`10.2.1
`10.2.2
`
`Primality Tests
`Choice of Coding Eaqaonents
`
`Qyptanalysis of RSA System
`10.3.1
`Factorization of m
`IOJBI2
`
`Computation of ¢(m) without
`Factorization of m
`
`10.3.3.
`
`Determining d Without Factoring
`m or Computing ¢(m)
`
`Exten 5 ion
`
`of RSA System to Matrix Rings
`
`167
`
`167
`
`1 67
`
`169
`170
`
`171
`
`171
`172
`
`172
`
`172
`
`172
`174
`
`183
`
`Trapdoor Rings
`Non-singular Matrices over
`Z/mZ
`Orthogonal Matrices over
`2/mz
`Upper Triangular Matrices over Z/mZ18S
`Linear Fractional Group
`189
`191
`— Proportion of Non—singu1ar
`Matrices over z/mz
`System Design and Operation
`System Implementation
`Discussion
`
`192
`19 5
`198
`
`10.4.1
`10.4.2
`
`10.4.3
`
`4 5 6
`
`4 4 4
`
`10.4.7
`10.4.8
`10.4.9
`
`Extension
`Rings
`10.5. 1
`10.5.2
`
`10.5.3
`
`10.5.4
`
`of RSA System to Polynomial
`
`‘ 200
`
`Concept of Galois Field
`A Polynomial Based RSA
`System
`An Improved Polynomial Based
`RSA System
`Discussion
`
`200
`
`Extension
`of RSA System to Matrix Rings
`with Polynomial Elements
`
`PMC Exhibit 2117
`Apple v. PMC
`IPR2016-00753
`Page 8
`
`

`
`Cbntents 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 — FACTORIZATION TRAPDOOR FROM IDEAL FOINT 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
`
`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
`
`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 Cbding
`System in Z[i]
`Security of the System in
`Z[i]
`_
`Representation of Messages
`and System Operation
`
`Factorization Trapdor System in other
`Qmmficfiflfi
`
`12.3.1
`12.3.2
`
`12.3.3
`
`12.3.4
`
`12.3.5»
`
`Quadratic Fields R (J5)
`Design of Trapdoor Coding
`System: Complex Euclidean
`Quadratic Fields
`Security of the System in
`R (J5)
`Representation of Messages
`and System Operation
`Real Quadratic Fie1ds_“
`
`— viii —
`
`Pagevfii
`
`PMC Exhibit 2117
`Apple v. PMC
`IPR2016-00753
`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
`
`General
`
`Logarithms over Finite Fields
`
`Public Key Distribution in <31-12")
`
`Short cyciing Attack
`
`DES/PKD Hybrid System
`13.5.1
`13.5.2
`13.5.3
`
`Central Public Key File
`Local Public Key File
`No Public Key File
`
`Expanentiation in GF(2n)
`13.5.1
`Method 1
`
`_13.6.2
`
`Method 2
`
`Hardyare Desig of an Exponentiator in
`GF(2 )
`=
`
`Normal Basis Generators in GI-12127)
`Extension of Diffie—He11man System to
`Matrix Rings
`13.9.1
`13-9.2
`13.9.3
`
`Design of Base Matrix
`Example
`Use of Upper Triangular Matrices
`over z/pz
`
`CHAPTER 14 — PERMJTATION HIJYNOMIALS 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 =
`
`xp (mod n)
`
`Fblynomial y
`‘ ax-4-b (mod m)
`Linear Fractioal Substitution
`
`Redei Rational Functias
`
`‘Dickson Polynomial based Public Key
`System
`Discussion
`
`CHAPTER 15 - CHAINING TECHNIQUES AND BROAEXZASTIPG WITH PUE.IC
`KEY SYSTEMS
`
`'1's.1
`
`General
`
`PMC Exhibit 2117
`Apple v. PMC
`IPR2016-00753
`Page 10
`
`

`
`Contents continued. . .
`
`15.2
`
`Chaining Techniques
`15.2.1
`Method 1
`15.2.2
`Method 2
`
`Broadcasting of Messages
`
`CHAPTER 16 — G)NO..USIONS
`
`REFERENCES
`
`Data Encryption Standard : A Software
`Design
`_
`Point-to-Raint Connmmication : Block
`
`Encryption Program (ECB)
`Extended Character Set
`
`Graphics Display Program (RES‘1‘RY.F77)
`Point-to—Point Communication: Cipher
`Block chaining Program (CH2)
`Point—to-Point Communication :
`
`Stream
`
`Cipher Feedback Program (CFB)
`Results of some Statistical Tests on
`
`DES Output Sequences
`File Security : Cipher Block Chaining
`Program (CK?)
`PRESTE. Editing Keyboard
`Chinese Remainder Theorem
`Euc1id's Algorithm
`Determinant of .3 Matrix over GF(2)
`Program (DEl‘J‘vDD.F77)
`Matrix Exponentiation Program
`(MATE-:P.rm)
`Polynomial Exponentiation Program
`(P(1.YE('l".F‘77)
`.
`Cycle Length Calculation Program
`in GF(2~+7)(ora.E.F77)
`Short Cycling Attack in FKD System
`over GI-‘(2**7)( RANDCYciE.F77)
`'
`Results of Cycling in PKD System
`over GF(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.MATRIX.F77)
`Multiplier Implementation Using T—Matrix
`Approach‘ (T—Matrix.F"77)
`
`PMC Exhibit 2117
`Apple v. PMC
`IPR2016-00753
`Page 11
`
`

`
`Contents continued. . .
`
`23.
`
`24.
`
`25.
`
`26.
`
`E:-cr:1u5ive—or Gate Count Program
`(EXDR Mo. P77)
`Inverse Matrix over GF(2) Program
`(INVIVDD. F77)
`Matrix based Fublic Key Distribution
`Program (PKDBCI. F77)
`Dickson Polynomials Based PK System
`Program (DFOLY. F77)
`
`Papers Published/Submitted
`
`PMC Exhibit 2117
`Apple v. PMC
`IPR2016-00753
`Page 12
`
`

`
`Some gryptograghic Iechigges For Secure Data Commnication
`
`V Varadharajan
`
`Abstract
`
`This thesis investigates conventional and public key
`cryptographic techniques 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
`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 outpt sequences in each of these
`techniques has been made. Furthernnre ,the developed system can be
`used on the Prestel public netuork 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) pblic 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—He11man 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 distribution and the DES for
`data security has been implemnted and the advantage of normal Rasis
`representation in the comutation of the exponentiation in GF(2 ) is
`examined.
`
`The role of permutation polynomials in the design of public
`key systems has also been investigated.
`In particular, it is shown
`that secure public key systems can be designed using Dickson
`permutation polynomials and Redei rational functions. Further the
`complexity of public key systems can be increased by combining the
`permutation polynomials under the law of composition.
`
`PMC Exhibit 2117
`Apple v. PMC
`IPR2016-00753
`Page 13
`
`

`
`CHAPTER
`
`INTROl1}Cl'I(]\l
`
`General
`
`The concept of data security is becoming increasingly
`
`sigificant 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 techologies 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
`
`centralltechnique of communication 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
`transformed data cannot deduce the hidden information.
`Such
`
`transformations provide solutions to two major problem of data
`
`security namely the privacy problem and the authetication 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 communication
`
`where the called party cannot determine wh 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 recogised [3] as the most reliable
`
`method for not only protecting vital information from eavesdroppers
`
`but also a technique of mssage authentication preventing injection of
`
`false information into a communication system by illegitimate users.
`
`Pagel
`
`PMC Exhibit 2117
`Apple v. PMC
`IPR2016-00753
`Page 14
`
`

`
`This thesis is mainly concerned with the data privacy problem.
`
`Ch one hand.
`the easy availability of enormous computer
`power enables the cryptographer to design comlicated algorithms.
`But on the other hand,
`the comuter technology also helps the code
`
`breakers to be more effective in cracking the system.
`
`So it is a
`
`never ending struggle betwen 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-sharnir.Ad.1eman (RSA)
`systems.
`
`[12] type factorization trapdoor
`
`1.2
`
`Thesis Organization
`
`In Chapter 2, basic cocepts of symmetric and asymmetric
`
`cryptosystems and major cryptographic techniques are briefly reviewed.
`
`An analysis of the DES is preseted in Chapter 3 which
`
`includes a software implementation of the Standard, its possible
`
`weaknesses.
`
`some of its underlying desig criteria and its crypto-
`
`graphic strength.
`
`The desig of a microprocessor based
`
`data encryption
`
`interface unit using the DES is described in Chapter 4.
`
`The operation of the interface uit to provide a two—way
`
`secure data transfer in a two—nde Apple microcomputer network is the
`
`subject of Chapter 5.
`
`Four different stream and block chaining
`
`techiques 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
`
`PMC Exhibit 2117
`Apple v. PMC
`IPR2016-00753
`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 som 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 must be taken when the
`
`RSA system or its extensionare used in a broadcasting type situation
`are described.
`
`Chapter 16 contains the main conclusions.
`
`PMC Exhibit 2117
`Apple v. PMC
`IPR2016-00753
`Page 16
`
`

`
`CHAPTER 2
`
`CRYPTCFRAPHIC CDNCEPI‘S
`
`Cryptographic 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 communicated to a legitimate receiver over an insecure
`
`channel monitored by an eavesdopper.
`
`To prevent the eavesdropper from
`
`learning the contents of M, the sender encrypts M, with an invertible
`
`transformation to produce the cryptggram or ciphertext, C = T(M).
`
`when the legitimate receiver obtains C. it is deciphered with the
`inverse transformation to obtain the plaintext message. M = T'1(C).
`
`The transformation I 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 mssages and vice versa. The particular
`
`transformation used is chsen from a family of transformations. The
`
`parameter that selects the individual transformation to be employed is
`
`called the 531. 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.
`
`5.
`
`A plaintext message space M ;
`
`A ciphertext message space C ;
`
`A key space K;
`
`A family of encryption transformations ER : M4-C where
`kE K.
`
`A family of decryption transformations
`kc K.
`
`Dh : C+ M where
`
`The encryption and decryption transformations Ek and Q‘ are defined by
`the encrypting and decrypting algbrithms 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 (sq
`
`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
`
`Page4
`
`PMC Exhibit 2117
`Apple v. PMC
`IPR2016-00753
`Page 17
`
`

`
`EAVESDROPPER
`
`NCRYPTII
`
`DECRYPTION r1
`
`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-00753
`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
`
`cryptosystem that the security must not depend on the secrecy of
`
`something like a cryptographic algorithmukfich 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.
`
`Simons [5] classifies cryptosystems as symmetric (one-key)
`and asymmetric (two key).
`In symetric cryptosystems, the enciphering
`and deciphering keys are the same or easily determined from each other.
`
`Because te general method of encryption and decryption is known, this
`
`means that the transformations Ek and Ck are also easily derived from
`each other. Thus if both Ek and Ck are protected both secrecy and
`authenticity are achieved. However secrecy cannot be separated from
`
`authenticity because making either Ek or-Eh 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 asymetric cryptosystems,
`
`the enciphering and deciphering
`
`keys differ in such a way that at least one key is comptationally
`
`infeasible to determine from the other,» Thus one of the transformations
`
`Secrecy and
`Ek _or Dk can be revealed without endangering the other.
`authenticity are provided by protecting the separate transformations
`
`Such asymmetric systems
`namely Ci 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 algcmithm over a secure
`
`channel among the communicators. Moreover such systems can be used to
`
`transmit the secret key required for conventional symmetric systems.
`
`Such asymetric systems are also able to deal with the
`
`problem of dispute that may 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-00753
`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 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, 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
`
`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
`
`generated 3 because he is the only one who knows DA. To obtain
`secrecy of conmmnication as well as authentication, user A sends
`
`3
`E3 (5) instead of S to user B. As only B knows D -, he is the only
`one who can recover S and hence M.
`
`Cgmtoggst Securig and Comlexity Theory
`
`Any atteunpt by the eavesdropper either to decrypt a
`
`cryptogrann 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'ca1led cxtanalysis [2].
`that a cryptanalyst cannot deduce M from C or C’
`from‘-M’ 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 must withstand.
`
`In this
`
`attack, the cryptanalyst attempts to decipher the
`
`cryptogrann using only the statistical properties of the
`
`-7-
`
`:_
`PMC Exhibit 2117
`Apple v. PMC
`IPR2016-00753
`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 most likely
`sent.
`
`Under a ‘known p1aintext' attack, the cryptanalyst e is
`
`assmned to have a substantial amonmt of corresponding
`
`message - cryptogram pairs and tries to determine the
`
`key used in the algorithm.
`
`‘Ibis 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 enample 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 more formidable cryptanalytical threats. These not
`only give more realistic nndels 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 cryptosystern is said to be unconditionally secure under a
`
`PMC Exhibit 2117
`Apple v. PMC
`IPR2016-00753
`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 the information content
`
`of the message plus the information content of the key is greater than
`
`the maadmum possible amount of information in the cryptogram.
`
`then this
`
`wstem is unconditionally secure under a cipher.-text only attack.
`
`The
`
`cryptanalyst cannot determine the complete message and key from the
`
`cryptogram alone, since he would obtain_uore 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 solution 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 parameters used to express the work factor. Frequently,
`
`however, it is measured in one or more of the following ways‘.
`
`cryptanalyst hours, number of mathematical or logical operations,
`
`computing resources such as data storage and processing requirements,
`
`special hardware and calender time or more generally the cost in some
`
`money 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-
`
`
`
`PMC Exhibit 2117
`Apple v. PMC
`IPR2016-00753
`Page 22
`
`

`
`which are regarded to be the ‘hardest’ problems. The class NP-
`
`complete is thought to be a source of problems that can be adapted to
`
`cryptographic applications and will by virtue of their computational
`
`complexity produce strong cryptographic systems.