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
`
`Plymouth Fblytechnic
`
`August 1984
`
`IPR Petition - USP 7,805,749
`
`'Department of Communication Engineering
`
`Collaboration;
`
`British Telecom Research Labs.,
`
`Martlesham
`
`Amazon Ex. 1023
`
`PMC Exhibit 2169
`Apple v. PMC
`IPR2016-01520
`Page 1
`
`

`

`XWOSB‘QBIZ
`
`{‘33-‘- mgl';1005.82 VAR
`
`C" ' """_'.‘f'\_g_r\--:C
`
`' [—
`
`Swami-3:0
`
`PMC Exhibit 2169
`Apple v. PMC
`IPR2016-01520
`Page 2
`
`

`

`award of the CNAA or other academic or professional institution.
`
`Signed: Vguaa
`
`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
`
`van Vamfllell-m
`
`PMC Exhibit 2169
`Apple v. PMC
`IPR2016-01520
`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 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
`
`Pageifi
`
`also due to Dr G Wade (Dept of Cbmmunication 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 adviser 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, GlaSQOw University), Prof J Massay (Institute of
`
`COmmunication 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 Cemmunication 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 previded 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 acc0mp1ishment of my task.
`
`PMC Exhibit 2169
`Apple v. PMC
`IPR2016-01520
`Page 4
`
`

`

`CONTENTS
`
`Abstract
`
`CHAPTER 1 - INTRODUCTION
`
`1.1
`1.2
`
`General
`
`Thesis Organization
`
`Weak and Semiweak Keys
`
`Design Criteria
`3.5.1
`S—Boxes
`3.5.2
`Initial and' Final Permutations
`3.5.3
`P—Permutation
`
`CHAPI'ER 2 - CRYPICGRAPHIC CDNCEFTS
`
`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
`
`- DATA ENGRYPI‘ION WRITHMS
`
`3.1
`
`General
`
`3. 1 . 1
`3. l . 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
`
`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-
`
`PMC Exhibit 2169
`Apple v. PMC
`IPR2016-01520
`Page 5
`
`

`

`
`
`
`
`Contents continued. . . .
`
`3.7 ‘
`3.8
`
`Cryptanalysis of DES
`Discussion
`
`CHAPTER 4 - DESIGN OF ENCRYPTION SYSTEM: SYSTEM HARDWARE
`
`4. 1
`
`System Requirement 5
`
`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
`Nodem
`
`— POINT T0 POINI‘ COMMICATION SYSTEM: SYSTEM
`
`50ng (1)
`
`5.1
`
`General
`
`5.1.1
`5 . 1 . 2
`5. 1 .3
`
`Results and Discussion
`
`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 Gtaining with Plaintext
`Feedback
`
`'
`
`5 1
`5.2
`5 3
`
`Principle
`Implementation
`Results and Discussion
`
`Stream Cipher Feedback with Vector
`
`Implementation
`
`PMC Exhibit 2169
`Apple v. PMC
`IPR2016-01520
`Page 6
`
`

`

`
`
`- LOCAL FILE SECURITY: SYSTEM SOFTWARE (2)
`
`7.1
`7.2
`
`7.3
`
`General
`(Juice of DES Mode
`
`Implementation
`
`.. SECURITY IN PRESTEL VIWTA 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 CRYPTCXERAPHY
`
`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 1
`
`9.6
`
`Public Key Systems
`
`9 . 6. l
`
`9.6.2
`
`Contents condinued. . .
`
`CHAPTER 6 - STATISTICAL 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
`
`
`
`Public Key Cryptosystern
`
`Merl-cle-Hellman Trapdoor
`Knapsack Public Key Cryptosystem
`Rivest—Shamir-Adleman (RSA)
`
`PMC Exhibit 2169
`Apple v. PMC
`IPR2016-01520
`Page 7
`
`

`

`
`
`Contents continued. . .
`
`9.6.3
`
`Diffie-Hellman Public Key
`Distribution System
`
`Key Distribution Using Public Key for
`Gronps of Users
`9.7.]
`Method 2
`9.7.2
`Method 3
`9.7.3
`Method 4
`
`Key Distribution for Prestel chryption
`System
`
`CHAPTER 10 — BCIENSIONS OF THE RSA CRYPIOSYSTBVI
`
`10.1
`
`10.2
`
`General
`
`Same 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
`In or Con'qmting ¢(m)
`
`167
`
`167
`
`167
`
`169
`170
`
`171
`171
`
`172
`
`172
`
`Page Vii
`
`Trapdoor Rings
`Non—singular Matrices over
`z/mz
`Orthogonal Matrices over
`Z/mZ
`Upper Triangular Matrices over Z/leBS
`Linear Fractional Group
`189
`- Proportion of Non—singular
`191
`Matrices over Z/mz
`System Design and Operation
`System Implementation
`Discussion
`
`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
`
`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
`
`,
`
`172
`174
`
`183
`
`192
`195
`198
`
`‘ 200
`
`200
`
`PMC Exhibit 2169
`Apple v. PMC
`IPR2016-01520
`Page 8
`
`

`

`contents continued...
`
`10.6.1
`
`10.6.2
`
`Non—singular Matrices
`over. R = Z[x]/(m,f(x))
`Upper Triangular Matrices
`over R = Z[x]/(m.f(x))
`
`Discussion
`
`CHAPTER 11 - FACI‘ORIZATION TRAme FROM IDEAL POINT OF VIBN
`
`1 1 . 1
`
`11 . 2
`
`General
`
`Basic Concepts
`11.2.1
`Ideal
`
`
`
`
`
`Quadratic Fields R NB)
`Design of Trapdoor Coding
`System: Complex Euclidean
`madratic Fields
`Security of the System in
`R (J6)
`Representation of Messages
`and System Operation
`Real madraticw Fields
`
`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 l .5.2
`
`Approach (a)
`Approach (b)
`
`CHAPTER 12 — FACTORIZATION TRAPIIDR IN ALGEBRAIC NUMBER FIEDS
`
`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 h‘bssages
`and System Operation
`
`Factorization Trapdoor System in other
`Quadratic Fields
`
`12.3.1
`12.3.2
`
`_
`
`— viii —
`
`Page viii
`
`PMC Exhibit 2169
`Apple v. PMC
`IPR2016-01520
`Page 9
`
`

`

`Contents continued...
`
`12.4
`
`Discussion
`
`CHAPTER 13 - GDNVENTIONAL CRYFTOSYSTEM WITH PUBLIC KEY
`DISTRIBUTION
`
`
`
`Design of Base Matrix
`Example
`Use of Upper Triangular Matrices
`over z/pz
`
`13.1
`
`13.2
`
`13.3
`
`13.4
`
`13.5
`
`General
`
`Logarithms over Finite Fields
`
`Public Key Distribution in (31-12")
`
`Short cycling Attack
`
`mas/Hm Hybrid System
`
`13.5.1
`13.5.2
`13.5.3
`
`Cbntral 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 Design of an Exponentiator in
`GF(2 )
`>-
`
`Normal Basis Generators in 617(2127)
`Extension of Diffie—Hellman System to
`Matrix Rings
`
`13.9.1
`13.9.2
`13.9.3
`
`CHAPTER 14 - PERMJ'TATION MYNOMIALS IN THE DESIGN OF PUEIC
`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
`
`Redei Rational Functions
`
`'Dickson Polynomial based Public Key
`System
`Discussion
`
`CHAPTER 15 - CHAINING TECHNIQJES AND BROAIIZASTII‘G WITH PUEIC
`KEY SYSTEMS
`
`'15.1
`
`Genetél
`
`PMC Exhibit 2169
`Apple v. PMC
`IPR2016-01520
`Page 10
`
`

`

`CHAPTER 16 — OJNQUSIONS
`
`REFERENCES
`
`Data Encryption Standard : A Software
`Design
`Pbint—to—I-bint Communication : Block
`
`Enoryption Program (ECB)
`Extended Character Set
`
`Graphics Display Program (RESIRY.F‘77)
`Point—to—Pbint Communication: Cipher
`Block Chaining Program (CBC)
`Point—to-Point Commication : Stream
`
`Cipher Feedback Program (CI-‘3)
`Results of some Statistical Tests on
`
`DPS Output Sequences
`File Security : Cipher Block chaining
`Program (C32)
`PRESTH. Editing Keyboard
`01111959 Remainder Theorem
`
`Contents continued. . .
`
`l 5. 2
`
`Chaining Techniques
`15.2.1
`Method 1
`15.2.2
`Method 2
`
`Broadcasting of Messages
`
`Approach (T—Matrix.F77)
`
`Euclid's Algorithm
`Determinant of a Matrix over GF(2)
`Program (DE'DDD.F77)
`Matrix Exponentiation Program
`(MATHEW)
`Polynomial Exponentiation Hogram
`(R1.YEC1".F‘77)
`‘
`Qrcle Length Calculation Program
`in GF(2*‘*7)(CYG.E.F77)
`Short chling Attack in MD System
`over GF(2H7)( mar-'77)
`'
`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
`
`PMC Exhibit 2169
`Apple v. PMC
`IPR2016-01520
`Page 11
`
`

`

`24.
`
`25.
`
`26.
`
`Contents continued. . .
`
`23.
`
`Exclusive-or Gate Count Program
`(EDDR M0. F77)
`Inverse Matrix over GF‘(2) Program
`(INVMDD. F77)
`Matrix based Public Key Distribution
`Program (PKDDLT. F77)
`Dickson Polynomials Based PK System
`Program (DPCLY. F77)
`
`Paper 5 Publ i shed/Submitted
`
`PMC Exhibit 2169
`Apple v. PMC
`IPR2016-01520
`Page 12
`
`

`

`Some ggyptographic Technigues For Secure Data Communication
`
`V Varadharajan
`
`Abstract
`
`This thesis investigates conventional and public key
`cryptographic techniques for secure data communication.
`
`Block and stream cipher methods 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 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
`campletely and partly encrypted frames of information on the Prestel
`database.
`
`Pagexh
`
`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 asacure,
`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 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 implemented and the advantage of normal Rasis
`representation in the computation 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 2169
`Apple v. PMC
`IPR2016-01520
`Page 13
`
`

`

`CHAPTER
`
`INTROUJCIICN
`
`General
`
`The concept of data security is becoming increasingly
`
`significant owing to the expanding role of distributed computation,
`
`distributed 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 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.
`
`Pagel
`
`Cryptography is the science and study of secret writing [1].
`Icryptography can be defined as the transfermation 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 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 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 communication system by illegitimate users.
`
`_]__
`
`PMC Exhibit 2169
`Apple v. PMC
`IPR2016-01520
`Page 14
`
`

`

`This thesis is mainly concerned with the data privacy problem.
`
`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)
`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.
`
`On one hand.
`the easy availability of enornnus computer
`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
`
`
`
`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 2169
`Apple v. PMC
`IPR2016-01520
`Page 15
`
`

`

`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 must be taken when the
`
`extended in Chapter 7 to a110w 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 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.
`
`Chapter 16 contains the main conclusions.
`
`RSA system or its extensionaare used in a broadcasting type situation
`are described.
`
`PMC Exhibit 2169
`Apple v. PMC
`IPR2016-01520
`Page 16
`
`

`

`CHAPTER 2
`
`CRYPI‘CBRAPHIC CONCEPTS
`
`Cmtggraphic Systems
`
`Detailed treatment of cryptographic principles can be found
`
`in [2, 3I 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 eavesdropper.
`
`To prevent the eavesdropper from
`
`learning the contents of M.
`
`the sender encrypts M, with an invertible
`
`transformation to produce the cmtgram or cighertext. 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 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 E2. Note that there may be more than one key involved.
`
`Page 4
`
`Assuming that the same key is used in both encryption and decryption,
`then c = rk (M) and M = film)-
`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 Ek : M+ C where
`kE K.
`
`A family of decryption transformations
`kc K.
`
`Dk : O» M where
`
`The encryption and decryption transformations Ek and DR 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 comnnn
`
`to every transformation in the family. Different values of the key (5.)
`
`result in totally different transformations of plaintexts and cipher-
`
`‘mis implies that the family of transformations, that is, the
`texts.
`general cryptographic system, can be made public information without
`
`PMC Exhibit 2169
`Apple v. PMC
`IPR2016-01520
`Page 17
`
`

`

`EAVESDROPPER
`
`DECRYPTICN 7"
`
`RECEIVER
`
`_- --—__._--.-.—-.—-_.—-__
`SECURE CHANNEL
`
`Fig. 2.1 - Basic Cryptographic Privacy System
`
`
`
`Fig. 2.2 - Basic Cryptographic Authentication System
`
`EAVESDROPPER
`
`SECURE CHANNEL
`
`ENCRYPTION
`
`DECRYPTION
`
`PMC Exhibit 2169
`Apple v. PMC
`IPR2016-01520
`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 algorithmcflfich 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.
`
`Because the 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 Dk are protected both secrecy and
`authenticity are achieved. However secrecy cannot be separated from
`
`authenticity because making either Ek or ck 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
`
`ilegitimate 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.
`
`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.
`
`Page6
`
`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
`
`Secrecy and
`Ek _or EL can be revealed without endangering the other.
`authenticity are provided by protecting the separate transformations
`
`Such asymmetric systems
`namely Oh 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 may arise between the sender and the receiver
`
`over the actual message sent in an authentication system.
`
`The
`
`- 6 _
`
`PMC Exhibit 2169
`Apple v. PMC
`IPR2016-01520
`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 asymetric 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
`
`generated 5 because he is the only one who knows DA. To obtain
`secrecy of communication as well as authentication, user A sends
`
`3
`BB (5) instead of S to user B. As only B knows D ', he is the only
`one who can recover S and hence M.
`
`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
`
`E_—_'__4
`
`Cmtosystem Security and Complexity Theog
`
`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 emanalysis [2].
`that a cryptanalyst cannot deduce M from C or C from‘M" without prior
`
`said to be secure.
`the cryptographic system can be
`l-mowledge'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
`
`cryptogram using only the statistical properties of the
`
`-7-
`
`PMC Exhibit 2169
`Apple v. PMC
`IPR2016-01520
`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—
`
`lmiformities 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 liker
`sent.
`
`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.
`
`‘lhis 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.
`
`A cryptosystem is said to be unconditionally secure under a
`
`necessary to consider are formidable cryptanalytical threats. These not
`only give more realistic models of the working invironment of a
`
`A 'chosen text' attack generally occurs less frequently
`
`than a known plaintext attack.
`
`In this case,
`
`the
`
`cryptanalyst
`
`is assnmed 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
`
`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.
`
`PMC Exhibit 2169
`Apple v. PMC
`IPR2016-01520
`Page 21
`
`

`

`
`
`
`
`may be the key or the plaintext, whatever he the camputing pewer 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 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 camputationally 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
`
`given form of attack if the amount of information available to the
`cryptanalyst is actually insufficient to determine the solution, which
`
`IIiiiiiiiiiiii===EEaEEElllllllEl!!!!!!!!!!!!!!lIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII
`
`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 processbng 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 3' [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 2169
`Apple v. PMC
`IPR2016-01520
`Page 22